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

Ответ 1

Я бы предположил, что регулярное выражение лучше, чем проверка для каждой подстроки индивидуально, потому что концептуально регулярное выражение моделируется как 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

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

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, которые, мы надеемся, дадут нам некоторое представление о проблемах, обнаруженных с помощью этот вопрос.

Ответ 2

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)

Ответ 3

Я просто хочу указать разницу во времени между ответом 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

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

Ответ 4

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

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

Например, если у вас есть подстрока со словом "ant", вы должны иметь root node, дочерний node 'a', внук node 'n' и отличный внук node 't'.

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

class Node(object):
    children = []

    def __init__(self, name):
        self.name = name

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

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

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

Ответ 5

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

Ответ 6

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

>>> 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')

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

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

• Фильтрация списка подстрок до тех, что находятся в строке
• Построение списка кортежей, содержащих индекс подстроки, и подстроку
• Если подстрока найдена, найдите минимальное значение на основе индекса