Хранение данных в дереве. Это как вообще?
Роман Халкечев, руководитель отдела аналитики в Яндекс.Еде и Лавке Роман Халкечев, руководитель отдела аналитики в Яндекс.Еде и Лавке
Хранение данных в дереве. Это как вообще?
Бустинг — ещё один способ машинного обучения

Эта ста­тья из обла­сти «Как быва­ет». Она доволь­но слож­ная, но может суще­ствен­но рас­ши­рить ваши гори­зон­ты в вопро­сах ком­пью­те­ров, дан­ных и про­грам­ми­ро­ва­ния. Ста­тья вдох­нов­ле­на нашим раз­го­во­ром с Рома­ном Хал­ке­че­вым — руко­во­ди­те­лем направ­ле­ния ана­ли­ти­ки в «Еде» и «Лав­ке». Про­чи­тай­те, там инте­рес­ное о дата-сайенсе, машин-лёрнинге и карьер-билдинге.

Формальное определение

Trie (пре­фикс­ное дере­во, бор, или нагру­жен­ное дере­во) — это струк­ту­ра дан­ных, n-арное дере­во, в узлах кото­ро­го хра­нят­ся не клю­чи, а сим­во­лы. А ключ — это путь от кор­ня дере­ва до это­го узла. Пока слож­но. Теперь по порядку. 

Почти всё, чем мы поль­зу­ем­ся в интер­не­те, — это дан­ные: лич­ная инфор­ма­ция поль­зо­ва­те­лей, спи­сок това­ров и поку­пок, кар­тин­ки и текст для вёрст­ки, исто­рия поис­ко­вых запро­сов. Эти дан­ные надо как-то хра­нить, что­бы в опре­де­лён­ный момент быст­ро подой­ти и достать нужные.

Напри­мер, часто дан­ные хра­нят­ся в таб­ли­цах. Это не един­ствен­ный спо­соб, но доволь­но рас­про­стра­нён­ный и инту­и­тив­но понят­ный. Напри­мер, у нас есть инфор­ма­ция о струк­ту­ре ком­па­нии. В таб­ли­це она будет выгля­деть так:

Назва­ние должности Кому под­чи­ня­ет­ся Кто в подчинении
Гене­раль­ный директор

Тех­ни­че­ский директор

Дирек­тор по маркетингу

Тех­ни­че­ский директор Гене­раль­но­му директору

Тим­лид фронтенд-команды

Тим­лид бэкенд-команды

Дирек­тор по маркетингу Гене­раль­но­му директору

Арт-директор

SMM-менеджер

Руко­во­ди­тель отде­ла продаж Гене­раль­но­му директору
Тим­лид фрон­тенд команды Тех­ни­че­ско­му директору
Тим­лид бэкенд команды Тех­ни­че­ско­му директору
Арт-директор Дирек­то­ру по маркетингу
SMM-менеджер Дирек­то­ру по маркетингу

В целом понят­но, но слож­но пред­ста­вить, что кто-то будет поль­зо­вать­ся таким спо­со­бом запи­си: это неудоб­но. Такие дан­ные про­ще пред­ста­вить в виде дерева:


Та же самая инфор­ма­ция в виде дере­ва — намно­го нагляд­нее и понятнее 

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

👉 Струк­ту­ра дан­ных — это то, как хра­нят­ся дан­ные. Дере­во — одна из воз­мож­ных струк­тур дан­ных. Ещё есть свя­зан­ные спис­ки, сте­ки, оче­ре­ди, мно­же­ства, хеш-таблицы, кар­ты и даже кучи (heap). Сей­час раз­бе­рём имен­но деревья.

Дерево

Дере­во состо­ит из узлов и свя­зей меж­ду ними. Самый верх­ний узел, из кото­ро­го начи­на­ет­ся дере­во, назы­ва­ют кор­не­вым. Если из узла выхо­дят дру­гие, то их назы­ва­ют потом­ка­ми, или детьми. Узлы вто­ро­го уров­ня — потом­ки кор­не­во­го узла. Если у узла нет детей, то его назы­ва­ют листом.


Струк­ту­ра дерева 

Двоичное дерево

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

Давай­те на при­ме­ре: рас­ста­вим чис­ла 3, 1, 5, 2 и 4 в виде дво­ич­но­го дере­ва. Добав­лять узлы будем имен­но в таком порядке.

3 — кор­не­вой узел, самый верх­ний. Теперь нуж­но доба­вить 1. 1 < 3, зна­чит, ста­но­вит­ся его левым потом­ком. Теперь 5. 5 > 3, зна­чит, ста­но­вит­ся пра­вым потом­ком. Теперь 2. 2 < 3, зна­чит, идём нале­во. 2 > 1, зна­чит, ста­но­вит­ся его пра­вым потом­ком. Теперь 4. 4 > 3, так что идём напра­во. 4 < 5, так что ста­но­вит­ся его левым ребён­ком. Вот так вот:


Бинар­ное, или дво­ич­ное дерево 

Если в дере­ве не циф­ры, а стро­ки, то мож­но срав­ни­вать их по алфа­ви­ту. Пер­вая бук­ва потом­ка по алфа­ви­ту рань­ше, чем у узла — ста­вим потом­ка сле­ва. И наоборот.

Из-за такой струк­ту­ры по бинар­ным дере­вьям удоб­но искать: нуж­но срав­нить запрос с теку­щим узлом, а потом пой­ти напра­во или нале­во. Напри­мер, вот бинар­ное дере­во с цита­той из тре­ка «Касты»:


И один из них я сам, иду в цен­траль­ный парк 

Допу­стим, мы хотим най­ти в этом дере­ве сло­во «зевак». Полу­ча­ет­ся такой путь:

Шаг 1. Смот­рим на корень дере­ва — «Любовь». Это то, что мы ищем? Нет. Иско­мое зна­че­ние боль­ше или мень­ше? Мень­ше, пото­му что «з» в алфа­ви­те рань­ше, чем «л». Идём налево.

Шаг 2. Смот­рим на лево­го потом­ка — «для». Это то, что мы ищем? Нет. Иско­мое зна­че­ние боль­ше или мень­ше? Боль­ше, пото­му что «з» в алфа­ви­те поз­же, чем «д». Идём направо.

Шаг 3. Смот­рим на пра­во­го потом­ка — «зевак». Это то, что мы ищем? Да. Отлич­но, мы на месте.

Вы навер­ня­ка поль­зо­ва­лись сло­ва­ря­ми — орфо­гра­фи­че­ски­ми или тол­ко­вым. Там поиск рабо­та­ет похо­жим обра­зом: мы ищем какое-то сло­во и для это­го срав­ни­ва­ем его с теми, на кото­рые наты­ка­ем­ся, пока пере­ли­сты­ва­ем стра­ни­цы. И потом листа­ем сло­варь впе­рёд или назад, если недо­ли­ста­ли или пере­ли­ста­ли, дви­га­ем­ся вниз по дво­ич­но­му дереву.

N-арное дерево

На дере­ве со струк­ту­рой ком­па­нии мы виде­ли, что у узла может быть не толь­ко два, но и боль­ше потом­ков. Такие дере­вья назы­ва­ют n-арными — у узлов в нём может быть n детей: и 1, и 5, и 200.

N-арное дере­во может, напри­мер, изоб­ра­жать струк­ту­ру сай­та. Вот так:


У узлов раз­ное коли­че­ство потом­ков: с «Глав­ной» мож­но перей­ти на 3 стра­ни­цы, из «Бло­га» — на мно­же­ство ста­тей, из «Услуг» на B2B-услуги и B2C-услуги 

Trie

Trie — это при­мер n-арного дере­ва. Но в его узлах хра­нят­ся не клю­чи, а сим­во­лы. Что это значит?

Когда мы смот­рим на кар­ту сай­та, мы видим понят­ные зна­че­ния: ссыл­ки на «Ста­тью 1», «О ком­па­нии» или «B2B-услуги». Это и есть клю­чи — кон­крет­ные ука­за­те­ли на то, что мы ищем. В Trie в узлах таких клю­чей нет. Обыч­но там лежат стро­ки, напри­мер бук­вы. Вот как может выгля­деть Trie:


В этом дере­ве лежат клю­чи «Бог», «Бор», «Бег», «Бы», «Буй» и «Бунт»

Ключ в Trie — это не узел, а путь от кор­ня до опре­де­лён­но­го узла. У каж­до­го узла есть допол­ни­тель­ная харак­те­ри­сти­ка, кото­рая ука­зы­ва­ет, явля­ет­ся ли этот узел конеч­ной точ­кой или про­ме­жу­точ­ным зна­че­ни­ем. На дере­ве выше это зелё­ные и белые узлы: так ком­пью­тер зна­ет, что «Бунт» — это ключ, а «Бун» — нет.

Сим­во­лов в узле может быть и несколь­ко, напри­мер не бук­вы слов, а сло­ги. Но прин­цип тот же: ключ — не сам узел, а путь от кор­ня до него.

Зачем это нужно

Trie часто исполь­зу­ют в рабо­те со сло­ва­ря­ми. С помо­щью дере­ва рабо­та­ет, напри­мер, Т9. Поль­зо­ва­тель вво­дит набор цифр, а про­грам­ма смот­рит, какие клю­чи мож­но для тако­го набо­ра полу­чить. А потом выби­ра­ет самый попу­ляр­ный и под­став­ля­ет его. Так из ком­би­на­ции 5-6-4-2-3-6 полу­ча­ет­ся «при­вет».

Ещё Trie помо­га­ет в под­сказ­ках в поис­ке. Вот что про это гово­рит Роман Хал­ке­чев, руко­во­ди­тель отде­ла ана­ли­ти­ки в «Яндекс.Лавке» и «Яндекс.Еде», кото­рый несколь­ко лет раз­ра­ба­ты­вал подсказки:

«Пре­фикс­ное дере­во лежит в осно­ве быст­ро­го поис­ка строк, начи­на­ю­щих­ся на пре­фикс — сим­вол или несколь­ко сим­во­лов, кото­рые вво­дит пользователь.

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

То есть, поль­зо­ва­тель начи­на­ет вво­дить запрос, мы идём вниз по дере­ву и смот­рим, какие запро­сы так начи­на­ют­ся. А затем сор­ти­ру­ем их по акту­аль­но­сти, кон­тек­сту и ещё куче пара­мет­ров. И в ито­ге пред­ла­га­ем поль­зо­ва­те­лю то, что ему может быть нужно». 

Экс­перт:
Роман Хал­ке­чев
Текст и иллю­стра­ции:
Сла­ва Уфимцев
Редак­тор:
Мак­сим Ильяхов
Кор­рек­тор:
Ири­на Михеева
Худож­ник:
Даня Бер­ков­ский
Вёрст­ка:
Мария Дро­но­ва
Раз­нёс весть:
Вита­лий Вебер

Дре­во дан­ных, дай нам сил.