2

ソース文字列と一連のパターン文字列の間であいまい一致を実行する必要があります。このマッチングは、式 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」であるため)

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

ありがとう

4

2 に答える 2

2

例として挙げたマッピングには、一般的な文字を探しているだけなので、私が見ることができる編集距離はまったく組み込まれていません。誤解しているかもしれませんが、一般的な文字のマッピングに編集距離マトリックスは必要ありません。編集距離を確認するのは、D(I,P) の計算中だけで、最高得点のパターン文字列を決定します。例として示したマッピングを生成するには、両方の文字列を繰り返し処理して、ペアを識別するための文字インデックスを決定するだけです。

于 2010-12-08T05:58:06.580 に答える
0

列挙されたソース文字列内の位置である「ソース」と「宛先」と呼ばれる同じ配列の 2 つのコピーから始めます。削除すると、両方の配列から対応する要素が削除され、宛先配列の次の値が減少します。挿入は、宛先配列の次の値を増やします。次に、両方の配列を圧縮してマップを生成します。

于 2010-12-04T20:35:49.830 に答える