Редактировать Расстояние с акцентом

Question

Есть ли какое-то расстояние редактирования в python, учитывающее акцент. Где для Exemple провести следующее свойство

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

Answer 1

С Levenshtein module:

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 

Answer 2

Юникода позволяет разложение символов с диакритическими знаками в базовый символ плюс комбинационной акцента характера; например à разлагается на a, за которым следует сложный серьезный акцент.

Вы хотите преобразовать обе строки, используя форму нормировки NFKD, которая разлагает акцентированные символы и преобразует символы совместимости в их канонические формы, а затем использует метрику расстояния редактирования, которая ранжирует замены над вставками и удалениями.

Answer 3

Вот решение, основанное на 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