Знайти багато рядків у тексті - Python - python, string

Я шукаю найкращий алгоритм для вирішенняця проблема: маючи список (або dict, a set) малих речень, знайдіть усі входження цих речень у більший текст. Речення в списку (або dict або set) складають близько 600к, але формуються в середньому на 3 слова. Текст в середньому становить 25 слів. Я просто відформатував текст (видаляючи пунктуацію, всі літери та продовжую подібне).

Ось що я спробував (Python):

to_find_sentences = [
"bla bla",
"have a tea",
"hy i m luca",
"i love android",
"i love ios",
.....
]

text = "i love android and i think i will have a tea with john"

def find_sentence(to_find_sentences, text):
text = text.split()
res = []
w = len(text)
for i in range(w):
for j in range(i+1,w+1):
tmp = " ".join(descr[i:j])
if tmp in to_find_sentences:
res.add(tmp)
return res


print find_sentence(to_find_sentence, text)

Вихід:

["i love android", "have a tea"]

У моєму випадку я використовував набір для прискорення роботи in операція

Відповіді:

5 за відповідь № 1

Швидке рішення було б побудувати Trie з ваших пропозицій і перетворити цей код у регулярний вираз. Для вашого прикладу, шаблон буде виглядати наступним чином:

(?:bla bla|h(?:ave a tea|y i m luca)|i love (?:android|ios))

Ось ан приклад на debuggex:

Можливо, це доцільно додати "b" як кордони слова, щоб уникнути відповідності "have a team".

Вам потрібен маленький Сценарій Trie. Це ще не офіційний пакет, але ви можете просто завантажити його тут як trie.py у вашому поточному каталозі.

Потім ви можете використовувати цей код, щоб створити trie / regex:

import re
from trie import Trie

to_find_sentences = [
"bla bla",
"have a tea",
"hy i m luca",
"i love android",
"i love ios",
]

trie = Trie()
for sentence in to_find_sentences:
trie.add(sentence)

print(trie.pattern())
# (?:bla bla|h(?:ave a tea|y i m luca)|i love (?:android|ios))

pattern = re.compile(r"b" + trie.pattern() + r"b", re.IGNORECASE)
text = "i love android and i think i will have a tea with john"

print(re.findall(pattern, text))
# ["i love android", "have a tea"]

Ви інвестуєте деякий час, щоб створити Trie і регулярний вираз, але обробка повинна бути надзвичайно швидкою.

Ось а Відповідна відповідь (прискорити мільйони заміни регулярних виразів у Python 3) якщо ви хочете отримати більше інформації.

Зауважте, що не знайдено суперечливих речень:

to_find_sentences = [
"i love android",
"android Marshmallow"
]
# ...
print(re.findall(pattern, "I love android Marshmallow"))
# ["I love android"]

Вам доведеться модифікувати регулярний вираз з позитивними оглядовими накладами, щоб знайти суперечливі речення.

---