2

Are there some edit-distance in python that take account of the accent. Where for exemple hold the following property

d('ab', 'ac') > d('àb', 'ab') > 0
4

3 回答 3

6

使用Levenshtein 模块：

In [1]: import unicodedata, string

In [2]: from Levenshtein import distance

In [3]: def remove_accents(data):
   ...:     return ''.join(x for x in unicodedata.normalize('NFKD', data)
   ...:                             if x in string.ascii_letters).lower()

In [4]: def norm_dist(s1, s2):
   ...:     norm1, norm2 = remove_accents(s1), remove_accents(s2)
   ...:     d1, d2 = distance(s1, s2), distance(norm1, norm2)
   ...:     return (d1+d2)/2.

In [5]: norm_dist(u'ab', u'ac')
Out[5]: 1.0

In [6]: norm_dist(u'àb', u'ab')
Out[6]: 0.5
于 2013-04-03T15:21:47.773 回答
3

Unicode 允许将重音字符分解为基本字符和组合重音字符；例如à分解成a后跟重音组合。

您想使用规范化形式 NFKD 转换两个字符串，它分解重音字符并将兼容性字符转换为其规范形式，然后使用编辑距离度量将替换排在插入和删除之上。

于 2013-04-03T15:24:02.007 回答
1

这是一个基于difflib和unicodedata的解决方案，没有任何依赖关系：

import unicodedata
from difflib import Differ

# function taken from https://stackoverflow.com/a/517974/1222951
def remove_accents(input_str):
    nfkd_form = unicodedata.normalize('NFKD', input_str)
    only_ascii = nfkd_form.encode('ASCII', 'ignore').decode()
    return only_ascii

def compare(wrong, right):
    # normalize both strings to make sure equivalent (but
    # different) unicode characters are canonicalized 
    wrong = unicodedata.normalize('NFKC', wrong)
    right = unicodedata.normalize('NFKC', right)

    num_diffs = 0
    index = 0
    differences = list(Differ().compare(wrong, right))
    while True:
        try:
            diff = differences[index]
        except IndexError:
            break

        # diff is a string like "+ a" (meaning the character "a" was inserted)
        # extract the operation and the character
        op = diff[0]
        char = diff[-1]

        # if the character isn't equal in both
        # strings, increase the difference counter
        if op != ' ':
            num_diffs += 1

        # if a character is wrong, there will be two operations: one
        # "+" and one "-" operation
        # we want to count this as a single mistake, not as two mistakes
        if op in '+-':
            try:
                next_diff = differences[index+1]
            except IndexError:
                pass
            else:
                next_op = next_diff[0]
                if next_op in '+-' and next_op != op:
                    # skip the next operation, we don't want to count
                    # it as another mistake
                    index += 1

                    # we know that the character is wrong, but
                    # how wrong is it?
                    # if the only difference is the accent, it's
                    # a minor mistake
                    next_char = next_diff[-1]
                    if remove_accents(char) == remove_accents(next_char):
                        num_diffs -= 0.5

        index += 1

    # output the difference as a ratio of
    # (# of wrong characters) / (length of longest input string)
    return num_diffs / max(len(wrong), len(right))

测试：

for w, r in (('ab','ac'),
            ('àb','ab'),
            ('être','etre'),
            ('très','trés'),
            ):
    print('"{}" and "{}": {}% difference'.format(w, r, compare(w, r)*100))

"ab" and "ac": 50.0% difference
"àb" and "ab": 25.0% difference
"être" and "etre": 12.5% difference
"très" and "trés": 12.5% difference
于 2017-08-13T16:27:18.390 回答