Trie или префиксное дерево хорошо подходит для решения задачи. Это дерево для набора строк. В корне хранится dict
со всеми возможными первыми символами строк. В узлах внутри тоже хранятся словари с буквами, которыми можно продолжить строку. Признак конца строки - пустой ключ в словаре. Пример:
import pprint
def make_trie(iterable):
root = {}
for s in iterable:
node = root
for c in s:
node = node.setdefault(c, {})
node[''] = None
return root
pprint.pprint(make_trie(('then', 'than', 'thing', 'those')))
{'t': {'h': {'a': {'n': {'': None}},
'e': {'n': {'': None}},
'i': {'n': {'g': {'': None}}},
'o': {'s': {'e': {'': None}}}}}}
С помощью префиксного дерева можно проверить, что данный текст содержит какое-нибудь слово из дерева.
Например, чтобы проверить что строка есть в дереве, будем брать из неё символы по одному и спускаться по дереву:
s = ... # строка которую ищем в дереве
node = root # корень префиксного дерева
for c in s: # символ за символом ...
node = node[c] # ... спускаемся по дереву
Если очередного символа в узле не оказалось, то строки в дереве нет. Если последний узел содержит ключ '', то строка в дереве есть.
Так как нам надо проверять не только начало текста, но и любое место внутри, то будем поддерживать список узлов, которые действительны на данном символе. С каждым новым символом текста список пополняется новым элементом - корнем дерева. Все узлы, которые не соответствуют очередному символу из списка удаляются. Чтобы эти операции были быстрыми приходится работать с индексами, что не привычно для Питона:
def contains(text, trie):
if '' in trie:
return True
nodes = []
for c in text:
nodes.append(trie) # анализируем строку, которая начинается на этом символе
i = 0
while i < len(nodes):
node = nodes[i]
if c in node:
# спуск по дереву
node = node[c]
nodes[i] = node
if '' in node: # признак конца строки в trie
return True
i += 1
else:
# удаляем узел из списка
nodes[i] = nodes[-1]
nodes.pop()
return False
Для проверки эффективности trie были изготовлены тестовые данные. Скрипт generate_sample.py готовит файл со строками для поиска (50'000 строк от 10 до 20 символов) ...
...
uctufrxhfomiuwrhvkyy
hbzkmicgsw
gupmuoeiehxrrix
nsmlheqpcybdeufzvnt
mmtoqiravxd
...
... и текст в котором они ищутся (20'000 строк длиной от 20 до 100 символов) ...
...
oeosbugxnbfvqgfonutgbzrmmuzumrglpphrqritsiwavmwfvdamrlvulfjswnuzsrhikfybbzxajlfxwhtt
qizjtyarlbiwnstvtmrqqomblafkhmvwtiocelcyczobausadcudkzykcgyzwajxzkbdwytlnxdqxxycgsdwsyqtn
xtwlvjyxcisvvbvacljxzmdjrhsueyjffdd
wyctzgitvbzroiiquohbfostrsvvrorslfevbyhrxqadpytrswk
fwxeyfmkqavccxgjrtjsikpazaajpknqiizbpbweublcowani
...
В текст с некоторой вероятностью вставлены слова из словаря, чтобы иногда что-то находилось.
Оригинальный поиск на этих данных выполняется 112 секунд. baseline.py:
with open('patterns.txt') as f:
patterns = tuple(line.replace('\n','') for line in f)
with open('corpus.txt') as f:
for line in f:
for p in patterns:
if p in line:
print(line, end='')
break
Поиск с помощью trie
около двух секунд. trie.py:
def make_trie(iterable):
...
def contains(text, trie):
...
with open('patterns.txt') as f:
trie = make_trie(line.replace('\n', '') for line in f)
with open('corpus.txt') as f:
for line in f:
line = line.replace('\n','')
if contains(line, trie):
print(line)
Так как обработка посимвольная, то Питон не лучший кандидат для быстрого решения. Решение на C или C++ должно работать быстрее раз в 10-20 если не больше.
linesB
из списка строк в список множеств слов. Тогда проверкаif lineA in y
будет выполняться моментально. Возможно, это даст нужное ускорение.linesB
, сразу конструировать из строки множество слов и проверять его на пересечение с множествомlinesA