python -regex, соответствующий списку слов

Question

У меня есть скрипт на python, в котором примерно 100 или около того строк регулярных выражений в каждой строке соответствуют определенным словам.

Сценарий, очевидно, потребляет до 100% процессора каждый раз, когда он запускается (я в основном передаю ему предложение, и он возвращает все найденные совпадающие слова).

Я хочу объединить их в 4 или 5 различных «скомпилированных» парсеров регулярных выражений, таких как:

>>> words = ('hello', 'good\-bye', 'red', 'blue')
>>> pattern = re.compile('(' + '|'.join(words) + ')', re.IGNORECASE)

Сколько слов я могу смело использовать в этом, и будет ли это иметь значение? Прямо сейчас, если я запускаю цикл с тысячей случайных предложений, он обрабатывает, возможно, 10 секунд в секунду, пытаясь резко увеличить эту скорость, чтобы она достигала 500 секунд (если это возможно).

Кроме того, возможен ли такой список?

>>> words = ('\d{4,4}\.\d{2,2}\.\d{2,2}', '\d{2,2}\s\d{2,2}\s\d{4,4}\.')
>>> pattern = re.compile('(' + '|'.join(words) + ')', re.IGNORECASE)
>>> print pattern.findall("Today is 2010 11 08)

Answer 1

Ваш алгоритм здесь в основном O(N*M*L) (где N - длина предложения, M - количество слов, которые вы ищете, а L - самое длинное слово, которое вы ищете ) для каждого предложения. Использование регулярных выражений не ускорит это больше, чем просто использование поиска. Единственное, что он дает, - это возможность сопоставлять шаблоны, как во втором примере.

Если вы хотите просто найти слова, Trie будет гораздо лучшим подходом. Реализация тоже очень проста:

TERMINAL = 'TERMINAL' # Marks the end of a word

def build(*words, trie={}):
    for word in words:
        pointer = trie
        for ch in word:
            pt = pt.setdefault(ch, {TERMINAL:False})
        pt[TERMINAL] = True
    return trie

def find(input, trie):
    results = []
    for i in range(len(input)):
        pt = trie
        for j in range(i, len(input)+1):
            if pt[TERMINAL]:
                results.append(input[i:j])
            if j >= len(input) or input[j] not in pt:
                break
            pt = pt[input[j]]
    return results

Это возвращает все слова в вашем предложении, которые находятся в три. Время выполнения - O(N*L), что означает, что вы можете добавить столько слов, сколько хотите, не замедляя алгоритм.