問題タブ [levenshtein-distance]

最近、職場で興味深い問題が発生しました。データベースでユーザーが送信したデータが重複していることがわかりました。このデータのほとんどの間のレーベンシュタイン距離は、問題の2つの文字列の違いにすぎないことがわかりました。これは、ある文字列から別の文字列に文字を追加するだけでは、同じ文字列になることを示しています。ほとんどの場合、これは重複するアイテムを説明するための最良の方法のようです。

タイプミスも考慮したいと思います。そこで私たちは、平均して単語ごとにオンラインでタイプミスをする頻度について考え始め、この距離内でそのデータを使用しようとしました。そのような統計は見つかりませんでした。

データの一致に対してこの種のしきい値を作成するときにタイプミスを説明する方法はありますか？

明確にできるかどうか教えてください！

重複の可能性：
このダメラウ・レーベンシュタインの実装のバグを修正するにはどうすればよいですか？

ダメラウ・レーベネンシュテインの編集距離計算を行う次のCythonコード（bpbioプロジェクトから採用）があります。

コードは正常かつ高速に実行されます（私のPCでは1秒あたり300,000 ... 400,000の比較）。

課題は、このコードをUnicode文字列でも機能させることです。Python 3.1を実行していて、データベースからテキストを取得し、クエリテキストと照合します。

比較のためにCython関数に渡す前に、これらの文字列をエンコードするbytesことはお勧めできません。パフォーマンスが大幅に低下し（テスト済み）、7ビットのUSASCII以外の文字を含むテキストの結果が正しくない可能性があるためです。

（非常に簡潔な）Cythonマニュアルにはユニコード文字列が記載されていますが、目前の問題にはほとんど役立ちません。

私が見ているように、ユニコード文字列は、それぞれが単一のコードポイントを表す整数の配列として考えることができ、上記のコードは基本的にcharすでにsの配列で動作しているので、 （1）それを拡張する必要があると思います整数のC配列を処理するため。（2） Pythonユニコード文字列をC配列に変換するコードを追加します。（3）利益！

（ 注： このアプローチには2つの潜在的な問題があります：1つはユニコード代理文字の処理ですが、私はそれらをどうするか知っていると思います。もう1つの問題は、ユニコードコードポイントが実際には文字の概念に1：1でマッピングされないことです'。私はそれをよく知っていますが、この質問の範囲外だと思います。1つのUnicodeコードポイントが1つの比較単位であると想定してください。）

だから私はどのように提案を求めています

• unsigned intPythonユニコード文字列を受け入れてCythonのC配列（4バイト）を返す高速Cython関数を記述します。

• これらの配列を処理し、正しいメモリ割り当て/割り当て解除を行うように示されているコードを変更します（これは私にとってかなり異質なことです）。

編集：ジョン・マチンchar *m1は、奇妙なタイプキャストなどはおそらく速度やメモリの最適化のために行われていると指摘しています。これらの変数は、引き続き数値の配列として扱われます。私は、コードが長い文字列で起こりうるオーバーフローを防ぐために何もしていないことに気づきました。1つの配列要素が127または255を超えると、誤った結果が発生する可能性があります（使用するCコンパイラによって異なります）。バイオインフォマティクスプロジェクトからのコードには、ある種驚くべきものがあります。

とは言うものの、私が興味を持っているのは、ほぼ100文字未満のほぼ同一の文字列の正確な結果だけです。60％未満の同一性の結果は、私の目的では「完全に異なる」（長いテキストの長さを返すことによって）として安全に報告される可能性があるため、char *m1キャストをそのままにしておくのが最善だと思いますが、オーバーフローをチェックするためのコードを追加します横行する非類似性の場合の早期中絶。

グラフ内の構造を検索するためのレーベンシュタイン距離の一般化はありますか?

さまざまなタスクを実行するためのさまざまなウィジェットを開くためのトップ メニュー ツリーを備えたオンライン Web アプリケーションがあります。アプリがより強力になるにつれて、そのツリーは大きくなり、ナビゲートするのが難しくなります。ユーザーがメニュー名またはその一部を入力できる検索機能を実装しました。正規表現を使用して、ユーザーが入力したものと一致するメニュー ツリー内のすべての項目を検索します。私の正規表現では、部分的な単語と交換された単語が許可され、検索が各単語の先頭に制限されます。許可されていないことの1つは、スペルミスの単語です。スペルミスのある単語を許可するには、正規表現を使用せず、代わりに文字列距離法を使用するのが最善であることを理解していますが、部分的な単語と交換された単語を許可したいと考えています。これは可能ですか？

たとえば、現在、メニュー項目が「Finance Rate Maintenance」の場合、「finance」、「finance ra」、「rate finance」などのいずれかがそのメニュー項目に一致します。「inance rate」は一致しません。そのメニュー項目のどの単語の先頭にも "inance" が表示されないため、一致します。「fnane rate」や「​​ratemaintainance」など、スペルが少し間違っている検索を一致させたいと考えています。

私は別の長い質問で戻ってきました。PythonベースのDamerau-Levenshtein編集距離の実装をいくつか試した結果、最終的に以下にリストされているものが見つかりましたeditdistance_reference()。正しい結果が得られ、効率的に実装されているようです。

そこで、コードをCythonに変換することにしました。私のテストデータでは、参照メソッドは11,000回の比較（12文字の長さの単語のペアの場合）の結果を提供しますが、Cythonizedメソッドは1秒あたり200,000回を超える比較を実行します。残念ながら、結果は正しくありません。デバッグ用に出力した変数を見ると、thisrow どのデータをスローしても、私のバージョンでは変数がいっぱいになっていますが、参照出力には別の画像が表示されます。たとえば、'helo'に対してテストすると'world' 、次の出力が生成されます（ED私の関数をマークEDRし、正しく機能する参照です）。

差出人editdistance()：

からeditdistance_reference()：

エラーはおそらくそれらの非常に明白なものの1つであるため、私は非常に愚かである必要があります。しかし、私はそれを見つけることができないようです。

2番目の問題がありmallocます。3つの配列、、、およびのスペースtwoagoがoneagoあれthisrowば、それらは循環的に入れ替わります。などを実行しようとするfree( twoago )と、glibcが文句を言う行が表示されdouble free or corruptionます。私はそれをグーグルで検索しました。ポインタ交換ビジネスによってglibcが少しめまいを起こし、メモリを正しく解放できなくなる可能性がありますか？

以下に、最初にsetup.pyコンパイル（）を実行するために必要なものをリストし/path/to/python3.1 ./setup.py build_ext --inplace、次に適切な距離コードを編集するので、興味のある人は複製が簡単であることがわかります。

もう1つ：これはPython3.1で実行されます。面白いことに、*.pyxファイル内には裸のUnicode文字列がprintありますが、それでも関数ではなくステートメントです。

はい、これはここに貼り付けるコードがたくさんあることは知っていますが、切り詰めすぎるとコードを実行できなくなります。私はeditdistance()正しく機能することを除いてすべての方法を信じていますが、あなたが感じる問題を自由に指摘してください。

setup.py：

cython_dameraulevenshtein.pyx（最後までスクロールして、興味深いものを確認してください）：

編集私もこのテキストをpastebinとCythonリストに投稿しました。

昨日、レーベンシュタイン法を使うように言われたところがありました。遅いクエリですか？多分私は何か他のものを使うことができますか？

非常に単純なSOLR / Luceneデータベースに入れた単語の長いリストがあります。私の目標は、単一用語クエリのリストから「類似した」単語を見つけることです。ここで、「類似性」は特に (damerau) levensthein 編集距離として理解されます。私はSOLRがスペルの提案にそのような距離を提供することを理解しています.

私のSOLRschema.xmlでは、フィールドタイプを設定しましたstring:

フィールドを定義するために使用します

このフィールドを検索し、レーベンシュタイン編集距離に従って結果を返したいと考えています。ただし、webspace~0.1デバッグと説明をオンにしてSOLRに対してクエリを実行すると、レポートには、スコアの計算にさまざまな考慮事項が含まれていることが示されます。

明らかに、私のアプリケーションでは、idf各ドキュメントには単一の用語しか含まれていないため、用語の頻度、s などは無意味です。スペル候補コンポーネントを使用しようとしましたが、実際の類似度スコアを返すようにできませんでした。

スコアが返され、 、、などの追加の操作を行わずに levensthein / jaro-winkler / n-gram 検索を実行するように SOLR を構成する方法のヒントを誰でも提供できますか? SOLR の必要最小限の構成サンプルはどこかにありますか? オプションの数には本当に圧倒されます。tfidfboost

Haskell でレーベンシュタイン距離の計算をいじっていますが、次のパフォーマンスの問題に少し不満を感じています。以下の (dist) のように、Haskell の最も「通常の」方法で実装すると、すべて正常に動作します。

しかし、頭を少し曲げて dist' として実装すると、実行速度が大幅に向上します (約 10 倍)。

最初のバージョンで通常のトリックをすべて試しましたseqが、速度が向上するものはないようです。最初のバージョンはマトリックス全体を評価する必要がなく、必要な部分だけを評価する必要があるため、 高速になると思っていたので、これは私にとって少し不満です。

これら2つの実装を同様に実行できるかどうかは誰にもわかりますか、それとも後者の末尾再帰最適化の利点を享受しているだけなので、パフォーマンスが必要な場合は読みにくいことに耐える必要がありますか?

ありがとう、オリオン

次の実装がありますが、しきい値を追加したいので、結果がそれよりも大きくなる場合は、計算を停止して戻ります。

どうすればそれについて行くでしょうか？

編集:これが私の現在のコードですthreshold。まだ使用されていません...目標は、それが使用されることです

私はあいまい検索の実装に取り​​組んでおり、実装の一部として、Apache の StringUtils.getLevenshteinDistance を使用しています。現時点では、あいまい検索の特定の最大平均応答時間を目指しています。さまざまな機能強化といくつかのプロファイリングの後、最も時間が費やされる場所は、レーベンシュタイン距離の計算です。3 文字以上の検索文字列では、合計時間の約 80 ～ 90% を占めます。

さて、ここでできることにはいくつかの制限があることはわかっていますが、以前の SO の質問と LD のウィキペディアのリンクを読んだことがあります。しきい値を設定された最大距離に制限したい場合は、アルゴリズムに費やした時間ですが、これを正確に行う方法がわかりません。

距離がしきい値 k より小さい場合にのみ距離に関心がある場合は、マトリックスで幅 2k+1 の斜めストライプを計算するだけで十分です。このようにして、アルゴリズムは O(kl) 時間で実行できます。ここで、l は最短の文字列の長さです [3]。

以下に、StringUtils の元の LH コードを示します。後は私の改造です。基本的に、i,j 対角線から一定の長さの距離を計算しようとしています (したがって、私の例では、i,j 対角線の上下にある 2 つの対角線)。ただし、これは私が行ったので正しくありません。たとえば、最も高い対角線では、常に真上のセル値が選択されます。これは 0 になります。説明したようにこれを機能させる方法、またはその方法に関する一般的なアドバイスを誰かが教えてくれたら、それは大歓迎です。

私の変更（forループのみ）：