Эффективный алгоритм поиска всех ключевых слов в тексте

Question

У меня есть много строк, содержащих текст в различных написаниях. Я маркирую эти строки путем поиска ключевых слов, и если ключевое слово найдено, я использую связанный текст для этого ключевого слова.

Допустим, строка поиска может содержать текст "schw.", "Schwa." и "Шварц". У меня есть три ключевых слова, которые все разрешают текст "schwarz".

Теперь я ищу эффективный способ найти все ключевые слова без использования строки. Содержит (ключевое слово) для каждого ключевого слова.

Пример данных:

H-Fuss ahorn 15 cm/SH48cm
Metall-Fuss chrom 9 cm/SH42cm
Metall-Kufe alufbg.12 cm/SH45c
Metall-Kufe verchr.12 cm/SH45c
Metall-Zylind.aluf.12cm/SH45cm
Kufe alufarbig
Metall-Zylinder hoch alufarbig
Kunststoffgl.schw. - hoch
Kunststoffgl.schw. - Standard
Kunststoffgleiter - schwarz für Sitzhoehe 42 cm

Примеры ключевых слов (ключ, значение):

h-fuss, Holz
ahorn, Ahorn
metall, Metall
chrom, Chrom
verchr, Chrom
alum, Aluminium
aluf, Aluminium
kufe, Kufe
zylind, Zylinder
hoch, Hoch
kunststoffgl, Gleiter
gleiter, Gleiter
schwarz, Schwarz
schw., Schwarz

Пример результата:

Holz, Ahorn
Metall, Chrom
Metall, Kufe, Aluminium
Metall, Kufe, Chrom
Metall, Zylinder, Aluminium
Kufe, Aluminium
Metall, Zylinder, Hoch, Aluminium
Gleiter, Schwarz, Hoch
Gleiter, Schwarz
Gleiter, Schwarz

Answer 1

Похоже, что это подходит " Алгоритмы с использованием конечного набора шаблонов "

Строка Aho – Corasick, соответствующая Алгоритм поиска строки алгоритм, изобретенный Альфредом В. Ахо и Маргарет Дж. Корасик. Это своего рода алгоритма сопоставления словаря, который находит элементы конечного набора строки («словарь») в пределах ввод текста. Это соответствует всем образцам «сразу», поэтому сложность Алгоритм является линейным по длине шаблоны плюс длина искомый текст плюс количество выходные совпадения. Обратите внимание, потому что все совпадения найдены, может быть квадратичное количество совпадений, если каждый совпадения подстроки (например, словарь = аа, ааа, аааа и входная строка аааа).

Алгоритм Рабина-Карпа представляет собой строку алгоритм поиска, созданный Майклом О. Рабин и Ричард М. Карп в 1987 г. который использует хеширование, чтобы найти любой из набор шаблонных строк в тексте. За текст длиной n и p шаблонов общая длина м, его средняя и наилучшее время выполнения O (n + m) в пространство O (p), но его худшее время O (нм). Напротив, Ахо-Корасик алгоритм сопоставления строк имеет асимптотическая сложность наихудшего времени O (n + m) в пространстве O (m).

Answer 2

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

используя: System.Text.RegularExpressions.

В вашем примере:

• "schw.", "Schwa." и "шварц"
• new Regex(@"schw(a?\.|arz)", RegexOptions.Compiled)

Дополнительная документация доступна здесь: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regexoptions(v=VS.90).aspx

Answer 3

Если у вас есть фиксированный набор ключевых слов, вы можете использовать (f) lex, re2c или ragel

Answer 4

Возможно, он немного подавлен, но вы обязательно должны взглянуть на ANTLR .

Answer 5

Я предлагаю подходы:

1) Токенизировать, используя string.Split и сопоставить со словарем ключей, которые у вас есть

2) Реализовать токенизатор самостоятельно, читатель с ReadToken() методом, который ондобавляет символы в буфер до тех пор, пока он не найдет (возможно, это делает Split) разделенный символ и выведет этот токен.Затем вы проверяете по своему словарю.