В предыдущих публикациях ( часть 1 И часть 2 ) рассмотрены основные подходы, используемые в алгоритме нечеткого поиска TextRadar, и особенности решения практических задач.
В продолжение того, что началось в часть 2 темы оптимизации, сегодня мы поговорим об индексировании, прежде всего, как о средстве ускорения поиска в многостраничных текстах, но не только.
В результате мы получим тот же результат, что и при использовании ранее описанных подходов, только быстрее.
Предварительные условия
Задача поиска фразы в тексте, разделенном на страницы, сводится к расчету коэффициента релевантности для каждой страницы и последующей сортировке списка по убыванию коэффициента.В процессе расчета в соответствии с базовым подходом каждая страница подвергается посимвольному анализу и здесь кроется возможность оптимизации.
При расчете коэффициента анализируются группы совпадающих символов в поисковых строках и данных, причем группы могут формироваться только внутри слов.
С другой стороны, рассматривая проблему завышенных «длинных» слов (в часть 2 ), в качестве возможного решения было предложено « расчет релевантности поисковой фразы как среднего значения релевантностей составляющих ее слов, рассчитанных независимо " Использование индекс позволит получить результат, эквивалентный данному конкретному подходу.
Индекс
Идея индексации не нова и заключается в следующем: за счет того, что слова в тексте повторяются, объем вычислений можно сократить.Для этого предварительно необходимо сформировать индекс для текста, по которому будет осуществляться поиск.
В простейшем случае индекс представляет собой таблицу всех слов в тексте, которая помимо слов содержит данные о страницах, на которых они встречаются.
Фрагмент индексной таблицы по тексту романа Л.
Н.
«Война и мир» Толстого (всего в ней около 50 тысяч слов) представлена на рисунке.
Непосредственно во время обработки запроса строка поиска сначала разбивается на слова.
Далее для каждого из слов в строке поиска рассчитывается релевантность каждому из слов.
индекс .
Результаты расчетов накапливаются в таблица предварительных результатов , содержащий столбцы «Слово строки поиска», «Индексное слово», «Коэффициент релевантности», «Номер страницы».
В таблицу включаются только те индексные строки, коэффициент релевантности слов которых превышает заданный порог.
То есть каждая индексная строка с совпадающим словом генерируется в таблица предварительных результатов строк в количестве, равном количеству страниц текста, на которых встречается это слово.
Ниже приведен фрагмент таблицы предварительных результатов выполнить поиск по фразе «Вечер с Анной Павловной Шерер».
Затем таблица предварительных результатов отсортировано по столбцам Номер страницы , Поиск строкового слова , Коэффициент (по убыванию).
Путем обхода строк отсортированной таблицы для каждой страницы и для каждого слова строки поиска определяется наиболее релевантное слово этой страницы — благодаря описанной выше сортировке это первое слово для каждой комбинации.
Номер страницы – строковое слово поиска .
Остальные строки комбинации отбрасываются.
Таким образом, для каждой страницы текста, входящего в таблица предварительных результатов , для каждого слова в строке поиска будут найдены наиболее релевантные слова на этой странице с соответствующими коэффициентами.
Сумма коэффициентов слов, найденных на странице, деленная на количество слов в строке поиска, даст коэффициент релевантности для страницы.
Например, на рисунке выше поиск осуществляется по строке «Вечер у Анны Павловны Шерер» (предлог «у» не учитываем), строки, выделенные серым цветом, при обходе отбрасываются.
Коэффициент релевантности для 1 страницы составит (0,75+1+0,875+1)/4 = 0,906, для 2 страницы – 0,906, для 3 – 0,75.
Преимущества
Если не учитывать время, затраченное на индексацию, результаты которой используются неоднократно, и учесть, что общий объем вычислений, оцененный в часть 1 , кратно длине строки данных:
; можно сказать, что выигрыш от использования индекса будет кратен соотношению:
Например, на демонстрационном стенде textradar.ru Текст романа «Война и мир» разбит на 1488 страниц по 2000 знаков каждая.
В этом случае общее количество символов в словах индекса, состоящего из 52156 элементов, составит 434060. То есть выигрыш от индексации составит около 7: 
Благодаря тому, что результаты, полученные с помощью индексирования, эквивалентны результатам, полученным с помощью одного из ранее описанных подходов без него, появляется возможность совместной обработки результатов поиска для индексируемых и неиндексированных частей текста.
В связи с тем, что индексирование является относительно дорогостоящей операцией и обычно выполняется по расписанию, возможно, что часть текста проиндексирована, а часть еще не проиндексирована.
В этом случае экономия в объеме вычислений будет кратна доле индексируемого текста в его общем размере: 
Помимо увеличения скорости поиска, использование индекса открывает целый спектр возможностей.
Например, используя статистические данные, полученные при индексировании, можно повысить значимость редких слов, а также выделить страницы текста, на которых слова поисковой фразы встречаются чаще.
Вы также можете расширить индексную таблицу синонимами.
На этом завершается серия публикаций, посвященных описанию TextRadar. Спасибо всем за интерес и ценные комментарии, которые позволили нам продвинуться дальше, чем планировалось изначально.
Реализацию (C# ASP.NET MVC) можно найти Здесь .
Теги: #Алгоритмы #релевантность #нечеткий поиск #нечеткое сравнение строк #текстовый радар #нечеткий поиск
-
Уйгурский Язык
19 Oct, 24 -
Работа С Usb-Видеокамерой В Linux. Часть 2
19 Oct, 24
