задача 2

Постановка задачи
Построить инвертированные индексы для русской и английской Википедий.
Индекс должен состоять из строк вида word \t docid1:tfidf1 \t docid2:tfidf2 …, где word - слово, docid - идентификатор статьи, tfidf - значение меры TD-IDF (https://ru.wikipedia.org/wiki/TF-IDF) для пары слово-статья, \t - символ табуляции (пробелов вокруг него быть не должно).
Для каждого слова должно быть включено 20 наиболее релевантных статей в порядке убывания их TF-IDF. При равных значениях TF-IDF статьи должны располагаться в порядке возрастания docid.
При построении индекса следует игнорировать 20 наиболее часто встречающихся в текстах статей слов, используя предварительно вычисленный список данных слов.
Требования к парсингу слов минимальные. Обязательно только отбрасывание знаков пунктуации и приведение к нижнему регистру. Для простоты в тексте русской Википедии можно вообще оставлять только кириллические символы, а в английской - латинские. Приведение слов к нормальной форме не требуется.
Дополнительно требуется минимизировать время построения индекса и обеспечить масштабируемость реализации, то есть возможность эффективно обрабатывать данные большего объема и использовать большее число машин.
Для решения следует использовать Hadoop MapReduce. Программы могут быть реализованы на Python (Hadoop Streaming) или Java. Полученные индексы должны быть сохранены в HDFS в отдельных директориях в описанном формате.
Исходные данные
Путь к данным в HDFS:
/data/wiki/ru/articles - русская Википедия (~5 GB)
/data/wiki/en/articles - английская Википедия (~12 GB)
Данные состоят из строк вида docid \t content, где docid - идентификатор статьи, content - название и текст статьи (с убранной вики-разметкой), \t - символ табуляции (пробелов вокруг него быть не должно).
Не запускайте свою программу сразу на всех данных. Сначала попробуйте подать на вход кусочек данных для отладки (~70-80 MB):
/data/wiki/ru/articles-part
/data/wiki/en/articles-part
Тестирование решений
Для запуска MapReduce-программ на кластере следует использовать сервисы Hadoop MapReduce (Streaming) и Hadoop MapReduce (Java) (или альтернативный вариант - командная строка кластера). Данный сервис не выполняет запуск программ, а только проверяет полученные результаты. Для этого сервису необходимо передать пути к директориям с построенными индексами в HDFS.
Ссылки для запуска и логин, пароль для входа я предоставлю.
Выполняются следующие проверки:
Соответствие формата индекса требованиям задачи
Отсутствие в индексе знаков пунктуации и заглавных букв
Отсутствие в индексе высокочастотных слов вроде "the" и "в"
Соответствие эталонному индексу (сравниваются наиболее релевантные статьи для определенных слов, значения TF-IDF не учитываются)
Время выполнения тестов - несколько минут.
Контрольные вопросы
1. Опишите свое решение. Какие MapReduce-программы запускаются, что каждая из них делает, как реализованы map и reduce?
2. Какие из рассмотренных на занятиях приемов, оптимизаций и стратегий для MapReduce-программ вы использовали в своем решении? Почему?
3. Какое число редьюсеров используется для каждого из запусков? Почему?
4. Насколько хорошо ваше решение будет масштабироваться в случае многократного роста объема входных данных? Не станут ли какие-то этапы узким местом? Нет ли риска переполнения памяти?
Требования к отчету
Отчет должен содержать:
Описание решения и ответы на контрольные вопросы.
Ссылки на все запуски программ (задания Everest), выполненные для получения требуемых результатов.
В случае запусков через командную строку кластера, надо включить в отчет полные команды запусков и ссылки на соответствующие задания в веб-интерфейсе YARN вида http://hadoop2-10.yandex.ru:8088/cluster/app/application_ID.
Прикрепленный исходный код программ, в случае если он не доступен по ссылкам на задания Everest (например, в случае посылки jar-файла чере