В предыдущей публикации Алгоритм нечеткого поиска TextRadar. Основные подходы (часть 1) Рассмотрены основные подходы.
При решении практических задач выявлены ситуации, когда использование только базовой методики не обеспечивает требуемого качества поиска.
В результате были созданы дополнения (варианты алгоритма), о которых и пойдет речь.
Фрагменты одного слова искомой строки располагаются в нескольких словах строки данных.
Пусть строкой поиска будет ABCD, а строкой данных — ABCE DFG. 
Применение основного алгоритма даст следующий результат: 
Если такие коллизии происходят, ненужные группы удаляются.
Выбор групп для удаления — отдельный сложный вопрос.
В результате должны остаться наиболее значимые группы.
В случае с приведенным примером ответ очевиден – следует удалить самую маленькую из групп.
Начальный фрагмент слова строки поиска находится внутри слова строки данных.
Рассмотрим пример поиска строки ABC в строке XYZAB. 
Базовый алгоритм даст следующее: 
Как правило, такой результат не имеет практического значения и его следует отбросить.
Недостаточное покрытие слова строки данных найденными фрагментами
Если вы ищете в строке ABCDEF слово ABXYZ
мы получаем:
Этот результат также не имеет никакой ценности и его следует отбросить.
Супергруппы
Дана строка поиска ABCXEF и строка данных ABCEF ABCDEF.
С точки зрения базового алгоритма оба слова строки данных эквивалентны, но приоритет будет иметь первое из них (если при прочих равных условиях выбрано первое встреченное слово) и тогда результат поиска будет такой: следует:
Если ввести понятие супергруппы как объединения групп слов, расположенных на одной диагонали (или сдвиге, см.
предыдущую публикацию, где обсуждаются основы алгоритма) и повысить приоритет групп, входящих в супергруппы, через параметр размер супергруппы , рассчитанный для каждой из групп и предположим, что если группа не входит в супергруппу, то размер супергруппы для нее будет равен размеру самой группы - для нашего примера получим следующий результат: 
Переоценка длинных слов
При поиске фразы, содержащей длинное слово и короткое слово, найденные фрагменты длинного слова могут «затмевать» фрагменты короткого.Это связано с использованием квадратичной функции при расчете коэффициента релевантности.
При этом с точки зрения качества поиска более длинное слово не всегда значительнее.
Давайте посмотрим на пример.
Допустим, нам нужно найти строку ABCDEFG XYZ в тексте, состоящем из двух страниц:
1. ABCDEFG.QWE 
2. АВСДЕФО…XYZ 
Числитель коэффициента состава группы (знаменатель не оказывает качественного влияния на результат, см.
формулу выше) для первой страницы будет равен 49, для второй - 36 + 9 = 45. То есть, если опустить влияние коэффициента длины на результат, то результат поиска на первой странице будет иметь большую релевантность, что не соответствует ожиданиям – в некоторых случаях результат поиска на странице 2 будет более ценным.
Одним из решений может быть введение ограничения на максимальную длину групп .
В нашем примере, если мы ограничим максимальную длину групп, например, 6, мы получим 36 для первой страницы и 45 для второй, что обеспечит ожидаемый нами результат - релевантность второй страницы будет выше, чем первый.
Еще один способ решения проблемы несоответствия значимости слов поисковой фразы в общем результате и их длины – вычисление релевантности поисковой фразы как среднего значения релевантностей составляющих ее слов , рассчитывается независимо.
Но здесь возникает противоположная проблема – необходимость снижения значимости коротких слов, которую можно решить аналогичным образом – установив пороговое значение длины слов, участвующих в формировании общей релевантности, но минимальное.
ценить.
Многократное повторение необходимых фрагментов
Как следует из формулировки, задача состоит в том, чтобы найти наиболее соответствующий искомой строке набор фрагментов, поэтому факт неоднократного повторения искомых фрагментов в тексте не влияет на результат – в качестве первого подходящего фрагмента будет использоваться результат поиска, остальные отбрасываются при обработке.
Рассмотрим пример поиска строки ABC в строке ABCD ABCE ABCF ABCG. 
Применение основного алгоритма даст следующий результат: 
С точки зрения поиска наиболее релевантной страницы это правильно, но при создании детального представления результатов поиска необходимо найти и выделить все релевантные фрагменты.
Для этого можно использовать многократное повторение процедуры поиска на отображаемой странице с последовательным выключением фрагментов, найденных на предыдущих итерациях.
В нашем примере это позволит нам найти все соответствующие вхождения строки поиска.
Скорость обработки
Обработка данных на лету предъявляет определенные требования к скорости — поиск не должен занимать слишком много времени.Ограничение минимального размера обрабатываемых групп, отключение возможностей поиска Для увеличения скорости поиска вы можете ограничить минимальную длину обрабатываемых групп.
На практике используется следующий подход – сначала делается первый «грубый» проход с ограничением минимального размера групп и отключением некоторых опций всего массива поисковых данных и выявлением первой порции данных (размера оптимальная порция данных определяется из контекста решаемой задачи), а затем вторая, более тщательная, сканирующая только страницы этой порции, без ограничения размера групп и со всеми необходимыми опциями.
Параллельная обработка данных Еще одна возможность увеличить скорость поиска — параллельная обработка данных.
В результате при большой базе поиска приемлемое общее время обработки может быть достигнуто за счет увеличения количества параллельных процессов, что, естественно, требует увеличения мощности оборудования.
Полученные результаты
Использование описанных подходов позволило существенно повысить качество поиска, снизить зависимость его результатов от различного рода опечаток – лишних, пропущенных символов, перестановок и т.п., и, что немаловажно, не важно.
где находятся эти опечатки - в самой строке поиска или в тексте, в котором осуществляется поиск.
Загрузите или просмотрите демонстрационный проект с расширенным функционалом (C# ASP.NET MVC) ты можешь здесь .
Алгоритм нечеткого поиска TextRadar. Указатель (часть 3) Теги: #Алгоритмы #релевантность #нечеткий поиск #нечеткое сравнение строк #текстовый радар #нечеткий поиск
-
Структуры Против Классов
19 Oct, 24 -
Оптимальный Код?
19 Oct, 24 -
Правильный Инструмент: Выбор Cms
19 Oct, 24 -
Учебная Программа Jdbc
19 Oct, 24
