私は、ページに 10000 の単語が含まれる Web コンテンツ フィルタリングに取り組んでいます。これを 1500 ～ 2500 語の辞書と照合する必要があります。そして、ページに単語が存在するかどうかを確認する必要があります。
私のパターンをより速く検索して保存するための最良のデータ構造を提案してください。私はツリー構造を研究しました。しかし、次の文字に 26 通りの可能性がある単語 (abc) を考えてみましょう。次のノードのために 26 個のポインターを保持する必要があります。(26x4 バイトを消費します)。単語ごとにパターンを保存するために、それほど多くのメモリを費やすことはできません。
最高の検索と最高のメモリを提案してください。
私はこの分野の初心者です。
最良の検索はtriehttp ://en.wikipedia.org/wiki/Trie です。最良のメモリと検索の神の複雑さについては、http： //en.wikipedia.org/wiki/Suffix_arrayまたはhttp：をお勧めします。 //en.wikipedia.org/wiki/Suffix_tree もう1つのアプローチは、辞書（O（NlogN））と単語O（MlogM）を並べ替え、1回の走査ではなく、各要素O（N + M）に一致するかどうかを確認することです。2つのインデックスから始め、各ステップで、1つのインデックスの辞書の文字列を、2番目のインデックスにある単語と比較した結果に基づいて、そのうちの1つを増やします。一致する場合は、一致して次のインデックスに進みます。あなたが持っている単語、そうでなければあなたの単語が辞書の単語よりも低い場合は次の単語に行きます（あなたはすでにその前にすべての辞書の単語を調べて一致するものを見つけられなかったので）そうでなければあなたは辞書の次の要素に行きます（あなたの単語より低くない単語を辞書で見つけてみてください）
あなたの問題はAho-Corasickによって正確に解決されます。いくつかの前処理の後、各 Web ページを O(n) 時間で処理できます。ここで、n はそのページのサイズです。辞書とほぼ同じ大きさの補助記憶域が必要になります。
メモリの制約はかなり厳しいように見えますが、実際にメモリ フットプリントを削減する必要がある場合は、各状態で 26 文字の配列を使用するのではなく、特定の状態で存在するすべての文字のリストを使用できます。Web ページを処理するときにこれらの文字をスキャンする必要があります。これにより、一定の割合で速度がかなり低下しますが、スペースを節約できます。