Анализ данных Индексирование данных и обработка запроса

План лекции Задачи и проблемы индексации Этапы нормализации текста Подготовка к ранжированию на этапах нормализации Обработка запроса Основная цель: рассмотреть основные этапы нормализации и обработки запроса

В предыдущей серии… Индексатор КэшированиеНормализатор Сниппеты Поиск Недоступные страницы

В предыдущей серии… Нормализатор – часть индексатора, преобразующая документ в вид удобный для последующего поиска Задача нормализатора: перевести неструктурированную информацию в структурированную

Удобный вид Нужно узнать, в каких документах встречается запрашиваемое слово Варианты решения: Просмотреть тексты всех документов Составить список документов, в которых встречается слово

Инвертированный индекс СловоID документов спрятать1, 4, 5, 7, 11 найти8, 14, 15, 23 труп10, 11, 23 мясорубка11, 14, 99 Индекс Запрос спрятатьтруп

Инвертированный индекс СловоID документов спрятать1, 4, 5, 7, 11 найти8, 14, 15, 23 труп10, 11, 23 мясорубка11, 14, 99 Индекс Запрос спрятатьтруп Результат [1, 4, 5, 7, 11] AND [10, 11, 23] = [11]

Словопозиции Часто важно, чтобы искомые слова шли подряд. Нужно учитывать позиции слов. Пример: «Варенье лучше прятать от солнечного света… … … … … Банка была холодная как труп.»

Словопозиции СловоID документов спрятать1, 11, … найти8 труп11, 23 мясорубка11, 14 Индекс Чем ближе слова друг к другу, тем релевантнее в итоге документ

Этапы нормализации Разбиение страницы на зоны текста Разбиение текста на слова Преобразование слов в термы Удаление стоп-слов

Разбиение страницы на зоны Заголовок страницы Мета-данные Заголовки разных уровней Первый блок текста Списки Остальные блоки текста

Разбиение текста на слова Что является разделителем? Специфические слова Составные слова

Разделитель слов Пробельные символы Знаки препинания Проблемы в английском языке: ONeill arent

Специфические слова Некоторые «слова» выглядят необычно С T-34 Разбираются по отдельным правилам, паттернам

Составные слова Некоторые слова нужно правильно разделить город Ростов-на-Дону рейс Лос-Анжелес-Сан-Франциско монолог «быть или не быть» Решение: составление статистики устойчивости употребления слов

Группировка слов Термин – класс эквивалентных слов, имеющих несущественные отличия (в окончаниях, префиксах и т.д.) [прячу, спрятанный, припрятал] ~ спрятать

Получение терминов Стемминг – последовательное удаление незначащих частей слов Лемматизация – морфологический разбор слова, приведение к нормальной форме

Стеммер Портера 5 шагов, на каждом применяется правило удаления окончания Первый шаг: Плюс: быстрое получение термина Минус: для многих языков термин плохо воспринимается человеком

Лемматизатор Разбор слова по составу: (как в школе, только автоматически) Крупнейший лемматизатор русского языка: AOT.ru (py_morphy, PHPMorphy, …) Плюсы: получение термина в нормально форме, воспринимаемой человеком Минусы: долго работает

Стоп-слова Стоп-слово – слово, которое встречается во многих текстах, но никак текст не характеризует Примеры: союзы, междометия Запрос: «что делать с трупом он плохо пахнет»

Итог нормализации Термин 23 прят нык … ID терминаID документа и словопозиции 231, 3, 6, , 6, 8, 44 …… ID документассылкаКэш страницы… 1http://... Как пра…… 8https:// …

Нормализация и ранжирование Во время нормализации можно пытаться определить не только термины документа, но и их значимость для него Примеры: Орфографический словарь «Тихий Дон» на одной странице

Нормализация и ранжирование Во время нормализации можно пытаться определить не только термины документа, но и их значимость для него Примеры: Орфографический словарь «Тихий Дон» на одной странице

Документная частота Документная частота – сколько документов содержат данный термин. Определяет насколько термин важен вообще. Чем специфичнее термин, тем меньше документов его содержат Стоп-слова содержат почти все документы

Обратная документная частота Отношение количества документов с термином ко всему количеству документов: Как ведет себя эта функция? Что может происходить с ростом N?

Частота термина Частота термина в документе (term frequency) – отношение количества вхождений термина ко всем терминам. Определяет, насколько важен термин для данного документа

Масштабирование tf Что делать с документом, в котором 20 повторений термина из 100 слов?

Метрика wf-idf Поведение: Максимальное значение, если термин встречается часто в нескольких документах Уменьшается, если термин встречается нечасто и во многих документах («размазан») Минимален, если это стоп-слово, то есть встречается почти в каждом документе

Итоговый вид нормализованного документа Векторная модель документа (VSM) – каждый термин является вектором, направление вектора – термин длина вектора - вес ID терминаID документа, вес, 23(1, 12.4, ), (3, 1, ) … 42(21, 13.5, ), (3, 11.1, ) … ……

Обработка запроса Запрос нужно привести к тому же виду, что и проиндексированные страницы (перевести в термины) Так как запрос значительно меньше текстов документа, можно и нужно применять более сложный анализ

Этапы обработка запроса Исправление опечаток Преобразование в термины Поиск полного набора терминов Разбиение запроса на подзапросы Поиск подзапросов

Исправление опечаток Расстояние редактирования – для случая, когда палец попал на неправильную кнопку или есть 1-2 орфографических ошибок Фонетические исправления – для случая, когда человек не знает, как пишется слово, но знает, как оно звучит (пример: фр. oiseaux)

Расстояние Левенштейна Расстояние редактирования – количество простых операций для превращения одной строки в другую Простые операции: вставка символа удаление символа замена символа другим

Индекс Soundex Кодируем слово в индекс Soundex. Созвучные слова имеют одинаковый индекс. Пример индекса: R163: Rupert, Robert Для русского языка Soundex не доработан. Можно переводить слово в транслит и пользоваться английским

Преобразование запроса Термин 23 прят нык … Термин 41 труп мертв … Запрос спрятатьтруп Документы [23] AND [41] Документы [23] Документы [41] Результаты Ранжирование