Алгоритм множественного совпадения слов в тексте
У меня есть большой набор слов (около 10 000), и мне нужно найти, появляется ли какое-либо из этих слов в данном блоке текста.
Есть ли более быстрый алгоритм, чем простой текстовый поиск для каждого слова в блоке текста?
Ответы
Ответ 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 должен работать. в зависимости от размера /# или слов в блоке текста, вы можете использовать его в качестве ключа для поиска списка слов (есть ли больше слов в списке, чем в блоке). Кроме того, вы, вероятно, захотите удалить любые дубликаты из обоих списков.