Алгоритм сопоставления строк: (многотонные строки)

Question

У меня есть словарь, который содержит большое количество строк. Каждая строка может иметь диапазон от 1 до 4 токенов (слов). Пример:

Словарь:

1. Побег из Шоушенка
2. Крестный отец \
3. Pulp Fiction
4. The Dark Knight
5. Бойцовский клуб

Теперь у меня есть пункт и мне нужно выяснить, сколько строк в параграфе являются частью словаря. Пример, когда пункт ниже:

Побег из Шоушенка считается величайшим фильм когда-либо сделанных в соответствии с IMDB Top 250.For по крайней мере год или два, что я иногда проверял в на IMDB Top 250 The Shawshank Redemption был battling The Godfather для верхнего пятна.

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

Как я могу это сделать с наименьшими словарными вызовами.

Благодаря

Answer 1

Вы могли бы быть лучше использовать Trie. Trie лучше подходит для поиска частичных совпадений (т. Е. При поиске по тексту абзаца), которые потенциально вы ищете, в отличие от создания кучи вызовов в словаре, которые в большинстве случаев терпят неудачу.

Причина, почему я думаю, что Trie (или изменения) подходит потому, что он построен, чтобы делать то, что вы пытаетесь сделать:

Если вы используете эту (или некоторые модификации который имеет обозначенные слова на каждом узле вместо буквы), это было бы наиболее эффективным (по крайней мере, я знаю) с точки зрения хранения и поиска; Хранение, потому что вместо того, чтобы хранить слово «The» пару тысяч раз в каждой записи Dict, которая имеет это слово в названии (как в случае с названиями фильмов), она будет храниться один раз в одном из узлов прямо под корнем. Следующее слово «Shawshank» будет находиться в дочернем узле, а затем «выкуп» будет в следующем, и в общей сложности три поиска; то вы перейдете к следующей фразе. Если он терпит неудачу, то есть фраза - это только «Shawshank Looper», тогда вы терпите неудачу после тех же трех поисков, и вы переходите к сломанному слову, Looper (который, как это бывает, также будет дочерним узлом под корнем, и вы получаете удар. Это решение работает, если вы читаете абзац без названий фильмов mashup).

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

Answer 2

В Python:

import re 

movies={1:'The Shawshank Redemption', 2:'The Godfather', 3:'Pretty Woman', 4:'Pulp Fiction'} 

text = 'The Shawshank Redemption considered the greatest movie ever made according to the IMDB Top 250.For at least the year or two that I have occasionally been checking in on the IMDB Top 250 The Shawshank Redemption has been battling The Godfather for the top spot.' 

repl_str ='(?P<title>' + '|'.join(['(?:%s)' %movie for movie in movies.values()]) + ')' 

result = re.sub(repl_str, '<b>\g<title></b>',text) 

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

лай

Answer 3

Это не полный ответ, больше как продлен комментарий.

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

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

Я могу себе представить, как Rabin-Karp с функциями прокатки и некоторыми фильтрами (фильтр Bloom) можно использовать для ускорения процесса. Например, вместо фактического соответствия подстрок вы можете сначала фильтровать (например, со слабыми хэшами), а затем фактически проверять, тем самым уменьшая количество необходимых проверок. Плюс это должно уменьшить работу, выполненную с помощью самого оригинального словаря, так как вы сохраните его хэши или другие фильтры.