Каков наиболее эффективный способ найти одну из нескольких подстрок в Python?

У меня есть список возможных подстрок, например ['cat', 'fish', 'dog']. На практике список содержит сотни записей.

Я обрабатываю строку, и я ищу, чтобы найти индекс первого появления любой из этих подстрок.

Чтобы уточнить, для '012cat' результат равен 3, а для '0123dog789cat' результат равен 4.

Мне также нужно знать, какая подстрока была найдена (например, ее индекс в списке подстрок или сам текст), или, по крайней мере, длину подстроки.

Есть очевидные способы грубой силы для достижения этого, я задавался вопросом, есть ли какое-нибудь изящное решение Python / Regex для этого.

Спасибо, Rax

6 Solutions collect form web for “Каков наиболее эффективный способ найти одну из нескольких подстрок в Python?”

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

Итак, вот пример:

import re def work(): to_find = re.compile("cat|fish|dog") search_str = "blah fish cat dog haha" match_obj = to_find.search(search_str) the_index = match_obj.start() # produces 5, the index of fish which_word_matched = match_obj.group() # "fish" # Note, if no match, match_obj is None 

ОБНОВЛЕНИЕ: Следует соблюдать осторожность при объединении слов в один образец альтернативных слов. Следующий код создает регулярное выражение, но избегает любых специальных символов регулярных выражений и сортирует слова, чтобы более длинные слова имели возможность сопоставляться перед любыми более короткими префиксами одного и того же слова:

 def wordlist_to_regex(words): escaped = map(re.escape, words) combined = '|'.join(sorted(escaped, key=len, reverse=True)) return re.compile(combined) >>> r.search('smash atomic particles').span() (6, 10) >>> r.search('visit usenet:comp.lang.python today').span() (13, 29) >>> r.search('a north\south division').span() (2, 13) >>> r.search('012cat').span() (3, 6) >>> r.search('0123dog789cat').span() (4, 7) 

END UPDATE

Следует отметить, что вы захотите сформировать регулярное выражение (т.е. – call to re.compile ()) как можно меньше. Лучшим случаем было бы знать заранее, что ваши поиски (или вы их вычисляете один раз / нечасто), а затем сохраняете результат re.compile где-то. Мой пример – просто простая бессмысленная функция, поэтому вы можете увидеть использование регулярного выражения. Здесь есть еще несколько регулярных документов:

http://docs.python.org/library/re.html

Надеюсь это поможет.

UPDATE: я не уверен, как python реализует регулярные выражения, но чтобы ответить на вопрос Rax о том, существуют ли ограничения re.compile () (например, сколько слов вы можете попытаться «|» вместе совместить сразу) , и количество времени для запуска компиляции: ни одна из них, похоже, не является проблемой. Я пробовал этот код, который достаточно хорош, чтобы убедить меня. (Я мог бы сделать это лучше, добавив время и результаты отчетов, а также бросив список слов в набор, чтобы убедиться, что дубликатов нет … но оба этих улучшения кажутся излишними). Этот код выполнялся в основном мгновенно, и убедил меня, что я могу найти 2000 слов (размером 10), и что они будут соответствовать соответствующим образом. Вот код:

 import random import re import string import sys def main(args): words = [] letters_and_digits = "%s%s" % (string.letters, string.digits) for i in range(2000): chars = [] for j in range(10): chars.append(random.choice(letters_and_digits)) words.append(("%s"*10) % tuple(chars)) search_for = re.compile("|".join(words)) first, middle, last = words[0], words[len(words) / 2], words[-1] search_string = "%s, %s, %s" % (last, middle, first) match_obj = search_for.search(search_string) if match_obj is None: print "Ahhhg" return index = match_obj.start() which = match_obj.group() if index != 0: print "ahhhg" return if words[-1] != which: print "ahhg" return print "success!!! Generated 2000 random words, compiled re, and was able to perform matches." if __name__ == "__main__": main(sys.argv) 

ОБНОВЛЕНИЕ: Следует отметить, что порядок вещей ORed вместе в регулярном выражении имеет значение . Взгляните на следующий тест, вдохновленный TZOTZIOY :

 >>> search_str = "01catdog" >>> test1 = re.compile("cat|catdog") >>> match1 = test1.search(search_str) >>> match1.group() 'cat' >>> match1.start() 2 >>> test2 = re.compile("catdog|cat") # reverse order >>> match2 = test2.search(search_str) >>> match2.group() 'catdog' >>> match2.start() 2 

Это говорит о том, что порядок имеет значение: – /. Я не уверен, что это означает для приложения Rax, но, по крайней мере, поведение известно.

ОБНОВЛЕНИЕ: Я разместил эти вопросы о реализации регулярных выражений в Python, которые, мы надеемся, дадут нам некоторое представление о проблемах, обнаруженных с этим вопросом.

 subs = ['cat', 'fish', 'dog'] sentences = ['0123dog789cat'] import re subs = re.compile("|".join(subs)) def search(): for sentence in sentences: result = subs.search(sentence) if result != None: return (result.group(), result.span()[0]) # ('dog', 4) 

Я просто хочу указать разницу во времени между ответом DisplacedAussie и ответом Тома. Оба были быстрыми, когда они использовались один раз, поэтому у вас тоже не должно быть заметного ожидания, но когда вы их время:

 import random import re import string words = [] letters_and_digits = "%s%s" % (string.letters, string.digits) for i in range(2000): chars = [] for j in range(10): chars.append(random.choice(letters_and_digits)) words.append(("%s"*10) % tuple(chars)) search_for = re.compile("|".join(words)) first, middle, last = words[0], words[len(words) / 2], words[-1] search_string = "%s, %s, %s" % (last, middle, first) def _search(): match_obj = search_for.search(search_string) # Note, if no match, match_obj is None if match_obj is not None: return (match_obj.start(), match_obj.group()) def _map(): search_for = search_for.pattern.split("|") found = map(lambda x: (search_string.index(x), x), filter(lambda x: x in search_string, search_for)) if found: return min(found, key=lambda x: x[0]) if __name__ == '__main__': from timeit import Timer t = Timer("_search(search_for, search_string)", "from __main__ import _search, search_for, search_string") print _search(search_for, search_string) print t.timeit() t = Timer("_map(search_for, search_string)", "from __main__ import _map, search_for, search_string") print _map(search_for, search_string) print t.timeit() 

Выходы:

 (0, '841EzpjttV') 14.3660159111 (0, '841EzpjttV') # I couldn't wait this long 

Я бы пошел с ответом Тома, как на читаемость, так и на скорость.

Это неопределенный теоретический ответ без кода, но я надеюсь, что он может указать вам в правильном направлении.

Во-первых, вам понадобится более эффективный поиск списка подстрок. Я бы рекомендовал какую-то древовидную структуру. Начните с корня, затем добавьте узел 'a' если любые подстроки начинаются с 'a' , добавьте узел 'b' если любые подстроки начинаются с 'b' и т. Д. Для каждого из этих узлов продолжайте добавлять подузлы.

Например, если у вас есть подстрока со словом «ant», у вас должен быть корневой узел, дочерний узел 'a' , узел внука 'n' и узел великого внука 't' .

Узлы должны быть достаточно легкими.

 class Node(object): children = [] def __init__(self, name): self.name = name 

где name – символ.

Итерации через ваши строки буквой. Следите за тем, какое письмо вы находитесь. В каждой букве попробуйте использовать следующие несколько букв, чтобы пересечь дерево. Если вы успешны, ваш номер письма будет позицией подстроки, и ваш ордер на обход укажет найденную подстроку.

Уточняющее редактирование: DFA должны быть намного быстрее, чем этот метод, и поэтому я должен одобрить ответ Тома . Я сохраняю этот ответ только в том случае, если ваш список подстрок изменяется часто, и в этом случае использование дерева может быть быстрее.

Прежде всего, я предлагаю вам отсортировать начальный список в порядке возрастания. Поскольку сканирование для более короткой подстроки выполняется быстрее, для сканирования более длинной подстроки.

Как насчет этого.

 >>> substrings = ['cat', 'fish', 'dog'] >>> _string = '0123dog789cat' >>> found = map(lambda x: (_string.index(x), x), filter(lambda x: x in _string, substrings)) [(10, 'cat'), (4, 'dog')] >>> if found: >>> min(found, key=lambda x: x[0]) (4, 'dog') 

Очевидно, вы могли бы вернуть что-то другое, кроме кортежа.

Это работает:

  • Фильтрация списка подстрок до тех, которые находятся в строке
  • Построение списка кортежей, содержащих индекс подстроки, и подстроку
  • Если подстрока найдена, найдите минимальное значение, основанное на индексе
  • Регулярное выражение Python для извлечения части строки
  • Regex для соответствия Domain.CCTLD
  • Как преобразовать некоторый символ в пятизначный unicode в Python 3.3?
  • Строковое манипулирование с помощью обычного выражения или выражений
  • регулярное выражение python с проблемой utf8
  • Как подстроить строку?
  • Проверьте CSV на данный формат
  • python: шаблон поиска регулярных выражений для двоичных файлов (половина байта)
  • Соответствие букв на любом языке
  • Могу ли я иметь не-жадное регулярное выражение с dotall?
  • Как заполнить строку регулярных выражений параметрами
  •  
    Interesting Posts for Van-Lav

    Хеширование файла в Python

    DatabaseError: таблица OmniCloud_App_user не имеет имени с именем пользователя

    QDialog не открывается из главного окна (pyQt)

    ТипNotFound: Тип не найден: (схема, http://www.w3.org/2001/XMLSchema,)

    Как использовать переменные в регулярном выражении Python

    Запись в файлы Python только для файлов gzipped

    Получите все документы RavenDB для документов коллекции для модификации «для каждого документа»

    Зачем мне нужно импортировать класс внутри этого класса, а не вверху файла?

    Python, В linux получить спецификации VGA через lspci или HAL?

    Показать последовательные изображения / массивы с imshow как повторяющиеся анимации в python

    Установите lxml в качестве парсера BeautifulSoup по умолчанию

    Python – найти наибольшее число в списке чисел

    Можно ли создать матрицу размером 1 миллион x 1 миллион, используя numpy?

    Предсказание того, как долго будет проводиться классификация scikit-learn

    import matplotlib.pyplot зависает

    Python - лучший язык программирования в мире.