Levinshtein距離Python中的文本文件中的兩個單詞的距離

我有一個很小的30行文本文件，每行有兩個相似的單詞。我需要計算每行兩個詞之間的levenshtein distance。在計算距離時我還需要使用memoize函數。我對Python和算法一般都很陌生，所以這證明對我來說很困難。我打開並閱讀文件，但我無法弄清楚如何將兩個單詞中的每一個都分配給變量'a'&'b'來計算距離。Levinshtein距離Python中的文本文件中的兩個單詞的距離

這裏是我當前的腳本，只打印文檔的現在：

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

下面是從文本文件中的幾句話使大家得到一個想法：

拱形物，原型

propietary，專有

recogize，認識

exludes，排除

tornadoe，龍捲風

happenned，發生

vacinity，附近

該處是腳本的更新的版本，仍然沒有的功能，但更好的：

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)

來源

2012-10-09 Ty Bailey

這是一個很好的做法，讓您的定義（memoize的，LEV等），您的實際任務（讀取文件時，循環）分開。即在'if __name __ =='__ main __'之前保留所有的定義：'和'if'語句下的腳本的所有主要工作。因此，在'__name__'檢查之後進行「open」調用會很好。我覺得'current = range（a + 1）'是你的'lev'實現的一部分，試着縮進它。爲了更加清晰，現在你是否還可以顯示'wordfile.txt'中的幾行？ –

什麼構成這個情景中的一個詞？我只是假設任何信件，但是這是你正在做的假設？ – grieve

是的，任何只有字母的東西。這些詞非常簡單，非常相似，每個詞中沒有少數字母。爲了清楚起見，我在文件中添加了幾個字。 –

假設問題出在傳遞給的文字。而假設你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)

來源

2012-10-09 16:11:45

好吧，這允許我將單詞賦給a＆b變量，但現在我得到這樣的錯誤「不能連接'我沒有使用任何整數'的'str'和'int'對象」？編輯：錯誤來自行'電流=範圍（a + 1）' –

您正在添加+ 1，但a是一個字符串「範圍（a + 1）」 – grieve

如果您想要生成的範圍是比變量'a'（這是一個字符串）的長度多1個，你可以做'range（len（a）+ 1）' –

我想通了這個問題的答案與阿布舍克的回答和評論一些幫助。下面是如果最終的運行腳本，任何人都需要它：

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): 
    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__": 
    lev = Counter(lev) 
    word_file = open('wordfile.txt', 'r') 
    for line in word_file: 
      a,b = line.split() 
      print a,b, lev(a, b)

來源

2012-10-09 18:57:44

Levinshtein距離Python中的文本文件中的兩個單詞的距離

回答

相關問題