データベースに文字列のセットがあります。各セットは500人未満のメンバーを持ち、数万のセットがあり、ストリングは自然言語です。私は各セット内の重複する文字列を検出したいと思います。新しい文字列は既存のセットと比較され、ユニークな場合はデータベースに追加されます。重複するテキスト検出/ハッシュ
類似した文字列を検索するのに有効なハッシングアルゴリズムはありますか？例えば、文字列はおそらく同じ数の単語を持ちますが、エンコーディングは若干異なります（UTF-8とLatin-1）。
まず、何らかの正規化を行うべきでしょう。おそらく、すべてのテキストを単一のエンコーディングに変換する必要があります（例：UTF-8）。また、大文字と小文字の折り返し、他のUnicode normalizationsを実行して、それぞれのセットをソートすることもできます（格納方法によって異なります）。
正確に一致するものを探したいのか、「類似している」ものだけを見つけるのかはあなたの質問からはわかりません。正規化が考慮された後の正確なマッチだけを気にしていれば、ほとんど完了です。正規化された文字列セットのインデックスを取得するだけで、正規化して新しいセットをすばやく検索することができます。
近くのマッチを探したい場合は、おそらく類似性のハッシュを実行したいと思うでしょう。 Locality Sensitive HashingのWikipediaの記事には、多くの技術が記載されています。
これらのテクニックの背景にある基本的な考え方は、各文字列h [0]からh [n]に非常に損失の多いハッシュを計算することです。新しい文字列セットを検索するには、ハッシュを計算し、それぞれを調べます。少なくとも1つのマッチを得るものはどれも「似ている」、より似ているほどマッチするものが多くなります。
データベースに500文字列しかない場合は、おそらくそれぞれの文字列と直接比較できます。最初に標準表現（UTF-16など）に変換します。 Levenshtein distanceは、2つの文字列の類似性を比較する優れた方法です。
多くのセットが存在するため、Difflibなどで提供される類似距離を使用することは実行可能ではありません。 – wehriam
簡単な答えは、あなたの「似たような」アイデアにマッチするよいハッシュパラメータがどれだけあるかを推測するだけです。
おそらく、すべての文字の合計（A）と隣接する文字の違いの合計（B）のように、機能するかもしれません。それぞれの新しい文字列について、そのAとBの値を使用して、類似した文字列のより小さなセットをすばやく検索し、次にこれらをより慎重に比較します。
これはおそらく最も純粋な解決策ではありませんが、実際にはこのように多くの問題が解決されています。これ以外にも、遺伝学における同様の問題（すなわち、巨大なデータベース内で類似の遺伝子配列を見つけること）を解決する作業は現在かなり多少あると思いますが、この問題に対する汎用的な解決策はないと思います。
これは残酷かもしれませんが、あなたはNLTK (Natural Language Toolkit)を試してみるとよいでしょう。これはPythonベースです。
便利な機能の1つはanalyze sentence structureです。もちろん、それは同じ文法構造を持っているが、異なる言葉と意味を持っているため、一部の文字列が重複としてマークされる可能性があります。
確率と分類機能を使用することもできます。
あなたはクレイジー取得し、潜在意味解析/マッピングおよび特異値分解を試みることができる： latent semantic mapping
一緒SVDLIBCで、一緒に行くを取得するのは簡単です。
This post私のブログに興味があるかもしれません。
アルゴリズムの説明とコードへのリンクが提供されています。要するに、これは、入力の内容や構造について何も想定せず、すべての入力文書に対して一定の長さの署名を生成する、nグラムに基づくアプローチです。
シングリングはアプローチの一部である可能性があります。http://nlp.stanford.edu/IR-book/html/htmledition/near-duplicates-and-shingling-1.html – wehriam
必要に応じてメタフォンまたはsoundexを保存できます類似のもの –
シングリング。クール、初めて聞いたことがある。 – si28719e