たつをの ChangeLog

73 件 見つかりました。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [ 次へ ]

ソート済みテキストを二分探索する look コマンドの pure Python 実装

2023-10-17-1 [Programming][Python][Algorithm]
Python で Perl の Search::Dict[2013-08-01-1] 相当のライブラリないかなー、と思いつつ過ごす日々です。
最近、二分探索 (binary search) のロジックを Python で書いてソート済みテキストを検索するというコードをネットで見つけました。
確実に遅くなるだろうけどとりあえず実用性を調べてみることに。

1


まずこちらのスクリプトを試しました。


しかしうまく検索できないこと多々あり。
"/usr/share/dict/words" の各ワードをASCII順序でソート済みの "/usr/share/dict/words" から検索して取り出す実験を行ったところ約 27% (171318/235970) の単語にヒットしませんでした。
コード中の「途中の行は読み捨てる」とコメントされてる箇所に問題がありそうです。
捨てちゃいけないものが混じっているのかと。

実験コマンド:
cat WORDS-ASCII_SORTED | xargs -L1 ./look.py > res

2


1の「lookコマンドのpythonによる実装」で参考として挙げられていたこちらも調べてみました。


こちらはというと、二分探索の各ステップで行頭までファイルポインタを移動するときのこちらのコードに少々問題が。

while p >= 0:
    self.f.seek(p)
    if self.f.read(1) == '\n': break
    p -= 1

一行が長いとき（例えば 5000 バイトなど）に無茶苦茶遅くなるのです。
C言語とかなら問題ないのですが、スクリプトレベルでやるには厳しいですね。

3


ということで、結局既存のものをそのまま利用するのはあきらめて、前述の1と2のコードをベースに書き直しました。
（なお、1でやった実験と同じ実験をしたら単語ヒット率 100% でした）


ポイントは行頭までのファイルポインタ移動 (go_to_line_top()) に readline() を使ったこと。
readline() はコンパイルされた実装なので速いです。

ファイルポインタ行頭移動ロジック:
  • 事前準備: そのファイルに含まれる行の最大長＋αを buffer_size にセット
  • 現在のファイルポインタから buffer_size 分前方に seek()
  • そこから readline() を繰り返して最終行を取得
  • 最終行の長さ分前方に seek ()
  • 行頭にファイルポインタが移動できた！

先日の実験で最速だった look.pl (Search::Dict 使用) と比べると 6倍くらい時間がかかりました（buffer_size を小さくすると縮まります）。
ここらへんがスクリプト言語ロジック記述の限界かなあ。


おわりに


look コマンドの Perl モジュールである Search::Dict。これに相当の Python ライブラリが見つからないので、Python スクリプトで実現する方法の実用性を調べました。

その結果、Search::Dict 版には及ばないもののそこそこの速さでした。
このくらいの速度差ならば普段の私のタスクでは実用上問題ないレベルかも。
Perl が使えないときとか、Python プログラムの中から使いたいときとか。

とはいえ、やはり Perl の Search::Dict 相当の Python ライブラリ (C extention?) を切望します！
情報あったら教えてくださいませ。
この記事に言及しているこのブログ内の記事

【類似文字列マッチ】agrep (approximate grep) の簡単チュートリアル

2022-01-19-1 [Algorithm][NLP]
agrep は、アルゴリズム界隈では有名な研究者 Udi Manber と Sun Wu によって開発された、曖昧文字列マッチに対応した grep である。
ターゲットとなるテキストを走査して、クエリと近似マッチしたものを表示する。

agrep


類似文字列マッチならではのオプション:
  • "-E NUM, --max-errors=NUM": エラー文字数の上限
  • "-# (# = 0,1,2,3,4,5,6,7,8,9): エラー文字数の上限 ("-E #" と同じ)
  • "-B, --best-match": ベストマッチな結果だけを表示する。
  • "-s, --show-cost": コストの表示。何文字異なるかというエラー文字数を表示する。
  • "--show-position": 何文字目から何文字目までマッチしたかを表示する。0始まり。

（分かりやすさ優先で「エラー文字数」と表現しているが、実際はクエリ文字列とターゲット文字列を同じ文字列にするために行う挿入・削除・置換の合計回数）

「やってみよう！」のコーナー


クエリ abbc はファイル a.txt 内の ababacd の行と1文字エラーでマッチ（エラー文字数は "-s" オプションで表示される）。
詳しく見ると ababacd の 2-6 の箇所とマッチ、つまり、ab[abac]d で abac のところにマッチしている（マッチ位置は "--show-position" オプションで表示される）。
マッチした箇所 abac の2番目の a (ab[a]c) が b に置き換わってクエリ abbc と完全一致するということで、1エラーとなる。
% cat a.txt
ababacd
vwwaxxyzz
ydgjkdfjgkfd

% agrep -B abbc a.txt
ababacd
% agrep -B abbc a.txt -s
1:ababacd
% agrep -B abbc a.txt -s --show-position
1:2-6:ababacd

最大3つのエラーまで許容した検索結果。
abbc と vwwaxxyzz は3エラー、つまり、abbc の a しか合ってない。
% agrep -E 3 abbc a.txt -s --show-position
1:2-6:ababacd
3:3-7:vwwaxxyzz

許容エラーを1ずつ変えてみた結果。
4の場合はクエリ無視で a.txt 内の行が全部出てくるので意味がない（クエリの文字数が4ゆえ）。
% agrep -1 abbc a.txt -s --show-position
1:2-6:ababacd
% agrep -2 abbc a.txt -s --show-position
1:2-6:ababacd
% agrep -3 abbc a.txt -s --show-position
1:2-6:ababacd
3:3-7:vwwaxxyzz
% agrep -4 abbc a.txt -s --show-position
1:2-6:ababacd
3:3-7:vwwaxxyzz
4:0-4:ydgjkdfjgkfd

日本語文字 (utf-8) もいける。
position がバイト列ベースなので注意。
下の例では、クエリ「鈴木さん」に対応する箇所が「鈴木さま」なのだが、0-4 ではなく 0-12 になってる。
% cat aj.txt
鈴木さま、こんにちは
こんにちは、山田さん
おはよう、太田ちゃん

% agrep -B 鈴木さん aj.txt -s --show-position
1:0-12:鈴木さま、こんにちは

アルゴリズムの性質上、前後の塊が入れ替わっているパターンには弱い。
心情的には「山田さん、こんにちは」に対して「こんにちは、山田さん」がベストとして出てほしい。
% agrep -B 山田さん、こんにちは aj.txt -s --show-position
3:0-30:鈴木さま、こんにちは
% agrep -5 山田さん、こんにちは aj.txt -s --show-position
3:0-30:鈴木さま、こんにちは
5:0-15:こんにちは、山田さん

まあ、これは文字列マッチではなく自然言語処理の範疇。
手軽になんとかしたい場合は ngram とかで（関連記事を参照）。

関連記事


Perl の標準ライブラリ Search::Dict を使った転置インデックスによる類似テキスト検索スクリプト

2022-01-17-2 [Algorithm][NLP][Programming][Perl][Release]
手元でのちょっとした用途で類似テキスト検索をやりたいのですが、
Linux環境であれこれインストールしなくても動かせて、
気ままにカスタマイズできる気が利いたやつがなかったので、
改めて作ってみました。
過去に何度も書いたことのあるプログラムなので目新しさはありませんが。
（「車輪の再発明を気にしない」が私の行動指針です！）

simpii


私の母プログラミング言語（母語）である Perl で書いています。
標準ライブラリしか使っていないので、
Perl さえインストールすればどこでも動くはずです。

転置インデックス（＋リランキング）用のスクリプトと、リランキングだけするスクリプトがあります。
リランキング時のスコア計算方法は README.md を参照されたし。

関連記事

この記事に言及しているこのブログ内の記事

渋谷ハチラボ企画展「ときめく化石の展示会」

2017-11-05-1 [Museum][Family][Algorithm]
渋谷区の子供科学教育施設的な「ハチラボ」の企画展は「ときめく化石の展示会」。

ハチラボ ときめく化石の展示会 2017.11.5

  • 渋谷区／こども科学センター・ハチラボ
    ときめく化石の展示会

    9月1日(金)～11月12日（日）

    化石には夢や想像力を刺激する驚きがあります。本展示では、こどもたちの「え！」「なに？」という心の動きを大切にしながら、化石にまつわる探究を深めるために、さまざまなテーマで化石を扱います。

    協力：ふぉっしる・山と渓谷社

いろんな化石が置いてあって、さわれます。
キラキラしたアンモナイトや恐竜のうんちの化石など。
とらちゃん（小1息子）も面白がってさわっていましたよ。

ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5 ハチラボ ときめく化石の展示会 2017.11.5

これまでのハチラボ企画展

この記事に言及しているこのブログ内の記事

渋谷ハチラボの現在の企画展は『秋山仁先生の「科学・数学ワンダーランドへようこそ」』

2017-07-16-1 [Museum][Family][Algorithm]
渋谷区の子供科学教育施設的な「ハチラボ」の企画展は秋山仁先生の「科学・数学ワンダーランドへようこそ」。
展示品が入れ替わりつつ常設展示されているのですが、それが今回は一堂に会する、的な。
明日までです。

ハチラボ

  • 渋谷区／こども科学センター・ハチラボ
    http://www.city.shibuya.tokyo.jp/edu/bunka/hachirabo.html
    企画展示　秋山仁先生の「科学・数学ワンダーランドへようこそ」～すべては感動から！～

    6月20日(火)～7月17日(月・祝)

    数学研究者の秋山仁先生が監修された"見て・さわって・かんがえる"体験型の作品を、どどーんとイッキに展示します。科学や数学の不思議な世界を体験して、考えて、学びましょう！
    協力：秋山数学研究所

ソートアルゴリズムの展示がありました。
見るの初めて（ここ半年以上ハチラボに行けてなかったので）。

ハチラボ

えっと、これなにソートだったけな。

これまでのハチラボ企画展

この記事に言及しているこのブログ内の記事

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [ 次へ ]

たつをの ChangeLog
Powered by chalow