В современном мире интернет плотно вошёл в жизнь человека. И если раньше на поиск нужного товара или услуги надо было бы объехать как минимум пол города или обзвонить сотни различных контор, то теперь, введя запрос в поисковую систему, можно без труда отыскать то, что нужно. Об информации можно даже не говорить, ведь и так известно что «в интернете есть все». Сейчас уже сложно представить поиск сайтов без соответствующих поисковых систем.
В процессе разработки информационной системы сетевого семантического поиска необходимо:
- выбрать тип поисковой системы;
- выбрать математическую модель;
- выбрать методику оценки качества поиска;
- определить, какие дополнительные задачи должна решать разрабатываемая система.
Тип поисковой системы определяется типом используемых поисковых алгоритмов.
В статье Ильи Сегаловича «Как работают поисковые системы» [2]автор выделяет следующие виды поисковых алгоритмов:
- прямого поиска;
- инвертированных файлов;
- суффиксных деревьев;
- сигнатур.
И. Сегалович приходит к выводу, что, несмотря на медлительность алгоритмов прямого поиска, они вполне применимы при использовании мощного технического обеспечения, позволяющего обслуживать большое количество запросов в единицу времени. Автор выделяет положительную сторону данной группы алгоритмов — неограниченные возможности по приближенному и нечеткому поиску, аргументируя это тем, что алгоритмы прямого поиска работают с оригинальными документами без искажений (при использовании же индекса происходят упрощение и нормализация терминов, а следовательно возникает потеря информации). Автор утверждает, что алгоритмы суффиксных деревьев и сигнатур не получили широкого распространения.
А. В. Кириллов в статье «Поисковые системы: компоненты, логика и методы ранжирования» [1]утверждает, что в большинстве поисковых систем используется алгоритм инвертированных файлов.
Модель поиска — это некоторое упрощение реальности, на основании которого получается формула, позволяющая программе принять решение: какой документ считать найденным и как его ранжировать.
В статье Ильи Сегаловича «Как работают поисковые системы» [2]автор выделяет следующие виды математических моделей:
- теоретико-множественные (булевская, нечетких множеств, расширенная булевская);
- алгебраические (векторная, обобщенная векторная, латентно-семантическая, нейросетевая);
- вероятностные.
И. Сегалович пишет о том, что булевская модель неоднократно подвергалась критике из-за ее крайней жесткости и непригодности для ранжирования. Автор утверждает, что вероятностные, латентно-семантическая модели не получили большого распространения, в отличие от успешно реализованной в поисковой системе SMART векторной модели.
В статье А. В. Кириллова «Поисковые системы: компоненты, логика и методы ранжирования» [1]автор пишет, что подход к ранжированию с использованием вектора документа является достаточно популярной технологией, однако у нее имеется существенный недостаток, заключающийся в том, что такой метод может дать ошибочные результаты, т. к. количество слов на странице подсчитывается «вслепую». Во избежание этого вносятся корректирующие коэффициенты, основанные на таких факторах, как расположение термов относительно друг друга, статистические измерения корреляции между термами и аспектами форматирования страницы (например, шрифт и размер шрифта, которым представлены термы).
Кириллов также пишет, что одним из популярных методов ранжирования является OKAPI BM25, основывающаяся на вероятностной модели. [8]В статье «Поисковые системы: компоненты, логика и методы ранжирования» [1]также указано, что существует улучшенный вариант функции — OKAPI BM25F, в которой ранжирующая функция разбивается на части относительно полей документа, таких как заголовки, ссылки, основной текст и т. д.
Какая бы ни была модель, поисковая система нуждается в оценке качества. Благодаря ей можно судить применимости или не применимости выбранной модели.
В статье Ильи Сегаловича «Как работают поисковые системы» [2]автор выделяет два параметра, обычно использующиеся для оценки качества поиска, однако делает поправку, что есть и «альтернативные» метрики. Эти параметры:
- точность — доля релевантного материала в ответе поисковой системы;
- полнота — доля найденных релевантных документов в общем числе релевантных документов коллекции.
Автор утверждает, что эти параметры используются для выбора моделей и их параметров в рамках созданной Американским Институтом Стандартов (NIST) конференции по оценке систем текстового поиска (TREC). К каждой очередной конференции готовится новый материал (т. н. «дорожка») по каждому из интересующих направлений. Она включает коллекцию документов и запросов.
Эти два параметра оценки качества поиска также фигурируют в статье А. В. Кириллова «Поисковые системы: компоненты, логика и методы ранжирования». [1]
И. Сегалович пишет в своей статье, что одним из естественных ограничений качества поиска служит следующее наблюдение: мнения двух «асессоров» (специалистов, выносящих вердикт о релевантности) в среднем не совпадают друг с другом в очень большой степени. Отсюда вытекает естественная верхняя граница качества поиска, ведь качество измеряется по итогам сопоставления с мнением асессора. [2]
В статье D. Harman «What we have learned, and not learned, from TREC» [5]автор пишет, что проверка устойчивости показала: перекрытие релевантных документов между любыми двумя асессорами примерно 40% в среднем, точность и полнота, измеренная между асессорами, около 65%, что накладывает практическую верхнюю границу на качество поиска в районе 65%.
Не существует ни одной поисковой системы, которой бы не приходилось решать дополнительные задачи.
В статье Ильи Сегаловича «Как работают поисковые системы» [2]автор выделяет следующие дополнительные задачи, которые приходится решать информационным системам сетевого семантического поиска:
- задачи, разделяющие с поиском общую идеологию (классификация,
- маршрутизация, фильтрация, аннотирование);
- задачи, являющиеся неотъемлемой частью поискового процесса (кластеризация результатов, расширение и сужение запросов, обратная связь, «запросо-зависимое» аннотирование, поисковый интерфейс и языки запросов).
Отдельно автор выделяет задачи, решаемые лингвистическими и окололингвистическими методами:
- автоматическое определение языка документа;
- токенизация (графематический анализ): выделение слов, границ предложений;
- исключение неинформативных слов (стоп-слов);
- лемматизация (нормализация, стемминг): приведение словоизменительных форм к «словарной», в том числе и для слов, не входящих в словарь системы;
- разделение сложных слов (компаундов) для некоторых языков (например, немецкого);
- дизамбигуация: полное или частичное снятие омонимии;
- выделение именных групп.
Также Илья Сегалович отмечает, что ряд задач решается алгоритмами словообразовательного, синтаксического и семантического анализа. Но такие задачи имеют узкоспециализированный характер.
В своей статье «Использование семантики в поисковых механизмах» [3]С. В. Перминов также делает вывод о применимости синтаксического анализа лишь для ограниченного круга задач. Однако автор также отмечает, что в остальных случаях может быть полезен семантический подход к проблеме поиска информации.
Сегалович в своей статье [2]также упоминает методы учета ссылочной популярности, состоящего в подсчете числа ссылок, указывающих на страницы:
- метод глобального (т. е. статического) учета PageRank;
- метод локального (т. е. динамического, основанного на запросе) учета HITS.
Данные методы могут использоваться для решения таких дополнительных задач системы сетевого семантического поиска, как определение порядка обхода документов, ранжирование поиска по тексту ссылок и т. д.
Сегалович утверждает, что метод HITS не используется на практике в основном из-за вычислительной дороговизны.
Еще одна задача, упоминаемая автором статьи «Как работают поисковые системы», — это задача поиска мало отличающихся документов, увеличивающих размер базы данных информационной системы, что приводит к дополнительным затратам на ее поддержку.
Для решения этой задачи И. Сегалович предлагает использовать алгоритм «шинглов».
Проведенный обзор публикаций позволяет выделить наиболее перспективные технологии, применяемые при создании информационных систем сетевого семантического поиска.
Библиографический список
- Кириллов, А.В. Поисковые системы: компоненты, логика и методы ранжирования / А.В. Кириллов // Бизнес-информатика. — 2009.- № 4.- С. 51-59.;
- Сегалович, И.В. Как работают поисковые системы / И.В. Сегалович // Мир Internet. — 2002.- № 10.- С. 23-25.;
- Перминов, С.В. Использование семантики в поисковых механизмах / С.В. Перминов // Труды СПИИРАН. — 2008.- № 6.- С. 161-167.;
- Brin S. The Anatomy of a Large-Scale Hypertextual Web Search Engine / S. Brin, L. Page // Computer Networks.-1998.- Vol.30.- P.107-117.;
- Harman D. What we have learned, and not learned, from TREC / D. Harman // BCS IRSG ’2000 Proceedings.-2000.- P.2–20.;
- Kleinberg J. Authoritative sources in a hyperlinked environment / J. Kleinberg // Journal of the ACM.-1999.- Vol.46.- P.604-632.;
- Поисковая система [Электронный ресурс] // Википедия — свободная энциклопедия: [web-сайт]. 06.09.2011. http://ru.wikipedia.org/wiki/Поисковая_система;
- Okapi BM25 [Электронный ресурс] // Википедия — свободная энциклопедия: [web-сайт]. 08.09.2011. http://ru.wikipedia.org/wiki/Okapi_BM25;
- Поисковые системы и их роль в современном мире [Электронный ресурс] // Блог матерого компьютерщика: [web-сайт]. 15.06.2011. http://soft-x.info/internet/poiskovye-sistemy-i-ikh-rol-v-sovremennom-mire.
Количество просмотров публикации: Please wait