問題タブ [edit-distance]

この Wiki ページで提案されている LD 距離計算アルゴリズムのC#実装を検討してください。

特定の（事前定義された）距離しきい値をすでに超えている場合に計算プロセスを中止する機能を拡張したいと思います。

この概念的な最適化アプローチは、このスレッドで Alex Martelli によって提案されました。

問題は、提案された C# ソリューションに対して、このソリューションをどのように実装できるかということです。{補足: 関数は、返されるまでの最大距離を返す必要があります。}

どうもありがとう。

特定の編集距離を持つデータベース内のすべての文字列を特定の文字列に一致させたいという問題があります。

d私のアイデアは、文字列までの編集距離を持つすべての文字列に一致する正規表現を生成することでしたs。

たとえば、次の形式で正規表現を生成したいとしrます。しかし、これが非常に効率的であるかどうか、またはその問題に対するいくつかの優れたアルゴリズムがすでにあるかどうかはわかりません。編集距離での文字交換も検討したい。したがって、の一部でもある必要があります。PHPでそれを実現してから、SQLクエリを作成したいと思います。d = 1s = 'abc'r = 'abc|.abc|.bc|a.c|ab.|abc.''acb'rSELECT * FROM table WHERE name RLIKE TheRegularExpression

そのようにするのは良い方法ですか？または、何をお勧めしますか？

m = strlen(t) および n = strlen(s) で指定された 2 つの文字列 t および s の編集距離を計算するコードを書いています。コードは O(m) のメモリのみを使用する必要があります。さらに、約 50 文字の 2 つの文字列の計算に 4 秒以上かかることはありません。私の書いたコードは後者を満たしていますが、前者についてはよくわからないので、O(m) メモリ以下であるか確認していただければ幸いです。そうでない場合は、その方法のヒントを聞くことも役に立ちます。ありがとう。

たとえば、入力は["div","table","tr","td","a"]および["table","tr","td","a","strong"]であり、対応する出力は である必要があります2。

私の問題は、どちらかの入力リストのサイズが大きすぎる場合 (たとえば、リストに 40 個の文字列がある場合)、プログラムがcan't reserve enough space for object heapエラーを生成することです。JVM パラメータは-Xms512m -Xmx512m. 私のコードはそんなに多くのヒープ領域を必要とするでしょうか? または、コードの論理的なバグが原因ですか?

編集：リストのクローンを作成するかどうかに関係なく、この再帰的なアプローチはどちらの方法でも機能しないようです。誰かが私のために働くために必要な総ヒープメモリを見積もってくれませんか? 衝撃的だったと思います。とにかく、代わりに動的計画法のアプローチに目を向ける必要があると思います。

それを解決するために多くのコードを見てきましたが、2 つの単語間の距離を表すために行列を使用している理由がわかりません。誰でも私に説明してもらえますか？

これが私が見つけたサンプルコードです：

Edit Distanceアルゴリズムを使用して、名前データベースにあいまい検索を実装することを検討しています。

分割統治アプローチを通じてこれを高速化するのに役立つと思われるデータ構造を見つけました - Burkhard-Keller Trees。問題は、この特定の種類の木に関する情報があまり見つからないことです。

BK ツリーに任意のノードを設定すると、バランスの問題が発生する可能性はどのくらいありますか?

BK ツリーでバランスの問題が発生する可能性がある場合、構築後にそのようなツリーのバランスを取る方法はありますか?

BK ツリーのバランスを適切にとるためのアルゴリズムはどのようなものでしょうか?

これまでの私の考え：

子ノードは距離が異なるように見えるため、その下のツリー全体を再調整しないと、ツリー内の特定のノードを単純に回転させることはできません。ただし、最適な新しいルート ノードを見つけることができれば、これはまさに私がすべきことかもしれません。ただし、最適な新しいルート ノードを見つける方法がわかりません。

また、いくつかの方法を試して、空のツリーから開始し、事前に配布されたデータを挿入することによって、かなりバランスの取れたツリーを取得できるかどうかを確認します。

• アルファベット順にソートされたリストから始めて、真ん中からキューに入れます。（アルファベット順は編集距離での並べ替えとは異なるため、これが良いアイデアかどうかはわかりません）。
• 完全にシャッフルされたデータ。(これは運に大きく依存して、偶然に「それほどひどくない」ルートを選択します。ひどく失敗する可能性があり、最適ではないことが確率的に保証される可能性があります)。
• リスト内の任意の単語から始めて、残りの項目をその項目からの編集距離で並べ替えます。そして真ん中から並びます。(これにはコストがかかると思いますが、すべての単語間のメトリック空間の接続を計算するわけではないため、各単語と単一の参照単語だけで計算することはできません)。
• 任意の方法で最初のツリーを構築し、それを平坦化し (基本的には事前注文トラバーサルのように)、途中から新しいツリーのキューに入れます。(これもコストがかかります。事前にすべての単語間のメトリック空間の接続を計算せず、単に別の不均一な分布が得られるため、まだうまくいかない可能性があると思います)。
• 名前の頻度で並べ替え、最も人気のあるものを最初に挿入し、バランスの取れたツリーの概念を捨てます。(私のデータは均等に分散されておらず、純粋にランダムな単語が入ってくることはないので、これが最も理にかなっているかもしれません)。

参考までに、私は現在、同義語の問題 (Bill vs William) について心配していません。私はそれを個別に扱いますが、まったく異なる戦略が適用されると思います.

長い (> 1000 項目) 単語のリストがあり、残りの単語がすべて「著しく異なる」まで、他の単語と「あまりにも似ている」単語を削除したいと考えています。たとえば、編集距離 D 内に 2 つの単語が入らないようにします。

一意のソリューションは必要ありません。また、正確に最適である必要もありませんが、(Python では) 適度に高速であり、あまりにも多くのエントリを破棄しないようにする必要があります。

どうすればこれを達成できますか？ありがとう。

編集：明確にするために、編集距離を測定するPythonルーチンをグーグルで検索できます。問題は、これを効率的に行う方法であり、おそらく、D の「自然な」値を見つける方法です。おそらく、すべての単語からある種のトライを構築し、剪定することでしょうか?

私は一日中、対処できないような問題に取り組んできました。タスクは、編集距離の再帰的実装が時間計算量Ω（2 ^{max（n、m）}）を持っていることを示すことです。ここで、n＆mは測定される単語の長さです。

実装はこの小さなPythonの例に匹敵します

差出人：http ：//www.clear.rice.edu/comp130/12spring/editdist/

さまざまな短い単語に対して再帰の深さのツリーを描画しようとしましたが、ツリーの深さと複雑さの関係を見つけることができません。

私の計算からの再帰式

しかし、長さが0に達しないため、各呼び出しは3つの新しい呼び出しにつながるため、どのように進めるかはわかりません。

下限の複雑さがΩ（^{2max（n、m）}）であることを示すためにどのように進めることができるかについてのヒントをいただければ幸いです。

現在、3つの観測値を持つ折れ線グラフを作成しています。したがって、3つのx軸ティックがあります。

x軸の目盛り間の距離を手動で減らし、基本的に観測値を互いに近づけたいと思います。つまり、x軸の目盛り間の距離を縮めたいのです。

私のデータ：

私のコード：

Edit Distance / Levenshtein Distance に基づいて、ELKI を使用して多数の文字列をクラスター化する必要があります。データ セットが大きすぎるため、ファイル ベースの事前計算された距離行列は避けたいと思います。どうやって

(a) ファイルから ELKI に文字列データをロードしますか (「ラベル」のみ)?

(b) ラベルにアクセスする距離関数を実装します (AbstractDBIDDistanceFunction を拡張しますが、ラベルを取得する方法は?)

いくつかのコード スニペットまたは入力ファイルの例が役立ちます。