1# fix-header: skip 2 3# http://hetland.org/coding/python/levenshtein.py 4 5# This is a straightforward implementation of a well-known algorithm, and thus 6# probably shouldn't be covered by copyright to begin with. But in case it is, 7# the author (Magnus Lie Hetland) has, to the extent possible under law, 8# dedicated all copyright and related and neighboring rights to this software 9# to the public domain worldwide, by distributing it under the CC0 license, 10# version 1.0. This software is distributed without any warranty. For more 11# information, see <http://creativecommons.org/publicdomain/zero/1.0> 12 13 14def astrcmp_py(a, b): 15 """Calculates the Levenshtein distance between a and b.""" 16 n, m = len(a), len(b) 17 if n > m: 18 # Make sure n <= m, to use O(min(n,m)) space 19 a, b = b, a 20 n, m = m, n 21 22 if n == 0 or m == 0.0: 23 return 0.0 24 25 current = range(n+1) 26 for i in range(1, m+1): 27 previous, current = current, [i]+[0]*n 28 for j in range(1, n+1): 29 add, delete = previous[j]+1, current[j-1]+1 30 change = previous[j-1] 31 if a[j-1] != b[i-1]: 32 change = change + 1 33 current[j] = min(add, delete, change) 34 35 return 1.0 - current[n] / max(m, n) 36 37 38try: 39 from picard.util._astrcmp import astrcmp as astrcmp_c 40 astrcmp = astrcmp_c 41 astrcmp_implementation = "C" 42except ImportError: 43 astrcmp = astrcmp_py 44 astrcmp_implementation = "Python" 45