文字列の類似性を認識

Question

私は、インポートされたファイルを他の言語にローカライズできるシステムを開発中です。

これは主に、MVC3、EntityFramework、LINQなどのハングアップを取得するプライベートプロジェクトです。したがって、私は最終結果を盛り上げるためにいくつかの狂ったことをするのが好きです。そのようなことの1つは、同様の文字列を認識することです。

• Megabeth：：私は過去に働いてきたゲームから借りた -

  あなたは、文字列の次のリスト持っている想像聖ローラー制服を - 頭、胴、および脚

• Megabethが含まれています：ホーリーローラー制服ヘッド
• Megabeth：ホーリーローラー制服美脚
• Megabeth：ホーリーローラー制服トルソー
• Megabeth：PAX東2012制服 - 頭、胴、および脚が含まれてい
• Megabeth：PAX東2012制服ヘッド
• Megabeth：PAX東2012制服美脚
• Megabeth：PAX東2012制服トルソー

あなたが見ることができるように、ユーザーが最初の4つの文字列を翻訳した後、この場合は、次の4シェア多くの類似点、：

• Megabeth
• 制服
• は頭、胴、および脚
• ヘッド
• 美脚
• トルソーが含まれています

ユーザーがどのような種類の、リストから5番目の文字列を選択したとき、最初の4つの文字列が実際にすでに翻訳されて考えてみましょうアルゴリズムや技術を使用して、「類似の文字列」のサブヘッダーの下に1番目の文字列（およびその他の文字列）を表示できますか？

編集 - Levenshtein Distanceに関する少しのコメント： 私は現在、データベースに10k文字列をターゲットにしています。 Levenshtein Distanceは文字列ごとの文字列を比較します。この場合、10k x（10k -1）の可能な組み合わせです。私はこれを実現可能な方法でどのようにアプローチしますか？この特定のアルゴリズムより優れたソリューションがありますか？

Answer 1

Levenshtein Distanceを調べることができます。特定の閾値以下のものは類似しているとみなされます。同一の2つの文字列の距離はゼロになります。

Rosetta Codeには、他の言語の中でもC＃の実装があります。

Answer 2

これは、データのサイズとボキャブラリの濃さによって異なります。 これは最初の考えです： 文字列への単語のマップを作成します 文字列への単語のペアの別のマップ とおそらくデータが文字列への三つ組の文字列の巨大なマップではない場合。 単一の文字列をポイントするマッピングを削除します（これにより、トリプレットマッピングの数が大幅に削減されます）。 構築に時間がかかる場合は、結果の辞書をディスクまたはデータベースに保存します。

文字列を指定すると、すぐに単語、単語のペア、および3つ組に分割し、それに関連するすべての文字列を検索できます。トリプレットマッチングと4単語マッチングを重視して遊ぶ必要があります。私。 「老人がニンジンを食べました」または「男が老犬を矢で殺した」（「トリプレットマッチ」のような音がより重要です）に近い「私は老人です」。

更新：Microsoft SQL Serverデータベースでこれをフルテキスト検索機能で使用することができます。私はそれを試したことはありません。 Luceneもご覧ください。