алгоритм тестирования подстрок с несколькими строками

Question

У меня есть несколько миллионов строк, X, каждая из которых содержит не более 20 слов. У меня также есть список из нескольких тысяч подстрок-кандидатов C. для каждого x в X, я хочу посмотреть, есть ли в C какие-либо строки, содержащиеся в x. Прямо сейчас я использую наивный двойной цикл, но это было давно, и оно еще не закончилось ... Есть предложения? Я использую python, если кто-нибудь знает о хорошей реализации, но ссылки на любой язык или общие алгоритмы тоже подойдут.

Answer 1

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

Answer 2

Это будет длиннее . Вы должны проверить каждую из этих нескольких миллионов строк на каждую из этих нескольких тысяч подстрок-кандидатов, что означает, что вы будете выполнять (несколько миллионов * несколько тысяч) сравнений строк. Да, это займет некоторое время.

Если это то, что вы собираетесь делать только один раз или редко, я бы предложил использовать fgrep. Если это то, что вы собираетесь делать часто, то вы захотите реализовать что-то вроде алгоритма совпадения строк Aho-Corasick .

Answer 3

Посмотрите на http://en.wikipedia.org/wiki/Aho-Corasick.. Вы можете построить сопоставление с образцом для набора фиксированных строк по времени, линейного по общему размеру строк, а затем выполнить поиск по тексту или нескольким разделам текста во времени. линейный по длине текста + количество найденных совпадений.

Другой быстрый точный сопоставитель шаблонов - http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

Answer 4

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

subs=re.compile('|'.join(C))  
for x in X:  
    if subs.search(x):  
        print 'found'  

Answer 5

Если ваш x в X содержит только слова, и вы хотите сопоставлять только слова, вы можете сделать следующее:

Вставить ваши ключевые слова в набор, который делает журнал доступа (n), а затем проверитьдля каждого слова в x, если оно содержится в этом наборе.

вроде:

keywords = set(['bla', 'fubar'])
for w in [x.split(' ') for x in X]:
    if w in keywords:
        pass # do what you need to do

Хорошей альтернативой будет использование библиотеки googles re2, которая использует теорию супер хороших автоматов для создания эффективныхmatchers.(http://code.google.com/p/re2/)

РЕДАКТИРОВАТЬ: Убедитесь, что вы используете правильную буферизацию и что-то на скомпилированном языке, что делает его намного быстрее. Если его размер меньше пары гигабайт, он должен работать и с питоном.