問題タブ [levenshtein-distance]

それらの間のレーベンシュタイン距離を取得したいデータを含むExcelシートがあります。私はすでにテキストとしてエクスポートし、スクリプト（php）から読み込み、Levenshteinを実行し（Levenshtein距離を計算）、保存して再びExcelにしようとしました。

しかし、私はVBAでレーベンシュタイン距離をプログラムで計算する方法を探しています。どうすればいいですか？

おやすみなさい、

私はしばらくの間、ファジー文字列マッチングに取り組んでおり、C をいくつかのポインターと共に使用して、2 つの文字列間のレーベンシュタイン距離の非常に高速な (私のニーズに合わせた) 実装を作成できました。unsafe コードとfixedキーワードを使用してコードを C# に移植しようとしましたが、パフォーマンスが大幅に低下しました。そこで、C++ dll をビルドして使用することにしました。[DllImport]C# から、すべての文字列を自動的にマーシャリングします。問題は、プロファイリングの後、これが私のプログラムの中で最も時間のかかる部分であり続け、プログラムの総実行時間の 50 ～ 57% を占めていることです。約 300 万のデータベース レコードから取得したテキスト フィールドの多くの部分文字列を処理する必要があると思うので、レーベンシュタイン距離にかかる時間はほとんど許容できないと思います。ということで、以下のコードに対してアルゴリズムまたはプログラミング関連の提案があるかどうか、またはこの距離を計算するためのより良いアルゴリズムを知っているかどうかを知りたいです。

BufferVar と BufferTab は 2 つの外部int *(この場合、int[]C# からマーシャリングされる変数) であり、プロセス全体を高速化するためにすべての関数呼び出しでインスタンス化しないことに注意してください。それでも、このコードは私のニーズに対してかなり遅いです。誰かが私にいくつかの提案をしてもらえますか、可能であれば、より良いコードを提供してもらえますか?

編集：距離を制限することはできません。実際の距離が必要です。

どうもありがとうございました、

「レーベンシュタイン距離がX未満のすべての文字列を取得する」を実行するための効率的なデータ構造があるかどうか疑問に思います。

私が興味を持っていることはほとんどありません：

• アルゴリズムの説明。
• 既存のデータベース/プログラミング言語に既存の実装はありますか？
• 参照できる紙・記事は？

私は、多数の単語セットを比較することを含む問題を解決しようとしています。各セットには、一連の単語 (合計約 600 +、非常に高い次元!) からの多数の順序付けられた単語が含まれており、類似性があり、それらをクラスター化して明確なグループ分け。ソリューションは、可能な限り監視されていない必要があります。

データは次のようになります

[りんご、バナナ、オレンジ…]
[りんご、バナナ、ぶどう…]
[ゼリー、アニス、オレンジ…]
[いちご、バナナ、オレンジ…]
...etc

各セットの単語の順序が重要です ([Apple, Banana, Orange] は [Apple, Orange, Banana] とは異なります)

私がこれまでに使用してきたアプローチは、Python スクリプトで計算されるメトリックとしてレーベンシュタイン距離 (距離のしきい値によって制限される) を使用し、各単語を一意の識別子として、距離から類似度マトリックスを生成し、そのマトリックスをグループ化のための KNIME の k-Mediods。

私の質問は次のとおりです。

• レーベンシュタインは、この問題に使用する最も適切な距離計量ですか?
• 平均/medoid プロトタイプ クラスタリングは、グループ化を行うための最良の方法ですか?
• クラスタリングで「k」の選択を検証することについては、まだあまり考えていません。クラスタリングの SSE 曲線を評価することは、これを行うための最良の方法でしょうか?
• 私の方法論に欠陥はありますか？
• 将来のソリューションの拡張として、トレーニング データが与えられた場合、クラスター割り当てに確率を割り当てる方法について考えている人はいますか? たとえば、セット 1 がクラスター 1 に含まれる確率は 80% です。

私の質問があまりにもばかげているように見えたり、答えが痛々しいほど明白に見えたりしないことを願っています.私はデータマイニングに比較的慣れていません.

ありがとう！

ソース文字列と一連のパターン文字列の間であいまい一致を実行する必要があります。このマッチングは、式 1 - D(I,P) / max(length(I),length(P))
で 与えられます。

• I は入力文字列です
• P はパターン文字列です
• D(I,P) は、I と P の間のレーベンシュタイン距離です。

このスコアを最大化する P を見つけたら、I と P の共通部分をマッピングしたいと思います。

例: I="sunday" および P="saturday" の場合、マッピングは次のペアのリストのようになります:
{{0, 0}, {1, 3}, {3, 5}, {4 , 6}, {5, 7}}
(一般的な文字は「s」、「u」、「d」、「a」、および「y」であるため)

このウィキペディアの記事では、レーベンシュタイン距離を計算するための実装を簡単に見つけることができますが、説明されているプロセス中に構築されたマトリックスからマッピングを取得する方法は完全にはわかりません。誰でも私を啓発できますか？

ありがとう

ネットで見つけたレーベンシュタイン アルゴリズムを使用して、検索語に最も近い値を計算しようとしています。ファジー用語マッチングを実装するため。現在のクエリは、約 45 秒間実行されます。最適化できることを願っています。レーベンシュタイン値を計算するフィールドのインデックスは既に追加しています。私が見つけたレーベンシュタイン関数は、最も最適化されていない可能性があり、その実装を信用していません。その関数は次のとおりです。

そして、ここに私が使用しているクエリがあります:

私は DBA ではないので、ベスト プラクティスに関する私の無知を許してください。私は本当にこの処理をビジネス層でオフロードしたくなく、データ層に保持したいと考えていますが、処理に 45 秒かかる 16,000 レコードのみでは現在使用できません。これは、入力ファイルの処理が完了すると、データ ストア全体を構成するレコードの小さなサブセットのみです。前もって感謝します。

str1 str2 str3 ...のテキストファイルがあり、LD（str1、str2）LD（str2、str3）LD（str3、str4）などの別のテキストファイルを出力したいと思います。これを行う方法？どんな言語でもかまいません。

sql-sever2008dbの結果を使用してjQuery-UIオートコンプリートを使用して検索候補に取り組んでいます。テストにAdventureWorksDBProductsテーブルを使用する。この例では、2つのフィールドを検索したいと思います。製品番号と名前。

私はこれに関して以前に2つの質問をしました...こことここ

そして、これまでのところ、これを思いついたのです...

私の問題は結果の順序付けです...正しい結果が得られていますが、名前または製品番号で並べ替えられているだけで、入力文字列とは関係ありません...

たとえば、「BZ-」で始まる製品番号を検索できます。リストの他の場所でより関連性の高い結果が得られますが、返される上位の結果は「A」で始まるProductNumです。

検索文字列との関連性の観点から結果を並べ替えるためのアイデアはありますか？

編集：

ここにあるlevenschtein距離のtql実装に関して（前の質問にリンクされています）...

関数に送信するMAX値を決定するための最良の方法は何でしょうか（上記の例では6）

与えられたデータセットに対してうまく機能すると思われるものに基づいて、任意の値を選択するのが最善でしょうか？または、入力文字列の長さに基づいて動的に調整するのが最善でしょうか。

私の最初の考えは、toの値はsearchStringの長さに非常に比例する必要があるということでした...検索文字列が大きくなり、より具体的になるにつれて、許容範囲が減少します...思考??

私が取り組んでいる問題では、2つのシーケンス間の距離を見つけて類似性を判断するために、シーケンスの順序が非常に重要です。ただし、私が持っているシーケンスはすべて同じ長さではないため、ハミング距離の要件を満たすために、両方のシーケンスが同じ長さになるように、不足している文字列を空のポイントで埋めます。私が気にしているのは転置の数だけなので（レーベンシュタインのように挿入や削除ではない）、これを行うことに大きな問題はありますか？

より長いシーケンスの距離メトリックとして、ハミング距離はレーベンシュタインよりもはるかに高速であることがわかりました。はるかに安いハミング距離の代わりに、いつレーベンシュタイン距離（またはレーベンシュタイン距離の派生物）を使用する必要がありますか？ハミング距離は、2つのシーケンス間の可能なレーベンシュタイン距離の上限と見なすことができるため、シーケンスに一致する絶対最小移動数ではなく、順序に偏った類似性メトリックについて2つのシーケンスを比較している場合、明らかなものはありません。メトリックとしてハミングではなくレーベンシュタインを選択する理由はありますか？

オランダ語を話す人々にとって、2つの文字「ij」は「y」と簡単に交換できる1文字と見なされます。

私が取り組んでいるプロジェクトでは、ダメラウ・レーベンシュタイン距離の変形を使用して、「ij」と「y」の間の距離を現在の値2ではなく1として計算したいと思います。

私はこれを自分で試しましたが失敗しました。私の問題は、両方のテキストの長さが異なるという事実をどのように処理するかについての手がかりがないことです。誰かがこれを解決する方法についての提案/コードフラグメントを持っていますか？

ありがとう。