与えられたテキストファイルのエントリの巨大なリストと一致します

Question

与えられたテキストファイルのエントリのリストと一致させようとしています。リストはかなり巨大です。組織名のリスト。名前は複数の単語を持つことができます。各テキストファイルは、いくつかの段落を持つ普通の書き込みの一種であり、合計で約5000語/ txtです。そのプレーンテキストのコンテンツであり、組織名を特定できる明確な境界はありません。

リストからすべてのエントリをテキストファイルで検索し、一致するものが認識されタグ付けされる方法を探しています。

これを行うためのツールやフレームワークはありますか？

私はウィキペディアに掲載されているすべてのテキストマイニングツールを試してみましたが、このニーズに合致するものはありません。

いずれの入力も高く評価されます。

Answer 1

アプローチ1：有限ステートマシン

あなたは、有限状態機械（FSM）に検索用語を組み合わせることができます。結果として得られるFSMは、線形時間内にすべての項を同時にスキャンすることができます。 FSMは各文書で再利用できるので、作成する費用は検索するすべてのテキストにわたって償却されます。

良い正規表現ライブラリは、カバーの下にFSMを作成します。自分でビルドするためのコードを書くことはおそらくStack Overflowの答えの範囲を超えています。

基本的な考え方は、すべての検索用語を入れ替えた正規表現から始めることです。あなたの組織リストが "cat"と "dog"で構成されているとします。それらを組み合わせてcat|dogとしましょう。 「ピンクの豚」も検索しなければならない場合、正規表現はcat|dog|pink pigsになります。

正規表現から、グラフを作成できます。グラフのノードは状態です。これはあなたが見たテキストを追跡します。グラフのエッジは、現在の状態と入力内の次の文字が与えられた状態をステートマシンに伝える遷移です。州によっては「最終的な」状態としてマークされているものもありますが、そのうちの1つに到達した場合は、あなたの組織のインスタンスが見つかりました。

最も単純な正規表現以外のすべてからグラフを作成するのは面倒で計算時間がかかります。したがって、すでにこの作業を行っている十分にテストされた正規表現ライブラリを探したいと思うかもしれません。

アプローチ2：あなたが持っているどのように多くの検索条件に応じて、時間

で一つのキーワードを検索し、あなたが持っているどのように多くの文書、およびお使いのシンプルなテキスト検索ツールは、（おそらくサブリニア）でどれだけ速く、それを用語をループして、各用語ごとに各文書を別々のコマンドとして検索するのが最善の方法です。これは確かに最も簡単なアプローチです。

for doc in documents: 
    for term in search_terms: 
     search(term, doc) 

このようにループをネストすることは、おそらくディスクキャッシュに最も適していることに注意してください。

これは、これが1回限りのタスクであった場合の私のアプローチです。新しい文書を検索し続ける必要がある場合（または検索用語のリストが異なる場合）、これは高価すぎるかもしれません。

アプローチ3：サフィックスツリー1つの巨大なドキュメントに

連結し、すべての文書は、ソート、検索用語を接尾辞木を構築し、マッチを探している接尾辞木を歩きます。接尾辞配列の作成と使用の詳細のほとんどはJon Bentley article from Dr. Dobb'sにありますが、他にも多くのリソースがあります。

このアプローチはメモリを大量に消費しますが、大部分はキャッシュに適しているため、非常に高速です。

Answer 2

プレフィックスツリー別名Trieを使用してください。

すべての候補名をプレフィックスツリーに読み込みます。 文書の場合は、ツリーと照合してください。

{} 
+-> a 
| +-> ap 
| | +-> ... apple 
| +-> az 
|  +-> ... azure 
+-> b 
    +-> ba 
     +-> ... banana republic