В предыдущих публикациях (ч. 1 и ч. 2) были рассмотрены основные подходы, применяемые в алгоритме нечеткого поиска TextRadar и особенности решения практических задач. В продолжение начатой в ч. 2 темы оптимизации, сегодня речь пойдет об индексировании, в первую очередь как средстве ускорения поиска в многостраничных текстах, но не только. В результате мы получим тот же результат, что и с использованием описанных ранее подходов, только быстрее.

Предпосылки

Задача поиска фразы в тексте, разбитом на страницы, сводится к расчету коэффициента релевантности для каждой из страниц и последующей сортировке списка в порядке убывания коэффициента.

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

В предыдущей публикации Алгоритм нечеткого поиска TextRadar. Основные подходы (ч. 1) рассмотрены основные подходы. При решении практических задач были выявлены ситуации, когда использование только базовой методики не обеспечивает требуемого качества поиска. В результате были созданы дополнения (опции алгоритма), о которых и пойдет речь.

Фрагменты одного слова строки поиска расположены в нескольких словах строки данных

Пусть строка поиска ABCD, а строка данных — ABCE DFG.



Применение базового алгоритма даст следующий результат:

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

Постановка задачи

Даны строка данных и строка поиска как произвольные наборы символов, состоящие из слов – групп символов, разделенных пробелами.

Требуется найти в строке данных наиболее близкий к строке поиска по составу и взаимному расположения символов набор фрагментов.

Для оценки качества результата поиска вычислить коэффициент релевантности, значение которого должно лежать в диапазоне от 0 до 1, где 0 должен соответствовать полному отсутствию символов строки поиска в строке данных, а 1 – наличию строки поиска в строке данных в неискаженном виде.

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

Описание алгоритма

Поиск осуществляется в несколько этапов.

Построение матрицы совпадений

Матрица совпадений (M) представляет собой двумерную матрицу, количество столбцов которой соответствует длине строки данных, а количество строк – длине строки поиска. Элементы матрицы совпадений принимают значения 0 или 1 в зависимости от того, совпадают или нет соответствующие символы строк за исключением пробелов (разделителей слов).
Матрица совпадений для строки данных «ABCD EF» и строки поиска «ABC» имеет вид: