Към съдържанието
wannacode

Trie

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

Проблем

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

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

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

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

Идеята

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

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

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

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

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

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

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

Виж го

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

Map пази децата по реда на вмъкване. Затова събирането подрежда буквите със sort, по азбучен ред.
class Node {
  kids = new Map();
  end = false;
  count = 0;
}


class Trie {
  #root = new Node();


  insert(name, count) {
    let at = this.#root;
    for (const ch of name) {
      if (!at.kids.has(ch)) at.kids.set(ch, new Node());
      at = at.kids.get(ch);
    }
    at.end = true;
    at.count = count;
  }


  complete(prefix) {
    let at = this.#root;
    for (const ch of prefix) {
      at = at.kids.get(ch);
      if (at === undefined) return [];
    }
    const found = [];
    this.#collect(at, prefix, found);
    return found;
  }


  #collect(at, word, found) {
    if (at.end) found.push(word);
    const letters = [...at.kids.keys()].sort();
    for (const ch of letters) {
      this.#collect(at.kids.get(ch), word + ch, found);
    }
  }
}

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

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

const trie = new Trie();
trie.insert("кафе", 120);
trie.insert("какао", 15);
trie.insert("кана", 40);
trie.insert("чай", 60);
console.log(`ка: [${trie.complete("ка").join(", ")}]`);
console.log(`каф: [${trie.complete("каф").join(", ")}]`);
console.log(`м: [${trie.complete("м").join(", ")}]`);
Изход
ка: [какао, кана, кафе]
каф: [кафе]
м: []

class Node {
  kids = new Map();
  end = false;
  count = 0;
}


class Trie {
  #root = new Node();


  insert(name, count) {
    let at = this.#root;
    for (const ch of name) {
      if (!at.kids.has(ch)) at.kids.set(ch, new Node());
      at = at.kids.get(ch);
    }
    at.end = true;
    at.count = count;
  }


  complete(prefix) {
    let at = this.#root;
    for (const ch of prefix) {
      at = at.kids.get(ch);
      if (at === undefined) return [];
    }
    const found = [];
    this.#collect(at, prefix, found);
    return found;
  }


  #collect(at, word, found) {
    if (at.end) found.push(word);
    const letters = [...at.kids.keys()].sort();
    for (const ch of letters) {
      this.#collect(at.kids.get(ch), word + ch, found);
    }
  }
}
Стъпка по стъпка, с думи
  1. Празно trie: само коренът. Всяка стъпка надолу е една буква, затова пътят от корена изписва име.
  2. insert(„кафе“): букви още няма, затова всяка стъпка прави нов възел. Последният става зелен: тук свършва име.
  3. „какао“ почва като „кафе“: първите две букви ги има и само се минава през тях. Нови възли има само там, където имената се разделят.
  4. „кана“ също споделя началото, а „чай“ почва свой клон от корена. Четири имена, общо начало.
  5. complete(„ка“): две стъпки надолу, по една за всяка буква на префикса. Това е цялото търсене, колкото и продукта да има.
  6. Събирането: обхожда се само клонът под префикса, децата по азбучен ред. Всеки зелен възел е име и отива в списъка.
  7. Три допълнения: какао, кана, кафе. „чай“ изобщо не е погледнат: клонът му не е под префикса.

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

Пробвай

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

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

const trie = new Trie();
trie.insert("кафе", 1);
trie.insert("кабел", 1);
trie.insert("кафемелачка", 1);
console.log(`каф: [${trie.complete("каф").join(", ")}]`);
Отговор

Пробвай

Попълни

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

if (at.) found.push(word);

Идеята

Колко струва

  • Вмъкване: една стъпка на буква от името: O(m), където m е дължината му.
  • Слизане по префикс: една стъпка на буква от префикса: O(m), колкото и продукта да има.
  • Събиране: колкото е клонът под префикса. Ако показваш само първите 5 предложения, спираш след петото.

Пусни трите начина. Каталогът е n имена от 4 до 8 букви, по азбучен ред. Клиентът пише 20 префикса от по две букви, и за всеки трябват първите 5 имена. Броят се знаците, които търсенето поглежда: сравнение на буква от името с буква от префикса или стъпка от възел към дете. Trie-то се строи веднъж, при зареждането на каталога, и не се брои.

  • Обхождане на всички имена O(n)
  • Двоично търсене в подредения каталог O(log n)
  • Trie O(1)
Алгоритъмn = 10n = 1000n = 10 000n = 100 000
Обхождане на всички имена22311 77893 0711 303 482
Двоично търсене в подредения каталог125542676808
Trie46403342266
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
class Node {
  kids = new Map();
  end = false;
  count = 0;
}


class Trie {
  #root = new Node();


  insert(name, count) {
    let at = this.#root;
    for (const ch of name) {
      if (!at.kids.has(ch)) at.kids.set(ch, new Node());
      at = at.kids.get(ch);
    }
    at.end = true;
    at.count = count;
  }


  complete(prefix) {
    let at = this.#root;
    for (const ch of prefix) {
      at = at.kids.get(ch);
      if (at === undefined) return [];
    }
    const found = [];
    this.#collect(at, prefix, found);
    return found;
  }


  #collect(at, word, found) {
    if (at.end) found.push(word);
    const letters = [...at.kids.keys()].sort();
    for (const ch of letters) {
      this.#collect(at.kids.get(ch), word + ch, found);
    }
  }
}

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

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

Виж го

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

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

countOf(name) {
  let at = this.#root;
  for (const ch of name) at = at.kids.get(ch);
  return at.count;
}


suggest(prefix, k) {
  const names = this.complete(prefix);
  names.sort((a, b) => this.countOf(b) - this.countOf(a));
  return names.slice(0, k);
}
const trie = new Trie();
trie.insert("кафе", 120);
trie.insert("какао", 15);
trie.insert("кана", 40);
trie.insert("чай", 60);
trie.insert("кафемелачка", 8);
trie.insert("кабел", 25);
console.log(`ка: [${trie.suggest("ка", 3).join(", ")}]`);
Изход
ка: [кафе, кана, кабел]

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

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

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

Пробвай

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

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

#collect(at, word, found) {
  found.push(word);
  const letters = [...at.kids.keys()].sort();
  for (const ch of letters) {
    this.#collect(at.kids.get(ch), word + ch, found);
  }
}
const trie = new Trie();
trie.insert("кафе", 120);
trie.insert("какао", 15);
trie.insert("кана", 40);
trie.insert("чай", 60);
console.log(`ка: [${trie.complete("ка").join(", ")}]`);
Изход
ка: [ка, как, кака, какао, кан, кана, каф, кафе]

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

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

Идеята

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

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

function normalize(text) {
  return text.trim().toLowerCase().replace(/\s+/g, " ");
}
const trie = new Trie();
trie.insert("кафе", 120);
trie.insert("какао", 15);
trie.insert("кана", 40);
trie.insert("чай", 60);
trie.insert("кафемелачка", 8);
trie.insert("кабел", 25);
console.log(`КаФе: [${trie.complete(normalize("  КаФе ")).join(", ")}]`);
console.log(`кафe: [${trie.complete(normalize("кафe")).join(", ")}]`);
Изход
КаФе: [кафе, кафемелачка]
кафe: []

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

По-точно, за любопитните
toLowerCase() не зависи от езика на машината. toLocaleLowerCase("tr") би сменил „I“ на „ı“. for…of обхожда низа по знаци (code points), затова и емоджи са по една „буква“. Индексът name[i] обаче е по 16-битови единици.

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

Идеята

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

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

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

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

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

const names = ["кабел", "какао", "кана", "кафе", "кафемелачка", "чай"];
const prefix = "ка";
let lo = 0;
let hi = names.length;
while (lo < hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (names[mid] < prefix) lo = mid + 1;
  else hi = mid;
}
const found = [];
for (let at = lo; at < names.length && names[at].startsWith(prefix); at++) {
  found.push(names[at]);
}
console.log(`${prefix}: [${found.join(", ")}]`);
Изход
ка: [кабел, какао, кана, кафе, кафемелачка]
JavaScript няма вградено двоично търсене в масив, затова тук е написано на ръка. < сравнява низовете по кода на знака, както sort() без функция.

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

Упражнение

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

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

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

Изход
ка: 5
каф: 2
ч: 1
м: 0

Още задачи

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

Тест

Провери се

1. Каталогът има 200 000 продукта. Колко стъпки прави trie-то, за да стигне до възела на префикса „кафе“?
2. Защо във възела има отделен знак „тук свършва име“?
3. Имената на продуктите се сменят веднъж на ден, а трябва само „всички, които започват с …“. Какво стига?
4. Клиентът пише „Кафе“, а в каталога е „кафе“. Какво правиш?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·