В этой статье я хотел бы ответить на один из вопросов, сформулированных в Проблемы с читалкой.
Рай где-то рядом? .
Дело вот в чем.
У нас есть система, которая получает текстовые сообщения; для каждого сообщения нам нужно создать набор вики-страниц, соответствующих тексту.
Допустим, есть текст: «Барак Обама встретился с Путиным».
Вывод должен содержать ссылки на страницы Википедии «Барак Обама» и «В.
В.
Путин.
" Опишем один из возможных алгоритмов.
И так, пусть частота (А) – частота встречаемости фразы А в тексте страниц Википедии в виде ссылки или обычного текста.
То есть, скажем так А = «Дед Мороз» .
Затем freq("Санта-Клаус") – это количество раз, когда данный текст появляется на страницах Википедии.
Естественно, нам необходимо учитывать различные формы, для этого мы используем один из алгоритмов лематизации или стемминга.
ссылка(А) – частота встречаемости фразы А как ссылки на страницах Википедии.
ссылка(Дед Мороз) — сколько раз эта фраза является ссылкой на всех страницах вики.
ссылка(А) <= freq(A) – Я думаю, это очевидно.
lp(A) = связь(A)/частота(A) – вероятность того, что А - связь.
То есть, что А В целом его следует рассматривать как кандидата на викификацию по тексту.
Пг(А) – все страницы Википедии, на которые есть ссылки с текстом А .
ссылка(п,А) – сколько раз ссылки с текстом А ссылка на страницу п .
Р(р|А) – вероятность того, что А ссылки на страницу п .
Рассчитано как ссылка(p,A)/Pg(A) .
Аннотирующий текст А напрямую зависит от вероятности Р(р|А) Построение таблицы с расчетами ссылка(А) И лп(А) .
Потом мы все выбрасываем ссылка(А) < 2 или лп(А) < 0.1 левые элементы образуют словарь linkP. На основе этого словаря мы будем выбирать фразы из текста.
Пороги можно взять свои.
Чем выше порог, тем меньше будет кандидатов на викификацию.
Соответственно, перед строительством все А приводим его к исходному виду.
Но если мы будем действовать только Р(р|А) , то результаты сомнительны, так как смысл во многом зависит от контекста, поэтому идем дальше.
Для этого нам нужны данные о зависимости страниц Википедии.
Для всех страниц мы рассчитываем зависимость на основе расстояния Google. 
Где в (п) – множество страниц, ссылающихся на п , |В| — количество страниц в Википедии.
Мы сохраняем эти данные для пар страниц, коэффициент которых больше определенного порогового значения.
Как уже говорилось выше, какой странице соответствовать фразе, во многом зависит от контекста, поэтому рассчитываем влияние контекста.
Где Б, А — фразы, извлеченные из текста, которые необходимо сопоставить с вики-страницами, п – вики-страница, опция сопоставления для А .
Общая формула выбора будет следующая.
Вероятность того, что А нужно соответствовать странице п , В — выбранные фразы из текста А (кандидаты на сопоставление страниц).
В целом шаги алгоритма следующие.
- Токенизируем и стемлируем полученный текст.
- Выбираем в нем все фразы длиной до N (выбираем сами, исходя из наличия ресурсов).
- Смотрим на наличие выделенных фраз в словаре ссылкаP (все тексты ссылок, найденные в Википедии, вероятность которых превышает наш порог).
Формирование В – выбранные фразы из текста и найденные в словаре ссылкаP .
- Если мы столкнемся со случаем, а, б – выделенные фразы, как в словаре ссылкаP И а подстрока б , затем сравниваем лп(а) И лп(б) Если лп(а) < lp(b) Выбрось это В .
Таким образом мы избавляемся от случаев, когда у нас есть a = «яблоко» b = «компьютеры Apple» .
Если lp(a) > = lp(b) , тогда смотрим частота(а) И частота (б) .
Если частота(а) > частота(б) тогда скорее всего А - бессмысленный элемент и от него мы тоже избавляемся.
- Для каждой фразы мы строим набор кандидатов на сопоставление на основе Р(р|а) > 0 (общая вероятность, а принадлежит В ).
То есть находим все доступные варианты соответствия.
- Мы рассчитываем Пр(р|а) на основе составленных наборов.
- Выбирать п с величайшим Пр(р|а) для каждого а .
ссылкаP – служит для выделения из текста кандидатов на викификацию.
- А — фраза, найденная в Википедии в виде ссылки;
- лп(А) ;
- частота (А) .
- А — фраза, найденная в Википедии в виде ссылки;
- п — идентификатор страницы Википедии;
- Р(р|А) – вероятность того, что А ссылки на страницу п .
- Вики-страница п1 ;
- Вики-страница п2 ;
- отн(p1,p2) .
Заключение
Сам алгоритм достаточно прост, но при реализации возникают трудности.В частности, размер хранимых данных достаточно велик, а поиск должен занимать минимум времени.
В одной из реализаций индексы строились в памяти с помощью lucene, после чего по этим индексам осуществлялся поиск.
Основная проблема — работа со связанной таблицей.
Если вы храните данные в базе данных, то процесс обработки текста занимает довольно много времени; если он хранится в памяти, потребуется значительный объем памяти.
Все алгоритмы викификации, с которыми я столкнулся, были построены по описанному выше принципу, с небольшими отличиями.
Было бы интересно посмотреть реализацию с использованием нейросетей, но я таких работ не видел.
Теги: #викификатор #Алгоритмы
-
Рыболовные Судна
19 Oct, 24 -
Приглашаем Вас На Mskdotnet Meetup #24
19 Oct, 24 -
Мвцк-6. Очистка
19 Oct, 24 -
Оффлайн И Онлайн-Общение
19 Oct, 24
