ウィキペディアの 25 GB のコーパスから 1 つの単語を検索する必要があります。grep を使用しましたが、時間がかかります。すばやく検索できる効率的で簡単な表現はありますか。また、完全一致を見つけたいです。
ありがとうございました。
4 に答える
3
おそらく、単語から場所のリスト (バイトコード オフセット) へのマッピングのインデックスを作成する必要があります。単語のリストはアルファベット順にソートされます。次に、この大量の単語のリストで特定の文字が始まる場所のセカンダリ インデックスを作成できます。
Lazy hash | Word index | Corpus
aaa starts at X | aaa | lorem ipsum dolor
aab starts at Y | ... | sit amet .....
aac ... | and 486, 549, 684, ... | ...
... ... | |
zzz ... | |
これは、私の学部の自然言語の教授が提唱する方法です (この演習は、アルゴリズム コースのラボとして行いました)。
于 2010-05-15T07:33:20.823 に答える
3
索引付けエンジンを使用してみました...たとえば、Lucene with Nutch? Lucene はインデックス作成エンジンです。Nutch は Web クローラーです。力を合わせろ！
言い忘れました... CouchDB ( http://couchdb.apache.org/ )
于 2010-05-15T07:37:04.530 に答える
2
Boyer-Mooreアルゴリズムとその単純化されたバージョンで成功しました。Web に浮かぶさまざまな言語の実装があります。
于 2010-05-15T07:36:21.540 に答える
0
@aloobe は、単語を場所にマッピングするインデックス ファイルを使用するという答えを出しました。これについて説明したいだけですが、OPが探している答えはBoyer-Mooreかもしれません.
インデックス ファイルは次のようになります (人間が読める 2 桁を使用するように簡略化されています)。
53 17 89 03
77 79 29 39
88 01 05 15
...
上記の各エントリは、インデックス化するのに十分重要であると判断した単語または文字のバイト オフセットです。実際には、インデックス ファイルがコーパスよりも大きいため、文字インデックスは使用しません。
秘訣は、これらの場所の単語を場所に置き換えると、インデックス ファイルはコーパスのアルファベット順に並べ替えられたバージョンになるということです。
and and are as
ate bad bat bay
bear best bin binge
これにより、インデックス ファイルを介してコーパスでバイナリ検索を行うことができます。上記の "best" という単語を検索する場合は、インデックス ファイルの中央のエントリ 79 を取得します。次に、コーパスの位置/バイト 79 に移動し、そこにある単語を確認します。ですbad。アルファベット順でわかっているbest > badので、位置はインデックス ファイルの後半にある必要があります。
したがって、79 (6 番目) と 15 (12 番目) の間の中間インデックスを取得します。これは、私の例では 01 です。次に、コーパス内の位置/バイト 88 (9 番目) を見て、 を見つけますbear。 best > bear再試行します - 中央のインデックスは、丸め方に応じて 01 (10 番目) または 05 (11 番目) になります。しかし、bestあと 1 ～ 2 回検索すれば明らかに見つかります。例のように 12 個の単語がある場合、最悪の場合でも最大で 4 回の検索が必要になります。平均単語長が 5 文字で、その間にスペースがある25 GB のファイルの場合、これは約 40 億語になります。ただし、最悪のシナリオでは、最大 32 回しか検索できません。その時点で、プログラムの時間の多くは、実際の検索よりもディスクの起動と入力のバッファリングに費やされます!
この方法は、重複する単語でも機能します。単語のすべての場所を見つけたい場合は、インデックスが見つかるまでtheバイナリ検索を行います。the次に、コーパスを調べるたびに値を使用して、インデックス ファイル内の位置から繰り返し 1 を減算します。その場所の単語がまだ である場合はthe、続行します。最終的に停止すると、 にマップされるインデックス ファイル内の最も古いインデックスが作成されtheます。
インデックスファイルの作成だけが大変です。コーパス内の各単語を調べて、単語とそのインデックスのデータ構造を構築する必要があります。途中で、「a」、「I」、「the」、「and」、「is」などの一般的または短すぎる単語をスキップします。終了したら、そのデータ構造を使用できます。インデックスファイルに変換します。25GB のファイルの場合、インデックスは残念ながら 32 ビット以上である必要があるため、long(Java の場合) またはlong long(C の場合) を使用して保持します。人間が読めるようにする必要はないので、インデックスを文字列ではなく 64 ビット値として書き出します。
私が推奨する構造は、自己均衡二分探索木です。各ノードは文字列値 (単語) とインデックスです。ただし、ツリーは文字列のみに基づいてノードを比較します。これを行うと、順序どおりのトラバーサル (左、ノード、右) で正確にインデックス ファイルが得られます。
お役に立てれば！私が何年も前に携帯電話用の辞書を作成した例として、Jim Breen の EDICTがあります。EUC エンコーディングと日本語文字のため、わかりにくいかもしれませんが、意図は同じです。
于 2010-05-16T07:00:43.337 に答える