いくつかの店舗名を一致させる必要があり、データを考慮してLevenshteinとSoundExで許容できる結果を得るのに苦労しています。
これが私が扱っているもののいくつかの例です：
The Home Depot
Office Depot
Apple store
Apple
Walgreens
Walgreens Denver
Quiznos
Quiznos Sandwich Restaurants
たとえば、「クイズノスサンドイッチレストラン」を考えると、「クイズノス」...「ウォルグリーンデンバー」から「ウォルグリーン」に一致させたいと思います。私はこれらの店名の全リストを持っています。
どんな助けでも素晴らしいでしょう。
少し「正規化」して検索フィールドを絞り込んでみてはいかがでしょうか。クエリから「the」や「store」などの綿毛を削除し、辞書を調べて明らかな間違いやタイプミスを修正しますか？明らかな場所の参照（上記の「denver」など）を特定して削除することも役立ちます。
編集：少し拡張する（そして他のいくつかのCSトピックに名前を付ける;-)）-「最良の」（最も複雑な）方法を本当に解決することを検討している場合は、入力文字列を取得して実行する必要がありますいくつかの品詞タガー（ここで役立つ質問を参照してください。JavaStanford NLP：品詞ラベル？）次に、タグ付けデータを使用して接続する単語を削除します（たとえば、「マンハッテンの周りのmcdonalnds」-周りを識別して削除できます）。多分それは複数形を識別するのに役立つかもしれません（知らない、試したことはありません）ので、「ワシントンのホームデポ」のようなものは「ホームデポ」に正規化することができます
この問題の場合、レーベンシュタインの複雑さはO（mn）であり、巨大なデータの場合は非常に高くなります。
行の代わりに対角線を調べ、を使用するとlazy evaluation、O（m（1 + d））時間（dはレーベンシュタイン距離）でレーベンシュタイン距離を見つけることができます。これは、距離が通常の動的計画法アルゴリズムよりもはるかに高速です。小さいです。
遅延評価へのリンク：http：//en.wikipedia.org/wiki/Lazy_evaluation
または、行列の最初の行を0で初期化することもできます。このアルゴリズムはfuzzy string search、テキスト内の文字列に使用できます。この変更により、テキストの一致する部分文字列の終了位置がわかります。一致する部分文字列の開始位置を決定するために、挿入と削除の数を別々に保存し、終了位置から開始位置を計算するために使用できます。