Как определить наиболее близкое соответствие шаблону регулярных выражений - PullRequest
Новая
       42

Как определить наиболее близкое соответствие шаблону регулярных выражений

2 голосов
/ 07 ноября 2019

Допустим, у меня есть следующий список: 

abc_Pickled_efg
abc_Pickller_efg
abcd_something_Picklesefgh
efg_Pickles_abc

И шаблон регулярного выражения: 

abc.*Pickles.*efg

Ни один из них в списке не соответствует шаблону. Но как мне найти наиболее близкое совпадение (в данном случае abc_Pickled_efg). Есть ли какой-нибудь модуль Python или что-то, что может сказать, если что-то соответствует 92% или 0% или что-то в этом роде?

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

a  => a = 1 point
b  => b = 1 point
c  => c = 1 point
.* => _ = 1 point
P  => P = 1 point
i  => i = 1 point
c  => c = 1 point
k  => k = 1 point
l  => l = 1 point
e  => e = 1 point
r  => d = 0 point
.* => _ = 1 point
e  => e = 1 point
f  => f = 1 point
g  => g = 1 point
-----------------
         14 points out of 15 possible ~= 93% match

Имеет ли это смысл или что-то подобное?

1 Ответ

1 голос
/ 07 ноября 2019

Как это можно сделать в регулярном выражении?

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

В терминах регулярного выражения вы должны использовать следующее (очевидно, если указанное вами в вашем вопросе регулярное выражение задано заранее, вы можете объединить его;prepend (?: и append ){e}): 

(?:abc.*Pickles.*efg){e}

В приведенном выше регулярном выражении {e} допускает любой тип ошибки (удаление, вставка, замена) при сопоставлении строки. Вы можете изменить это по своему вкусу, некоторые примеры перечислены ниже (многие скопированы по ссылке, указанной в первом абзаце):

  • {d} только удаление
  • {d,i} удалениеи только вставка
  • {d,s,i} удаление, замена или вставка (аналогично {e}) - порядок не имеет значения
  • {e<=3} допускает не более 3 ошибок
  • {i<3} разрешить менее 3 вставок
  • {1<=e<3} разрешить не менее 1 ошибки, но менее 3 ошибок
  • {1<=2,d>2} разрешить не более 2 вставок, разрешить не менее 2 удалений
  • {2i+d2+1s<=4} каждая вставка стоит 2, каждое удаление стоит 2, каждая замена стоит 1, общая стоимость не должна превышать 4
  • {i<=1,d<=1,s<=1,2i+2d+1s<=4} не более 1 вставки, не более 1 удаления, не более 1замещение;каждая вставка стоит 2, каждое удаление стоит 2, каждая замена стоит 1, общая стоимость не должна превышать 4

Как выглядит ее реализация?

Теперь, когда выиметь представление о том, что это такое и как это работает, мы можем перейти к фактической реализации. Приведенный ниже код использует в вычислениях модуль регулярных выражений fuzzy_counts, чтобы определить лучшую строку на основе ее оценки. Мой расчет преобразуется в процент и работает следующим образом (вы можете изменить его по своему вкусу и, в сочетании с информацией выше, изменить оценки для каждого типа ошибок, с которыми сталкивается регулярное выражение): 

# 100 * (1 - (fuzziness/length of original string))
100*(1 - (n/len(s)))

Смотрите этот код, работающий здесь

Примечание: я использовал pprint, чтобы красиво отобразить вывод;нет необходимости использовать его, просто облегчает чтение результатов. 

import regex, pprint

strings = [
    "abc_Pickled_efg",
    "abc_Pickller_efg",
    "abcd_something_Picklesefgh",
    "efg_Pickles_abc"
]

r = r'(?:abc.*Pickles.*efg){e}'
matches = []

for i,s in enumerate(strings):
    x = regex.fullmatch(r,s, regex.BESTMATCH)   # match result
    n = sum(x.fuzzy_counts)             # fuzziness
    c = 100*(1 - (n/len(s)))            # closeness
    matches.append(c)

result = sorted(zip(strings, matches),key=lambda x: x[1],reverse=True)

pp = pprint.PrettyPrinter(indent=4)
pp.pprint(result)

И результат: 

[   ('abcd_something_Picklesefgh', 96.15384615384616),
    ('abc_Pickled_efg', 93.33333333333333),
    ('abc_Pickller_efg', 87.5),
    ('efg_Pickles_abc', 60.0)]
...