calculating Levenshtein Distance using word lists
first i want to say that i am a newbie in python. I trying to calculate the Levenshtein Distance for many lists of word. Until now i succeed writing the code for a pair of word, but i'm having some problems doing it for lists. I just habe two lists with words one below the other like this: carlos stiv peter
I want to use the Levenshtein distance for a similarity approach. Could somebady tell me how i can load the lists and then use a function to calculate de distance?
I'll appreciated!
Here is my code just for two strings:
#!/usr/bin/env python
# -*- coding=utf-8 -*-
def lev_dist(source, target):
if source == target:
return 0
#words = open(test_file.txt,'r').read().split();
# Prepare matrix
slen, tlen = len(source), len(target)
dist = [[0 for i in range(tlen+1)] for x in range(slen+1)]
for i in xrange(slen+1):
dist[i][0] = i
for j in xrange(tlen+1):
dist[0][j] = j
# Counting distance
for i in xrange(slen):
for j in xrange(tlen):
cost = 0 if source[i] == target[j] else 1
dist[i+1][j+1] = min(
dist[i][j+1] + 1, # deletion
dist[i+1][j] + 1, # insertion
dist[i][j] + cost # substitution
)
return dist[-1][-1]
if __name__ == '__main__':
import sys
if len(sys.argv) != 3:
print 'Usage: You have to enter a source_word and a target_wor开发者_StackOverflowd'
sys.exit(-1)
source, target = sys.argv[1], sys.argv[2]
print lev_dist(source, target)
I finally got the code working with some help from a friend :) You can compute the Levenshtein distance and compare it to every word from the second list changing the last line in the script, i.e: print(list1[0], list2[i]), to compare the first word from the list1 to every word in list2.
Thanks
#!/usr/bin/env python
# -*- coding=utf-8 -*-
import codecs
def lev_dist(source, target):
if source == target:
return 0
# Prepare a matrix
slen, tlen = len(source), len(target)
dist = [[0 for i in range(tlen+1)] for x in range(slen+1)]
for i in range(slen+1):
dist[i][0] = i
for j in range(tlen+1):
dist[0][j] = j
# Counting distance, here is my function
for i in range(slen):
for j in range(tlen):
cost = 0 if source[i] == target[j] else 1
dist[i+1][j+1] = min(
dist[i][j+1] + 1, # deletion
dist[i+1][j] + 1, # insertion
dist[i][j] + cost # substitution
)
return dist[-1][-1]
# load words from a file into a list
def loadWords(file):
list = [] # create an empty list to hold the file contents
file_contents = codecs.open(file, "r", "utf-8") # open the file
for line in file_contents: # loop over the lines in the file
line = line.strip() # strip the line breaks and any extra spaces
list.append(line) # append the word to the list
return list
if __name__ == '__main__':
import sys
if len(sys.argv) != 3:
print 'Usage: You have to enter a source_word and a target_word'
sys.exit(-1)
source, target = sys.argv[1], sys.argv[2]
# create two lists, one of each file by calling the loadWords() function on the file
list1 = loadWords(source)
list2 = loadWords(target)
# now you have two lists; each file has to have the words you are comparing on the same lines
# now call you lev_distance function on each pair from those lists
for i in range(0, len(list1)): # so now you are looping over a range of numbers, not lines
print lev_dist(list1[0], list2[i])
# print lev_dist(source, target)
Don't reinvent wheels:
http://pypi.python.org/pypi/python-Levenshtein/
精彩评论