ИЗУЧЕНИЕ СТАТИСТИКИ ВСТРЕЧАЕМОСТИ ТЕРМИНОВ И ПАР ТЕРМИНОВ В ТЕКСТАХ ДЛЯ ВЫБОРА МЕТОДОВ СЖАТИЯ ИНВЕРТИРОВАННОГО ФАЙЛА. Губин Максим Вадимович «Информационная. - презентация

1 ИЗУЧЕНИЕ СТАТИСТИКИ ВСТРЕЧАЕМОСТИ ТЕРМИНОВ И ПАР ТЕРМИНОВ В ТЕКСТАХ ДЛЯ ВЫБОРА МЕТОДОВ СЖАТИЯ ИНВЕРТИРОВАННОГО ФАЙЛА. Губин Максим Вадимович «Информационная компания «Кодекс»

2 Цель: Выбор алгоритма сжатия инвертированного файла реальной коллекции. План : Изучить статистику распределения данных в пост листах. Выбрать возможные алгоритмы сжатия. Проверить их работоспособность.

3 Индексирование по парам Улучшение точности поиска Увеличение скорости обработки запроса Дополнительный сервис – подсказки пользователю, расширение запроса и т.д.

4 Особенности коллекции Относительно большие документы (сред. размер документа тысячи слов) Большой разброс в размерах документов (10 – слов) Много словоформ (коэф. Хипса ~ 1)

5 Особенности статистики пар Количество растет линейно от N Чаще повторяются в документе, чем в коллекции. На порядок больше слов

6 Особенности пост листов Основной объем составляют короткие листы

7 Выбор алгоритма сжатия Классический подход - кодирование дельт не подходит (40-50%).

8 Предлагаемое решение Объединение пост листов. Заголовок Объединенный пост лист Сжатый дельта + байт код Номера слов, сжатые кодом Хаффмана Коэффициент сжатия – 20-25%

9 Выводы Реальная статистика значительно отличается от классической Выбор алгоритма сжатия позволяет улучшить сжатие в разы. Индекс по парам может быть сравним с координатным индексом.