entityMap|0|type|LINK|mutability|MUTABLE|data|url|https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python|blocks|key|cb9gi|text|我在这里看到了很多实现：https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|b9tgr|因此，我只是询问了所有开箱即用的方法，以帮助他们理解成本。|4cf0c|import+numpy+as+np

def+Mylevenshtein(String1,+String2):
++++if+len(String1)+and+len(String2)+!=+0:
++++++++rows+=+len(String1)+%2B+1
++++++++columns+=+len(String2)+%2B+1
++++++++distance+=+[[0+for+x+in+range(columns)]+for+x+in+range(rows)]
++++++++for+i+in+range(1,+rows):
++++++++++++distance[i][0]+=+i
++++++++for+i+in+range(1,+columns):
++++++++++++distance[0][i]+=+i
++++++++for+column+in+range(1,+columns):
++++++++++++for+row+in+range(1,+rows):
++++++++++++++++if+String1[row+-+1]+==+String2[column+-+1]:
++++++++++++++++++++cost+=+0
++++++++++++++++else:
++++++++++++++++++++cost+=+2
++++++++++++++++distance[row][column]+=+min(distance[row+-+1][column]+%2B+1,++#+deletion
+++++++++++++++++++++++++++++++++++++distance[row][column+-+1]+%2B+1,++#+insertion
+++++++++++++++++++++++++++++++++++++distance[row+-+1][column+-+1]+%2B+cost)+#substitution
++++Distance+=+distance[row][column]
++++return+Distance


def+levenshtein1(s1,+s2):
++++if+len(s1)+<+len(s2):
++++++++return+levenshtein1(s2,+s1)

++++#+len(s1)+>=+len(s2)
++++if+len(s2)+==+0:
++++++++return+len(s1)

++++previous_row+=+range(len(s2)+%2B+1)
++++for+i,+c1+in+enumerate(s1):
++++++++current_row+=+[i+%2B+1]
++++++++for+j,+c2+in+enumerate(s2):
++++++++++++insertions+=+previous_row[
+++++++++++++++++++++++++++++j+%2B+1]+%2B+1++#+j%2B1+instead+of+j+since+previous_row+and+current_row+are+one+character+longer
++++++++++++deletions+=+current_row[j]+%2B+1++#+than+s2
++++++++++++substitutions+=+previous_row[j]+%2B+(c1+!=+c2)
++++++++++++current_row.append(min(insertions,+deletions,+substitutions))
++++++++previous_row+=+current_row

++++return+previous_row[-1]


def+levenshtein2(a,+b):
++++if+not+a:+return+len(b)
++++if+not+b:+return+len(a)
++++return+min(levenshtein2(a[1:],+b[1:])%2B(a[0]+!=+b[0]),+levenshtein2(a[1:],+b)%2B1,+levenshtein2(a,+b[1:])%2B1)


def+levenshtein3(s,t):
++++s+=+'+'+%2B+s
++++t+=+'+'+%2B+t
++++d+=+{}
++++S+=+len(s)
++++T+=+len(t)
++++for+i+in+range(S):
++++++++d[i,+0]+=+i
++++for+j+in+range+(T):
++++++++d[0,+j]+=+j
++++for+j+in+range(1,T):
++++++++for+i+in+range(1,S):
++++++++++++if+s[i]+==+t[j]:
++++++++++++++++d[i,+j]+=+d[i-1,+j-1]
++++++++++++else:
++++++++++++++++d[i,+j]+=+min(d[i-1,+j],+d[i,+j-1],+d[i-1,+j-1])+%2B+1
++++return+d[S-1,+T-1]




def+levenshtein5(source,+target):
++++if+len(source)+<+len(target):
++++++++return+levenshtein5(target,+source)

++++#+So+now+we+have+len(source)+>=+len(target).
++++if+len(target)+==+0:
++++++++return+len(source)

++++#+We+call+tuple()+to+force+strings+to+be+used+as+sequences
++++#+('c',+'a',+'t',+'s')+-+numpy+uses+them+as+values+by+default.
++++source+=+np.array(tuple(source))
++++target+=+np.array(tuple(target))

++++#+We+use+a+dynamic+programming+algorithm,+but+with+the
++++#+added+optimization+that+we+only+need+the+last+two+rows
++++#+of+the+matrix.
++++previous_row+=+np.arange(target.size+%2B+1)
++++for+s+in+source:
++++++++#+Insertion+(target+grows+longer+than+source):
++++++++current_row+=+previous_row+%2B+1

++++++++#+Substitution+or+matching:
++++++++#+Target+and+source+items+are+aligned,+and+either
++++++++#+are+different+(cost+of+1),+or+are+the+same+(cost+of+0).
++++++++current_row[1:]+=+np.minimum(
++++++++++++++++current_row[1:],
++++++++++++++++np.add(previous_row[:-1],+target+!=+s))

++++++++#+Deletion+(target+grows+shorter+than+source):
++++++++current_row[1:]+=+np.minimum(
++++++++++++++++current_row[1:],
++++++++++++++++current_row[0:-1]+%2B+1)

++++++++previous_row+=+current_row

++++return+previous_row[-1]

def+levenshtein6(s,+t):
++++'''+From+Wikipedia+article;+Iterative+with+two+matrix+rows.+'''
++++if+s+==+t:
++++++++return+0
++++elif+len(s)+==+0:
++++++++return+len(t)
++++elif+len(t)+==+0:
++++++++return+len(s)
++++v0+=+[None]+*+(len(t)+%2B+1)
++++v1+=+[None]+*+(len(t)+%2B+1)
++++for+i+in+range(len(v0)):
++++++++v0[i]+=+i
++++for+i+in+range(len(s)):
++++++++v1[0]+=+i+%2B+1
++++++++for+j+in+range(len(t)):
++++++++++++cost+=+0+if+s[i]+==+t[j]+else+1
++++++++++++v1[j+%2B+1]+=+min(v1[j]+%2B+1,+v0[j+%2B+1]+%2B+1,+v0[j]+%2B+cost)
++++++++for+j+in+range(len(v0)):
++++++++++++v0[j]+=+v1[j]

++++return+v1[len(t)]


for+implementation_variant+in+[g+for+g+in+globals()+if+"leven"+in+g]:
++++print("Try+variant+%25s"+%25+implementation_variant)
++++for+a,+b+in+[("hamchenoonan",+"hamchenin"),
+++++++++++++++++("Tier",+"Tor")]:
++++++++print("+-Distance+of+%25s+and+%25s+is+%25i"+%25+(a,+b,+globals()[implementation_variant](a,+b)))|code-block|syntax|javascript|cr7vg|输出显示：|9ubio|Try+variant+Mylevenshtein
+-Distance+of+hamchenoonan+and+hamchenin+is+5
+-Distance+of+Tier+and+Tor+is+3
Try+variant+levenshtein1
+-Distance+of+hamchenoonan+and+hamchenin+is+4
+-Distance+of+Tier+and+Tor+is+2
Try+variant+levenshtein2
+-Distance+of+hamchenoonan+and+hamchenin+is+4
+-Distance+of+Tier+and+Tor+is+2
Try+variant+levenshtein3
+-Distance+of+hamchenoonan+and+hamchenin+is+4
+-Distance+of+Tier+and+Tor+is+2
Try+variant+levenshtein5
+-Distance+of+hamchenoonan+and+hamchenin+is+4
+-Distance+of+Tier+and+Tor+is+2
Try+variant+levenshtein6
+-Distance+of+hamchenoonan+and+hamchenin+is+4
+-Distance+of+Tier+and+Tor+is+2|a49tv|德国维基百科中提到了Tier和Tor的距离，只是作为第二次验证。因此，民主党的答案似乎是4。|70h08^0|C|2I|0|0|0|0|0|0|0^^$0|$1|$2|3|4|5|6|$7|8]]]|9|@$A|B|C|D|2|E|F|Y|G|@]|H|@$I|Z|J|10|A|11]]|6|$]]|$A|K|C|L|2|E|F|12|G|@]|H|@]|6|$]]|$A|M|C|N|2|O|F|13|G|@]|H|@]|6|$P|Q]]|$A|R|C|S|2|E|F|14|G|@]|H|@]|6|$]]|$A|T|C|U|2|O|F|15|G|@]|H|@]|6|$P|Q]]|$A|V|C|W|2|E|F|16|G|@]|H|@]|6|$]]|$A|X|C|-4|2|E|F|17|G|@]|H|@]|6|$]]]]

Here I've seen many implementations:
<a href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python" rel="nofollow noreferrer">https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python</a>

So I just asked all that worked out of the box for their understanding of costs. 

<pre><code>import numpy as np

def Mylevenshtein(String1, String2):
 if len(String1) and len(String2) != 0:
 rows = len(String1) + 1
 columns = len(String2) + 1
 distance = [[0 for x in range(columns)] for x in range(rows)]
 for i in range(1, rows):
 distance[i][0] = i
 for i in range(1, columns):
 distance[0][i] = i
 for column in range(1, columns):
 for row in range(1, rows):
 if String1[row - 1] == String2[column - 1]:
 cost = 0
 else:
 cost = 2
 distance[row][column] = min(distance[row - 1][column] + 1, # deletion
 distance[row][column - 1] + 1, # insertion
 distance[row - 1][column - 1] + cost) #substitution
 Distance = distance[row][column]
 return Distance


def levenshtein1(s1, s2):
 if len(s1) &lt; len(s2):
 return levenshtein1(s2, s1)

 # len(s1) &gt;= len(s2)
 if len(s2) == 0:
 return len(s1)

 previous_row = range(len(s2) + 1)
 for i, c1 in enumerate(s1):
 current_row = [i + 1]
 for j, c2 in enumerate(s2):
 insertions = previous_row[
 j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
 deletions = current_row[j] + 1 # than s2
 substitutions = previous_row[j] + (c1 != c2)
 current_row.append(min(insertions, deletions, substitutions))
 previous_row = current_row

 return previous_row[-1]


def levenshtein2(a, b):
 if not a: return len(b)
 if not b: return len(a)
 return min(levenshtein2(a[1:], b[1:])+(a[0] != b[0]), levenshtein2(a[1:], b)+1, levenshtein2(a, b[1:])+1)


def levenshtein3(s,t):
 s = ' ' + s
 t = ' ' + t
 d = {}
 S = len(s)
 T = len(t)
 for i in range(S):
 d[i, 0] = i
 for j in range (T):
 d[0, j] = j
 for j in range(1,T):
 for i in range(1,S):
 if s[i] == t[j]:
 d[i, j] = d[i-1, j-1]
 else:
 d[i, j] = min(d[i-1, j], d[i, j-1], d[i-1, j-1]) + 1
 return d[S-1, T-1]




def levenshtein5(source, target):
 if len(source) &lt; len(target):
 return levenshtein5(target, source)

 # So now we have len(source) &gt;= len(target).
 if len(target) == 0:
 return len(source)

 # We call tuple() to force strings to be used as sequences
 # ('c', 'a', 't', 's') - numpy uses them as values by default.
 source = np.array(tuple(source))
 target = np.array(tuple(target))

 # We use a dynamic programming algorithm, but with the
 # added optimization that we only need the last two rows
 # of the matrix.
 previous_row = np.arange(target.size + 1)
 for s in source:
 # Insertion (target grows longer than source):
 current_row = previous_row + 1

 # Substitution or matching:
 # Target and source items are aligned, and either
 # are different (cost of 1), or are the same (cost of 0).
 current_row[1:] = np.minimum(
 current_row[1:],
 np.add(previous_row[:-1], target != s))

 # Deletion (target grows shorter than source):
 current_row[1:] = np.minimum(
 current_row[1:],
 current_row[0:-1] + 1)

 previous_row = current_row

 return previous_row[-1]

def levenshtein6(s, t):
 ''' From Wikipedia article; Iterative with two matrix rows. '''
 if s == t:
 return 0
 elif len(s) == 0:
 return len(t)
 elif len(t) == 0:
 return len(s)
 v0 = [None] * (len(t) + 1)
 v1 = [None] * (len(t) + 1)
 for i in range(len(v0)):
 v0[i] = i
 for i in range(len(s)):
 v1[0] = i + 1
 for j in range(len(t)):
 cost = 0 if s[i] == t[j] else 1
 v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
 for j in range(len(v0)):
 v0[j] = v1[j]

 return v1[len(t)]


for implementation_variant in [g for g in globals() if "leven" in g]:
 print("Try variant %s" % implementation_variant)
 for a, b in [("hamchenoonan", "hamchenin"),
 ("Tier", "Tor")]:
 print(" -Distance of %s and %s is %i" % (a, b, globals()[implementation_variant](a, b)))
</code></pre>

The output shows:

<pre><code>Try variant Mylevenshtein
 -Distance of hamchenoonan and hamchenin is 5
 -Distance of Tier and Tor is 3
Try variant levenshtein1
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein2
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein3
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein5
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
Try variant levenshtein6
 -Distance of hamchenoonan and hamchenin is 4
 -Distance of Tier and Tor is 2
</code></pre>

The distance of Tier and Tor is mentioned in the german wikipedia, just as a second verification. So the democratic answer seems to be 4.

entityMap|blocks|key|9tdg0|text|你的代码是正确的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1l5g4|答案是5，但与注释的顺序不同。|ap44c|hamchenoonan+->++(substitution+%2B2)
+++++++%5E

hamchenionan+->++(delete+%2B1)
++++++++%5E

hamcheninan+->++(delete+%2B1)
+++++++++%5E

hamcheninn+->+(delete+%2B1)
+++++++++%5E

hamchenin|code-block|syntax|javascript|8pjcg|将1.99作为替换成本插入到您的代码中，很明显只进行了一次替换。|aq13t^0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|M|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|N|9|@]|A|@]|B|$]]|$2|E|4|F|6|G|8|O|9|@]|A|@]|B|$H|I]]|$2|J|4|K|6|7|8|P|9|@]|A|@]|B|$]]|$2|L|4|-4|6|7|8|Q|9|@]|A|@]|B|$]]]]

You code is correct.

The answer is 5 but for different sequence than the comment.

<pre><code>hamchenoonan -&gt; (substitution +2)
 ^

hamchenionan -&gt; (delete +1)
 ^

hamcheninan -&gt; (delete +1)
 ^

hamcheninn -&gt; (delete +1)
 ^

hamchenin
</code></pre>

Plug 1.99 as the substitution cost into your code and it's obvious only one substitution is made.

I have written a function which calculates the Levenshtein distance between two given strings. However, it seems that it is not working correctly. substitution cost = 2, insertion cost = 1, deletion cost = 1

<pre><code>def MyLevenshtein(String1, String2):
 if len(String1) and len(String2) != 0:
 rows = len(String1) + 1
 columns = len(String2) + 1
 distance = [[0 for x in range(columns)] for x in range(rows)]
 for i in range(1, rows):
 distance[i][0] = i
 for i in range(1, columns):
 distance[0][i] = i
 for column in range(1, columns):
 for row in range(1, rows):
 if String1[row - 1] == String2[column - 1]:
 cost = 0
 else:
 cost = 2
 distance[row][column] = min(distance[row - 1][column] + 1, # deletion
 distance[row][column - 1] + 1, # insertion
 distance[row - 1][column - 1] + cost) #substitution
 Distance = distance[row][column]
 return Distance
</code></pre>

For example, when I call the function with the strings 'hamchenoonan" and 'hamchenin', 5 is returned, although it should return 7.

calculating the Levenshtein Distance

Python

 我已经写了一个函数来计算两个给定字符串之间的Levenshtein距离。然而，它似乎不能正常工作。替代成本= 2，插入成本= 1，删除成本=1 def MyLevenshtein(String1, String2):    if len(String1) and len(String2) != 0:        r...

问计算Levenshtein距离
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算Levenshtein距离EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算Levenshtein距离
EN