Trie

Код на:JavaC#PythonJavaScript

Накратко: Trie е дърво от букви, в което общото начало на думите се пази веднъж, затова търсенето по префикс (автодовършване) струва колкото дължината на префикса.

Проблем

Полето за търсене

Магазинът има 200 000 продукта. Клиентът пише в полето за търсене „ка“, и под него трябва да излязат предложения: „кафе“, „кана“, „какао“. С всяка нова буква предложенията се сменят.

Първото решение минава през всички имена и проверява кое започва с написаното. Това е линейно търсене: 200 000 проверки при всеки натиснат клавиш. Хиляда клиента, които пишат едновременно, правят стотици милиони проверки в секунда.

А повечето имена дори не започват с „к“. Защо изобщо ги гледаш?

Идеята

Дърво от букви

Нарисувай имената като пътища. От корена тръгват клони по първата буква, от всеки от тях по втората, и т.н. „Кафе“, „какао“ и „кана“ почват с „ка“: тези две букви се пазят веднъж, а клоните се разделят чак след тях.

Това дърво е trie (от retrieval, най-често се чете „трай“). Всеки възел пази:

• децата си, по буква: колекция буква → възел;
• знак, че тук свършва име. Едно име може да свършва вътре в друго: „кафе“ и „кафемелачка“.

Търсенето по префикс има две части:

1. Слизане по буквите на префикса, по една стъпка на буква. Ако някоя буква липсва, няма такива продукти.
2. Събиране: обхождане на клона под последния възел. Всеки възел с „тук свършва име“ е предложение.

Слизането струва колкото буквите на префикса, а не колкото продуктите.

Виж го

Вмъкване и търсене по префикс

Речникът пази децата по реда на вмъкване. Затова събирането ги обхожда със sorted, по азбучен ред.

class Node:
    def __init__(self):
        self.kids = {}
        self.end = False
        self.count = 0


class Trie:
    def __init__(self):
        self._root = Node()

    def insert(self, name, count):
        at = self._root
        for ch in name:
            if ch not in at.kids:
                at.kids[ch] = Node()
            at = at.kids[ch]
        at.end = True
        at.count = count

    def complete(self, prefix):
        at = self._root
        for ch in prefix:
            at = at.kids.get(ch)
            if at is None:
                return []
        found = []
        self._collect(at, prefix, found)
        return found

    def _collect(self, at, word, found):
        if at.end:
            found.append(word)
        for ch in sorted(at.kids):
            self._collect(at.kids[ch], word + ch, found)

Събирането е рекурсия, както в урока „Рекурсия“: всеки възел събира своите имена и пита децата си. Дъното е възел без деца.

Четири продукта и три търсения:

trie = Trie()
trie.insert("кафе", 120)
trie.insert("какао", 15)
trie.insert("кана", 40)
trie.insert("чай", 60)
print(f"ка: [{', '.join(trie.complete('ка'))}]")
print(f"каф: [{', '.join(trie.complete('каф'))}]")
print(f"м: [{', '.join(trie.complete('м'))}]")

Изход

ка: [какао, кана, кафе]
каф: [кафе]
м: []

class Node:
    def __init__(self):
        self.kids = {}
        self.end = False
        self.count = 0


class Trie:
    def __init__(self):
        self._root = Node()

    def insert(self, name, count):
        at = self._root
        for ch in name:
            if ch not in at.kids:
                at.kids[ch] = Node()
            at = at.kids[ch]
        at.end = True
        at.count = count

    def complete(self, prefix):
        at = self._root
        for ch in prefix:
            at = at.kids.get(ch)
            if at is None:
                return []
        found = []
        self._collect(at, prefix, found)
        return found

    def _collect(self, at, word, found):
        if at.end:
            found.append(word)
        for ch in sorted(at.kids):
            self._collect(at.kids[ch], word + ch, found)

Стъпка по стъпка, с думи

1. Празно trie: само коренът. Всяка стъпка надолу е една буква, затова пътят от корена изписва име.
2. insert(„кафе“): букви още няма, затова всяка стъпка прави нов възел. Последният става зелен: тук свършва име.
3. „какао“ почва като „кафе“: първите две букви ги има и само се минава през тях. Нови възли има само там, където имената се разделят.
4. „кана“ също споделя началото, а „чай“ почва свой клон от корена. Четири имена, общо начало.
5. complete(„ка“): две стъпки надолу, по една за всяка буква на префикса. Това е цялото търсене, колкото и продукта да има.
6. Събирането: обхожда се само клонът под префикса, децата по азбучен ред. Всеки зелен възел е име и отива в списъка.
7. Три допълнения: какао, кана, кафе. „чай“ изобщо не е погледнат: клонът му не е под префикса.

„Чай“ изобщо не е погледнат: клонът му не е под „ка“.

Пробвай

Предвиди изхода

Три продукта. Едното име е начало на друго:

trie = Trie()
trie.insert("кафе", 1)
trie.insert("кабел", 1)
trie.insert("кафемелачка", 1)
print(f"каф: [{', '.join(trie.complete('каф'))}]")

Отговор

каф: [кабел, кафе, кафемелачка]

каф: [кафе, кафемелачка]

каф: [кафемелачка]

Провери

Пробвай

Попълни

Кое прави възела предложение при събирането?

if at.:
    found.append(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

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

class Node:
    def __init__(self):
        self.kids = {}
        self.end = False
        self.count = 0


class Trie:
    def __init__(self):
        self._root = Node()

    def insert(self, name, count):
        at = self._root
        for ch in name:
            if ch not in at.kids:
                at.kids[ch] = Node()
            at = at.kids[ch]
        at.end = True
        at.count = count

    def complete(self, prefix):
        at = self._root
        for ch in prefix:
            at = at.kids.get(ch)
            if at is None:
                return []
        found = []
        self._collect(at, prefix, found)
        return found

    def _collect(self, at, word, found):
        if at.end:
            found.append(word)
        for ch in sorted(at.kids):
            self._collect(at.kids[ch], word + ch, found)

При 100 000 имена обхождането поглежда 1 303 482 знака, двоичното търсене в подредения каталог 808, а trie-то 266. Колкото повече са имената, толкова по-гъсто е дървото и толкова по-бързо се събират петте: при 1000 имена trie-то поглежда 403 знака, при 100 000 по-малко.

Двоичното търсене е тук, защото каталогът е подреден: тогава то намира първото име с префикса за log₂ n сравнения (двоично търсене). За него виж по-долу.

Виж го

Първо най-купуваното

Азбучният ред не е най-полезен. Ако клиент пише „ка“, по-вероятно търси кафе, отколкото какао. Затова всеки възел, в който свършва име, пази и колко пъти е купуван продуктът (count). Предложенията се подреждат по него:

def count_of(self, name):
    at = self._root
    for ch in name:
        at = at.kids[ch]
    return at.count

def suggest(self, prefix, k):
    names = self.complete(prefix)
    return sorted(names, key=self.count_of, reverse=True)[:k]

trie = Trie()
trie.insert("кафе", 120)
trie.insert("какао", 15)
trie.insert("кана", 40)
trie.insert("чай", 60)
trie.insert("кафемелачка", 8)
trie.insert("кабел", 25)
print(f"ка: [{', '.join(trie.suggest('ка', 3))}]")

Изход

ка: [кафе, кана, кабел]

Подреждането е стабилно (виж стабилността): при равен брой купувания остава азбучният ред.

По-точно, за любопитните

Тук всяко търсене събира всички имена под префикса и после ги подрежда. При „к“ в истински каталог това са десетки хиляди. Затова големите търсачки пазят във всеки възел готовите първи 5–10 предложения за клона под него. Търсенето става само слизане, а цената е при вмъкването: всеки възел по пътя на ново име проверява дали то влиза в неговите първи.

Пробвай

Намери грешката

Колега е написал събирането, но предложенията са пълни с парчета от думи:

def _collect(self, at, word, found):
    found.append(word)
    for ch in sorted(at.kids):
        self._collect(at.kids[ch], word + ch, found)

trie = Trie()
trie.insert("кафе", 120)
trie.insert("какао", 15)
trie.insert("кана", 40)
trie.insert("чай", 60)
print(f"ка: [{', '.join(trie.complete('ка'))}]")

Изход

ка: [ка, как, кака, какао, кан, кана, каф, кафе]

На кой ред е грешката?

Избери реда с грешката.

1def _collect(self, at, word, found):2 found.append(word)3 for ch in sorted(at.kids):4 self._collect(at.kids[ch], word + ch, found)

Провери

Идеята

Кирилица и главни букви

За trie-то „К“ и „к“ са различни букви: различни деца на възела. Клиент, който пише „Кафе“ или „ кафе“ с интервал отпред, няма да намери нищо. Затова и името при вмъкване, и написаното при търсене минават през едно и също нормализиране: без интервали в краищата, един интервал между думите, малки букви.

def normalize(text):
    return " ".join(text.split()).lower()

trie = Trie()
trie.insert("кафе", 120)
trie.insert("какао", 15)
trie.insert("кана", 40)
trie.insert("чай", 60)
trie.insert("кафемелачка", 8)
trie.insert("кабел", 25)
print(f"КаФе: [{', '.join(trie.complete(normalize('  КаФе ')))}]")
print(f"кафe: [{', '.join(trie.complete(normalize('кафe')))}]")

Изход

КаФе: [кафе, кафемелачка]
кафe: []

Второто търсене не намира нищо, макар че „кафe“ изглежда точно като „кафе“. Последната буква е латинското „e“, а не кирилското „е“: друг знак, друго дете в дървото. Така се случва, когато клиентът забрави да смени клавиатурата. Нормализирането не го поправя само: трябва изрична замяна на латинските букви, които изглеждат като кирилски, ако искаш да ги прощаваш.

По-точно, за любопитните

lower() е достатъчно за кирилицата. За немски и други езици има casefold(): той прави и „ß“ на „ss“. Низът в Python се обхожда по знаци (code points), затова и емоджи са по един знак.

Как е в другите езици: Java и C# обхождат по 16-битов char, Python и for…of в JavaScript по знаци. За кирилицата и латиницата няма разлика.

Идеята

Паметта и кога стига подреден масив

Всеки възел пази своите деца. Има два начина:

• Колекция буква → възел, както тук: възелът пази само децата, които има.
• Масив от места, по едно за всяка буква: 26 за латиницата, 30 за българската азбука, 32 с интервал и тире. Детето се намира веднага по номера на буквата, но всеки възел пази всичките места, и празните.

Колко празни са? В trie-то на Bench за 100 000 имена (631 833 букви) има 210 642 възела, средно по едно дете на възел: общото начало е кратко, после всяко име си върви само. Масив от 30 места на възел пази над 6,3 милиона препратки, от които заети са 210 641. Колекцията е по-малка, а масивът е по-бърз само в горните нива, където децата са много.

Ако имената се сменят рядко и ти трябва само „всички, които започват с …“, често стига подреден масив. Двоичното търсене намира първото име, което не е преди префикса, а съвпаденията стоят едно до друго след него:

from bisect import bisect_left

names = ["кабел", "какао", "кана", "кафе", "кафемелачка", "чай"]
prefix = "ка"
at = bisect_left(names, prefix)
found = []
while at < len(names) and names[at].startswith(prefix):
    found.append(names[at])
    at += 1
print(f"{prefix}: [{', '.join(found)}]")

Изход

ка: [кабел, какао, кана, кафе, кафемелачка]

bisect_left връща първото място, на което префиксът може да се вмъкне, без да развали реда: това е първото име, което не е преди него.

Trie печели, когато имената се добавят и махат постоянно, когато ти трябват бройки и най-купувани за всеки префикс, или когато търсиш буква по буква, докато клиентът пише: всяка нова буква е една стъпка от възела, до който вече си стигнал.

Упражнение

Колко продукта започват с…

Реши задачата в редактора си.

Брой под префикса. До всяко предложение полето показва колко продукта започват с написаното. Добави във възела брояч колко имена минават през него и метод count_prefix, който слиза по префикса и връща брояча, без да събира имена. Вмъкни целия каталог от картата „Първо най-купуваното“ и провери префиксите „ка“, „каф“, „ч“ и „м“:

Изход

ка: 5
каф: 2
ч: 1
м: 0

Още задачи

• Изтриване. Продуктът спира да се продава. Махни името от trie-то, без да счупиш имената, които минават през същите възли.
• Брой възли. Преброй възлите след вмъкването на каталога и сравни с общия брой букви в имената.
• Буква по буква. Направи търсене, което пази възела, до който е стигнало, и при всяка нова буква прави само една стъпка.

Тест

Провери се

1. Каталогът има 200 000 продукта. Колко стъпки прави trie-то, за да стигне до възела на префикса „кафе“?

4: по една за всяка букваОколо 18: log₂ от 200 000200 000: по една за всеки продукт

2. Защо във възела има отделен знак „тук свършва име“?

За да е по-бързо слизанетоЗащото едно име може да свършва вътре в пътя на друго: „кафе“ е в началото на „кафемелачка“Защото листата нямат деца

3. Имената на продуктите се сменят веднъж на ден, а трябва само „всички, които започват с …“. Какво стига?

Задължително trieОбхождане на всички именаПодреден масив и двоично търсене на първото име с префикса

4. Клиентът пише „Кафе“, а в каталога е „кафе“. Какво правиш?

Нищо: търсенето не различава главни буквиПазиш всеки продукт по два пътиНормализираш и двете: малки букви и без излишни интервали, и при вмъкване, и при търсене

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Сложност по памет · Линейно търсене · Двоично търсене · Стабилно сортиране и вграденият sort
• Продължава в: Как да разпознаеш DP задача
• Задачи по темата: Структури от данни