levenshtein-distance - 複数の関連するレーベンシュタイン距離を計算する方法は？

Question

同じ長さの2つの文字列が与えられた場合、レーベンシュタイン距離により、最初の文字列が与えられた場合に、2番目の文字列を取得するために必要な変換の最小数を見つけることができます。ただし、すべて同じ方法で生成された文字列の複数のペアのアルゴリズムを調整する方法を見つけたいと思います。

Answer 1

コメントを読むと、これが問題であるように見えます。

すべて同じ長さの文字列のペアのセットが与えられ、各ペアは、関数からの出力とペアになっている関数への入力です。したがって、ペアA、Bの場合、f（A）=Bであることがわかります。目標は、A、Bペアの大規模なセットを使用してf（）をリバースエンジニアリングすることです。

セット全体でレーベンシュタイン距離を使用すると、最大で、実行する必要のある変換の最大数がわかります。

より良いスタートは、ハミング距離（複数の文字を許可するように変更）またはJaccardの類似性で、すべてのペアで文字列内の位置がまったく変化しないことを識別します。そうすれば、あなたは変化するものだけを残されます。

文字がずれると失敗します。

シフトを検出するには、グローバルアラインメント（Needleman-Wunsch）を使用します。"ABCDE"=>"xABCD"次に、入力から出力に左シフトがあったことを示すようなものが表示されます。

全体として、レーベンシュタイン距離は、元のアルゴリズムを取得するのにほとんど役立たないと思います。