Реализуйте mapper первой mapreduce задачи для расчета tf idf с помощью hadoop streaming
No definitions found in this file.
- Go to file T
- Go to line L
- Go to definition R
- Copy path
- Copy permalink
| # coding=utf-8 |
| «»»» |
| Реализуйте mapper первой mapreduce задачи для расчета TF-IDF с помощью |
| Hadoop Streaming. |
| Формат входных данных следующий: каждая строка содержит номер документа и |
| строку из него, разделенные «:». Ключ выходных данных является составным: |
| он содержит слово документа и его номер, разделенные «#». |
| Слово в документе — последовательность символов (букв или цифр), не содержащая |
| пробельных символов и знаков пунктуации. |
| Sample Input: |
| 1:aut Caesar aut nihil |
| 1:aut aut |
| 2:de mortuis aut bene aut nihil |
| Sample Output: |
| aut#1 1 |
| Caesar#1 1 |
| aut#1 1 |
| nihil#1 1 |
| aut#1 1 |
| aut#1 1 |
| de#2 1 |
| mortuis#2 1 |
| aut#2 1 |
| bene#2 1 |
| aut#2 1 |
| nihil#2 1 |
| «»» |
| import sys |
| import re |
| for line in sys . stdin : |
| num , text = line . strip (). split ( ‘:’ , 1 ) |
| for word in re . findall ( r'[\w]+’ , text ): |
| print ( ‘%s#%s \t 1’ % ( word , num )) |
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Источник
Реализуйте mapper первой mapreduce задачи для расчета tf idf с помощью hadoop streaming
Failed to load latest commit information.
README.md
01 Баланс скобок.
02 Определить высоту небинарного дерева.
03 Симулятор обработки сетевых пакетов.
04 Стек с поддержкой максимума.
05 Максимум в скользящем окне.
06 Построение кучи.
07 Телефонная книга.
01 Вычисление числа Фибоначчи.
02 Вычисление последнего числа n-ого числа Фибоначчи.
03 Нахождение наибольшего общего делителя.
04 Покрытие отрезков точками.
05 Задача о непрерывном рюкзаке.
06 Кодирование Хаффмана.
07 Декодирование Хаффмана.
08 Очередь с приоритетами на основе двоичной кучи.
09 Наибольшая последовательнократная подпоследовательность.
01 Переворот односвязного списка.
02 XML-документ.
03 Longest common substring.
01 Сортировка двумерного массива вставками.
02 Подсчет количества инверсий в массиве с помощью алгоритма сортировки слиянием.
03 Реализация работы стека.
04 Реализация работы очереди.
05 Нахождение высоты дерева поиска.
06 Удаление поддеревьев в дереве поиска.
07 Определение баланса для каждого из узлов АВЛ-дерева.
01 Max of two integers arguments.
02 Next even number.
03 Lambda expression that accepts seven string arguments and returns a string in upper case concatenated from all of them.
04 Production of all numbers in the range.
05 A lambda expression that accepts a list of strings.
06 A lambda expression with using closure (calculating).
07 A lambda expression with using closure (that adds prefix and suffix to the string).
08 Behaviour parametrization with lambda expressions.
09 Functional interfaces.
10 Composing predicates.
11 Checking if a number is prime.
12 Bad words detecting.
13 Numbers filtering.
14 Calculating a factorial.
15 The sum of odd numbers.
16 The general number of employees.
17 The total sum of canceled transactions.
18 Collectors in practice: the product of squares.
19 Collectors in practice: partitioning words into groups.
20 The total sum of transactions by each account.
21 Click count.
22 Parallel filtering of prime numbers.
23 Currying functions 1.
24 Currying functions 2.
25 Optional in action.
00 Hello World.
01 Data Types.
02 Operators.
03 Intro to Conditional Statements.
04 Class vs. Instance.
05 Loops.
06 Let’s Review.
07 Arrays.
08 Dictionaries and Maps.
09 Recursion.
10 Binary Numbers.
11 2D Arrays.
12 Inheritance.
13 Abstract Classes.
14 Scope.
15 Linked List.
16 Exceptions — String to Integer.
17 More Exceptions.
18 Queues and Stacks.
19 Interfaces.
20 Sorting.
21 Generics.
22 Binary Search Trees.
23 BST Level-Order Traversal.
24 More Linked Lists.
25 Running Time and Complexity.
26 Nested Logic.
27 Testing.
28 RegEx, Patterns, and Intro to Databases.
29 Bitwise AND.
01 Напишите программу, которая реализует mapper для задачи WordCount в Hadoop Streaming.
02 Напишите программу, которая реализует reducer для задачи WordCount в Hadoop Streaming.
03 Напишите программу, которая реализует In-mapper combining v.1 для задачи WordCount в Hadoop Streaming.
04 Напишите программу, которая реализует In-mapper combining v.2 для задачи WordCount в Hadoop Streaming.
05 Реализуйте reducer в задаче подсчета среднего времени, проведенного пользователем на странице.
06 Реализуйте Combiner в задаче подсчета среднего времени, проведенного пользователем на странице.
07 Реализуйте mapper из фазы 1 задачи Distinct Values v1.
08 Реализуйте reducer из фазы 1 задачи Distinct Values v1.
09 Реализуйте mapper из фазы 2 задачи Distinct Values v1.
10 Реализуйте reducer из задачи Distinct Values v2.
11 Реализуйте mapper для задачи Cross-Correlation, который для каждого кортежа создает все пары элементов, входящих в него.
12 Реализуйте mapper для задачи Cross-Correlation, который для каждого объекта из кортежа создает stripe.
13 Напишите mapper с помощью Hadoop Streaming, печатающий только те строки из файла, которые соответствуют пользователю user10.
14 Напишите mapper с помощью Hadoop Streaming, печатающий URL из каждой строки.
15 Напишите reducer, который объединяет элементы из множества A и B.
16 Напишите reducer, который делает пересечение элементов из множества A и B.
17 Напишите reducer, который делает вычитание элементов множества B из множества A.
18 Напишите reducer, который реализует симметричную разность множеств A и B.
19 Напишите reducer, реализующий объединение двух файлов (Join) по id пользователя.
20 Реализуйте mapper первой mapreduce задачи для расчета TF-IDF с помощью Hadoop Streaming.
21 Реализуйте reducer первой mapreduce задачи для расчета TF-IDF с помощью Hadoop Streaming.
22 Реализуйте mapper второй mapreduce задачи для расчета TF-IDF с помощью Hadoop Streaming.
23 Реализуйте reducer второй mapreduce задачи для расчета TF-IDF с помощью Hadoop Streaming.
01 Реализуйте метод, возвращающий ответ на вопрос: правда ли, что a + b = c? Допустимая погрешность – 0.0001 (1E-4)
02 Реализуйте метод flipBit, изменяющий значение одного бита заданного целого числа на противоположное.
03 Реализуйте метод, который возвращает букву, стоящую в таблице UNICODE после символа «» (обратный слэш) на расстоянии a.
04 Реализуйте метод, проверяющий, является ли заданное число по абсолютной величине степенью двойки.
05 Реализуйте метод, проверяющий, является ли заданная строка палиндромом. Палиндромом называется строка, которая читается одинаково слева направо и справа налево (в том числе пустая). При определении «палиндромности» строки должны учитываться только буквы и цифры. А пробелы, знаки препинания, а также регистр символов должны игнорироваться. Гарантируется, что в метод попадают только строки, состоящие из символов ASCII (цифры, латинские буквы, знаки препинания). Т.е. русских, китайских и прочих экзотических символов в строке не будет.
06 Реализуйте метод, вычисляющий факториал заданного натурального числа.
07 Реализуйте метод, сливающий два отсортированных по неубыванию массива чисел в один отсортированный в том же порядке массив. Массивы могут быть любой длины, в том числе нулевой.
08 Вам дан список ролей и сценарий пьесы в виде массива строчек. Напишите метод, который будет группировать строчки по ролям, пронумеровывать их и возвращать результат в виде готового текста.
09 Привести робота в заданную точку игрового поля.
10 Дан класс ComplexNumber. Переопределите в нем методы equals() и hashCode() так, чтобы equals() сравнивал экземпляры ComplexNumber по содержимому полей re и im, а hashCode() был бы согласованным с реализацией equals().
11 Реализуйте метод, выполняющий численное интегрирование заданной функции на заданном интервале по формуле левых прямоугольников.
12 Напишите класс AsciiCharSequence, реализующий компактное хранение последовательности ASCII-символов (их коды влезают в один байт) в массиве байт.
13 Реализуйте метод sqrt(), вычисляющий квадратный корень числа.
14 Реализуйте метод, позволяющий другим методам узнать, откуда их вызвали.
15 Реализовать метод который устанавливает соединение с роботом, отдает ему команду на перемещение в заданную точку и затем закрывает соединение, выполняя при необходимости повтор этой последовательности до трех раз.
16 Напишите метод, читающий входной поток и вычисляющий контрольную сумму прочитанных данных.
17 Реализуйте generic-класс Pair, похожий на Optional, но содержащий пару элементов разных типов и не запрещающий элементам принимать значение null.
18 Реализуйте метод, вычисляющий симметрическую разность двух множеств.
Источник
Map/Reduce: решение реальных задач — TF-IDF
Вчера я задал вопрос в своем ХабраБлоге — интересно ли людям узнать, что такое Hadoop с точки зрения его реального применения? Оказалось, интересно. Дело недолгое — статью я написал довольно быстро (по крайней мере, ее первую часть) — как минимум, потому, что уже давно знал, о чем собираюсь написать (потому как еще неплохо помню как я сам тыкался в поиске информации, когда начинал пользоваться Hadoop). В первой статье речь пойдет об основах — но совсем не о тех, про которые обычно рассказывают 🙂
Перед прочтением статьи я настоятельно рекомендую изучить как минимум первый и последний источники из списка для чтения — их понимание или хотя бы прочтение практически гарантирует, что статья будет понята без проблем. Ну что, поехали?
Что такое Hadoop?
Ну скажите, какой смысл об этом писать? Уже не раз это проговаривалось, неоднократно начинали писаться посты на тему Hadoop, HDFS и прочая. К сожалению, обычно все заканчивалось на довольно пространном введении и фразе “Продолжение следует”. Так вот: это — продолжение. Кому-то тема, затрагиваемая в этой статье может показаться совершенно тривиальной и неинтересной, однако же лиха беда начало — любые сложные задачи надо решать по частям. Это утверждение, в частности, мы и реализуем в ходе статьи. Сразу замечу, что я постараюсь избежать написания кода в рамках этой конкретной статьи — это может подождать, а понять принципы построения программ, работающих с Map/Reduce можно и “на кошках” (к тому же с текущей частотой кардинального изменения API Hadoop любой код становится obsolete примерно через месяц).
Когда я начинал разбираться с Хадупом, очень большой сложностью лично для меня стало первоначальное понимание идеологии Map/Reduce (я предпочитаю писать это словосочетание именно так, чтобы подчеркнуть, что речь идет не о продукте, а о принципе). Суть и ценность метода станет понятна в самом конце — после того, как мы решим несложную задачу.
- Количество слов в корпусе
- Количество терминов в корпусе (под термином здесь и далее я буду понимать уникальное слово-токен)
- Количество документов в корпусе
- Сколько раз каждый термин встречается в каждом документе
- Сколько документов содержит каждый термин.
Скажем прямо — задача несложная и решается в лоб довольно просто — не думаю, что у вас займет больше получаса написать такую программу. Все становится несколько сложнее, если текста становится больше, количество слов растет неограниченно, количество терминов приближается к количеству слов в языке текста, и словари перестают помещаться в памяти. Самое время вспомнить, что первейший принцип не только разработки сложного ПО, но и вообще решения проблем, был сформулирован уже довольно-таки давно и формулируется как “разделяй и властвуй”. Итак, разделим задачу на составные элементы.
Для начала сделаем допущение (для упрощения, а позже мы рассмотрим как решать эту задачу в более общем случае) что наши входные данные представлены в формате текстового файла с очень простой структурой:
Иными словами, каждый документ — это набор слов, которые возможно (и вполне вероятно) повторяются, и каждый такой набор слов расположен на одной строке текстового файла. Допущение это небольшое — практически каждый документ может быть представлен в таком виде.
Подсчет количества слов в корпусе — задача простая, и решается в линейное время, однако, возможно, ее даже не придется решать отдельно. То же самое касается и количества терминов — они посчитаются сами. Самая интересная задача на этом этапе — посчитать, сколько раз каждый термин встречается в корпусе текста.
Да-да, вы не ошибаетесь, это именно она — самая популярная и замученная уже всеми задача, первый пример в каждом руководстве по Hadoop — программа WordCount. Она настолько популярна, насколько же и проста — я даже не буду приводить ее здесь, ее можно посмотреть в официальном tutorial’е Хадупа. Если очень кратко, то на map-шаге программа формирует следующие пары:
На reduce-шаге каждый reduce-task получает ключ (то есть , и так далее) и список всех значений ассоциированных с этим ключем, полученных из всех map-задач (в данном случае — просто список единиц). Это будет выглядеть как:
Суммируя эти единицы (а по факту — просто считая количество элементов в списке) мы получаем количество вхождений каждого термина в корпус:
Это уже что-то, хотя ценность этих данных неочевидна. Однако простой подсчет количества строк в результирующем файле дает нам количество уникальных терминов. А суммируя все значения из второй колонки мы получаем общее количество токенов. Вроде бы ничего и не сделали — а уже получили несколько фундаментальных характеристик корпуса.
Дальше начинается классика information retrieval. Для начала на основе результатов работы WordCount мы строим словарь — то есть общий список терминов корпуса. Наша следующая задача — установить, как часто и какие именно термины словаря встречаются в каждом из документов. Для этого мы реализуем уже немного модифицированный вариант WordCount , который считает количество терминов применимо к конкретному документу. Наверное, самый простой способ добиться этого — это использовать в результатах map-задач ключ, состоящий из идентификатора документа (входной ключ mapper’а) и термина:
Reduce для этой задачи будет идентичен классическому WordCount — он будет просто суммировать значения с одинаковым ключем. В результате мы получим:
Так что же у нас получилось? А получилась у нас так называемая частота терминов — которую гораздо лучше знают как term frequency, сокращенно — tf(t,d) (здесь t и d означают, что значение считается применимо к конкретному документу и конкретному термину). К примеру, в статье про Лондон значение tf для слова london будет, вероятно, выше, чем в статье про свиноводство (а возможно, будет равным нулю — нулевая частота это тоже частота). Вероятно, надо заметить, что у нас получился ненормализованный вариант этой характеристики, для нормализации полученные значения следует разделить на общее количество токенов в корпусе.
В рамках нашего примера мы разработали алгоритм вычисления одной из наиболее популярных статистических характеристик в information retrieval. Ценность данного метода в том, что он может быть расширен на корпус практически любого размера — и это можно будет посчитать даже на одной машине (а можно без дополнительных усилий распараллелить на кластер в полторы-две тысячи нодов). Таким образом, ответ на вопрос, сформулированный в самом начале статьи звучит так: идеология Map/Reduce позволяет разбить вычислительно сложную задачу на маленькие блоки, которые можно посчитать отдельно, после чего объединить результаты. Эти блоки могут считаться параллельно, могут — последовательно и это не имеет никакого значения: суть в том, что мы превратили одну крайне ресурсоемкую задачу в большое количество задач, каждая из которых может быть решена на вашем домашнем компьютере.
Пожалуй, здесь мне все-таки следует произнести сакральную фразу — “Продолжение следует”. В следующем посте мы рассмотрим расчет второй части tf-idf — а именно, inverse document frequency, после чего плавно перейдем к решению этой задачи для реального большого (никому мало не покажется) набора данных.
P.S. Маленькое примечание, которое мне показалось важным: при написании русской версии статьи (а она изначально писалась практически параллельно на двух языках) я старался писать настолько по-русски, насколько это только возможно, однако я не переводил многие устойчивые сочетания (такие как Map/Reduce) и даже не пытался перевести названия фаз этого процесса, оттуда появились map-таски и reduce-таски. К сожалению, русская терминология не вполне устоялась применимо к этому предмету, но великий и могучий настолько велик и могуч, что любой школьник может просклонять слово “таск” по падежам — не говоря уж о программистах, которые и представляют собой целевую аудиторию этого поста.
Если вам показалось что-то непонятным — пожалуйста, пишите. После того, как долго работаешь в какой-то сфере, мозги до какой-то степени “замыливаются” и многие вещи воспринимаешь как само собой разумеющееся. Если где-то это имело место быть — напишите, и я исправлюсь.
Список литературы для домашнего чтения:
- Yahoo! Hadoop Tutorial — рекомендую прочитать первым, потому что лучше документации на данный момент просто нет, включая официальный сайт.
- Hadoop QuickStart Guide
- Hadoop Map/Reduce Tutorial
- Hadoop and Distributed Computing at Yahoo!
- Term frequency-inverse document frequency — статья в Wikipedia.
Оригинал фотографии был опубликован по лицензии Creative Commons: www.flickr.com/photos/antichrist/3427853501
Update: поскольку НЛО временно отключило возможность создавать новые блоги, опубликовал в алгоритмах — в конце концов, Hadoop это далеко не единственная реализация Map/Reduce, а ни одной строчки кода здесь нет. Когда НЛО смилостивится, создам блог Hadoop и перенесу туда вместе с новыми статьями, которые сейчас пишутся.
Update 2: я же сказал, что продолжение следует? Ну так вот оно — это самое продолжение — читайте и комментируйте!
Источник
