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

[Berlaga]

Кстати, похожую задачу предлагали мне и в Амазоне, 5 лет тому назад. Про выбор самых популярных покупок.

[Boriskin]

Поиск слова естественно с trie решается.

А зачем ограничиваться словом? Произвольная строка и никаких дополнительных танцев...

[Мальчик-Одуванчик]

Поиск слова естественно с trie решается.

А зачем ограничиваться словом? Произвольная строка и никаких дополнительных танцев...

С другой стороны, каким все это боком отностится к знанию плюсов?

[Berlaga]

С другой стороны, каким все это боком отностится к знанию плюсов?

У них же Ресеч Лаб. Наверное, плюсы не основной требуемый скилл, главное - чтоб был умный, соображал.

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

[dotcom]

Поиск слова естественно с trie решается.

А зачем ограничиваться словом? Произвольная строка и никаких дополнительных танцев...

Можно. Но танцы все равно нужны, т.к. надо будет отсортировать слова, нормализовать морфологию, орфографию, синтаксис и.т.д. и.т.п. Иначе мы забьем trie мусором и пропустим очевидно одинаковые запросы. И после разбора уже проще строить не radix trie, а граф из слов нормализованного запроса. Оно будет и экономичнее и быстрее в результате.

[Мальчик-Одуванчик]

С другой стороны, каким все это боком отностится к знанию плюсов?

У них же Ресеч Лаб. Наверное, плюсы не основной требуемый скилл, главное - чтоб был умный, соображал.

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

Ну в этом случае смысла нет заморачиваться на таком сильном сужении требований.
И полагаю, что не всякий умный и соображающий решит нечто подобное сходу, если ранее плотно не сталкивался с этим кругом задач. Они, на мой взгляд, отдают определенной спецификой, требующей больше привычки, нежели умения соображать.

[Boriskin]

Поиск слова естественно с trie решается.

А зачем ограничиваться словом? Произвольная строка и никаких дополнительных танцев...

С другой стороны, каким все это боком отностится к знанию плюсов?

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

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

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

[dotcom]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Если вы ко мне, то я как раз предлагал использовать граф, где узлами будут индексированные слова. А trie использовался бы только для поиска слов по словарю. На практике trie действительно будет сильно меньше 26^80. Оценки размеров словарных индексов и их сравнение было где-то даже в дебрях слайдов Сегаловича, когда он был на roadshow с презентацией Яндекса после IPO. Правда, он эти страницы быстро пролистывал перед нетехнической публикой. Для длинных несловарных выражений уже надо использовать b-tree, а не trie.

[crypto5]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

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

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

[crypto5]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

Зато строки aaaaaaaaaaaaaaa и aaaaaaaaaaaaaaaaab будут использовать дерево совместно.

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

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Если вы ко мне, то я как раз предлагал использовать граф, где узлами будут индексированные слова. А trie использовался бы только для поиска слов по словарю. На практике trie действительно будет сильно меньше 26^80. Оценки размеров словарных индексов и их сравнение было где-то даже в дебрях слайдов Сегаловича, когда он был на roadshow с презентацией Яндекса после IPO. Правда, он эти страницы быстро пролистывал перед нетехнической публикой. Для длинных несловарных выражений уже надо использовать b-tree, а не trie.

Слова дело хорошее и сушественно уменьшит размер датаструктуры, но думается будет так же не мало разношерстных guids, ids, asins, и прочей автоматически сгенерировной фигни, которая ко всему еще была придумана так, что бы минимизировать колизии.

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

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

Зато строки aaaaaaaaaaaaaaa и aaaaaaaaaaaaaaaaab будут использовать дерево совместно.

т.е. аааааааааа и аааааааааааб будет представлено, как
аааааааааа {2} -> аб {1)
отлично.

Но как только у нас попадется слово ааак, вам исходную структуры прийдется делить
ааа{3} -> ааааааа {2} -> аб {1)
....... -> к {1}

И такой работы будет имхо весьма не мало

[crypto5]

А что никого не смутило, что размер дерева для скажем среднестатистического запроса длиной в скажем 80 символов, будет теоретически размером (если только с буквами, без цифр) в 26 в степени 80? В реалии наверное много меньше, но все равно имхо слишком много?

Это случится только когда в индексе будет 26^80 абсолютно разных слов ))

http://a.....
http://b.....
http://c.....
....
уже на первом символе (забудем про http://) уже должно быть создано 26 бранчей, от а до z. У второго символа тоже 26, от aa до аz (и так до za ... zz). И так далее. От того что в URL два раза повторится слово mama/mama, не следует, что жизнь с таким URL будет простой, поскольку есть еще mama/papa/mama. And they should be counted differently.
Т.е. по моему мнению дерево будет разрастаться в бесконечность по мере увеличения длины URL. Правда возможно его можно тоже создавать и сохранять кусками, upload/dump на/с FS его по мере надобности.

Зато строки aaaaaaaaaaaaaaa и aaaaaaaaaaaaaaaaab будут использовать дерево совместно.

т.е. аааааааааа и аааааааааааб будет представлено, как
аааааааааа {2} -> аб {1)
отлично.

Но как только у нас попадется слово ааак, вам исходную структуры прийдется делить
ааа{3} -> ааааааа {2} -> аб {1)
....... -> к {1}

И такой работы будет имхо весьма не мало

Я такого не говорил. В классическом trie на каждую "a" будет создаваться массив из 26-и элементов, или не массив а какая то более экономная структура данных. Но из-за того что будет много слов с совпадающими префиксами, они будут шарить часть дерева и таким образом будет происходить компрессия.

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

Я такого не говорил. В классическом trie на каждую "a" будет создаваться массив из 26-и элементов, или не массив а какая то более экономная структура данных. Но из-за того что будет много слов с совпадающими префиксами, они будут шарить часть дерева и таким образом будет происходить компрессия.

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

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

Берлага, А Вам что мое решение совсем не нравится или Вы принципиальный противник Центрального Комитета?

[crypto5]

Я такого не говорил. В классическом trie на каждую "a" будет создаваться массив из 26-и элементов, или не массив а какая то более экономная структура данных. Но из-за того что будет много слов с совпадающими префиксами, они будут шарить часть дерева и таким образом будет происходить компрессия.

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

Если у вас второе слово ab, то для него массив для а уже создавать не нужно, он уже создан для первого слова аа. При этом слов с общим каким то префиксом очень много.

[Интеррапт]

Я такого не говорил. В классическом trie на каждую "a" будет создаваться массив из 26-и элементов, или не массив а какая то более экономная структура данных. Но из-за того что будет много слов с совпадающими префиксами, они будут шарить часть дерева и таким образом будет происходить компрессия.

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

Ну ес-но, если каждый запрос будет уникальный (т.е. народ только и будет делать, что искать всякие GUID). Но ведь в любом поисковике это совсем не так. Небось 99% запросов содержат слова и вполне типичные предложения.

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

Я такого не говорил. В классическом trie на каждую "a" будет создаваться массив из 26-и элементов, или не массив а какая то более экономная структура данных. Но из-за того что будет много слов с совпадающими префиксами, они будут шарить часть дерева и таким образом будет происходить компрессия.

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

Ну ес-но, если каждый запрос будет уникальный (т.е. народ только и будет делать, что искать всякие GUID). Но ведь в любом поисковике это совсем не так. Небось 99% запросов содержат слова и вполне типичные предложения.

Если мы обсуждаем стандартный язык, то принципиальной разницы в построении дерева

"privet"{2} -> "interuupt" {1}
.................-> "crypto" {1}

и

"p"{2} -> "r"{2} -> "i"{2} -> "v"{2} -> "e"{2} -> "t"{2} -> Ну и так далее

не будет

Посколько привет и правда расходятся уже на третьей букве, а привет и попа уже на 2-ой

Но граф (пардон) "попа интеррап" и (пардон) "где это попа интеррап" это два совершенно разных дерева, раз уж они расходятся на самой первой букве. Хотя и имеют общие слова

Комбинаций будет конечно не 26 в степени средней длины запроса, очевидно что какие-то последовательности букв слов не образуют ("зтруа"), но будет их много.

[crypto5]

Я такого не говорил. В классическом trie на каждую "a" будет создаваться массив из 26-и элементов, или не массив а какая то более экономная структура данных. Но из-за того что будет много слов с совпадающими префиксами, они будут шарить часть дерева и таким образом будет происходить компрессия.

Это как? Ну вот допустим у нас первая "а", я ее назвал а1
a1 => {a2, b2, ....., z2}
Но ведь на вторую а тоже нужен свой масив
a2 => {a3, b3, ....., z3}
И на вторую "b": b2 => {a32, b32, ....., z32}

Ну ес-но, если каждый запрос будет уникальный (т.е. народ только и будет делать, что искать всякие GUID). Но ведь в любом поисковике это совсем не так. Небось 99% запросов содержат слова и вполне типичные предложения.

Если мы обсуждаем стандартный язык, то принципиальной разницы в построении дерева

"privet"{2} -> "interuupt" {1}
.................-> "crypto" {1}

и

"p"{2} -> "r"{2} -> "i"{2} -> "v"{2} -> "e"{2} -> "t"{2} -> Ну и так далее

не будет

Посколько привет и правда расходятся уже на третьей букве, а привет и попа уже на 2-ой

Но граф (пардон) "попа интеррап" и (пардон) "где это попа интеррап" это два совершенно разных дерева, раз уж они расходятся на самой первой букве. Хотя и имеют общие слова

Комбинаций будет конечно не 26 в степени средней длины запроса, очевидно что какие-то последовательности букв слов не образуют ("зтруа"), но будет их много.

Я что-то только пропустил, какое именно решение ЦК Партии предлагает воплотить в жизнь Пламенным Комсомольцам, которое будет явно лучше trie?

[Komissar]

На следующем пленуме ЦК будет оглашено.

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

Труе это вот это?



Т.е. я правильно понял, что предлагается тянуть весь хвост, на первом уровне это только "м", на втором "ма", на третьем "мам", на четвертом "мама"?

Тогда, как я предлагал хранить ровно по одному символу м -> а -> м -> а

У вас же для URL-ов длинной в сотню симоволов будут гигансткие оверхеды по расходу памяти на хранение 99 symbols, 98 symbols, etc.

[crypto5]

Труе это вот это?

Т.е. я правильно понял, что предлагается тянуть весь хвост, на первом уровне это только "м", на втором "ма", на третьем "мам", на четвертом "мама"?

Тогда, как я предлагал хранить ровно по одному символу м -> а -> м -> а

У вас же для URL-ов длинной в сотню симоволов будут гигансткие оверхеды по расходу памяти на хранение 99 symbols, 98 symbols, etc.

НУ я думаю в большинстве имплементаций так все и работает (в узле не содержится полный префикс), по крайней мере в приведенных примерах кода так сделано.
На картинке думаю просто идею показали, что идет в поддерево.

[Boriskin]

Труе это вот это?



Т.е. я правильно понял, что предлагается тянуть весь хвост, на первом уровне это только "м", на втором "ма", на третьем "мам", на четвертом "мама"?

Нет, фраза строится как путь, хранится по одной букве, примерно как и предлагалось

хранить ровно по одному символу м -> а -> м -> а

Вообще, если задача стоит только как "найти 10 самых популярных запросов" из миллирдов несортированных - возможно, трие не самое эффективное. Если добавлять suggestions - то врядли есть чтото лучше.