 |
Алгоритмы морфологического анализа текстов
|
|
|
|
Некоторые поисковые системы используют морфологический анализ, который позволяет производить поиск более качественно.
Наибольший интерес представляет алгоритм русского морфологического анализа. Программная оболочка электронного морфологического словаря Yandex-Dict разработана подразделением «Аркадия» фирмы CompTek International [73].
Приведем описание алгоритма морфологического анализа текстов.
1. Находятся все варианты анализируемой словоформы.
2. Для каждого варианта основы, начиная с самого длинного, осуществляется бинарный поиск в инверсионном списке основ. Если вариант основы в этом списке отсутствует, то находятся наиболее близкие словарные основы, имеющие максимальное по длине общее окончание. Позиция первой наиболее близкой основы и мера ее сходства – число совпавших символов в основе и длина окончания – запоминаются.
3. По всем вариантам основ производятся следующие действия:
- для всех лексем, имеющих одинаковую меру сходства (одинаковую длину общего окончания основы), осуществляется морфологический анализ по лексеме;
- если вариант основы не совпадает ни с одной из ближайших словарных основ, то это означает, что анализируемое слово с данным вариантом основы в словаре отсутствует. В этом случае по варианту основы, окончанию и лексеме, соответствующей ближайшей словарной основе, генерируется гипотетическая лексема – модель словоизменения для этого неизвестного слова. В случае успешной генерации эта гипотеза подается на вход морфологического анализатора по лексеме;
- успешные варианты разбора запоминаются в виде
{Лексема (текст статьи), варианты разбора};
- если результат является гипотезой и при этом такая же гипотеза уже есть, то она не запоминается повторно. Вместо этого увеличивается счетчик продуктивности этой гипотезы;
|
|
|
- если среди лексем с одинаковой текущей мерой сходства есть хотя бы один вариант разбора, то переход к п. 5 с успешным результатом. Если вариантов разбора нет, то длина требуемого общего окончания основы уменьшается. Если после этого длина требуемого общего окончания основы стала меньше двух, то переход к п. 5 с отказом; иначе – переход к п. 3.
4. Проводится унификация гипотез по парадигмам (поскольку формат допускает неоднозначное описание парадигмы) и их фильтрация по продуктивности. Если продуктивность гипотезы меньше максимальной продуктивности в пять раз, то гипотеза отсеивается.
5. Конец.
Кроме использования морфологических словарей в поисковых системах для повышения релевантности запроса по узкоспециализированным темам очень часто применяются тематические тезаурусы (словари). [52].
Рассмотренные выше алгоритмы отличаются от классических алгоритмов поиска информации. Это обусловлено тем фактом, что классические модели поиска разрабатываются исходя из предпосылок, обусловленных поиском релевантных документов в Интернете. В рамках данной монографии метапоиск рассматривается как процесс сканирования информации из Интернета. В результате возникает ряд проблем, связанных с ранжированием полученной информации о ссылках на документы. Необходимо отметить, что представленные модели отличаются еще и тем, что поиск производится сразу по нескольким разноязычным сегментам Интернета, что накладывает дополнительные ограничения на существующие модели поиска информации. Разноязычность результатов поиска обусловлена необходимостью работы над составлением новых и актуализацией существующих мультилингвистических словарей.
Модели ранжирования
Модели ранжирования предназначены для того, чтобы упорядочить полученные ссылки с множества сайтов как внутри одного языкового множества, так и для многомерного языкового множества.
|
|
|
Рассмотрим модель поиска информации сразу по нескольким языкам.
Эта модель применяется при опросе Интернета в разных языковых сегментах одновременно. В результате получается множество ссылок на разноязычные документы djy, после чего проводится отсев дублирующихся ссылок и вычисляется вес ссылки на документ.
Таким образом, результат каждого запроса может быть представлен в виде r -мерного ранжированного вектора:
(3.5)
(3.6)
где i – номер опрашиваемого сайта (i = 1,..., n); n – количество опрашиваемых сайтов; j – номер ссылки из множества ссылок, выданных всеми опрошенными поисковыми сайтами, без дублей (j = 1,..., m); m – количество ссылок без повторений; y – номер языкового множества (y = 1,..., r); r – количество опрашиваемых языковых множеств; RangDoc jy – получаемый ранг j -й страницы k -го языкового множества; RangSite iy – ранг i -го сайта в текущей предметной области k -го языкового множества на данный момент; RangSiteDoc iy – ранг ссылки на страницу внутри i -го поискового сайта k -го языкового множества.
(3.7)
здесь Doc iy = 1, если i -й сайт дал ссылку на данную страницу, и 0, если ссылка на i -м сайте отсутствует.
Ранг сайта по каждой предметной области определятся по следующему алгоритму:
- при первом проходе RangSite iy = 0;
- в процессе опроса каждого сайта ранг изменяет свое значение по формуле
RangSite iy = RangSite iy + (DocRelTotal iy –
– DocNotRelTotal iy) / DocTotal iy, (3.8)
где DocRelTotal iy – количество релевантных документов, выданных i -м поисковым сайтом; DocNotRelTotal iy – количество нерелевантных документов, выданных i -м поисковым сайтом; DocTotal iy – общее количество документов:
DocTotal iy = DocRelTotali y + DocNotRelTotal iy. (3.9)
Ранг ссылки на страницу внутри множества ссылок, выданных каждым конкретным сайтом, определяется по формуле
RangSiteDoc iy = NumDoc iy – DocTotal iy. (3.10)
Если поиск проводится только в пределах одного языкового множества, то в предложенной модели ранжирования необходимо принять y = 1.
Если ввести один индекс w, отвечающий за предметную область, то полученная модель будет производить поиск и ранжирование сразу для нескольких предметных областей. При этом сумма всех неповторяющихся ссылок всех опрашиваемых предметных областей должна быть меньше или равна общей сумме ссылок без повторений, что связано с пересечением предметных областей или наличием смежных предметных областей.
|
|
|
Необходимо отметить, что в предлагаемой модели ранжирования все ранги должны быть не меньше единицы [6; 7; 16].
|
|
|
