Searcher_sphere

Запуск

Для тестов

  make test

Для использования

  make main
  ./main

Короткий/Полный запуск

При первом запуске нужно создать индекса с нуля. Если файлы со словарем и url уже созданы то не нужно строить индекс с нуля.

Запрос

В запросе каждый после каждого токена должен идти пробел (в конце тоже). Токеными являются слова, &, |, (, ).

  Яблоко | ( Путин & Обама ) 

Скобочная последовательность должна быть правильной.

Информация об обратном индексе

Index have 10015 urls
Index have 311613 words
Index size is 14687800 bytes
Index have compressed Index
Compressed Index size is 2704872 bytes

Размер после сжатия уменьшился ~6 раз. Использовался varbyte и кодировались разница между последовательными элементами отсортированного массива.

  a > 0, b > a => b - a < b

Вследствии этого требовалось кодировать меньшие числа

Поиск

Были реализованы naive и stream search. Для

Naive search
Time total: 0.000005
1) http://lenta.ru/articles/2002/08/06/bancrupt
2) http://lenta.ru/news/2005/03/16/business/
3) http://lenta.ru/news/2013/09/30/sign1/
4) http://lenta.ru/news/2008/02/12/putin/
5) http://lenta.ru/news/2015/04/23/putin

Stream search
Time total: 0.000037
1) http://lenta.ru/articles/2002/08/06/bancrupt
2) http://lenta.ru/news/2005/03/16/business/
3) http://lenta.ru/news/2013/09/30/sign1/
4) http://lenta.ru/news/2008/02/12/putin/
5) http://lenta.ru/news/2015/04/23/putin

Хоть на таких коротких запросах разница практически не заметна иногда даже медленнее, но на длинных векторах засчёт бин поиска и потоковой обработки работает быстрее

Выводы

varbyte достаточно быстрый и эффективный, что позволяет использовать его при каждом обращение к индексу

потоковая обработка требует меньше памяти и работает быстрее.

P.s В моей реализации в Node храниться vector, а не указатель на вектор, но не думаю что это отразится на сути алгоритма, но копирование вектора естественно замедляет код