python - Levinshtein 使用 Python 从文本文件中提取两个单词的距离

Question

我有一个 30 行的小文本文件，每行有两个相似的词。我需要计算 levenshtein distance在每行的两个词之间。我还需要使用 memoize函数同时计算距离。一般来说，我对 Python 和算法还很陌生，所以事实证明这对我来说非常困难。我打开并读取了文件，但我不知道如何将这两个词中的每一个分配给变量“a”和“b”来计算距离。

这是我目前的脚本，它现在只打印文档:

txt_file = open('wordfile.txt', 'r')

def memoize(f):
    cache = {}
    def wrapper(*args, **kwargs):
        try:
            return cache[args]
        except KeyError:
            result = f(*args, **kwargs)
            cache[args] = result
            return result
    return wrapper

@memoize
def lev(a,b):
    if len(a) > len(b):
        a,b = b,a
        b,a = a,b

current = range(a+1)
for i in range(1,b+1):
    previous, current = current, [i]+[0]*n
    for j in range(1,a+1):
        add, delete = previous[j]+1, current[j-1]+1
        change = previous[j-1]
        if a[j-1] != b[i-1]:
            change = change + 1
        current[j] = min(add, delete, change)

return current[b]

if __name__=="__main__":
    with txt_file as f:
        for line in f:
            print line

以下是文本文件中的几句话，以便大家了解:

原型(prototype)，原型(prototype)

专有的，专有的

认识，认识

排除，排除

Tornado ， Tornado

发生了，发生了

邻近地区

这是脚本的更新版本，仍然不能正常工作但更好:

class memoize:
    def __init__(self, function):
    self.function = function
    self.memoized = {}

def __call__(self, *args):
    try:
      return self.memoized[args]
    except KeyError:
      self.memoized[args] = self.function(*args)
      return self.memoized[args]

@memoize
def lev(a,b):
    n, m = len(a), len(b)
    if n > m:
        a, b = b, a
        n, m = m, n
    current = range(n + 1)
    for i in range(1, m + 1):
        previous, current = current, [i] + [0] * n
        for j in range(1, n + 1):
            add, delete = previous[j] + 1, current[j - 1] + 1
            change = previous[j - 1]
            if a[j - 1] != b[i - 1]:
                change = change + 1
            current[j] = min(add, delete, change)
    return current[n]

if __name__=="__main__":
    for pair in open("wordfile.txt", "r"):
        a,b = pair.split()
        lev(a, b)

Answer 1

假设问题是将单词传递给 lev。并假设您的 wordfile 是这样的 -

bat, man
cat, goat
foo, bar

然后你可以做这样的事情-

if __name__ == '__main__':

    for pair in open("wordfile", "r"):

        # first, remove all spaces, then break around the comma
        a,b = pair.replace(' ', '').split(',')

        # pass these words to lev
        lev(a, b)