Можно создать дубликат:
Search for string allowing for one mismatch in any location of the string1-несовпадение регулярное выражение
Я дал строку s и строку t. Есть ли регулярное выражение, чтобы найти все вхождения t внутри s с не более одного несоответствующего символа. (Не более одного символа от t разрешено заменять другим.)
I Wouldn» t обязательно делать это с помощью регулярного выражения. Вы можете использовать расстояние Левенштейна.
>>> import Levenshtein
>>> s = "spam ham and eggs"
>>> t = "ram"
>>> for i,_ in enumerate(s):
... s_ = s[i:i+len(t)]
... if Levenshtein.distance(s_, t) == 1:
... print s_
...
pam
ham
звучит субоптимально. Левенштейн будет продолжать отсчет даже после 1 ошибки – mpen
Да, это будет, но расстояние Левенштейна довольно быстро и, возможно, это не критический код производительности. преждевременная оптимизация и все такое. – wim
за исключением того, что в своих комментариях он сказал, что пытался это сделать: http://stackoverflow.com/questions/2420412/search-for-string-allowing-for-one-mismatch-in-any-location-of-the -строка, которая представляет собой довольно большой набор данных. Я не думаю, что это преждевременно. – mpen
Да, абсолютно. Например, если t является "abcde", то один из таких регулярных выражений является
.bcde|a.cde|ab.de|abc.e|abcd.
Тем не менее, это почти наверняка не лучший или самый эффективный способ сделать это, особенно если t это вообще большой. (Если он большой, то вы можете улучшить его производительность несколько переформулировкой как
.bcde|a(?:.cde|b(?:.de|c(?:.e|d.)))
или, возможно, как
a(?:b(?:c(?:d.|.e)|.de)|.cde)|.bcde
, но это все-таки не самый лучший подход.)
Пожалуйста, добавьте некоторые примеры данных, чтобы играть, он делает вещи проще – Robjong
@Robjong: [Это] (http://stackoverflow.com/questions/2420412/search-for-string-allowing-for-one -mismatch-in-any-location-of-the-string) - это то, что я пытаюсь сделать. – Randomblue
Я не эксперт по этому вопросу, но вы можете использовать вариант этого, который допускает до 1 несоответствия: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm – mpen