Сравнение с помощью n-грамм

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

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

Сравнение с помощью «-грамм позволяет ограничить потенциальные совпадения такими, у которых есть одна или более «-грамм, общих со строкой запроса. В примере со словом tamming можно было бы рассмотреть не только строки с префиксом tarn, но и строки, содержащие другие триграммы: arnni. mmi, min, ing. В словаре из 100 000 слов лишь десятая часть слов содержит какую-нибудь из этих триграмм. И хотя сокращение не больше, чем при использовании одного лишь префикса, теперь мы можем исправлять и другие ошибки в исходном тексте, в том числе в первом символе. Подход на основе «-грамм позволяет очень просто ранжировать найденные совпадения: чем больше совпавших «-грамм, тем лучше рекомендация. В нашем примере 19 слов содержат 4 из 5 «-грамм, а 74 слова (с учетом этих 19) содержат 3 «-граммы. Ранжируя результаты поиска по «-граммам, мы можем принять решение, что будем рассматривать только фиксированное число рекомендаций с достаточно высокой уверенностью в совпадении, причем первым в списке будет слово с наименьшим редакционным расстоянием.

Поиск с помощью n-грамм в Soir

Soir поддерживает не только префиксный поиск, но и поиск с помощью «-грамм. Для этого предназначен класс org. apache. lucene.

analysis.ngram.NGramTokenFilter И связанный С НИМ фабричный класс org.apache.soir.analysis.NGramFilterFactory.

Но поиск с помощью «-грамм не учитывает позиционную информацию. Ценность «-граммы, расположенной в начале строки, но совпавшей с n-граммой в конце другой строки, никак не уменьшается. Один из способов преодолеть это ограничение - воспользоваться аффиксацией строк для запоминания позиционной информации о начале или конце строки. Эта техника уже рассматривалась в разделе 4.1.3.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >