問題タブ [edit-distance]

Python には、アクセントを考慮した編集距離がありますか。たとえば、次のプロパティを保持する場所

2 つの文字列の間にレーベンシュタイン距離 (または編集距離) がある文字列のように、グラフにも同様のものがあるのでしょうか?

つまり、グラフG1をグラフに変換するためのアトミック操作 (ノードとエッジの挿入/削除) の数を識別するスカラー メジャーですG2。

Zhang と Shasha によるアルゴリズムを実装して、2 つのツリー間の最小編集距離を計算しました。すべてがうまく機能しており、現在の実行時間に非常に満足しています。

ここで、変更/削除/挿入されたノードを強調表示する差分も生成したいと思います。彼らの論文によると、計算された距離をもたらすマッピングを求めるのは非常に自然なことであり、このプレゼンテーションの最後のスライドによると、最後の森林距離テーブルと樹木距離テーブルからマッピングを簡単に抽出できるようです。残念ながら、私はまだ正確なルールを把握できていません。

追加の説明をいただければ幸いです。どうもありがとう！

この記事では、サフィックス ツリーを利用してマッチング時間を改善する近似部分文字列マッチング手法について説明します。各回答は、異なるアルゴリズムに対応しています。

1. P部分文字列の近似一致では、文字列内の部分文字列 (パターン) を見つけようとしますが、不一致はT許容されます。k
2. サフィックス ツリーの作成方法については、ここをクリックしてください。ただし、一部のアルゴリズムでは追加の前処理が必要です。

新しいアルゴリズムを追加し (不完全であっても)、回答を改善するように人々を招待します。

順序付けられていない 2 つのシンボル コレクション間の最小編集距離を効率的に計算する方法が必要です。シーケンスに対してのみ機能するレーベンシュタイン距離のように、シンボルごとのコストが異なる挿入、削除、および置換が必要です。また、編集スクリプトの復元にも関心があります。

私が達成しようとしているのは、文字列編集距離の計算に非常に似ているため、順序付けられていない文字列編集距離または設定編集距離と呼ばれる可能性があると考えました。しかし、Google はそれらの検索用語では何も出てこないので、問題が別の名前で知られているかどうか知りたいです。

明確にするために、問題は次のように解決されます

たとえば、 はunordered_edit_distance('abc', 'cba')になりますが0、edit_distance('abc', 'cba')は です2。残念ながら、順列の数は非常に急速に大きくなり、適度なサイズの入力に対しても実用的ではありません。

編集操作がさまざまなコストに関連付けられていることをより明確にします。