MapReduce: более продвинутые примеры, попробуем без зауми

    Чтобы не откладывать в долгий ящик сразу порассказываю несколько других примеров для MapReduce, обещанные в топике "MapReduce без зауми". (Если не понимаете полностью что такое MapReduce — прочитайте тот топик сначала! Без него не разберетесь)

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

    Однако тема сама по себе сложная и все же напрячь мозги придется. Когда поймете — будет очень просто.

    Входящие ссылки


    Допустим у нас есть Интернет. В Интернете есть исходящие ссылки.

    Допустим на входе у нас есть такие данные об ИСХОДЯЩИХ ссылках, собранные нашим паучком:

    habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com, yandex.ru
    thematicmedia.ru -> habrahabr.ru, autokadabra.ru
    autokadabra.ru -> habrahabr.ru, yandex.ru


    Т.е. мы знаем, что Хабр ссылается на Apple, MS, Ubuntu и Яндекс но кто ссылается на Хабр? Да, вопрос примитивный, но все же разложим на MapReduce. Дальше будет интереснее и этот пример понадобится.

    Шаг «Map» (который мы пишем сами) делает следующее:
    (Еще разок — если не понимаете о чем речь — прочитайте "MapReduce без зауми").

    Все что в примерах идет после "//" — это комментарий, только поясняет откуда взялось, к MapReduce не имеет прямого отношения.

    map("habrahabr.ru -> thematicmedia.ru, apple.ru, microsoft.com, ubuntu.com") ->
    ["thematicmedia.ru", "habrahabr.ru"] // на thematicmedia.ru ВХОДИТ ссылка с habrahabr.ru
    ["apple.ru", "habrahabr.ru"]
    .....


    map("thematicmedia.ru -> habrahabr.ru, autokadabra.ru") ->
    ["habrahabr.ru", "thematicmedia.ru"]
    ["autokadabra.ru", "thematicmedia.ru"]
    ....


    Шаг «Reduce» не делает ничего, поскольку на входе мы уже получим такое:

    ["autokadabra.ru", ["thematicmedia.ru"]]
    ["habrahabr.ru", ["thematicmedia.ru", "autokadabra.ru"]] <-- то, что мы искали
    ....


    Вот и ответ — ВХОДЯЩИЕ ссылки.

    Какие сайты дают ТИЦ или PageRank?


    Аааа, ТИЦ, священный грааль торговли ссылками (circa 2010). Возьмем некую условную единицу рейтинга и назовем ее MegaRank (это может быть ТИЦ, может быть PageRank и т.п. — разницы нет).

    Предположим такую теорию — у каждого сайта есть определенный MegaRank, который он «передает» в каком-то количестве, либо «не передает» и вообще «убивает» MegaRank. Мы знаем только MegaRank конечных сайтов, как узнать кто из начальных сколько MegaRankа передает?

    Опять имеем начальные данные сайт А имеет MegaRank 100 и входящие ссылки с сайтов B,C,D. Сайт B имеет MegaRank 0 (предполагаем что MegaRank «убит» плохими ссылками, поскольку не можем исключить эту теорию) и имеет входящие ссылки с сайтов A,D,E,F и так далее…

    Разложим задачу так: Сайт А что-то получил от B,C,D, что стало равняться 100. Будем считать что каждый из B,C,D дал сайту A по 33 единицы MegaRank. Сайт B имеет убитый MegaRank, будем считать что его MegaRank = -500, а не нулю. Таким образом мы постараемся сильно занизить тех, кто «убивает» MegaRank (допустим это сайт A, на котором плохая реклама и он занижен поисковиками). Получается что каждый из сайтов A,D,E,F дал по -500/4 = -125 единиц MegaRank'а сайту B.

    Как посчитать входящие ссылки по исходящим — я выше уже описал, будем считать что это мы уже сделали…

    Итак, имеем входные данные:

    A (100) <- B,C,D // на сайт А с MegaRank=100 ссылаются сайты B,C,D
    B (-500) <- A,D,E


    Наш «Map» делает следующее:

    A (100) < — B,C,D:
    B, 100/3 = 33 // сайт B передает 33 едининцы MegaRank исходя из ссылки с сайта B на сайт A
    C, 33
    D, 33


    B (-500) < — A,D,E,F:
    A, -500/4 = -125
    D, -125
    E, -125
    F, -125


    На шаг Reduce приходит:

    A (-125) // в среднем ссылка с сайта "А" даст -125 единиц MegaRank
    B (33)
    C (33)
    D (33, -125) // в среднем ссылка с сайта "D" даст 33-125 = -92 единиц MegaRank
    E (-125)
    F (-125)


    Reduce опять складывает все, получаем, что A — самый негодный сайт, как и E,F, которые в отсутствии других данных действительно ссылаются только на сайт с обнуленным MegaRank. А вот D, несмотря на то, что ссылается и на A и на B — «подозрительный», но лучше, чем просто A.

    Теперь мы можем их выстроить в порядке убывания передаваемого MegaRank примером из MapReduce без зауми (сортировка по популярности).

    Этот пример куда лучше показывает зачем нужен MapReduce — мы можем анализировать одновременно миллионы сайтов по миллиардам ссылок и на напороться на проблему ограниченной памяти даже на одной машине, и присоединить другие машины для большей параллельной мощности.

    (И прежде чем Вы побежите спрашивать — да, проверял теорию на ТИЦе, да, работает :) мне просто этот ТИЦ без интереса как-то).

    Таким образом — имея только данные об исходящих ссылках с сайтов и некий параметр (ТИЦ, PageRank) сайтов, на которые эти ссылки направлены — мы можем найти те сайты, которые хорошо передают этот параметр.

    Процент населения в городах


    Допустим у нас есть информация по районам городов, что в районе Gdetto города Gorod1 живет 150 русских, 190 белорусов, 3 удмурта, а в районе Tutto города Gorod1 живут 3 русских, 5 белорусов.

    Теперь наша задача состоит в том, чтобы посчитать процент населения в городах (мы знаем в районах этих городов). Проблема? Районов миллионы, данные не сгруппированы по городам и все вместе не влезет в память…

    Очень просто на MapReduce:

    «Map»:

    map("в районе Gdetto города Gorod1 живет 150 русских, 190 белорусов, 3 удмурта") ->
    "gorod1", [ (150, "русский"), (190, "белорус"), (3, "удмурт") ]

    map("в районе Tutto города Gorod1 живут 3 русских, 5 белорусов") ->
    "gorod1", [ (3, "русский"), (5, "белорус") ]

    map("в районе Butto города Gorod2 живут 1 русский") ->
    "gorod2", [ (1, "русский") ]

    «Reduce»:

    На входе:
    "gorod1", [ (150, "русский"), (190, "белорус"), (3, "удмурт"), (3, "русский"), (5, "белорус") ]
    // обратите внимание, что некоторые национальности повторяются - это надо будет учесть при сложении
    "gorod2", [ (1, "русский") ]


    Думаю, что очевидно, что дальше просто можно сложить эти значения, которые вполне влезут уже в память и поделить на сумму человек в каждом городе.

    Еще один вариант как это можно сделать — можете додумать сами.

    У кого с кем хотя бы два общих друга?


    Допустим A, B, C, D, E — выдуманные 30 миллионов пользователей социальной сети ПальцамиВРозетке. Допустим мы знаем что:

    А дружит с B, D, E
    B дружит с A, D, E
    C дружит с B, E


    Как нам найти у кого из них есть хотя бы два общих друга?

    Очень просто на (догадайтесь?) MapReduce. Берем перебором каждую пару друзей для каждого человека и ставим на первое место.

    «Map»:

    (B,D), A // у человека "А" есть в контактах пара друзей "человек B и человек D"
    (B,E), A
    (D,E), A
    (A,D), B
    (A,E), B
    (D,E), B
    (B,E), C


    «Reduce» получает (и ничего не делает, кроме как отбирает все строки в которых второй элемент имеет несколько значений):

    (A,D), (B) // пара друзей "A,D" только у человека "B" встречается
    (A,E), (B)
    (B,D), (A)
    (B,E), (A,C) <-- ответ - пара друзей "B,E" встречается у "А" и у "С"
    (D,E), (A,B) <-- ответ


    Ответ:

    A и C имеют общих друзей B, E
    A и B имеют общих друзей D, E

    Ахтунг! Алгортим O(n2), что для тех кто в танке — значит, что при большом объеме входных данных имеет хорошие шансы закончить работу чуть раньше, чем погаснет солнце. На самом деле, конечно раньше, но квадратичные алгоритмы — это плохо.

    Найти нишевые тематики в ключевых словах


    Допустим у нас есть некоторые ключевые слова:

    кофеварки бабрабабр
    кофеварки
    миля
    ворота
    ворота гаражные
    ворота бабрабабр
    кофеварки


    Допустим мы хотим среди них выделить то, о чем можно бы писать. Такой «нишевой» тематикой можно считать нечто, что имеет хотя бы пару разных ключевых слов с участием этого слова и сами по себе являются ключевым словом. Например «кофеварки» — это тематика, потому что «кофеварки» и «кофеварки бабрабабр», а вот «гаражные» — это не ниша, потому что сами по себе не являются ключевым словом. «Миля» тоже не «ниша», потому что не имеет разных ключевых слов, кроме себя. Ну как? Готовы посчитать это без MapReduce? :)

    А это очень просто. Берем каждую строку и разбиваем на слова (лучше на н-граммы, но это уже сами). Для каждой из них выдаем «FULL», если это слово занимает всю строку, или «PART» если занимает только часть. Т.е. из примера выше:

    «Map»:

    кофеварки, PART // получилось из "кофеварки бабрабабр"
    бабрабабр, PART // получилось из "кофеварки бабрабабр"
    кофеварки, FULL // получилось из "кофеварки"
    миля, FULL
    ворота, FULL
    ворота, PART
    гаражные, PART
    ворота, PART
    бабрабабр, FULL
    кофеварки, FULL


    «Reduce» на вход получает:

    бабрабабр, (PART, FULL)
    ворота, (FULL, PART, PART)
    гаражные, (PART)
    кофеварки, (PART, FULL, FULL)
    миля, (FULL)


    Теперь просто смотрим где есть и PART и FULL: «бабрабабр», «ворота» и «кофеварки» — то, что мы искали — наши «ниши».

    Поиск слов-псевдо-синонимов


    Допустим у нас есть Интернет. Допустим там встречается много фраз, но среди них мы замечаем что есть такие фразы как «купил большой компьютер», «купил дорогой компьютер»… Тут мы задумываемся, что «дорогой» и «большой» — это псевдо-синонимы. Нам они нужны, чтобы делать плохосайт и зарабатывать WebCash, пока поисковая система Gotoooo не выкинет наш плохосайт.

    Проблема в том, что тут слов-то миллиарды, памяти не хватит. Да и может оказаться «купил вчера компьютер», а «вчера» — совсем не «большой» и вообще оно тут случайно один раз затесалось… Что же делать? Какой же алгоритм использовать (ладно-ладно, уберите камни, я знаю что вы уже все догадались). Поехали!

    Входные данные берем текст и прямо по порядку выбираем из него по три слова, для интереса оставлю только то, что нужно:
    "купил большой комп"
    "купил вчера комп"
    "купил дорогой комп"
    "видел большой автомобиль"
    "видел дорогой автомобиль"


    Этап 1 (нам нужен будет каскад из двух этапов):

    «Map»:

    "купил * комп", "большой" // получилось из "купил большой комп"
    "купил * комп", "вчера" // получилось из "купил вчера комп"
    "купил * комп", "дорогой"
    "видел * автомобиль", "большой"
    "видел * автомобиль", "дорогой"


    Звездочка — это просто символ звездочка, что значит «любое слово тут», чтобы Reduce пришло вот такое:

    "купил * комп", ["большой", "вчера", "дорогой"]
    // между словами "купил" и "комп" встречаются эти три слова

    "видел * автомобиль", ["большой", "дорогой"]


    «Reduce» ничего не делает.

    Этап 2 (каскада):

    «Map» — на вход получает то, что написано чуть выше, а выдает пары перебором из вторых значений ([«большой», «вчера», «дорогой»]):

    большой, вчера // получилось из ["большой", "вчера", "дорогой"]
    вчера, большой // получилось из ["большой", "вчера", "дорогой"]
    большой, дорогой // получилось из ["большой", "вчера", "дорогой"]
    дорогой, большой // получилось из ["большой", "вчера", "дорогой"]
    вчера, дорогой // получилось из ["большой", "вчера", "дорогой"]
    дорогой, вчера // получилось из ["большой", "вчера", "дорогой"]

    большой, дорогой // получилось из ["большой", "дорогой"]
    дорогой, большой // получилось из ["большой", "дорогой"]


    На Reduce они придут как:

    большой, (вчера, дорогой, дорогой)
    вчера, (большой, дорогой)
    дорогой, (большой, дорогой, большой)


    Не обращайте внимания что где-то кавычки есть, где-то нет — тайного смысла в этом нет, просто где-то поставил, где-то — нет.

    Теперь «Reduce» остается только посчитать слова в скобках (второй элемент его аргумента), что вполне влезет в память и откинуть те элементы, что встречаются только один раз:

    большой - дорогой(2) // "большой" является псевдо-синонимом "дорогой", подтверждено 2 случаями
    дорогой - большой(2)


    Ахтунг! Сложность O(n2) снова!

    JOIN


    Допустим мы имеем уже два MapReduce, которые нам надо объединить. Допустим один MapReduce нам считает среднюю оценку учеников в классе из десятка учительских журналов, а второй — количество приводов в мил полицию за последний год у учеников, исходя из данных от сотни полицейских участков. Как нам слить два MapReduce в один результат… проще говоря сделать INNER JOIN или OUTER JOIN.

    Сделайте так, чтобы первый MapReduce выдавал (оценка):
    Петя, ("оценка", 3.5)

    А второй MapReduce выдавал (приводы):
    Петя, ("приводов", 2)

    Затем все это прямо передавайте прямо подряд:
    Петя, ("оценка", 3.5)
    Петя, ("приводов", 2)


    Тогда на «reduce» получите:
    Петя, [ ("оценка", 3.5), ("приводов", 2) ]

    Вместо заключения


    Ясное дело, что MegaRankи, ниши, друзья, синонимы, нации, двоечники — далеко не единственное применение MapReduce, но пока, думаю этого вам хватит, чтобы начать думать как его применять. Я нашел ему очень много применений и использую постоянно.

    Как я уже и говорил — практически ЛЮБОЙ SQL запрос раскладывается на MapReduce, просто требуется немного тренировки. Зачем? Затем, чтобы быстрее, да и не всегда нужные функции в SQL вообще есть. Например тот же генератор н-грамм (многословных словосочетаний) из входящей строки… Может я конечно и ошибаюсь, но в том, что MapReduce — офигительная и очень полезная (и при этом потрясающе заумно описанная в сети) штука — это факт. Надеюсь удалось и Вас затянуть в сети MapReduce.

    В прошлом топике есть эталонная реализация (reference implementation) MapReduce на Python и PHP.

    Йои Хаджи,
    Вид, как всегда, с Хабра,
    2010

    (когда-нибудь я научусь объяснять кратко....)
    • +78
    • 21,4k
    • 7
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 7
    • 0
      «хабр * торт», [«несомненно», «полюбому», «разумеется»]
      • +12
        Вечер пятницы. Думал зайду на Хабр шуточные посты посмотрю, фотографии кошаков всяких. Да не тут то было :)
        • 0
          Отличная статья! Спасибо!
          • –1
            А реально ли упростить указанные алгоритмы, чтобы сложность была не O(n2)?
            • 0
              Хотел написать свою первую статью на хабр и даже уже полстатьи написал, а меня опередили :)

              Хорошая статья, спасиб :)
              • 0
                Если честно — мне эту статью было писать лень уже год, наверное, я все ждал когда кто-нибудь это сделает. :) Но не дождался.
              • 0
                Ну вот если вам Хадуп интересен, то вот здесь я писал пару постов про использование Hadoop для решения простейшей задачи расчета TF*IDF. Но там немного технически ;)

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.