W-shinglingの実装 - 帯状疱疹の格納

Question

2つのHTML文書の類似性を比較するには、w-shingling（Javaの場合）を実装する必要があります。疑問は、帯状疱疹を収集して保存する方法です。これらの文書の1つ（a、rose、is、a、rose、is、a、rose）を仮定しましょう。私は（LinkedListの）連想配列が最も速くないと思う：

1. 他の単語がない場合は、ここで停止します。
2. チェック（a）は帯状疱疹リストでoccurency
3. それが発生した場合は、そうでない場合は、最初のステップ
4. に行くリストに添付し、最初のステップ

ように行きます私は、これは大きな文書では極端に遅くなる可能性があると予測しています。早くするためのヒントを教えていただけますか？

Answer 1

アルゴリズムによれば、まず文書内で起こっている可能性のあるすべてのwinglingを作成する必要があります。wwの長さのウィンドウを文書から読み取る必要があります（つまり、を読み取った後、 + 1ワードを読み込むと、バッファの最初の単語は破棄されます）。

w-shinglingを格納するために、不変クラスを作成し、比較パフォーマンスを向上させるためにequals()とhashCode()を実装することができます。あなたがshinglingsを構築するときに、あなたはSetにそれらを保存して、その場で重複を取り除くことができます。