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

Ответ 1

введите 10 000 слов в хэш-таблицу, затем проверьте каждое из слов в блоке текста, если в его хеше есть запись.

Быстрее, хотя я не знаю, просто другой метод (будет зависеть от того, сколько слов вы ищете).

простой пример perl:

my $word_block = "the guy went afk after being popped by a brownrabbit";
my %hash = ();
my @words = split /\s/, $word_block;
while(<DATA>) { chomp; $hash{$_} = 1; }
foreach $word (@words)
{
    print "found word: $word\n" if exists $hash{$word};
}

__DATA__
afk
lol
brownrabbit
popped
garbage
trash
sitdown

Ответ 2

Попробуйте алгоритм Aho-Corasick: http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

Ответ 3

Ответ в значительной степени зависит от реальных требований.

• Насколько велик список слов?
• Насколько велико текстовый блок?
• Сколько текстовых блоков необходимо обработать?
• Как часто должен обрабатываться каждый текстовый блок?
• Изменились ли текстовые блоки или список слов? Если, как часто?

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

Если вам приходится обрабатывать текстовые блоки несколько раз, я предлагаю инвертировать текстовые блоки. Инвертирование текстового блока означает создание списка для каждого слова, содержащего все текстовые блоки, содержащие конкретное слово.

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

Ответ 4

Создайте trie ваших слов, а затем используйте это, чтобы найти, какие слова находятся в тексте.

Ответ 5

вы можете построить граф, используемый как конечный автомат, и когда вы обрабатываете i-й символ вашего входного слова - Ci - вы пытаетесь перейти на i-й уровень своего графика, проверив, был ли предыдущий node, связанный с Ci -1, имеет дочерний элемент node, связанный с Ci

ex: если в вашем корпусе есть следующие слова: ( "искусство", "есть", "быть", "пчела" )
у вас будут следующие узлы в вашем графике
n11 = 'a'
n21 = 'r'
n11.sons = (n21)
n31 = 'e'
n32 = 't'
n21.sons = (n31, n32)
n41 = 'art' (здесь у нас есть лист в нашем графе, а слово build из всех верхних узлов связано с этим node)
n31.sons = (n41)
n42 = 'are' (здесь снова мы имеем слово)
n32.sons = (n42)
n12 = 'b'
n22 = 'e'
n12.sons = (n22)
n33 = 'e'
n34 = 'be' (слово)
n22.sons = (n33, n34)
n43 = 'bee' (word)
n33.sons = (n43)

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

Этот метод сложнее реализовать, чем один словарь или Hashtable, но он будет гораздо более оптимизирован с точки зрения использования памяти

Ответ 6

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