如何计算两个.txt文件之间的Levenshtein距离？

Question

是否有标准的Linux命令来完成此操作？如果没有，能否描述一个Python脚本来实现相同的功能？

- blastoise

Answer 1

我不建议这样做。Levenshtein距离函数的复杂度几乎为O(n*m)，当文本相似时，它是O(n²)。但如果你想这么做...可以使用以下命令安装python-Levenshtein：pip install python-Levenshtein，然后代码将类似于：

from Levenshtein import *

txt1 = open("text1.txt").read()
txt2 = open("text2.txt").read()

print("distance:", distance(txt1,txt2))

- Luxusproblem

---

太好了，成功了 :). 你有比较两个文件更好的方法吗？我正在比较两个OCR程序的输出。 - blastoise

Answer 2

这要看情况。当OCR输出相似且预期有少量差异时，您可以进行“分割”并比较每个单词/行等。只有在行数相同时才使用Levenshtein距离来处理不同之处。例如：

def textLevi(txt1,txt2):
   lines = list(zip(txt1.split("\n"),txt2.split("\n")))
   distance = 0
   for i,ele in enumerate(lines,1):
        line1,line2 = ele
       if line1 != line2:
           actDistance = distance(line1,line2)
           print( "Distance of line %d: " %(i),actDistance)
           distance += actDistance


   print( "Sum of Lv Distances:",distance)
 
textLevi("Hello I \n like cheese","Hello I \n like cheddar")

将创建以下输出：

第二条线的距离：4

Lv距离之和：4

- Luxusproblem