言葉遣い
テキストの膨大なデータベースがあります（数十万のテキスト）。 テキストの長さはほぼ同じで、約250文字で、言語は英語です。 一部のテキストは編集されています（タイプミスの修正、コンマの配置など）。 したがって、元のテキストとその修正されたコピーの両方がデータベースに表示されます。 そのようなペアは多くありません。たとえば1％以下です。 タスク：そのようなペアをすべて見つけます。
「編集済みテキスト」とは何かを正式に定義するには、編集距離が適しています（Pythonでdifflibモジュールを使用しています）。 通常は編集が少ないため、2〜3回の編集で異なるテキストのペアを取得するだけで十分です。
問題は、多くのテキストがあり、編集距離の計算がかなり遅いため、ペアで比較できないことです。 さらに、スコアを下げるためにテキストを小さなグループに分割する（たとえば、主題ごとに）簡単な自然な方法はありません。
主なアイデア
サブセット内でのみ編集距離を計算する必要があるように、テキストのセット全体を小さなサブセットに分割したいと思います。 これは次のように行うことができます。各テキストを特定の多次元空間内のポイントに関連付けて、編集テキストが近いポイントに変換されるようにします。 編集距離は、幾何学的に近いテキストに対してのみ計算すれば十分です。
表示の2番目の要件は非常にソフトです。間違えたり、遠くのテキストを近いポイントに翻訳したりできます。 しかし、このような各エラーは、距離の不必要な計算につながります。
近くのポイントをすばやく見つけるには、空間インデックスを使用できます。
実装
このような表示、「テキスト->ピリオド」としては、文字カウントマッピングが適しています。 私たちが検討しているスペースは、言語のアルファベットの文字数に等しい寸法を持ちます。 特定の文字に対応する座標は、テキスト内の文字Xの出現回数に等しくなります。 たとえば、f（ "aac"）= [2、0、1、0、...、0]。 文字を座標として使用し、句読点は使用しません。テキストを観察すると、句読点がさらに大きく変化することが示されたためです（必ずしも人間の編集によるものではありません。たとえば、外見的に類似した句読文字は異なるUnicodeシーケンスでエンコードできます）。
したがって、近いテキストは近いポイントに表示されるという定義から得られます。
反対の条件が非常に正確に満たされることがわかります（短い距離の場合-これは私たちの場合です）。
各テキストにポイントが割り当てられた後、これらのポイントに空間インデックスを構築します （Pythonにはrtreeモジュールを使用します）。 インデックスを使用すると、「特定の多次元ボックスに該当するすべてのポイントを見つける」などの迅速なクエリを実行できます。
各ポイントの周りに、辺= 4（〜2 *編集の数）のキューブを記述し、このキューブに入るすべてのポイントを調べます。 編集したテキストの検索は、このキューブのみに制限できます。
わずかな最適化
スペースの寸法を増やすことで、編集距離をテストするためのポイントの数を減らすことができます。 次元の増加の自然な候補は、n-gramを座標として導入することです。 一方、ディメンションを増やすと、空間インデックスのパフォーマンスが低下します。 当然、「有用な」n-gramを割り当てる問題が発生します。
ただし、フォームの座標の少数の簡単な紹介でさえ
（バイグラムハッシュを自然数pで除算した残りの部分）は、キューブ内のポイント数を大幅に減少させます。hash(bigramm) % p
（パラメーターの選択は、テキストベースのプロパティ、ハッシュ関数の実装に依存しますが、私が持っていることに基づいて、p = 3を使用すると、テストされたペアの数が半分に減ります）。
すべてのバイグラムが同じように役立つわけではありません。 次元（モジュラスp）を増やしても、テストするペアの数が必ずしも減るとは限りません。 これは、残りを取得するときに、それ自体で有用ないくつかのバイグラムが1つの座標にマージされるという事実によるものです。
おかしい
ほとんど同じ文字のセットでは、意味がまったく異なる数十の文を記述することができることがあります（つまり、多数のテキストが短い辺の長さの1つの立方体に分類される可能性があります）。 ただし、これはめったに起こりません（私の既存のベースで）。
信じがたいことですが、次の2つのテキストは幾何学的に近いものです。「JSEは過去最高のJSE MARKET REPORTで終了します」と「365 Data Centers Offers Cloud Storage in 17 US Markets September 25、2014」。