Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.
Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.
Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.
Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.
Сейчас попытаюсь набросать - где бы взять миллиардный список запросов не подскажете ?
Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.
Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.
Сейчас попытаюсь набросать - где бы взять миллиардный список запросов не подскажете ?
Вы сама беспомощность ))
Скачайте википедию, разбейте текст на 3-4-5-6-7 граммы, и будет вам отличная эмуляция запросов, можете с ней поиграться.
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/
Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.
Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.
Я вообще не вижу здесь аналогии с кодом Хаффмана. В случае Хаффмана - дерево будет маленькое, т.к. строится на основе частот встречаемости символа.
Обьясните, что тут общего и где вы видите аналогию?
Tarasik wrote:Все таки строить дерево вхождений по буквам из каждого запроса - получится быстрей пройтись по нему (ну буквально максимум будет максимальная длина поисковой строки) чем делать семплинг\бутстреппинг 1000000 из 1000000000, его сортировку и проч. Кстати мне тоже задавали такой вопрос, я сначала предложил делать кластер или МР но правильным ответом было все же строить дерево, что я им на доске и исполнил.
Было бы неплохо узнать почему. И так ли очевидно что ваше дерево влезет в память вашего компьютера.
Оно не влезет. Оно поместится. По аналогии с деревьями Хоффмана которые используются в сферическом вакууме для компрессии текста.
Я вообще не вижу здесь аналогии с кодом Хаффмана. В случае Хаффмана - дерево будет маленькое, т.к. строится на основе частот встречаемости символа.
Обьясните, что тут общего и где вы видите аналогию?
В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
crypto5 wrote:
В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.
crypto5 wrote:
В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.
Да, потому что архиватор разбивает большой файл на маленькие блоки (например 8МБ), и для каждого строит отдельное дерево и потом им отдельно архивирует.
crypto5 wrote:
В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.
Да, потому что архиватор разбивает большой файл на маленькие блоки (например 8МБ), и для каждого строит отдельное дерево и потом им отдельно архивирует.
Ничего не поменяется, если построение дерева будет по гигабайтному англ тексту, а не по 8 мегабайт. На что спорим?
crypto5 wrote:
В случае с кодом Хаффмана дерево на самом деле маленькое, потому что блок архивирования маленький, а так бы оно было большое ))
Что такое "блок архивирования"? Например, если у тебя будет файл в 10 гигабайт с каким-нибудь английским текстом, то дерево будет такого же размера, как и для файла с 1 мегабайтом английского текста. А именно - будет маленьким.
Да, потому что архиватор разбивает большой файл на маленькие блоки (например 8МБ), и для каждого строит отдельное дерево и потом им отдельно архивирует.
Ничего не поменяется, если сканирование будет по гигабайту, а не по 8 мегабайт. На что спорим?
Ладно, согласен, я че то себе код Хаффмана по другому совсем представлял.
crypto5 wrote:Ладно, согласен, я че то себе код Хаффмана по другому совсем представлял.
Так вот, возвращаясь к нашим баранам, я поэтому совсем не вижу аналогии с кодом Хаффмана и нашей задачей. Дерево при построении кода Хаффмана - крошечное, поэтому ну хоть убей, но аналогии не вижу. Но может Tarasik обьяснит, что он общего увидел.
crypto5 wrote:Ладно, согласен, я че то себе код Хаффмана по другому совсем представлял.
Так вот, возвращаясь к нашим баранам, я поэтому совсем не вижу аналогии с кодом Хаффмана и нашей задачей. Дерево при построении кода Хаффмана - крошечное, поэтому ну хоть убей, но аналогии не вижу. Но может Tarasik обьяснит, что он общего увидел.
Они имеют общего то, что в запросах многие строки полностью или частично совпадают а дерево Хафмана сжимает потому что буквы в тексте повторяются (и их соответственно можно записать меньшим количеством битов чем они занимают в натуре, а если алгоритм усложнить и записывать битами словосочетания а не только буквы то будет сжимать еще лучше). Более того, если дерево для кодирования вебзапросов кодировать минимально необходимыми битами а не юникодом (2мя байтами) на символ, то дерево вебзапросов сожмет еще лучше потому что для нас не важна последовательность запросов - мы можем их восстановить в произвольном порядке а одного дерева хафмана для восстановления текста недостаточно - нужна последовательность битов.
Итак я утверждаю что для кодирования веб запросов
мама
ма
мамаша
мамашка
достаточно дерева из 8 нодов хотя текст занимает 19 символов.
м 4
\
а 4 w
\
м 3
\
а 3 w
\
ш2
\ \
а1 w к1
\
а1 w
пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.
Last edited by Tarasik on 25 Jan 2014 09:09, edited 1 time in total.
Tarasik wrote:пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.
Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.
Речь же тут не про компрессию файла с 1 млрд записей идет - это как-раз мало кого интересует и к тому же очень ресурсозатратно сжимать и разжимать.
Tarasik wrote:пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.
Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.
Ну мне показалось что это префиксное дерево а не дерево Хоффмана
