多次元文字列のレーベンシュタイン距離 (編集距離) の拡張機能を探しています。多次元の正式な定義があるかどうかはわかりませんが、ここで私が話していることは次のとおりです。
1-D 文字列:通常の文字列です
2-D 文字列:次のような 1-D 文字列のリストのようなものです
dfdsfdsfdsf
dsffgdfdgfdsdaf
dsfdsf
fdgfdgfdg
ND 文字列: (N-1)-D 文字列のリスト
このような多次元文字列間のレーベンシュタイン距離を計算するにはどうすればよいですか?
編集距離は、1 つの文字列を別の文字列に変換する操作の最小コスト シーケンスに基づいています。これらの操作がめったにないエラーを表す場合、その距離は、ある文字列が別の文字列に破損する確率のおおよその尺度です。
2 次元のバリアントを見つけるには、どのような種類の操作が許可されるかを決定する必要があります。これは、これを解決したい理由によって異なります。一方のリストの各文字列が他方のリストの対応する文字列にマップされている場合、結果のペアの編集距離の合計が必要になる場合があります。まったく対応がない場合は、n * m ペアのすべての文字列の編集距離を計算し、最初のリストの 1 つの文字列を 2 番目のリストの 1 つの文字列に関連付ける最小コストの一致を見つけ、一致をスコアリングします。一致した文字列のペアの編集距離の合計。破損プロセスが文字列全体の挿入と削除、および文字列内の文字の挿入と削除を行う場合、