Trie (prefiks daraxti): avtoto'ldirish va prefiks bo'yicha qidiruv JavaScript'da

Qisqacha: Trie (prefiks daraxti) so'zlarni harfma-harf saqlaydi: har tugun — bitta harf, umumiy boshlanishga ega so'zlar bitta yo'lni bo'lishadi. So'z qo'shish va qidirish so'z uzunligiga teng vaqt oladi — O(L), lug'atda qancha so'z bo'lishidan qat'i nazar. Prefiks bilan boshlanadigan so'zlarni topish uchun prefiks tuguniga tushib, faqat uning pastki daraxtini aylanamiz. Narxi — xotira: har harf uchun alohida tugun.

Bu darsda

• Trie tuzilishini chiza olasiz va Map bilan tugun yasay olasiz.
• insert, has, startsWith va avtoto'ldirish (complete) metodlarini yoza olasiz.
• Trie qachon filter(startsWith) dan tez, qachon teng va qachon ortiqcha ekanini o'lchovlar bilan tushuntira olasiz.
• vazifalar ilovasiga teg takliflarini qo'shasiz — PrefiksDaraxti klassi bilan.

Oldin bilishingiz kerak: Daraxt masalalari, Daraxt bo'ylab yurish: DFS va BFS, Map, Matn algoritmlari.

1. Nega bu kerak?

«Bahor» yetkazib berish xizmatini ochdi. Mehmon buyurtma berayotganda manzilini yozadi. Jasur aka shunday qulaylik xohlaydi: mehmon "Yun" deb yozishi bilan ostida "Yunusobod", "Yunusobod-4", "Yunus Rajabiy ko'chasi" kabi takliflar chiqsin. Toshkentda ko'cha, mahalla va mo'ljallar — o'n minglab nom.

Sardorning birinchi yechimi — Matn algoritmlari darsidagi kabi filter bilan:

const streets = ["Yunusobod", "Yunusobod-4", "Chilonzor",
  "Yunus Rajabiy ko'chasi", "Qatortol", "Chorsu"];

const suggest = (prefix) =>
  streets.filter((name) => name.startsWith(prefix)).slice(0, 5);

console.log(suggest("Yun").length); // 3
console.log(suggest("Ch")); // [ 'Chilonzor', 'Chorsu' ]

Ishlaydi. Lekin har harf terilganda butun ro'yxat ko'rib chiqiladi: n ta nom, har birida prefiks uzunligicha solishtirish — O(n · p). 80 000 nomda bitta harf ~0,8 ms oladi. Bir foydalanuvchi uchun bu sezilmaydi. Server esa minglab foydalanuvchiga xizmat qiladi va har biri har soniyada bir nechta harf teradi.

Kuzatish: "Yunusobod" va "Yunusobod-4" bir xil boshlanadi. Lug'at qog'oz kitob bo'lsa, "Yun" ni qidirish uchun hamma sahifani varaqlamaysiz — "Y" bo'limini, keyin "Yu" ni ochasiz. Bugun shu g'oyani daraxtga aylantiramiz.

2. Trie tuzilishi

2.1 Har tugun — bitta harf

Trie (prefiks daraxti) — so'zlarni harfma-harf saqlaydigan daraxt. Nomi inglizcha "retrieval" (qidirib topish) so'zidan olingan va odatda "tray" deb o'qiladi. Qoidalari:

• ildiz — bo'sh, harf yo'q;
• har qirra — bitta harf; ildizdan tugungacha yo'l — prefiks (so'zning boshlanishi);
• so'z tugaydigan tugunda belgi bor (end: true).

Bir xil boshlanadigan so'zlar bitta yo'lni bo'lishadi. "manti", "mastava" va "mampar" uchun "m" va "a" harflari bir martadan saqlanadi. Keyin yo'l uch shoxga ajraladi.

Tugunning bolalari ko'p bo'lishi mumkin (alifbodagi har harf uchun bittagacha). Ularni qanday saqlaymiz? Eng qulayi — Map: kalit — harf, qiymat — bola tugun. children.get("a") — o'rtacha O(1). Tugunning tuzilishi:

const node = { children: new Map(), end: false };
node.children.set("m", { children: new Map(), end: false });
console.log(node.children.has("m"), node.children.size); // true 1

Bu tugun binar daraxt darsidagi { value, left, right } tugunidan boshqacha. Buning ikki sababi bor. Birinchidan, bolalar ikkita emas, ko'p: chap va o'ng o'rniga children lug'ati turadi. Ikkinchidan, harf tugunning o'zida saqlanmaydi. U tugunga olib boradigan qirrada — Map kalitida yoziladi. Shuning uchun tugunda value maydoni yo'q. end esa yangi narsa: "shu joyda butun so'z tugaydimi?" degan savolga javob beradi.

Maslahat: Faqat kichik lotin harflari bo'lsa, Map o'rniga 26 katakli massiv ham ishlatiladi (children[ch.charCodeAt(0) - 97]). U biroz tezroq, lekin o'zbekcha apostrof (o'), katta harf, raqam yoki emoji kelsa — yaroqsiz. Map istalgan belgini qabul qiladi.

Endi o'zingiz hisoblang. Bo'sh Trie'ga "osh", "ota" va "olma" qo'shilsa, ildizdan tashqari ta tugun bo'ladi. Ishora: "o" uchala so'zda bitta.

2.2 Trie qanday o'sadi

To'rtta taomni qo'shamiz va "ma" bilan boshlanadiganlarini so'raymiz. Sariq — mavjud yo'ldan qayta foydalanilgan tugunlar, so'z — shu yerda so'z tugaydi:

18 ta tugunda to'rtta so'z (21 ta harf). "ma" uchun javob topishda faqat "ma" ostidagi shox aylanildi, "osh" ga umuman kirilmadi.

3. Kod: insert, has, startsWith

3.1 Qo'shish

insert so'zning harflari bo'ylab yuradi. Keyingi harf uchun bola bo'lmasa — yaratadi, bo'lsa — unga o'tadi. Oxirgi tugunga end = true qo'yadi.

Avval qo'lda bajarib ko'ramiz. Trie'da allaqachon "osh" bor, endi "ota" ni qo'shamiz:

1. Ildizda turibmiz. Birinchi harf — "o". Ildizning "o" bolasi allaqachon bor ("osh" uni ochgan). Yangi tugun yaratmaymiz, unga o'tamiz.
2. Ikkinchi harf — "t". "o" tugunining bolalari orasida faqat "s" bor. "t" yo'q — yangi tugun yaratamiz va unga o'tamiz.
3. Uchinchi harf — "a". Yangi "t" tugunida hali hech qanday bola yo'q — yana yangi tugun.
4. Harflar tugadi. Turgan tugunimizga end = true qo'yamiz: "ota" shu yerda tugaydi.

Ikkita yangi tugun ochildi, bittasi qayta ishlatildi. Har harfda bitta ish bajarildi: "bola bormi?" degan savol va o'tish. Demak, vaqt so'z uzunligiga teng — O(L), L — so'z uzunligi. Lug'atda 10 ta yoki 10 million so'z bo'lishi ahamiyatsiz: biz boshqa so'zlarga umuman qaramadik.

Harflar for...of bilan olinadi. Bu muhim: for...of satrni kod nuqtalari bo'yicha yuradi (Unicode va emoji). "non" dagi non emojisi bitta harf bo'lib qoladi. Oddiy for (let i...) va word[i] esa uni ikki bo'lakka bo'lib yuborardi.

3.2 Uchta savol, bitta yordamchi

Uchala qidiruv metodi bir xil ishdan boshlanadi: prefiks harflari bo'ylab tushish. Shuning uchun uni yashirin #find metodiga chiqardik (Private # maydon va metodlar). U prefiks tugunini yoki null ni qaytaradi:

• has(word) — tugun bor va unda so'z tugaydi. "mas" uchun yo'l bor, lekin u so'z emas — false.
• startsWith(prefix) — tugun borligining o'zi yetarli. "mas" — true.
• complete(prefix, limit) — prefiks tugunidan pastga DFS, end belgili tugunlarni yig'adi.

#find ichida nima bo'ladi? "mas" uchun: ildizdan "m" ga, undan "a" ga, undan "s" ga tushadi va "s" tugunini qaytaradi. "mak" uchun esa "a" tugunida "k" bola yo'q. get("k") undefined beradi va #find darhol null qaytaradi. Qolgan harflarni tekshirishning hojati yo'q: yo'l uzildi.

?. operatori #find null qaytarsa ham xato bermaydi — undefined bo'ladi va === true uni false ga aylantiradi (??, ?. va mantiqiy tayinlash).

Tekshirib ko'ring: Trie'ga "osh" va "oshxona" qo'shildi. has("osh"), has("oshx") va startsWith("oshx") nima qaytaradi?

3.3 Qo'shimcha: o'chirish

Bu bo'lim — qo'shimcha bilim. vazifalar ilovasida o'chirish kerak emas: u yerda daraxt ro'yxat o'zgarganda butunlay qayta quriladi. Lekin intervyuda "Trie'dan so'zni o'chiring" deb so'rashadi.

Mehmon manzilini xato yozdi va lug'atdan "oshxona" ni olib tashlash kerak. Faqat end = false qilish yetarlimi? Natija to'g'ri bo'ladi — has("oshxona") endi false. Lekin "x", "o", "n", "a" tugunlari bekorga xotirada qoladi. Ularni ham tozalash uchun rekursiya bilan pastga tushamiz va qaytishda so'raymiz: "bu tugun endi kimgadir kerakmi?" Tugunda so'z tugamasa va bolasi qolmagan bo'lsa — kerak emas, ota uni o'chiradi. Bu Daraxt masalalari darsidagi pastdan tepaga naqsh:

const make = () => ({ children: new Map(), end: false });
const root = make();
for (const word of ["osh", "oshxona"]) {
  let node = root;
  for (const ch of word) {
    if (!node.children.has(ch)) node.children.set(ch, make());
    node = node.children.get(ch);
  }
  node.end = true;
}

// true qaytarsa — ota bu bolani o'chirsin
function remove(node, chars, i = 0) {
  if (i === chars.length) {
    node.end = false; // so'z belgisini olamiz
  } else {
    const ch = chars[i];
    const child = node.children.get(ch);
    if (child === undefined) return false; // bunday so'z yo'q
    if (remove(child, chars, i + 1)) node.children.delete(ch);
  }
  return !node.end && node.children.size === 0; // keraksiz tugunmi
}

remove(root, [..."oshxona"]); // kod nuqtalari massivi
const h = root.children.get("o").children.get("s").children.get("h");
console.log(h.end, h.children.size); // true 0

"oshxona" o'chdi, lekin "osh" joyida: "h" tugunida so'z tugaydi, shuning uchun u o'chirilmadi, faqat bolasi ("x") ketdi. So'zni [..."oshxona"] bilan harflar massiviga aylantirdik — for...of kabi kod nuqtalari bo'yicha, emoji bo'linmaydi. Vaqt — O(L).

3.4 Avtoto'ldirish va limit

complete ikki bosqichda ishlaydi. Avval #find prefiks tugunini topadi — p ta qadam. Keyin shu tugun ostidagi shoxni aylanib chiqamiz va end belgili tugunlarni yig'amiz. Aylanish iterativ — o'z stekimiz bilan (Stack), xuddi o'tgan darslardagi preorder kabi.

Stekdagi har yozuv — juftlik: [tugun, shu tugungacha yig'ilgan so'z]. Tugundan bolaga tushganda so'zga bitta harf qo'shamiz: word + ch. Shunday qilib, end belgisiga yetganimizda to'liq so'z qo'limizda bo'ladi.

Bolalarni teskari tartibda stekka qo'yamiz (reverse). Stek oxirgi qo'yilganni birinchi beradi, shuning uchun birinchi qo'shilgan bola birinchi chiqadi. Sikl sharti result.length < limit — kerakli miqdor topilishi bilan to'xtaymiz. Mehmonga 5 ta taklif yetarli, qolgan 10 000 tasini qidirishning hojati yo'q.

Takliflar tartibi hozir — qo'shilish tartibi. Haqiqiy ilovalarda ko'pincha "ko'p tanlangani oldin" tartibi kerak. Buning uchun tugunda hisoblagich saqlanadi va topilganlar saralanadi — vazifalar dagi qadamda aynan shunday qilamiz.

4. Murakkablik va o'lchov

4.1 Nazariya

n — so'zlar soni, L — so'z uzunligi, p — prefiks uzunligi, s — topilgan so'zlar (yoki limit gacha ko'rilgan tugunlar) soni. Asosiy farq: Trie so'rovida n yo'q.

O(p + s · L) ni so'z bilan o'qiymiz. Birinchi qism — p: prefiks tuguniga tushish, har harfga bitta qadam. Ikkinchi qism — s · L: topilgan har so'zning harflari bo'ylab yurish. Lug'atdagi qolgan so'zlar bu hisobga umuman kirmaydi. filter esa har so'rovda n ta nomning hammasini ko'radi — mos kelmaydiganlarini ham.

4.2 Tezlik

Sintetik ko'cha nomlari lug'atini yasadik (urug'li generator, o'rtacha 8 harf). Har o'lchovda 1 000 ta so'rov — 4 harfli prefiks, 5 tagacha taklif:

filter: n ikki baravar — vaqt ikki baravar (×1,9–2,1), O(n). Trie: n sakkiz baravar oshdi, vaqt esa 2,5–5 ms atrofida qoldi — bitta so'rov ~3 mikrosoniya. 80 000 nomda farq 250 baravar.

4.3 Narxi: qurish va xotira

Trie tekin emas. Birinchidan, uni qurish kerak: 80 000 nom — ≈ 61 ms (n ikki baravar — vaqt ham ikki baravar). Bu bir martalik ish, lekin lug'at o'zgarganda takrorlanadi.

Ikkinchidan, xotira. 100 000 nomli lug'atni o'lchadik (--expose-gc, process.memoryUsage, Xotira murakkabligi darsidagi usul). Oddiy massiv — ≈ 3,5 MB. Trie — 227 567 tugun va ≈ 50 MB, ya'ni 14 baravar ko'p! Har tugun — alohida obyekt va alohida Map. Umumiy prefikslar tejagan joy obyektlar narxidan ancha kam.

Demak, Trie — vaqt va xotira almashinuvi: tezlikni xotira evaziga sotib olamiz. Xotirani kamaytirish uchun siqilgan Trie (radix tree) bor — bitta bolali tugunlar zanjirini bitta tugunga birlashtiradi ("stava" — bitta qirra). Uni bu yerda yozmaymiz.

4.4 Qo'shimcha: uchinchi yo'l — saralangan massiv

Bu bo'lim ham qo'shimcha: vazifalar qadamida ishlatilmaydi. Lekin u to'g'ri muhandislik savolini o'rgatadi. Trie'ni yozishdan oldin bitta savol bering: "lug'atni saralab qo'ysam-chi?" Saralangan ro'yxatda bir xil boshlanadigan nomlar yonma-yon turadi. Prefiksning birinchi o'rnini ikkiga bo'lib qidirish bilan topamiz, keyin mos nomlarni ketma-ket olamiz:

const streets = ["Yunusobod", "Chilonzor", "Yunusobod-4", "Qatortol",
  "Yunus Rajabiy ko'chasi", "Chorsu"].sort();

// birinchi "prefix dan kichik bo'lmagan" nomning indeksi
function lowerBound(sorted, value) {
  let left = 0;
  let right = sorted.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] < value) left = mid + 1;
    else right = mid;
  }
  return left;
}

function suggestSorted(prefix, limit = 5) {
  const result = [];
  let i = lowerBound(streets, prefix);
  while (i < streets.length && result.length < limit &&
    streets[i].startsWith(prefix)) {
    result.push(streets[i++]); // mos nomlar ketma-ket turadi
  }
  return result;
}

console.log(suggestSorted("Ch")); // [ 'Chilonzor', 'Chorsu' ]
console.log(suggestSorted("Yunusobod").length); // 2

lowerBound — Binary search variantlari darsidagi "birinchi ≥ qiymat" qidiruvi. Satrlar < bilan alifbo (kod birligi) tartibida solishtiriladi. So'rov — O(log n + s): n o'sganda faqat bitta-ikkita qadam qo'shiladi.

Shu lug'atda o'lchadik — natija kutilmagan bo'ldi:

Saralangan massiv Trie'dan ham 10 baravar tez va 14 baravar kam xotira oladi! Sababi — xotira: massivdagi satrlar ixcham, Trie esa har harfda yangi obyekt va Map ga sakraydi (Binary Search Tree darsidagi splice hodisasi kabi).

Unda Trie nimaga kerak? U quyidagi hollarda yutadi:

• Lug'at tez-tez o'zgaradi. Saralangan massivga qo'shish — splice, O(n). Trie'ga — O(L).
• Prefiks bo'yicha hisob kerak. "Nechta so'z 'ma' bilan boshlanadi?" — Trie tugunida hisoblagich saqlasa, O(p) (3-mashq).
• Harfma-harf yurish. Foydalanuvchi bitta harf qo'shganda Trie'da joriy tugundan bitta qadam tushish yetadi — qayta qidirish shart emas.
• Eng uzun mos prefiks. "Matndagi qaysi lug'at so'zi shu joydan boshlanadi?" — Trie'da tabiiy, massivda noqulay.

Xulosa: Trie — kuchli, lekin yagona vosita emas. Tanlashdan oldin o'lchang.

Tekshirib ko'ring: «Bahor» ko'chalar lug'ati yiliga bir marta yangilanadi, lekin kuniga million marta so'raladi. Trie, saralangan massiv yoki filter — qaysi birini tanlaysiz?

Diqqat: Lug'at kichik bo'lsa (o'nlab, yuzlab so'z), filter(startsWith) ham mikrosoniyalar oladi. Trie bu yerda tezlik bermaydi, faqat kodni murakkablashtiradi. «Bahor» menyusidagi 40 ta taom uchun filter — to'g'ri tanlov.

5. Chegaraviy holatlar

• Bo'sh prefiks "". #find("") ildizni qaytaradi — complete("") butun lug'atdan birinchi limit ta so'zni beradi. Ko'pincha bu kerak emas — UI'da bo'sh maydonda takliflarni yashiring.
• Bo'sh so'z. insert("") ildizga end = true qo'yadi — has("") true bo'lib qoladi. Qo'shishdan oldin tekshiring.
• Katta-kichik harf. "Manti" va "manti" — har xil yo'l. Qo'shishda ham, qidirishda ham toLowerCase() (yoki qidiruvdagi normallash).
• Apostrof turlari. o', oʻ, o‘ — uch xil belgi, uch xil yo'l. Normallash kerak.
• Takror. Ikkinchi insert("osh") yangi tugun yaratmaydi, faqat end ni qayta true qiladi. Hisoblagich bo'lsa, uni ikki marta oshirib yubormang.

6. Ko'p uchraydigan xatolar

6.1 has o'rniga startsWith mantiqi

"Yo'l bor — demak, so'z bor" — xato: "mas" yo'li bor, lekin "mas" taom emas. Tuzatish: has da end belgisini tekshiring.

6.2 Har harfda Trie'ni qayta qurish

Takliflar uchun har input hodisasida new Trie() va hamma so'zni qo'shish — O(jami harflar), filter dan ham sekin. Tuzatish: Trie'ni lug'at o'zgarganda bir marta quring, har harfda faqat so'rang.

6.3 Indeks bilan harflash

for (let i = 0; i < word.length; i++) emojini ikki "harf"ga bo'ladi va yarim belgili tugunlar paydo bo'ladi. Tuzatish: for...of.

6.4 Xotirani hisobga olmaslik

"Trie tez — hamma lug'atni Trie'ga solamiz." Million so'zli lug'at bizning o'lchovimiz bo'yicha yarim gigabaytga yaqin xotira olishi mumkin. Telefonda brauzer tabi yopilib qoladi. Tuzatish: avval o'lchang; xotira muhim bo'lsa — saralangan massiv yoki siqilgan Trie.

6.5 limit siz avtoto'ldirish

"a" prefiksida lug'atning yarmi chiqishi mumkin. Hammasini yig'ib, keyin slice(0, 5) qilish — O(n). Tuzatish: stek siklida limit ga yetganda to'xtang.

7. Mashqlar

1-mashq (oson): Trie'ni chizing

Bo'sh Trie'ga "non", "nok", "no'xat" va "osh" qo'shildi. Trie'ni chizing: nechta tugun bor (ildiz bilan)? Qaysi tugunlarda end: true?

        (ildiz)
        /     \
       n       o
       |       |
       o       s
     / | \     |
    n  k  '    h ✓
    ✓  ✓  |
          x
          |
          a
          |
          t ✓

2-mashq (o'rta): Eng uzun umumiy prefiks

commonPrefix(words) funksiyasini yozing: hamma so'zlarning umumiy boshlanishini qaytarsin. ["mastava", "manti", "mampar"] → "ma". Ishora: darsdagi Trie ga hamma so'zlarni qo'shing va ildizdan pastga tushing — toki tugunning bitta bolasi bor va unda so'z tugamaguncha.

function commonPrefix(words) {
  if (words.length === 0) return "";
  const root = { children: new Map(), end: false };
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, { children: new Map(), end: false });
      }
      node = node.children.get(ch);
    }
    node.end = true;
  }
  let prefix = "";
  let node = root;
  while (node.children.size === 1 && !node.end) {
    const [[ch, child]] = node.children; // yagona bola
    prefix += ch;
    node = child;
  }
  return prefix;
}

console.log(commonPrefix(["mastava", "manti", "mampar"])); // ma
console.log(commonPrefix(["osh", "oshxona"])); // osh
console.log(commonPrefix(["non", "osh"]) === ""); // true

3-mashq (qiyin): Prefiks bo'yicha sanash va testlar

kurs/mashqlar/14/41-trie/trie.test.mjs faylida Trie yozing, uning har tugunida pass hisoblagichi bo'lsin: shu tugundan nechta so'z o'tadi. countWithPrefix(prefix) — prefiks bilan boshlanadigan so'zlar sonini O(p) da qaytarsin (pastki daraxtni aylanmasdan). Takror qo'shish hisobni buzmasin. Testlar (node:test): bo'sh Trie, has faqat to'liq so'zda, sanash (bo'sh prefiks ham), takror, apostrof va emoji.

// kurs/mashqlar/14/41-trie/trie.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const makeNode = () => ({ children: new Map(), end: false, pass: 0 });

class Trie {
  root = makeNode();
  insert(word) {
    if (this.has(word)) return; // takror sanalmasin
    let node = this.root;
    node.pass++;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, makeNode());
      node = node.children.get(ch);
      node.pass++; // shu tugundan o'tgan so'zlar soni
    }
    node.end = true;
  }
  #find(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (node === undefined) return null;
    }
    return node;
  }
  has(word) {
    return this.#find(word)?.end === true;
  }
  countWithPrefix(prefix) {
    return this.#find(prefix)?.pass ?? 0;
  }
}

const menu = new Trie();
for (const dish of ["manti", "mastava", "mampar", "osh", "o'rama"]) {
  menu.insert(dish);
}

test("bo'sh Trie", () => {
  const t = new Trie();
  assert.equal(t.has(""), false);
  assert.equal(t.countWithPrefix("a"), 0);
  assert.equal(t.countWithPrefix(""), 0);
});

test("has — faqat to'liq so'z", () => {
  assert.equal(menu.has("manti"), true);
  assert.equal(menu.has("man"), false);
  assert.equal(menu.has("mantilar"), false);
});

test("prefiks bo'yicha sanash — O(p)", () => {
  assert.equal(menu.countWithPrefix("ma"), 3);
  assert.equal(menu.countWithPrefix("mas"), 1);
  assert.equal(menu.countWithPrefix("o"), 2);
  assert.equal(menu.countWithPrefix(""), 5);
  assert.equal(menu.countWithPrefix("x"), 0);
});

test("takror qo'shish sanoqni buzmaydi", () => {
  menu.insert("osh");
  assert.equal(menu.countWithPrefix("o"), 2);
});

test("apostrof va emoji — kod nuqtasi bo'yicha", () => {
  assert.equal(menu.countWithPrefix("o'"), 1);
  const t = new Trie();
  t.insert("🍞non");
  assert.equal(t.has("🍞non"), true);
  assert.equal(t.root.children.size, 1); // emoji — bitta tugun
});

✔ bo'sh Trie (0.837ms)
✔ has — faqat to'liq so'z (0.1729ms)
✔ prefiks bo'yicha sanash — O(p) (0.1081ms)
✔ takror qo'shish sanoqni buzmaydi (1.0208ms)
✔ apostrof va emoji — kod nuqtasi bo'yicha (0.199ms)
ℹ tests 5
ℹ suites 0
ℹ pass 5
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 107.7374

4-mashq: Vazifalar qadami — teg takliflari (PrefiksDaraxti)

vazifalar dagi uchinchi 14-qism qadami. Vazifa matnida teglar bor (Non olish #bozor). Endi "Yangi vazifa" maydoniga #bo yozilganda, ostida ro'yxatdagi mavjud teglardan takliflar chiqadi: #bozor, #bozorlik. Ko'p ishlatilgan teg oldin turadi.

Nega Trie? Teglar lug'ati ro'yxat o'zgarganda bir marta quriladi, har harfda esa faqat so'raladi. Halol aytamiz: o'nlab teg bo'lsa, filter(startsWith) ham mikrosoniyalar oladi. Kanonda Trie shu darsni amalda ko'rsatish uchun. Pastda o'lchovlar buni aniq ko'rsatadi.

vazifalar kanoni o'zbekcha nomlar bilan yozilgan: Trie — PrefiksDaraxti, insert — qosh, has — bormi, complete — boshlanganlar.

1. Branch:

git switch -c feature/teg-taklifi

2. Yangi fayl assets/js/prefiks-daraxti.js (// @ts-check bilan; JSDoc izohlari qisqartirilgan, to'liq fayl — kanon repoda):

// @ts-check
// prefiks-daraxti.js — Trie: so'zlar harfma-harf, umumiy
// boshlanishi bitta yo'lda. Prefiks bo'yicha qidiruv ro'yxat
// uzunligiga bog'liq emas

function yangiTugun() {
  return { bolalar: new Map(), soni: 0 };
}

export class PrefiksDaraxti {
  #ildiz = yangiTugun();
  #hajmi = 0;

  /** Turli so'zlar soni */
  get hajmi() {
    return this.#hajmi;
  }

  /** O(l), l — so'z uzunligi */
  qosh(soz, soni = 1) {
    let tugun = this.#ildiz;
    // for...of — kod nuqtalari bo'yicha: emoji ikkiga bo'linmaydi
    for (const harf of soz) {
      let bola = tugun.bolalar.get(harf);
      if (bola === undefined) {
        bola = yangiTugun();
        tugun.bolalar.set(harf, bola);
      }
      tugun = bola;
    }
    if (tugun.soni === 0) {
      this.#hajmi++;
    }
    tugun.soni += soni;
  }

  /** O(p), p — prefiks uzunligi */
  #tugunniTop(prefiks) {
    let tugun = this.#ildiz;
    for (const harf of prefiks) {
      tugun = tugun.bolalar.get(harf);
      if (tugun === undefined) {
        return undefined;
      }
    }
    return tugun;
  }

  bormi(soz) {
    return (this.#tugunniTop(soz)?.soni ?? 0) > 0;
  }

  /**
   * Ko'p ishlatilgani oldin, teng bo'lsa — kod birligi tartibida
   */
  boshlanganlar(prefiks, nechta = 5) {
    const boshi = this.#tugunniTop(prefiks);
    if (boshi === undefined) {
      return [];
    }
    const topilgan = [];
    // Chuqurlik bo'yicha aylanish (DFS) — rekursiyasiz, stek bilan
    const stek = [[boshi, prefiks]];
    while (stek.length > 0) {
      const [tugun, soz] = stek.pop();
      if (tugun.soni > 0) {
        topilgan.push({ soz, soni: tugun.soni });
      }
      for (const [harf, bola] of tugun.bolalar) {
        stek.push([bola, soz + harf]);
      }
    }
    return topilgan
      .sort(
        (a, b) =>
          b.soni - a.soni ||
          (a.soz < b.soz ? -1 : a.soz > b.soz ? 1 : 0),
      )
      .slice(0, nechta)
      .map(({ soz }) => soz);
  }
}

Darsdagi Trie bilan solishtiring. Bu yerda end: true o'rniga soni maydoni bor. Uning qiymati 0 bo'lsa, so'z bu yerda tugamaydi. Noldan katta bo'lsa — tugaydi va shuncha vazifada ishlatilgan. Metod boshlanganlar darsdagi complete dan bitta joyda farq qiladi: u prefiksli hamma teglarni yig'adi va keyin saralaydi. Sababi — tartib: "ko'p ishlatilgani oldin" bo'lishi uchun hammasini ko'rish kerak. Saralash ko'p kalitli: avval soni kamayib, teng bo'lsa — alifbo.

3. royxat.js — kursordagi teg. Yangi eksport joriyTeg(matn, kursor) — teg grammatikasi (TEG regex) yonida. U kursor oldidagi yozilayotgan tegni qaytaradi: { boshi, prefiks } (prefiks kichik harfda) yoki null. null — kursor so'z o'rtasida, # oldida harf bor (Non#uy) yoki probeldan keyin.

4. render.js — lug'at va tugmalar:

let tegDaraxti = new PrefiksDaraxti();

function tegDaraxtiniQur(sanoq) {
  tegDaraxti = new PrefiksDaraxti();
  for (const [teg, soni] of sanoq) {
    tegDaraxti.qosh(teg, soni);
  }
}

const TAKLIFLAR_SONI = 5;

// joriy — joriyTeg() natijasi; null — takliflar yashiriladi
export function tegTakliflariniYoz(joriy) {
  const takliflar =
    joriy === null
      ? []
      : tegDaraxti
          .boshlanganlar(joriy.prefiks, TAKLIFLAR_SONI + 1)
          .filter((teg) => teg !== joriy.prefiks)
          .slice(0, TAKLIFLAR_SONI);
  tegTakliflari.replaceChildren(
    ...takliflar.map((teg) => {
      const tugma = document.createElement("button");
      tugma.type = "button";
      tugma.dataset.teg = teg;
      tugma.textContent = teg;
      return tugma;
    }),
  );
  tegTakliflari.hidden = takliflar.length === 0;
}

tegDaraxtiniQur teglarniYoz() ichida chaqiriladi — ya'ni ro'yxat o'zgarganda, tegHisobi() natijasidan. Har harfda esa faqat boshlanganlar so'raladi. TAKLIFLAR_SONI + 1 va filter — aniq yozilgan tegni ("#bozor" to'liq yozilgan bo'lsa) takliflardan olib tashlash uchun. Tugma matni — textContent, HTML emas (XSS va DOM xavfsizligi).

5. asosiy.js — maydonning input tinglovchisiga bitta qator (// + — yangisi). maydon.selectionStart — kursorning matndagi o'rni:

// Kursor yozilayotgan teg ustida bo'lsa — mavjud teglardan taklif
function tegTakliflariniYangila() {
  tegTakliflariniYoz(joriyTeg(maydon.value, maydon.selectionStart));
}

maydon.addEventListener("input", () => {
  qoralamaniKechiktir(maydon.value);
  tegTakliflariniYangila(); // +
  if (maydon.getAttribute("aria-invalid") !== "true") {
    return;
  }
  // ... xatoni tozalash (o'zgarmagan)
});

Yana uchta ish: ↓ — birinchi taklifga fokus; Esc — takliflarni yopish (fokus maydonga qaytadi); taklif bosilsa — tegniQoy(teg). U setRangeText bilan yozilayotgan tegni to'liq teg va probel bilan almashtiradi. Keyin input hodisasini yuboradi — qoralama va xatolar odatdagi yo'ldan yangilansin.

6. index.html va CSS:

<div id="teg-takliflari" role="group"
     aria-label="Teg takliflari" hidden></div>

#teg-takliflari:not([hidden]) {
  display: flex;
  flex-wrap: wrap;
  gap: 0.5rem;
  margin-top: 0.5rem;
}

:not([hidden]) — tuzoqdan himoya: oddiy #teg-takliflari { display: flex } hidden atributini bosib ketardi va bo'sh guruh ko'rinib qolardi. sw.js — VERSIYA v4-6, QOBIQ ga prefiks-daraxti.js qo'shiladi.

7. Testlar. tekshiruv/prefiks-daraxti.test.js — 17 ta: Trie 7 (tartib, nechta chegarasi, to'liq so'z, bormi/hajmi, takror, emoji va apostrof, bo'sh daraxt), joriyTeg 9 holat, ro'yxat teglari + daraxt 1. Hammasi — 137/137 (v4 ning 90 tasi o'zgarishsiz). npm run lint, format:check, tip — toza. Brauzer tekshiruvi (Chrome 154) — 159/159, ulardan teg takliflariga tegishlilari:

✅ teg: #bo — ko'p ishlatilgani oldin: ["#bozor","#bozorlik"]
✅ teg: # — hammasi (soni, keyin alifbo): ["#o'quv","#bozor","#bozorlik","#oila"]
✅ teg: ↓ — birinchi taklifga fokus: "#bozor"
✅ teg: Enter — teg qo'yildi, fokus maydonda, takliflar yopildi: ["Guruch #bozor ","yangi-matn",14,true]
✅ teg: qoralama ham yangilandi: "Guruch #bozor "
✅ teg: yangi hisob bilan (#bozor endi 3): ["#o'quv","#oila"]
✅ teg: Esc — yopildi, matn joyida: [null,"Kitob #oila #b"]
✅ teg: kursor so'z o'rtasida — taklif yo'q: null

8. Halol o'lchov (Node 24, kanondagi murakkablik.md; 1 000 va 100 000 vazifa, ulardagi turli teglar T = 276 va 2 010):

Xulosa darsdagi nazariya bilan bir xil. Kam mos keladigan prefiksda Trie lug'at hajmiga bog'liq emas va 14–50 baravar tez. Ko'p mos keladiganda ikkalasi teng — vaqtni pastki daraxtni aylanish va saralash oladi (O(s log s)). Qurish — 0,19 ms va 1,5 ms, faqat ro'yxat o'zgarganda.

9. Ataylab qilinmagan (TEXNIK-QARZ.md, 20- va 21-qator): takliflar — tugmalar guruhi, to'liq ARIA combobox emas (ekran o'quvchi takliflar paydo bo'lganini e'lon qilmaydi); #o'quv va #oʻquv — ikki xil teg (qidiruv ularni birlashtiradi, teglar — yo'q).

10. Commit va PR — sarlavha qisqa (47 belgi), tafsilot tanada:

git add assets/js/prefiks-daraxti.js tekshiruv/prefiks-daraxti.test.js
git add assets/js/royxat.js assets/js/render.js assets/js/asosiy.js
git add index.html assets/css/vazifalar.css sw.js
git add README.md AGENTS.md TEXNIK-QARZ.md
git add tekshiruv/ssenariy.md jsconfig.json
git commit -m "feat: teg takliflari — prefiks daraxti (Trie)" \
  -m "README murakkablik jadvali, AGENTS va TEXNIK-QARZ v4.1"
git push -u origin feature/teg-taklifi
gh pr create --fill
gh pr merge --merge

Shu bilan vazifalar v4.1 tayyor: qidiruv, saralash va teg takliflari. README'dagi "Murakkablik" jadvali har amalning Big-O'si va o'lchovini ko'rsatadi.

8. Real ishda

• Qidiruv maydonlari. Manzil, shahar, mahsulot nomlari bo'yicha avtoto'ldirish. Katta tizimlarda Trie serverda yoki qidiruv tizimida (Elasticsearch'ning "completion suggester"i shunga o'xshash tuzilma) turadi, brauzer esa faqat natijani oladi.
• Tarmoq marshrutizatsiyasi. Routerlar IP manzillarni eng uzun mos prefiks bo'yicha yo'naltiradi — bu ham Trie (bitlar bo'yicha).
• Veb-freymvorklar. Ko'p server freymvorklari URL marshrutlarini (/menyu/:id, /menyu/yangi) radix tree'da saqlaydi va har so'rovda kerakli ishlovchini O(URL uzunligi) da topadi. Node serverlarni 24-qismdan o'rganamiz.
• Imlo tekshiruvi va so'z o'yinlari. Lug'atdagi so'zlarni tez tekshirish, "shu harflardan qaysi so'zlar chiqadi" kabi masalalar.
• Intervyu. "Trie'ni amalga oshiring" (LeetCode 208), "so'zlarni qidirish" (211, 212) — Trie bo'yicha klassik savollar.

Xulosa

• Trie — har qirra bitta harf, umumiy prefiks bitta yo'l; so'z tugaydigan tugunda belgi (end yoki soni).
• insert, has, startsWith — O(L), lug'at hajmiga bog'liq emas; avtoto'ldirish — prefiks tuguni + pastki daraxtda DFS, limit bilan.
• O'lchov: 80 000 nomda 1 000 so'rov — Trie ≈ 3 ms, filter ≈ 830 ms. Lekin xotira — 14 baravar ko'p (100 000 nomga ≈ 50 MB).
• Kichik lug'atda filter yetarli; Trie lug'at katta va so'rov ko'p bo'lganda foyda beradi.
• vazifalar v4.1: teg takliflari — PrefiksDaraxti, lug'at ro'yxat o'zgarganda quriladi, 137 test, brauzerda 159/159.

Keyingi dars: Heap — eng kichik (yoki eng katta) elementni doim tepada tutadigan, massivda saqlanadigan daraxt.

Manbalar

• Edward Fredkin, "Trie Memory", Communications of the ACM, 1960 — "trie" atamasining kelib chiqishi.
• Robert Sedgewick, Kevin Wayne, "Algorithms", 4-nashr, Addison-Wesley, 2011 — 5-bob (tries).
• MDN: Map, String.prototype[Symbol.iterator] (kod nuqtalari bo'yicha for...of), HTMLInputElement.setRangeText() — developer.mozilla.org