Skip to content

Задание для техносферы (индексация)

Notifications You must be signed in to change notification settings

lalkakonus/ts-idx-2016

 
 

Repository files navigation

ДЗ по курсу Инфопоиск (Техносфера)

Дано: дамп lenta.ru (10k документов)

Документы доступны по адресу: https://cloud.mail.ru/public/FnMq/qCNif6bFG/dataset

Для чтения документов используем docreader.py Используем поля .url и .text

Разбор документов на слова лучше организовать с помощью regexp-а r'\w+', см. doc2words.py
Необходимая нормализация: приводим все слова к нижнему регистру.
Лемматизацию и пр. - в этом ДЗ не используем.

Необходимо:

  • Создать индекс
  • Реализовать булев поиск

А конкретно

На оценку 5 (набор - 1.5К документов):

  • имплементировать кодирование varbyte
  • создать словарь термов (в любом виде)
  • разобрать текстовый запрос простого формата (см. далее)
  • вывести подходящие под булев запрос URL-ы

На оценку 10 (10К документов):

Дополнительно к предыдущему:

  • имплементировать метод Simple9

На оценку 15 (100К документов):

Дополнительно к предыдущему:

  • реализовать текстовый запрос полного формата (см. далее)

На оценку 20 (600К документов):

Дополнительно к предыдущему:

  • потоковая обработка дерева запроса
  • обязательно: индекс в бинарном виде
  • обязательно: словарь в бинарном виде (см. 2ю лекцию)

Состав пакета

Помимо исходников на Python Ваш пакет должен содержать 3 .sh-файла:

  • index.sh (varbyte|simple9) path/to/*.gz : создение индекса (сжатие происходит на этом этапе)
  • make_dict.sh: создание словаря и оптимизация индекса
  • search.sh "query": непосредственно поиск
  • [опционально] preinstall.sh: скрипт, в котором вы можете установить необходимые пакеты. Если по каким-то причинам указанные пакеты не устанавливаются или устанавливаются криво, то это ваши проблемы - обходитесь без них.

Вывод (stdout) подразумевается только от утилиты поиска (результаты поиска - см.дальше).

Формат ввода

На stdin searcher.sh будет дана последовательность запросов в виде

запрос #1
запрос #2
...

Форматы запросов:

простой:

присутствуют только термы и конъюнкция ("&")

Пример: власти & бельгии

полный:

Формат каждого запроса - булево выражение содержашее слова и операторы: "(", ")", "&", "|", "!"

Пример: власти & (бельгии | парижа) & !теракт

Гарантируется что запрос валидный

Формат вывода:

ИСХОДНЫЙ ЗАПРОС
КОЛ-ВО результатов
URL1
URL2
...

Пример:
Путин & Медведев
2
https://lenta.ru/news/2015/08/30/putin/
https://lenta.ru/photo/2015/08/30/medput/

Внимание: выводимые url-ы должны быть в порядке возрастания docid!

Куда отправлять код

Код запакованный в .tgz отправляйте на index_infosearch@mail.ru

В теме письма обязательно указывайте вариант (баллы). Формат: idx, Иван Иванов (var: 15). Все Иваны Ивановы будут баниться как люди, которые не умеют читать инструкции.

Как будет происходить проверка

Для проверки будет использоваться набор документов lenta.ru в 10 и 50 раз больше данного.
Ограничение по RAM: 2Gb

Из-за необходимости проверки реализации, оценка не будет автоматической.
После получения оценки от робота, который проверит общую работоспособность вашего кода, пришлите то же самое письмо еще раз со словом FINALTRY в теме. "То же самое" значит, что чексуммы прикрепленных архивов должны совпадать.

Срок сдачи: МГУ: 30 октября 2018 23:59.

FAQ

Q: Почему Python? Если жесткие ограничения, то не лучше ли на C++ ?
A: Python выбран намеренно, чтобы вы не урывались в системные оптимизации и не разбирались с memleak/segfault и т.п., а больше времени потратили бы именно на проработку логики. Ограничения по времени и памяти соответствуют именно Python-варианту.

Q: Нужно ли реализовывать JumpTables ?
A: Нет, этого нет в задании и необходимости для данного кол-ва документов тоже нет. Однако, в свободное премя я настоятельно советую это реализовать т.к. грамотная реализация улучшит ваши навыки декомпозиции кода и, в целом, программирования.

Q: Что если я сдал на вариант на 10 баллов, а после deadline сделаю вариант на 20?
A: К сожалению, вы получите лишь ceil(20 / 2) = 10 баллов. Так что планируйте свое время заранее и не доводите до deadline.

Q: Для чего нужен preinstall.sh?
A: Этот скрипт небходим, если вам нужны дополнительные Python-модули. Но, как правило, достаточно уже предустановленных protobuf, numpy, mmh3

Вопросы?

Пишите на help_infosearch@mail.ru

About

Задание для техносферы (индексация)

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 99.8%
  • Shell 0.2%