Trie
Накратко: Trie е дърво от букви, в което общото начало на думите се пази веднъж, затова търсенето по префикс (автодовършване) струва колкото дължината на префикса.
Проблем
Полето за търсене
Магазинът има 200 000 продукта. Клиентът пише в полето за търсене „ка“, и под него трябва да излязат предложения: „кафе“, „кана“, „какао“. С всяка нова буква предложенията се сменят.
Първото решение минава през всички имена и проверява кое започва с написаното. Това е линейно търсене: 200 000 проверки при всеки натиснат клавиш. Хиляда клиента, които пишат едновременно, правят стотици милиони проверки в секунда.
А повечето имена дори не започват с „к“. Защо изобщо ги гледаш?
Идеята
Дърво от букви
Нарисувай имената като пътища. От корена тръгват клони по първата буква, от всеки от тях по втората, и т.н. „Кафе“, „какао“ и „кана“ почват с „ка“: тези две букви се пазят веднъж, а клоните се разделят чак след тях.
Това дърво е trie (от retrieval, най-често се чете „трай“). Всеки възел пази:
- децата си, по буква: колекция буква → възел;
- знак, че тук свършва име. Едно име може да свършва вътре в друго: „кафе“ и „кафемелачка“.
Търсенето по префикс има две части:
- Слизане по буквите на префикса, по една стъпка на буква. Ако някоя буква липсва, няма такива продукти.
- Събиране: обхождане на клона под последния възел. Всеки възел с „тук свършва име“ е предложение.
Слизането струва колкото буквите на префикса, а не колкото продуктите.
Виж го
Вмъкване и търсене по префикс
SortedDictionary пази децата подредени по буква, затова предложенията излизат по азбучен ред.class Node{ public readonly SortedDictionary<char, Node> Kids = []; public bool End; public int Count;}
class Trie{ private readonly Node root = new();
public void Insert(string name, int count) { Node at = root; foreach (char ch in name) { if (!at.Kids.TryGetValue(ch, out Node? next)) { next = new Node(); at.Kids[ch] = next; } at = next; } at.End = true; at.Count = count; }
public List<string> Complete(string prefix) { Node? at = root; foreach (char ch in prefix) { if (!at.Kids.TryGetValue(ch, out at)) return []; } var found = new List<string>(); Collect(at, prefix, found); return found; }
private void Collect(Node at, string word, List<string> found) { if (at.End) found.Add(word); foreach (var (ch, kid) in at.Kids) { Collect(kid, word + ch, found); } }}Събирането е рекурсия, както в урока „Рекурсия“: всеки възел събира своите имена и пита децата си. Дъното е възел без деца.
Четири продукта и три търсения:
var trie = new Trie();trie.Insert("кафе", 120);trie.Insert("какао", 15);trie.Insert("кана", 40);trie.Insert("чай", 60);Console.WriteLine("ка: [" + string.Join(", ", trie.Complete("ка")) + "]");Console.WriteLine("каф: [" + string.Join(", ", trie.Complete("каф")) + "]");Console.WriteLine("м: [" + string.Join(", ", trie.Complete("м")) + "]");ка: [какао, кана, кафе]каф: [кафе]м: []class Node{ public readonly SortedDictionary<char, Node> Kids = []; public bool End; public int Count;}
class Trie{ private readonly Node root = new();
public void Insert(string name, int count) { Node at = root; foreach (char ch in name) { if (!at.Kids.TryGetValue(ch, out Node? next)) { next = new Node(); at.Kids[ch] = next; } at = next; } at.End = true; at.Count = count; }
public List<string> Complete(string prefix) { Node? at = root; foreach (char ch in prefix) { if (!at.Kids.TryGetValue(ch, out at)) return []; } var found = new List<string>(); Collect(at, prefix, found); return found; }
private void Collect(Node at, string word, List<string> found) { if (at.End) found.Add(word); foreach (var (ch, kid) in at.Kids) { Collect(kid, word + ch, found); } }}Стъпка по стъпка, с думи
- Празно trie: само коренът. Всяка стъпка надолу е една буква, затова пътят от корена изписва име.
- Insert(„кафе“): букви още няма, затова всяка стъпка прави нов възел. Последният става зелен: тук свършва име.
- „какао“ почва като „кафе“: първите две букви ги има и само се минава през тях. Нови възли има само там, където имената се разделят.
- „кана“ също споделя началото, а „чай“ почва свой клон от корена. Четири имена, общо начало.
- Complete(„ка“): две стъпки надолу, по една за всяка буква на префикса. Това е цялото търсене, колкото и продукта да има.
- Събирането: обхожда се само клонът под префикса, децата по азбучен ред. Всеки зелен възел е име и отива в списъка.
- Три допълнения: какао, кана, кафе. „чай“ изобщо не е погледнат: клонът му не е под префикса.
„Чай“ изобщо не е погледнат: клонът му не е под „ка“.
Пробвай
Предвиди изхода
Три продукта. Едното име е начало на друго:
var trie = new Trie();trie.Insert("кафе", 1);trie.Insert("кабел", 1);trie.Insert("кафемелачка", 1);Console.WriteLine("каф: [" + string.Join(", ", trie.Complete("каф")) + "]");Пробвай
Попълни
Кое прави възела предложение при събирането?
if (at.) found.Add(word);Не всеки възел е име: „ка“ и „как“ са само начала. Име е там, където вмъкването е сложило знака за край.
Идеята
Колко струва
- Вмъкване: една стъпка на буква от името: O(m), където m е дължината му.
- Слизане по префикс: една стъпка на буква от префикса: O(m), колкото и продукта да има.
- Събиране: колкото е клонът под префикса. Ако показваш само първите 5 предложения, спираш след петото.
Пусни трите начина. Каталогът е n имена от 4 до 8 букви, по азбучен ред. Клиентът пише 20 префикса от по две букви, и за всеки трябват първите 5 имена. Броят се знаците, които търсенето поглежда: сравнение на буква от името с буква от префикса или стъпка от възел към дете. Trie-то се строи веднъж, при зареждането на каталога, и не се брои.
- Обхождане на всички имена
O(n) - Двоично търсене в подредения каталог
O(log n) - Trie
O(1)
| Алгоритъм | n = 10 | n = 1000 | n = 10 000 | n = 100 000 |
|---|---|---|---|---|
| Обхождане на всички имена | 223 | 11 778 | 93 071 | 1 303 482 |
| Двоично търсене в подредения каталог | 125 | 542 | 676 | 808 |
| Trie | 46 | 403 | 342 | 266 |
class Node{ public readonly SortedDictionary<char, Node> Kids = []; public bool End; public int Count;}
class Trie{ private readonly Node root = new();
public void Insert(string name, int count) { Node at = root; foreach (char ch in name) { if (!at.Kids.TryGetValue(ch, out Node? next)) { next = new Node(); at.Kids[ch] = next; } at = next; } at.End = true; at.Count = count; }
public List<string> Complete(string prefix) { Node? at = root; foreach (char ch in prefix) { if (!at.Kids.TryGetValue(ch, out at)) return []; } var found = new List<string>(); Collect(at, prefix, found); return found; }
private void Collect(Node at, string word, List<string> found) { if (at.End) found.Add(word); foreach (var (ch, kid) in at.Kids) { Collect(kid, word + ch, found); } }}При 100 000 имена обхождането поглежда 1 303 482 знака, двоичното търсене в подредения каталог 808, а trie-то 266. Колкото повече са имената, толкова по-гъсто е дървото и толкова по-бързо се събират петте: при 1000 имена trie-то поглежда 403 знака, при 100 000 по-малко.
Двоичното търсене е тук, защото каталогът е подреден: тогава то намира първото име с префикса за log₂ n сравнения (двоично търсене). За него виж по-долу.
Виж го
Първо най-купуваното
Азбучният ред не е най-полезен. Ако клиент пише „ка“, по-вероятно търси кафе, отколкото какао. Затова всеки възел, в който свършва име, пази и колко пъти е купуван продуктът (count). Предложенията се подреждат по него:
public int CountOf(string name){ Node at = root; foreach (char ch in name) at = at.Kids[ch]; return at.Count;}
public List<string> Suggest(string prefix, int k) => Complete(prefix).OrderByDescending(CountOf).Take(k).ToList();var trie = new Trie();trie.Insert("кафе", 120);trie.Insert("какао", 15);trie.Insert("кана", 40);trie.Insert("чай", 60);trie.Insert("кафемелачка", 8);trie.Insert("кабел", 25);Console.WriteLine("ка: [" + string.Join(", ", trie.Suggest("ка", 3)) + "]");ка: [кафе, кана, кабел]Подреждането е стабилно (виж стабилността): при равен брой купувания остава азбучният ред.
По-точно, за любопитните
Тук всяко търсене събира всички имена под префикса и после ги подрежда. При „к“ в истински каталог това са десетки хиляди. Затова големите търсачки пазят във всеки възел готовите първи 5–10 предложения за клона под него. Търсенето става само слизане, а цената е при вмъкването: всеки възел по пътя на ново име проверява дали то влиза в неговите първи.
Пробвай
Намери грешката
Колега е написал събирането, но предложенията са пълни с парчета от думи:
private void Collect(Node at, string word, List<string> found){ found.Add(word); foreach (var (ch, kid) in at.Kids) { Collect(kid, word + ch, found); }}var trie = new Trie();trie.Insert("кафе", 120);trie.Insert("какао", 15);trie.Insert("кана", 40);trie.Insert("чай", 60);Console.WriteLine("ка: [" + string.Join(", ", trie.Complete("ка")) + "]");ка: [ка, как, кака, какао, кан, кана, каф, кафе]На кой ред е грешката?
Избери реда с грешката.
Всеки възел се добавя като име, дори „ка“ и „как“, които са само начала. Трябва проверка на знака за край: if (at.End). С нея изходът е ка: [какао, кана, кафе].
Идеята
Кирилица и главни букви
За trie-то „К“ и „к“ са различни букви: различни деца на възела. Клиент, който пише „Кафе“ или „ кафе“ с интервал отпред, няма да намери нищо. Затова и името при вмъкване, и написаното при търсене минават през едно и също нормализиране: без интервали в краищата, един интервал между думите, малки букви.
static string Normalize(string text) => string.Join(' ', text.Split(' ', StringSplitOptions.RemoveEmptyEntries)) .ToLowerInvariant();var trie = new Trie();trie.Insert("кафе", 120);trie.Insert("какао", 15);trie.Insert("кана", 40);trie.Insert("чай", 60);trie.Insert("кафемелачка", 8);trie.Insert("кабел", 25);Console.WriteLine("КаФе: [" + string.Join(", ", trie.Complete(Normalize(" КаФе "))) + "]");Console.WriteLine("кафe: [" + string.Join(", ", trie.Complete(Normalize("кафe"))) + "]");КаФе: [кафе, кафемелачка]кафe: []Второто търсене не намира нищо, макар че „кафe“ изглежда точно като „кафе“. Последната буква е латинското „e“, а не кирилското „е“: друг знак, друго дете в дървото. Така се случва, когато клиентът забрави да смени клавиатурата. Нормализирането не го поправя само: трябва изрична замяна на латинските букви, които изглеждат като кирилски, ако искаш да ги прощаваш.
По-точно, за любопитните
ToLowerInvariant() дава едно и също правило на всяка машина. ToLower() ползва езика на машината, а на турска „I“ става „ı“ (i без точка). Още нещо: char в C# е 16-битов. Кирилицата се събира в един char, но емоджи са два, и trie по char ги цепи на половини.Как е в другите езици: Java и C# обхождат по 16-битов char, Python и for…of в JavaScript по знаци. За кирилицата и латиницата няма разлика.
Идеята
Паметта и кога стига подреден масив
Всеки възел пази своите деца. Има два начина:
- Колекция буква → възел, както тук: възелът пази само децата, които има.
- Масив от места, по едно за всяка буква: 26 за латиницата, 30 за българската азбука, 32 с интервал и тире. Детето се намира веднага по номера на буквата, но всеки възел пази всичките места, и празните.
Колко празни са? В trie-то на Bench за 100 000 имена (631 833 букви) има 210 642 възела, средно по едно дете на възел: общото начало е кратко, после всяко име си върви само. Масив от 30 места на възел пази над 6,3 милиона препратки, от които заети са 210 641. Колекцията е по-малка, а масивът е по-бърз само в горните нива, където децата са много.
Ако имената се сменят рядко и ти трябва само „всички, които започват с …“, често стига подреден масив. Двоичното търсене намира първото име, което не е преди префикса, а съвпаденията стоят едно до друго след него:
List<string> names = ["кабел", "какао", "кана", "кафе", "кафемелачка", "чай"];string prefix = "ка";int at = names.BinarySearch(prefix, StringComparer.Ordinal);if (at < 0) at = ~at;var found = new List<string>();while (at < names.Count && names[at].StartsWith(prefix, StringComparison.Ordinal)){ found.Add(names[at++]);}Console.WriteLine($"{prefix}: [{string.Join(", ", found)}]");ка: [кабел, какао, кана, кафе, кафемелачка]BinarySearch трябва да са с едно и също правило, тук StringComparer.Ordinal (по кода на знака). Отрицателният резултат е ~ от мястото за вмъкване.Trie печели, когато имената се добавят и махат постоянно, когато ти трябват бройки и най-купувани за всеки префикс, или когато търсиш буква по буква, докато клиентът пише: всяка нова буква е една стъпка от възела, до който вече си стигнал.
Упражнение
Колко продукта започват с…
Реши задачата в редактора си.
Брой под префикса. До всяко предложение полето показва колко продукта започват с написаното. Добави във възела брояч колко имена минават през него и метод CountPrefix, който слиза по префикса и връща брояча, без да събира имена. Вмъкни целия каталог от картата „Първо най-купуваното“ и провери префиксите „ка“, „каф“, „ч“ и „м“:
ка: 5каф: 2ч: 1м: 0Още задачи
- Изтриване. Продуктът спира да се продава. Махни името от trie-то, без да счупиш имената, които минават през същите възли.
- Брой възли. Преброй възлите след вмъкването на каталога и сравни с общия брой букви в имената.
- Буква по буква. Направи търсене, което пази възела, до който е стигнало, и при всяка нова буква прави само една стъпка.
Тест