ИЗУЧЕНИЕ СТАТИСТИКИ ВСТРЕЧАЕМОСТИ ТЕРМИНОВ И ПАР ТЕРМИНОВ В ТЕКСТАХ ДЛЯ ВЫБОРА МЕТОДОВ СЖАТИЯ ИНВЕРТИРОВАННОГО ФАЙЛА. Губин Максим Вадимович «Информационная компания «Кодекс»
Цель: Выбор алгоритма сжатия инвертированного файла реальной коллекции. План : Изучить статистику распределения данных в пост листах. Выбрать возможные алгоритмы сжатия. Проверить их работоспособность.
Индексирование по парам Улучшение точности поиска Увеличение скорости обработки запроса Дополнительный сервис – подсказки пользователю, расширение запроса и т.д.
Особенности коллекции Относительно большие документы (сред. размер документа тысячи слов) Большой разброс в размерах документов (10 – слов) Много словоформ (коэф. Хипса ~ 1)
Особенности статистики пар Количество растет линейно от N Чаще повторяются в документе, чем в коллекции. На порядок больше слов
Особенности пост листов Основной объем составляют короткие листы
Выбор алгоритма сжатия Классический подход - кодирование дельт не подходит (40-50%).
Предлагаемое решение Объединение пост листов. Заголовок Объединенный пост лист Сжатый дельта + байт код Номера слов, сжатые кодом Хаффмана Коэффициент сжатия – 20-25%
Выводы Реальная статистика значительно отличается от классической Выбор алгоритма сжатия позволяет улучшить сжатие в разы. Индекс по парам может быть сравним с координатным индексом.