Получить близкие совпадения строк с учетом удаления - python

Question

Есть ли способ позволить difflib рассмотреть удаление при сопоставлении строк?

Я попробовал difflib.get_close_matches() но он не учитывает строки с меньшей длиной в результатах близких совпадений. Например

from difflib import get_close_matches as gcm

x = """Erfreulich
Erfreuliche
Erfreulicher
Erfreulicherem
Erfreulicheres
Erfreulicherweis
Erfreulicherweise
Erfreuliches
Erfreulichste"""

x = [i for i in x.split("\n")]

for i in x:
  print i, gcm(i,x)

Выход:

Erfreulich ['Erfreulich', 'Erfreuliche', 'Erfreuliches']
Erfreuliche ['Erfreuliche', 'Erfreuliches', 'Erfreulicher']
Erfreulicher ['Erfreulicher', 'Erfreuliche', 'Erfreulicheres']
Erfreulicherem ['Erfreulicherem', 'Erfreulicheres', 'Erfreulicher']
Erfreulicheres ['Erfreulicheres', 'Erfreulicherweis', 'Erfreulicherem']
Erfreulicherweis ['Erfreulicherweis', 'Erfreulicherweise', 'Erfreulicheres']
Erfreulicherweise ['Erfreulicherweise', 'Erfreulicherweis', 'Erfreulicheres']
Erfreuliches ['Erfreuliches', 'Erfreuliche', 'Erfreulicheres']
Erfreulichste ['Erfreulichste', 'Erfreuliche', 'Erfreuliches']

Обратите внимание, что для строки Erfreulicher , Erfreulich не считается близким совпадением, хотя расстояние составляет всего -1.

Answer 1

Из документации, n Параметр может быть увеличен, чтобы получить больше совпадений. Некоторые слова короче, поэтому difflib считает удаление.

difflib.get_close_matches (слово, возможности [, n][, срез])
Вернуть список лучших "достаточно хороших" матчей. слово - это последовательность, для которой требуется близкое совпадение (обычно это строка), а возможность - это список последовательностей, с которыми сопоставляется слово (обычно это список строк).

Необязательный аргумент n (по умолчанию 3) - максимальное количество близких совпадений для возврата; n должно быть больше 0.

Необязательный аргумент cutoff (по умолчанию 0,6) является плавающей точкой в ​​диапазоне [0, 1]. Возможности, которые не оценивают, по крайней мере, как слово, игнорируются.

Лучшие (не более n) совпадений среди возможностей возвращаются в списке, отсортированном по показателю сходства, сначала наиболее похожему.

Здесь то же самое слово с gcm(i,x,6):

Erfreulicher ['Erfreulicher', 'Erfreuliche', 'Erfreulicheres', 'Erfreulicherem',
              'Erfreuliches', 'Erfreulich']

Answer 2

Вы должны принять ответ Марка Толонена - он читает документы;-)

Для более глубокого понимания, обратите внимание, что difflibПонятие сходства не имеет ничего общего с расстоянием редактирования Левенштейна, но, возможно, это то, что вы действительно хотите. Когда ты сказал:

Обратите внимание, что для строки Erfreulicher Erfreulich не считается близким совпадением, хотя расстояние составляет всего -1.

Я понятия не имею, что вы понимаете под понятием "расстояние". Строки отличаются на 2 символа, верно? "-1" загадочно.

difflib вычисляет "показатель сходства", который представляет собой число в диапазоне от 0,0 до 1,0. Вот как можно увидеть, что он делает внутри, используя свой список x:

import difflib
s = difflib.SequenceMatcher()
s.set_seq2("Erfreulicher")
full = []
for i in x:
    s.set_seq1(i)
    full.append((s.ratio(), i))
full.sort(reverse=True)
for score, i in full:
    print "{:20} {:.3f}".format(i, score)

Вот результат, отсортированный от наивысшего показателя сходства к наименьшему:

Erfreulicher         1.000
Erfreuliche          0.957
Erfreulicheres       0.923
Erfreulicherem       0.923
Erfreuliches         0.917
Erfreulich           0.909
Erfreulichste        0.880
Erfreulicherweis     0.857
Erfreulicherweise    0.828

Как говорят документы, по умолчанию get_close_matches() возвращает только верхний 3. Конкретное слово, о котором вы спрашиваете, оказывается шестым в списке и будет возвращено, если вы скажете функции возвращать 6 лучших (или 7 и т. д.) совпадений (см. ответ Марка).

Как вычисляется оценка, также задокументировано. Поскольку "Erfreulich" является префиксом "Erfreulicher", он сокращается до:

>>> 2.0 * len("Erfreulich") / (len("Erfreulich") + len("Erfreulicher"))
0.9090909090909091

Все строки над "Erfreulich" в списке имеют как минимум еще один общий символ, что увеличивает числитель. Знаменатель также больше для них, но увеличение числителя на (скажем) 1 оказывает большее влияние на результат, чем увеличение знаменателя на 1. Это может или не может соответствовать вашей интуиции, но это то, как это работает;-)

Answer 3

Я не разработчик Pyton, но, похоже, вам нужно вычислить левенштейновские расстояния между строками. Из вики:

расстояние Левенштейна между двумя словами - это минимальное количество односимвольных правок (вставка, удаление, замена), необходимых для замены одного слова на другое.

Если вы вычисляете расстояние от каждого слова до каждого слова, вы всегда можете получить самые близкие совпадения, основываясь на том, что вы определяете как "близко". Теперь, как я уже сказал, я не разработчик Pyton, поэтому я не могу помочь вам в реализации для конкретного языка, но я нашел пакет python-levenshtein.