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