Яндекс Лабс в Palo Alto набирает С++ developers

[Интеррапт]

пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.

Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.

Ну мне показалось что это префиксное дерево а не дерево Хоффмана

Возможно. Я больше по описанию ориентировался. Что там нарисовано - я не совсем понял.

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Я вам больше скажу - надо еще флажок для того, чтоб показать является ли нода концом слова и int или даже long для того чтоб показать сколько раз эта буква встречается. Так же и обычего дерево Хафмана не сжимает если текст короткий потому что надо сохранять дерево вместе с последовательностью битов чтоб правильно восстановить.
Но для запросов которые встречаются по http://www.google.com/trends/hottrends 200000+ раз экономия получается значительная. Так для Maveriсs нам понадобится ветка длиной 8 нод которой мы зашифруем 200000+ запросов (1600000 юникод символов). Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет. Вобщем памяти хватит.

[Интеррапт]

Каким образом это разумно позволит запроцессить файл с млрд запросов?

Ес-но, если время подсчета некритично (ну типа мы раз в несколько часов обрабатываем эти млрд запросов), то есть намного более простые способы, особенно для таких вещей как поисковые термины, где мы можем позволить себе некоторые "вольности", т.к. в случае небольшой ошибки - ничего страшного не случится. Как вариант - lossy counting алгоритм, который позволяет приблизительно прикинуть частоту встречаемости элементов, причем в один проход по потоку.

[Tarasik]

пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.

Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.

Ну мне показалось что это префиксное дерево а не дерево Хоффмана

Возможно. Я больше по описанию ориентировался. Что там нарисовано - я не совсем понял.

Да, я пытаюсь зашифровать список поисковых запросов "расширенным" префиксным деревом. Расширенным потому что в каждой ноде нужно хранить только один символ и флаг является ли эта нода листом (концом слова). Этого достаточно чтоб 1) восстановить список фраз без потерь 2) найти самую встречающуюся фразу за один проход по дереву.
Ах, да. Если дерево кодировать live по мере того как поступают запросы то будет совсем быстро - быстро обновили дерево и так же быстро можно из него прочитать. То есть буквально достаточно быстро чтоб полностью и абсолютно точно гуглмугл вам возвращал список по мере как вы печатаете.
Но даже если препарировать сырые логи - будет быстрей чем эти сортировки или МР с той же точностью. Но медленнее чем семплирование, зато точно как аптеке.

[crypto5]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

Миллиард уникальных запросов ? Хахаха. Человечество не такое умное. Мы все мыслим (научены мыслить) достаточно шаблонно, иначе сингулярности не стоило бы ожидать.

[crypto5]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

Миллиард уникальных запросов ? Хахаха. Человечество не такое умное. Мы все мыслим (научены мыслить) достаточно шаблонно, иначе сингулярности не стоило бы ожидать.

Оказывается умное: "15% of the searches we see everyday we’ve never seen before" http://www.google.com/competition/howgo ... works.html
При этом они кажется 2 миллиарда запросов каждый день обрабатывают, т.е. за неделю легко набирается миллиард новых уникальных запросов

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

[crypto5]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

У вас только указатель на нод на 64битной архитектуре 8 байт будет занимать, какие 5 байтов?

[Леонид Ильич Брежнев]

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

[Tarasik]

При этом они кажется 2 миллиарда запросов каждый день обрабатывают, т.е. за неделю легко набирается миллиард новых уникальных запросов

Задача изначально была про миллиард записей вообще. Из них 15% уникальных - ну чтож, зато остальные хорошо сжимаются в дереве. При чем я сомневаюсь что эти 15% будут хоть немного близко к самым часто встречающимся, Джастин Бибер (не к ночи вспомнил) как был так и будет вверху, так что их может быть надо заносить в отдельное дерево.

[Tarasik]

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

Оттудова не качает, если скачает то скажите как у вас это получилось и\или залейте на торрент дорогой Леонид Ильич.

[crypto5]

При этом они кажется 2 миллиарда запросов каждый день обрабатывают, т.е. за неделю легко набирается миллиард новых уникальных запросов

Задача изначально была про миллиард записей вообще. Из них 15% уникальных - ну чтож, зато остальные хорошо сжимаются в дереве. При чем я сомневаюсь что эти 15% будут хоть немного близко к самым часто встречающимся, Джастин Бибер (не к ночи вспомнил) как был так и будет вверху, так что их может быть надо заносить в отдельное дерево.

Задача кажется была про "миллиарды".

[crypto5]

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

Оттудова не качает, если скачает то скажите как у вас это получилось и\или залейте на торрент дорогой Леонид Ильич.

Я отсюда кажется скачал: http://www.infochimps.com/datasets/aol-search-data

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

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

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

У вас только указатель на нод на 64битной архитектуре 8 байт будет занимать, какие 5 байтов?

Хорошо, 256 Гб. Тоже не так страшно. А как вы собрались это сортировать, считать count и брать топ от них на одном компьютере ? МР тоже займет неплохо времени для этого.