問題タブ [levenshtein-distance]

Daitch-Mokotoff soundexing と Damerau-Levenshtein の両方を使用して、アプリケーションのユーザー エントリと値が「同じ」かどうかを調べています。

レーベンシュタイン距離は絶対値として使用することになっていますか? 20 文字の単語がある場合、4 の距離はそれほど悪くありません。単語が4文字の場合...

私が今行っているのは、距離/長さを取得して、単語の何パーセントが変更されたかをよりよく反映する距離を取得することです。

それは有効で実証済みのアプローチですか？それともただのバカですか？

もしそうなら、その方法を説明してください。

Re：距離とは-「2つの文字列間の距離は、一方を他方に変換するために必要な編集の最小数として定義されます。」

たとえば、xyzからXYZへの編集には3回かかるため、文字列xYZはXYZとxyzに近くなります。

パターンが[0-9]{3}またはたとえば123の場合、a23はab3よりもパターンに近くなります。

正規表現と一致しない文字列の間の最短距離をどのように見つけることができますか？

上記は、ダメラウ・レーベンシュタイン距離アルゴリズムです。

こんにちは、

.NET（または簡単に翻訳可能）でのLevenshtein DFA（決定性有限オートマトン）の「すぐに使える」実装を知っている人はいますか？私は160000を超える異なる単語を含む非常に大きな辞書を持っています。そして、最初の単語wが与えられた場合、レーベンシュタイン距離で最大2つのwのすべての既知の単語を効率的な方法で見つけたいと思います。

もちろん、特定の単語の1つを編集距離ですべての可能な編集を計算し、それをこれらの各編集に再度適用する関数を使用すると、問題が解決します（非常に簡単な方法で）。問題は効率です---7文字の単語を考えると、これは完了するのにすでに1秒以上かかる可能性があり、可能であれば、レーベンシュタインDFAの場合のように、O（| w |）ステップ。

編集：私は少し勉強することで問題への独自のアプローチを構築できることを知っていますが、現時点ではシュルツとミホフの60ページの長さの記事を読む余裕はありません。

どうもありがとうございます。

私は現在、用語 Web サービスのあいまい検索の実装に取り​​組んでおり、現在の実装を改善する方法についての提案を探しています。共有するにはコードが多すぎますが、思慮深い提案を促すには説明で十分だと思います。読むのは大変だと思いますが、助けていただければ幸いです。

まず、用語は基本的に名前 (または用語) の数です。単語ごとに、スペースでトークンに分割し、各文字を反復処理してトライに追加します。ターミナル ノード (イチゴの文字 y に達したときなど) では、マスター ターム リストへのインデックスをリストに格納します。そのため、ターミナル ノードは複数のインデックスを持つことができます (イチゴのターミナル ノードは「イチゴ」と「イチゴ アレルギー」に一致するため)。

実際の検索に関しては、検索クエリもスペースごとにトークンに分割されます。検索アルゴリズムはトークンごとに実行されます。検索トークンの最初の文字は一致する必要があります (したがって、traw はいちごと一致しません)。その後、連続する各ノードの子を調べます。一致する文字を持つ子があれば、検索トークンの次の文字で検索を続けます。子が指定された文字と一致しない場合は、検索トークンの現在の文字を使用して子を調べます (したがって、それを進めません)。これはあいまいな部分なので、「stwb」は「strawberry」に一致します。

検索トークンの最後に到達すると、そのノードの残りのトライ構造を検索して、すべての潜在的な一致を取得します (マスター ターム リストへのインデックスはターミナル ノードにのみあるため)。これをロールアップと呼びます。BitSet に値を設定してインデックスを保存します。次に、単純に各検索トークンの結果から BitSet を取得します。次に、anded BitSet から最初の 1000 または 5000 のインデックスを取得し、それらが対応する実際の用語を見つけます。レーベンシュタインを使用して各用語をスコアリングし、スコアで並べ替えて最終結果を取得します。

これはかなりうまく機能し、かなり高速です。ツリーには 39 万を超えるノードと、110 万を超える実際の用語名があります。しかし、このままでは問題があります。

たとえば、「car cat」を検索すると、望ましくない場合でも Catheterization が返されます (検索クエリが 2 つの単語であるため、結果は少なくとも 2 つになるはずです)。これは簡単に確認できますが、2 つの単語であるため、カテーテル挿入手順のような状況には対処できません。理想的には、心臓カテーテル法のようなものと一致させたいと考えています.

これを修正する必要性に基づいて、いくつかの変更を考え出しました。1 つは、深さ/幅が混在する探索でトライを通過することです。基本的に、キャラクターが一致する限り、深さを優先します。一致しなかった子ノードは優先キューに追加されます。優先キューは、トライの検索中に計算できる編集距離によって順序付けられます (文字の一致がある場合、距離は同じままであり、そうでない場合は 1 増加するため)。これにより、各単語の編集距離が得られます。BitSet は使用しなくなりました。代わりに、Terminfo オブジェクトへのインデックスのマップです。このオブジェクトには、クエリ フレーズのインデックスと用語フレーズ、およびスコアが格納されます。検索が「car cat」で、一致する用語が「Catheterization procedure」の場合 用語フレーズ インデックスは、クエリ フレーズ インデックスと同様に 1 になります。「Cardiac Catheterization」の場合、語句インデックスはクエリ フレーズ インデックスと同様に 1,2 になります。ご覧のとおり、後で単語フレーズ インデックスとクエリ フレーズ インデックスの数を確認するのは非常に簡単です。それらが少なくとも検索語数と等しくない場合は、それらを破棄できます。

その後、単語の編集距離を合計し、単語句インデックスに一致する単語を単語から削除し、残りの文字を数えて真の編集距離を取得します。たとえば、「イチゴ アレルギー」という用語に一致し、検索クエリが「ストロー」であった場合、イチゴのスコアは 7 になります。その場合、用語フレーズ インデックスを使用して用語からイチゴを除外し、カウントするだけです。 「アレルギー」（スペースを除く）で 16 のスコアを取得します。

これにより、期待どおりの正確な結果が得られます。ただし、速度が遅すぎます。以前は 1 単語の検索で 25 ～ 40 ミリ秒を取得できましたが、今では 0.5 秒にもなる可能性があります。これは主に、TermInfo オブジェクトのインスタンス化、.add() 操作、.put() 操作の使用、および多数の一致を返さなければならないという事実によるものです。各検索を 1000 件の一致のみを返すように制限することはできますが、「car」の最初の 1000 件の結果が「cat」の最初の 1000 件の一致のいずれかに一致するという保証はありません (110 万以上の用語があることを思い出してください)。

cat のような単一のクエリ ワードの場合でも、多数の一致が必要です。これは、'cat' を検索すると、検索が car に一致し、その下のすべてのターミナル ノードがロールアップされるためです (これは非常に多くなります)。ただし、結果の数を制限すると、編集距離ではなく、クエリで始まる単語が強調されすぎてしまいます。したがって、カテーテル法などの単語は、コートなどの単語よりも含まれる可能性が高くなります。

では、基本的に、2 番目の実装で修正された問題をどのように処理できるかについて何か考えはありますか? 物事を明確にするために選択したコードを含めることができますが、巨大なコードの壁を投稿したくありませんでした.

私はLevenshteinsEditDistanceアルゴリズムで遊んでいますが、これを拡張して、転置（つまり、隣接する文字の交換）を1つの編集としてカウントしたいと思います。変更されていないアルゴリズムは、別の文字列から特定の文字列に到達するために必要な挿入、削除、または置換をカウントします。たとえば、「KITTEN」から「SITTING」までの編集距離は3です。Wikipediaからの説明は次のとおりです。

1. 子猫→座る（「k」を「s」に置き換える）
2. シッテン→シッティン（「e」から「i」への置換）
3. シッティン→シッティング（最後に「g」を挿入）。

同じ方法で、「CHIAR」から「CHAIR」までの編集距離は2です。

1. CHIAR→CHAR（'I'を削除）
2. CHAR→CHAIR（「I」を挿入）

隣接する2文字しか交換しないので、これを「1編集」として数えたいと思います。どうすればこれを行うことができますか？

私は高度なレーベンシュタイン距離アルゴリズムを探していましたが、これまでに見つけた最高のものはO（n * m）です。ここで、nとmは2つの文字列の長さです。アルゴリズムがこのスケールである理由は、次のような2つの文字列の行列が作成されるため、時間ではなくスペースが原因です。

O（n * m）よりも優れた公的に利用可能なレーベンシュタインアルゴリズムはありますか？私は高度なコンピュータサイエンスの論文や研究を見るのを嫌がりませんが、何も見つけることができませんでした。私は、超高度で超高速のレーベンシュタインアルゴリズムを構築したと思われるExorbyteという会社を見つけましたが、もちろんそれは企業秘密です。レーベンシュタイン距離計算を使用したいiPhoneアプリを作成しています。Objective-cの実装が利用可能ですが、iPodとiPhoneのメモリ量が限られているため、可能であれば、より良いアルゴリズムを見つけたいと思います。

類似度と距離の尺度を変換する一般的な方法はありますか?

2 つの文字列に共通する 2 グラムの数などの類似度の尺度を考えてみましょう。

これを、レーベンシュタイン距離などの差の尺度を期待する最適化アルゴリズムにフィードする必要がある場合はどうすればよいでしょうか?

これは単なる例です...存在する場合、一般的な解決策を探しています。レーベンシュタイン距離から類似度の尺度への移行方法のように？

アドバイスをいただければ幸いです。

パターンが各文字列に一致する量を評価しながら、パターンを一連の文字列と 1 つずつ比較する最良の方法は何でしょうか? 正規表現に関する私の限られた経験では、正規表現を使用して文字列とパターンを一致させることは、かなりバイナリ操作のようです...パターンがどれほど複雑であっても、最終的には一致するかしないかのどちらかです。単なるマッチング以上の機能を求めています。これに関連する優れた手法またはアルゴリズムはありますか?

次に例を示します。

パターンfoo barがあり、次の文字列から最も一致する文字列を見つけたいとしましょう。

さて、これらのどれも実際にはパターンに一致しませんが、どの不一致が最も一致に近いでしょうか? この場合、foo bax7 文字中 6 文字に一致するため、 が最適です。

これが重複した質問である場合はお詫びします。この質問が既に存在するかどうかを確認したときに、正確に何を検索すればよいかわかりませんでした。

アルゴリズムを実装しましたが、他の文字列との編集距離が最も短い文字列の編集距離を見つけたいと思います。

アルゴリズムは次のとおりです。

q-gram距離や単純な「バッグ距離」、またはPythonのレーベンシュタイン距離などで、〜100,000個の短い文字列をクラスター化したいと考えています。私は距離行列 (100,000 は 2 つの比較を選択) を記入し、pyClusterで階層的クラスタリングを行うことを計画していました。しかし、地面に着く前に、いくつかのメモリの問題に遭遇しています。たとえば、numpy には距離行列が大きすぎます。

これは合理的なことのように思えますか? または、このタスクでメモリの問題が発生する運命にありますか? ご協力いただきありがとうございます。