如何計算多個相關的Levenshtein距離？

Question

給定兩個等長的字符串，Levenshtein距離允許找到獲得第二個字符串所需的最小轉換次數，給定第一個字符串。但是，我想找到一種方法來調整多個字符串對的算法，因爲它們都是以相同的方式生成的。

Answer 1

閱讀註釋，看來這就是問題所在：

您將得到一組字符串對的，都是一樣的長度，每對是輸入與來自函數的輸出配對的一些功能。所以，對於A，B，我們知道f（A）= B。目標是用大量的A，B對對f（）進行逆向工程。

在整個集合上使用Levenshtein距離最多可以告訴您必須發生的最大轉換次數。

更好的開始將是漢明距離（修改爲允許多個字符）或Jaccard相似度來確定字符串中有多少位置根本不會改變所有對。然後，你只剩下那些改變了的人。

如果字母改變，這將失敗。

要檢測換檔，您想使用全局比對（Needleman-Wunsch）。然後，您將看到類似"ABCDE"=>"xABCD"的內容，以顯示從輸入到輸出的結果是左移。總的來說，我覺得Levenshtein距離對於幫助你獲得原始算法做的很少。