3

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

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

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

def unordered_edit_distance(target, source):
    return min(edit_distance(target, source_perm) 
               for source_perm in permuations(source))

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

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

4

4 に答える 4

1

置換はしばらく無視しましょう。

これで、最初のセットのみの要素 (削除としてカウントされる) と 2 番目のセットのみの要素 (挿入としてカウントされる) を決定するという、かなり些細な問題になります。これは、次のいずれかで簡単に実行できます。

  • セットを並べ替えて両方を同時に反復する、または
  • 最初のセットの各要素をハッシュ テーブルに挿入し、次に 2 番目のセットの各要素をハッシュ テーブルから削除します。見つからなかった各要素は挿入であり、完了後にハッシュ テーブルに残っている各要素は削除です

さて、置換を含めるには、挿入された要素と削除された要素の最適な組み合わせを見つけるだけです。これは実際には安定した結婚の問題です:

安定結婚問題 (SMP) は、各要素の一連の設定が与えられた場合に、要素の 2 つのセット間の安定した一致を見つける問題です。マッチングとは、一方のセットの要素から他方のセットの要素へのマッピングです。マッチングは、次の両方に当てはまらない場合はいつでも安定しています。

  1. 最初に一致したセットの特定の要素 A は、A が既に一致している要素よりも、2 番目に一致したセットの特定の要素 B を優先し、
  2. B は、B が既に一致している要素よりも A を優先します

Gale-Shapley アルゴリズムで解決できるもの:

Gale-Shapley アルゴリズムには、多数の「ラウンド」(または「反復」) が含まれます。最初のラウンドでは、まず a) 婚約していない各男性が最も好む女性にプロポーズし、次に b) 各女性が最も好む求婚者に「たぶん」と答え、他のすべての求婚者には「いいえ」と答えます。彼女はその後、彼女が今のところ最も好む求婚者と暫定的に「婚約」し、その求婚者も同様に彼女と暫定的に婚約します。その後の各ラウンドでは、まず a) 婚約していない各男性が、まだプロポーズしていない最も好ましい女性にプロポーズし (その女性がすでに婚約しているかどうかに関係なく)、次に b) 各女性が自分の求婚者に「たぶん」と答える。ほとんどの場合 (彼女の既存の暫定パートナーか他の誰か) を好み、残り (おそらく現在の暫定パートナーを含む) を拒否します。

コストを正しく取得する必要があるだけです。挿入と削除を対にして置換すると、挿入と削除の両方のコストが失われ、置換のコストが得られるため、ペアリングの正味のコストは になりますsubstitutionCost - insertionCost - deletionCost。

上記のアルゴリズムは、すべての挿入または削除がペアになることを保証します-必ずしもこれが必要なわけではありませんが、簡単な修正があります-「そのままの状態で」要素の束を作成するだけです(挿入側と削除側の両方で)- 「そのまま維持」要素と組み合わせた挿入または削除のコストは 0 であり、結果として挿入または削除のままになり、ペアになった 2 つの「そのまま維持」要素については何も起こりません。

于 2014-03-12T11:56:44.017 に答える
1

あなたの観察はある程度正しいですが、実際には単純な問題をより複雑にしています。

ソースは元のソースの任意の順列になる可能性があるため、最初に文字レベルの違いを確認する必要があります。

2 つのマップを作成し、各マップでターゲット文字列とソース文字列の個々の文字数をカウントします。

例: a: 2 c: 1 d: 100

ここで、2 つのマップを比較します。文字が欠落している場合はもちろん挿入する必要があり、余分な文字がある場合は削除します。それでおしまい。

于 2014-03-12T09:20:52.907 に答える
1

それらを並べ替え (必須ではありません)、両方のセットで同じ (そして同じ数の!) アイテムを削除します。次に、セットのサイズが等しい場合は、その数の置換が必要です。1 つが大きい場合は、いくつかの挿入または削除も必要です。とにかく、最初のフェーズの後に残っているより大きなセットのサイズに等しい操作の数が必要です。

于 2014-03-12T09:17:30.127 に答える
0

重要な観察: 各文字列内のすべての文字を並べ替えることができるため、文字列に含まれる 'a'、'b'、...、'z' またはその他のアルファベット文字の数だけに関心があります。

したがって、問題は次のように要約されます:s['a']文字 'a'、文字 'b'、...、文字 'z' を文字 'a'、文字s['b']'b'、...、文字s['z']'z' に変換します。'。アルファベットが短く、配列にすることができる場合。一般に、 C++ やPython などのように、アルファベットから整数へのマッピングです。t['a']t['b']t['z']s[]t[]map <char, int>dict

さて、各文字について、とcがわかりました。の場合、最初の順不同文字列 ( ) から文字を削除する必要があります。の場合、 2 番目の順不同文字列 ( ) に文字を追加する必要があります。s[c]t[c]s[c] > t[c]s[c] - t[c]css[c] < t[c]t[c] - s[c]ct

、そのようなすべてXの の合計を取ると、合計で削除する必要がある文字の数が得られます。、そのようなすべての の合計を取ると、合計で削除する必要がある文字の数が得られます。s[c] - t[c]cs[c] > t[c]sYt[c] - s[c]cs[c] < t[c]t

さて、みましょうZ = min (X, Y)。置換を行うことができZ、残るのはX - Z挿入とY - Z削除です。したがって、操作の総数はZ + (X - Z) + (Y - Z)、またはX + Y - min (X, Y)です。

于 2014-03-12T09:18:28.193 に答える