Qidiruv tizimlari qanday ishlaydi: inverted index, BM25 va typo tolerance

Qisqacha: Qidiruv dvigateli matnni oldindan so'zlarga bo'lib, har so'z uchun "qaysi hujjatlarda bor" ro'yxatini — inverted index ni — tuzadi. So'rov kelganda butun bazani o'qimaydi, faqat so'zlarning ro'yxatlarini oladi va hujjatlarni BM25 formulasi bilan "qanchalik mos" bo'yicha saralaydi. Xato yozilgan so'zni topish (typo tolerance) va natijani toifalar bo'yicha sanash (facet) — shu indeks ustiga qurilgan qo'shimchalar.

Bu darsda

• Inverted index'ni JavaScript'da o'zingiz qurib, u nega LIKE '%so'z%' dan tez ekanini tushuntirasiz.
• Tokenizatsiya, normallash va stemming nima qilishini va o'zbek tilida qayerda qoqilishini ko'rasiz.
• BM25 formulasini qismlarga bo'lib, hujjatlarni ball bo'yicha saralaysiz.
• Typo tolerance (Levenshtein masofasi) va facet'larni o'zingiz yozasiz.
• Postgres full-text search yetadigan va alohida qidiruv dvigateli kerak bo'ladigan vaziyatni ajrata olasiz.

Oldin bilishingiz kerak: Postgres'da full-text search (tsvector, uz_normal, pg_trgm), Map, Transactional outbox naqshi.

1. Nega bu kerak?

Postgres'da full-text search darsida vazifalar jadvaliga tsvector ustun va GIN indeks qo'shgandik. U ishladi. Lekin uchta savol ochiq qoldi.

Birinchisi — foydalanuvchi kitb deb yozsa, Postgres hech narsa topmaydi. Ikkinchisi — kitoblarni so'zi kitob bilan bog'lanmaydi: Postgres'da o'zbek tili uchun lug'at yo'q. Uchinchisi — internet-do'kon qidiruvida chap tomonda "Kategoriya: kitoblar (124), daftarlar (37)" kabi sanoqlar bo'ladi. Ularni har so'rovda GROUP BY bilan hisoblash qimmat.

Bu ishlarni maxsus qidiruv dvigateli (search engine) qiladi: Meilisearch, Typesense, Elasticsearch. Ularni keyingi darslarda ishlatamiz. Bu darsda esa ichiga qaraymiz: dvigatel aslida nima qiladi? Javob — oddiy JavaScript bilan yozsa bo'ladigan bir nechta g'oya. Ularni tushunsangiz, har qanday dvigatelning sozlamalari ("searchable attributes", "typo tolerance", "ranking rules") o'z-o'zidan ma'noli bo'ladi.

O'xshatish: kutubxonachi. U har kitobni varaqlab so'z qidirmaydi. Unda kartochkalar qutisi bor: "bozor — 3-, 17-, 42-kitob". Mana shu quti — inverted index.

2. Inverted index

2.1 Oddiy indeks va teskari indeks

Bazadagi jadval "hujjat → matn" ko'rinishida: 1 → "Kitob do'koniga borish". Bu to'g'ri (forward) yo'nalish. Qidiruvga esa teskarisi kerak: "so'z → hujjatlar". Shuning uchun nomi inverted index (teskari indeks). Har so'z uchun saqlanadigan hujjatlar ro'yxatini posting list deyishadi.

Keling, to'rt hujjat bilan quramiz. Bu blok brauzerda ham ishlaydi:

const hujjatlar = [
  { id: 1, matn: "Kitob do'koniga borish" },
  { id: 2, matn: "Ingliz tili kitobini o'qish" },
  { id: 3, matn: "Kitob o'qish: har kuni 20 bet" },
  { id: 4, matn: "Bozordan non va sut olish" },
];

const tok = (s) =>
  s.toLowerCase().split(/[^a-z0-9']+/).filter(Boolean);

const indeks = new Map();
for (const h of hujjatlar) {
  for (const soz of new Set(tok(h.matn))) {
    if (!indeks.has(soz)) indeks.set(soz, []);
    indeks.get(soz).push(h.id);
  }
}

console.log(indeks.get("kitob"));
console.log(indeks.get("o'qish"));
console.log(indeks.get("kitobini"));
console.log(indeks.size, "ta term");

Konsolda:

[ 1, 3 ]
[ 2, 3 ]
[ 2 ]
16 ta term

tok — tokenizatsiya (tokenization): matnni so'zlarga (token) bo'lish. Indeksdagi har noyob so'z — term. new Set bir hujjatda takrorlangan so'zni bir marta yozadi.

Endi kitob o'qish so'rovi uchun butun matnni o'qish shart emas. Ikkita ro'yxatni olamiz va kesishmasini topamiz: [1, 3] va [2, 3] → [3]. Hujjat 50 000 ta bo'lsa ham, biz faqat ikki ro'yxatga qaraymiz.

2.2 LIKE bilan farqi

WHERE matn ILIKE '%kitob%' har qatorni boshidan oxirigacha o'qiydi. U kitobini ni ham topadi (bo'lak sifatida), lekin do'kon so'rovi do'koniga ni topgani kabi, ingliz so'rovi inglizcha ni ham, non so'rovi nonvoyxona ni ham topadi — bu ko'pincha keraksiz. Eng muhimi, LIKE natijani saralamaydi: qaysi hujjat ko'proq mos — bilmaydi.

Indeks esa yuqoridagi chiqishda yana bir muammoni ko'rsatdi: kitobini — alohida term. kitob so'rovi 2-hujjatni topmaydi. Buni normallash va stemming hal qiladi.

Tekshirib ko'ring: Nega posting list'dagi hujjat raqamlari o'sish tartibida saqlanadi?

3. Matnni tayyorlash: normallash va stemming

3.1 Normallash

Indeksga yozishdan oldin har so'z bir xil shaklga keltiriladi — normallash (normalization). Kichik harf — eng oddiysi. O'zbek tilida yana bitta muhim qadam bor: apostrof. Foydalanuvchi o'qish ni to'rt xil yozishi mumkin — oddiy apostrof, chap va o'ng qo'shtirnoq yoki maxsus ʻ belgisi bilan. Ekranda deyarli bir xil, kompyuter uchun to'rt xil so'z.

const norm = (s) =>
  s.toLowerCase().replace(/[‘’ʻʼ`]/g, "'");

const yozuvlar = [
  "o'qish",
  "O‘qish",
  "o’qish",
  "oʻqish",
];
console.log(yozuvlar.map((s) => s.length));
console.log(new Set(yozuvlar).size, "xil");
console.log(new Set(yozuvlar.map(norm)).size, "xil");

Konsolda:

[ 6, 6, 6, 6 ]
4 xil
1 xil

Muhim qoida: indekslashda va so'rovda bir xil normallash ishlatiladi. Hujjatni normallab, so'rovni normallamasangiz — yoki aksincha — hech narsa topilmaydi. Postgres'da full-text search darsidagi uz_normal ham, bu darsdagi norm ham shu qoidaga bo'ysunadi.

Kirill va lotin yozuvini birlashtirish ham normallashning bir turi. Uni Backend'da ko'p tillilik darsida transliteratsiya bilan qilamiz.

3.2 Stemming

Stemming — so'zdan qo'shimchalarni kesib, ildizga yaqin shaklni olish: kitoblarni → kitob. Ingliz tilida running → run. O'zbek tili qo'shimchalar bilan quriladi (agglutinativ til): bitta ildizga -lar, -ni, -ga, -dan, -imiz kabi qo'shimchalar ketma-ket qo'shiladi. Shuning uchun stemming bu yerda ayniqsa kerak.

Keng tarqalgan stemmerlar to'plami Snowball'da o'zbek tili yo'q (2026-10 holatiga). Postgres ham, ko'p dvigatellar ham o'zbekcha uchun tayyor stemming bermaydi. Eng oddiy o'z stemmerimizni yozib ko'ramiz — va uning qayerda adashishini ham:

const QOSHIMCHALAR = [
  "larning", "lardan", "larni", "larga",
  "ning", "dan", "lar", "ni", "ga", "da",
];

function ildiz(soz) {
  for (const q of QOSHIMCHALAR) {
    if (soz.endsWith(q) && soz.length - q.length >= 3) {
      return soz.slice(0, -q.length);
    }
  }
  return soz;
}

const sozlar = [
  "kitoblarni", "kitoblar", "bozordan", "toshkentda",
  "kitobini", "panda", "kitobim",
];
for (const s of sozlar) console.log(s, "→", ildiz(s));

Konsolda:

kitoblarni → kitob
kitoblar → kitob
bozordan → bozor
toshkentda → toshkent
kitobini → kitobi
panda → pan
kitobim → kitobim

Uch xil natija ko'rinyapti:

• kitoblarni, kitoblar, bozordan, toshkentda — to'g'ri ildiz.
• kitobini → kitobi: egalik qo'shimchasi (-i) qoldi. Bu — understemming (yetarlicha kesilmagan).
• panda → pan: hayvon nomi o'rin-payt qo'shimchasi deb kesildi. Bu — overstemming (ortiqcha kesilgan). Endi pan so'rovi panda haqidagi hujjatni topadi.

Ro'yxat tartibi ham muhim: avval uzun qo'shimchalar. Aks holda kitoblarni dan avval -ni kesilib, kitoblar qolardi. Uzunlik chegarasi (>= 3) soda, bino kabi qisqa so'zlarni himoya qiladi, lekin panda ni emas.

Xulosa: stemming qidiruvni kengaytiradi (ko'proq topadi), lekin aniqlikni pasaytiradi (keraksizini ham topadi). O'zbekcha uchun yaxshi stemmer — lug'atli morfologik tahlil. Oddiy loyihada ko'pincha stemming o'rniga prefiks qidiruv (kitob → kitob... bilan boshlanganlar) va typo tolerance yetarli bo'ladi. Ularni pastda ko'ramiz.

Diqqat: Stemming va normallash qoidasini o'zgartirsangiz — butun indeksni qaytadan qurish kerak. Eski hujjatlar eski qoida bilan yozilgan, yangi so'rovlar esa yangi qoida bilan keladi.

3.3 Tahlil zanjiri

Dvigatellarda bu bosqichlarning hammasi bitta analyzer (tahlilchi) ichida ketma-ket ishlaydi. Elasticsearch'da u aynan shunday ataladi, Meilisearch'da esa ichiga qurilgan. Indekslash va qidiruv yo'li quyidagicha:

flowchart LR
  H["Hujjat matni"] --> T["Tokenizatsiya"]
  T --> N["Normallash"]
  N --> S["Stemming"]
  S --> I[("Inverted index")]
  Q["So'rov matni"] --> T2["Xuddi shu zanjir"]
  T2 --> I
  I --> R["Ball (BM25) va saralash"]

Diagrammadagi asosiy fikr: so'rov ham hujjat bosib o'tgan zanjirdan o'tadi. Ikkala yo'l bitta indeksda uchrashadi.

4. Relevance: BM25 bilan saralash

4.1 Qaysi hujjat "ko'proq mos"?

Relevance (moslik) — hujjat so'rovga qanchalik javob berishi. Uni hisoblashda uchta sezgi bor:

1. TF (term frequency — so'z chastotasi): so'z hujjatda ko'p uchrasa — hujjat ko'proq mos. Lekin 10 marta uchragani 1 martadan 10 barobar mos emas. Shuning uchun o'sish to'yinadi.
2. IDF (inverse document frequency — teskari hujjat chastotasi): kam uchraydigan so'z qimmatroq. va deyarli hamma hujjatda bor — u hech narsani ajratmaydi. dorixona esa kam — u topilsa, muhim.
3. Uzunlik: so'z qisqa hujjatda topilsa, uzun hujjatdagidan kuchliroq signal. 3 so'zli sarlavhadagi kitob 300 so'zli matndagi kitob dan muhimroq.

BM25 (Best Matching 25) — shu uchta sezgini bitta formulaga yig'adi. U 1990-yillardan beri qidiruvda asosiy formula: Elasticsearch va OpenSearch'da sukut bo'yicha, Lucene asosidagi boshqa dvigatellarda ham.

Ikki sozlama bor: k1 (odatda 1.2) — TF qanchalik tez to'yinadi; b (odatda 0.75) — uzunlik qanchalik hisobga olinadi. Hujjat balli — so'rovdagi har so'z ballari yig'indisi.

4.2 JavaScript'da BM25

Kanon BM25'ni 20 qatorga yaqin kod bilan yozgan. Biz o'sha formulani kichik, real matnlarda ishlatamiz:

const hujjatlar = [
  "Kitob o'qish",
  "Kitob o'qish klubi: har shanba kitob muhokamasi",
  "Ingliz tilida kitob o'qish va so'z yodlash",
  "Kitob do'koniga borish",
  "Bozordan non olish",
  "Kitob kitob kitob: kutubxona ro'yxati",
];
const tok = (s) =>
  s.toLowerCase().split(/[^a-z0-9']+/).filter(Boolean);
const sozlar = hujjatlar.map(tok);
const N = sozlar.length;
const ortacha = sozlar.reduce((a, s) => a + s.length, 0) / N;

function bm25(sorov, k1 = 1.2, b = 0.75) {
  const ballar = sozlar.map(() => 0);
  for (const t of tok(sorov)) {
    const n = sozlar.filter((s) => s.includes(t)).length;
    if (n === 0) continue;
    const idf = Math.log(1 + (N - n + 0.5) / (n + 0.5));
    sozlar.forEach((s, i) => {
      const f = s.filter((x) => x === t).length;
      const L = 1 - b + b * (s.length / ortacha);
      ballar[i] += idf * (f * (k1 + 1)) / (f + k1 * L);
    });
  }
  return ballar
    .map((ball, i) => ({ i, ball: Number(ball.toFixed(3)) }))
    .filter((x) => x.ball > 0)
    .sort((a, b) => b.ball - a.ball);
}

for (const x of bm25("kitob o'qish")) {
  console.log(x.ball, hujjatlar[x.i]);
}

Konsolda:

1.209 Kitob o'qish
0.852 Kitob o'qish klubi: har shanba kitob muhokamasi
0.761 Ingliz tilida kitob o'qish va so'z yodlash
0.37 Kitob kitob kitob: kutubxona ro'yxati
0.279 Kitob do'koniga borish

Natijani o'qiymiz:

• Birinchi o'rinda eng qisqa hujjat — Kitob o'qish. Ikkala so'z bor, matn qisqa — kuchli signal.
• Kitob kitob kitob: kutubxona ro'yxati da kitob uch marta, lekin o'qish yo'q. TF to'yingani uchun u uch barobar ball olmadi va ikkala so'z bor hujjatlardan pastda qoldi.
• Bozordan non olish ro'yxatda yo'q: ball 0.

Bu misolda haqiqiy indeks yo'q — har so'rovda hamma hujjatni aylanamiz. Dvigatel esa n ni posting list uzunligidan, f ni esa posting ichida saqlangan sondan oladi va faqat so'z bor hujjatlarni hisoblaydi.

Tekshirib ko'ring: b = 0 qilsangiz natija qanday o'zgaradi?

4.3 Kanon o'lchovi: 50 000 hujjat

Kanon xuddi shu g'oyani (posting list bilan, k1 = 1.2, b = 0.75) 50 000 ta sun'iy vazifada o'lchagan. Vazifa matnlari 35 so'zli lug'atdan tasodifiy yig'ilgan (Node 24.21.0, i5-12500H, Windows 11):

indeks: 35 term, 50000 hujjat, qurish 525 ms; "kitob" posting ro'yxati 6857 ta
bm25("kitoblar") (stemming yo'q): 0 natija; bm25("o‘qish" — boshqa apostrof): 5 natija (normallash ishladi)
so'rov vaqti (4 so'z): mediana 25.27 ms

Uch xulosa. Birinchisi — indeks bir marta quriladi (525 ms), keyin har so'rov ~25 ms. Ikkinchisi — stemming bo'lmasa kitoblar hech narsa topmaydi. Uchinchisi — apostrof normallash ishladi.

Kanon bitta halol eslatma ham qoldirgan: lug'at atigi 35 so'z bo'lgani uchun eng yaxshi beshta natija bir xil 4.99 ball oldi (matnlari ham bir xil — o'qish do'kon kitob kitob). Sun'iy ma'lumotda saralashni baholab bo'lmaydi. Shuning uchun yuqorida real matnlardan foydalandik.

5. Typo tolerance va prefiks

5.1 Levenshtein masofasi

Foydalanuvchi kitb yozdi. Inverted index'da bunday term yo'q. Typo tolerance (xatoga chidamlilik) — so'rovdagi so'zga "yaqin" termlarni ham qidirish. Yaqinlik o'lchovi — Levenshtein masofasi: bir so'zni ikkinchisiga aylantirish uchun nechta harf qo'shish, o'chirish yoki almashtirish kerak.

function masofa(a, b) {
  const d = Array.from({ length: a.length + 1 }, (_, i) =>
    Array.from({ length: b.length + 1 }, (_, j) =>
      i === 0 ? j : j === 0 ? i : 0,
    ),
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      const narx = a[i - 1] === b[j - 1] ? 0 : 1;
      d[i][j] = Math.min(
        d[i - 1][j] + 1,
        d[i][j - 1] + 1,
        d[i - 1][j - 1] + narx,
      );
    }
  }
  return d[a.length][b.length];
}

const termlar = ["kitob", "kino", "hisobot", "dorixona", "bozor"];
const ruxsat = (soz) =>
  soz.length >= 8 ? 2 : soz.length >= 4 ? 1 : 0;

for (const s of ["kitb", "hisobt", "dorxna", "bzr"]) {
  const mos = termlar.filter((t) => masofa(s, t) <= ruxsat(s));
  console.log(s, "→", mos);
}

Konsolda:

kitb → [ 'kitob' ]
hisobt → [ 'hisobot' ]
dorxna → []
bzr → []

Bu Dinamik dasturlash dagi jadval usuli. ruxsat funksiyasi — dvigatellardagi muhim qoida: qisqa so'zda xatoga ruxsat yo'q. bzr uch harfli — unga bitta xato ruxsat bersak, bor, bir, biz kabi o'nlab so'z mos keladi. Kanon Meilisearch'ni aynan shunday sozlagan: 4 harfdan — bitta xato, 8 harfdan — ikkita.

dorxna → dorixona ikki harf qo'shish talab qiladi, lekin dorxna 6 harfli — ikki xatoga ruxsat yo'q. Shuning uchun topilmadi.

Haqiqiy dvigatel har so'rovda hamma termlar bilan masofa hisoblamaydi — bu sekin. Ular termlarni maxsus avtomat yoki daraxtda saqlab, "masofasi 1 dan oshmaydiganlar"ni bir yurishda topadi (Meilisearch va Lucene'da Levenshtein avtomatlari). G'oya esa bir xil.

5.2 Prefiks qidiruv

Foydalanuvchi hali yozib turibdi: dorixon. Natija darhol chiqishi kerak (search-as-you-type). Prefiks qidiruv — oxirgi so'zni "shu bilan boshlanadi" deb qidirish. Termlar saralangan bo'lsa, prefiksli termlar ketma-ket turadi — ularni ikkilik qidiruv bilan tez topish mumkin.

Kanon buni tayyor kichik kutubxona — MiniSearch 7.2.0 bilan, o'sha 50 000 hujjatda sinagan:

indekslash 434 ms
"kitob" {} → 6857 natija; 1-si: "kitob hisobot kitob kitob"
"kitb" {"fuzzy":0.2} → 6857 natija; 1-si: "kitob hisobot kitob kitob"
"dorixon" {"prefix":true} → 5739 natija; 1-si: "dorixona imtihon dorixona"
"hisobotlar" {"fuzzy":0.2} → 0 natija; 1-si: "undefined"

fuzzy: 0.2 — ruxsat etilgan xato soni so'z uzunligining 20 % i. kitb (4 harf) uchun bu 0.8 — MiniSearch uni yaxlitlab 1 ta xato beradi va kitob ni topadi. hisobotlar esa hisobot dan uch harf uzun: 10 × 0.2 = 2 ta xato yetmaydi. Bu yerda stemming yoki prefiks yordam berardi, typo tolerance emas. Har vosita o'z muammosini hal qiladi.

MiniSearch — brauzerda ham ishlaydigan kichik qidiruv kutubxonasi. Bir necha ming hujjatli sayt ichidagi qidiruv uchun (masalan hujjatlar sayti) serversiz yechim. 50 000 dan ortiq hujjat va ko'p foydalanuvchi uchun esa server tomondagi dvigatel kerak.

6. Facet'lar

Facet — qidiruv natijasini maydon qiymatlari bo'yicha sanash: "ustuvorlik: yuqori (3), o'rta (4), past (1)". Foydalanuvchi bosib, natijani toraytiradi. Mantiq oddiy — natijadagi hujjatlarni guruhlab sanash:

const natija = [
  { id: 4, ustuvorlik: "yuqori", bajarildi: false },
  { id: 9, ustuvorlik: "orta", bajarildi: false },
  { id: 12, ustuvorlik: "orta", bajarildi: true },
  { id: 15, ustuvorlik: "past", bajarildi: false },
  { id: 21, ustuvorlik: "yuqori", bajarildi: true },
];

function facetlar(hujjatlar, maydonlar) {
  const sanoq = {};
  for (const m of maydonlar) {
    sanoq[m] = {};
    for (const h of hujjatlar) {
      const k = String(h[m]);
      sanoq[m][k] = (sanoq[m][k] ?? 0) + 1;
    }
  }
  return sanoq;
}

console.log(facetlar(natija, ["ustuvorlik", "bajarildi"]));

Konsolda:

{
  ustuvorlik: { yuqori: 2, orta: 2, past: 1 },
  bajarildi: { false: 3, true: 2 }
}

Natija 5 ta bo'lsa — oson. Natija 200 000 ta bo'lsa, hammasini xotiraga olib sanash sekin. Dvigatellar facet maydonlari uchun alohida indeks saqlaydi: "ustuvorlik = yuqori → [hujjatlar to'plami]". Keyin natija to'plami bilan kesishma hajmini hisoblaydi — hujjatlarning o'zini o'qimaydi. Shuning uchun Meilisearch'da maydonni oldindan filterableAttributes ga yozish kerak: dvigatel unga indeks tuzadi. Buni keyingi darsda ko'ramiz.

7. Postgres FTS yoki alohida dvigatel?

Kanon o'sha 50 000 matnni Postgres'ga ham yozib, simple konfiguratsiyadagi full-text search bilan solishtirgan (PostgreSQL 18.6):

Postgres FTS (filtr bilan): mediana 3.96 ms; xato so'z "kitb" → 0 natija (typo tolerance yo'q; pg_trgm kerak — 27-qism)
"o'qish" simple parser'da: 'kitob':3 'o':1 'qish':2 — apostrof so'zni bo'ladi (27-qism topilmasi)

Postgres tez (4 ms), lekin typo tolerance va facet'lar yo'q. Apostrof muammosi — 27-qismda uz_normal bilan hal qilgandik. Qaror jadvali:

Oxirgi qator ko'pincha hal qiluvchi. Alohida dvigatel — yana bitta server, unga ma'lumotni yetkazish (sinxronlash) va u ishlamay qolsa nima bo'lishi haqida qaror. Sinxronlashni keyingi darsda Transactional outbox bilan ulaymiz.

Kanon xulosasi: vazifalar-api uchun 27-qismdagi Postgres FTS yetarli. Alohida dvigatel — typo tolerance, facet va millionlab hujjat kerak bo'lganda. Bunday joy kursda bor: 38-qismdagi bozor loyihasining mahsulot katalogi.

8. Hujumchi nigohi

Qidiruv — foydalanuvchi matni to'g'ridan dvigatelga boradigan joy. Hujumchi nima qiladi:

1. Boshqalarning hujjatini ko'radi. Indeks hamma foydalanuvchining vazifalarini saqlaydi. Qidiruvda egasi bo'yicha filtr unutilsa — begona vazifalar chiqadi. Himoya — filtrni server qo'yadi, mijoz emas (keyingi darsda Meilisearch tenant token'i).
2. Og'ir so'rov yuboradi. 5 000 so'zli so'rov yoki har so'zda typo tolerance — har biri ko'p posting list ochadi. Himoya — so'rov uzunligini cheklash (masalan 200 belgi, 10 so'z) va Rate limiting.
3. So'rovni regex qilib yuboradi. Agar server foydalanuvchi matnidan new RegExp(q) yasasa — (a+)+$ kabi ifoda serverni qotiradi (ReDoS). Himoya — foydalanuvchi matnini regex qilmang, token sifatida ishlating.
4. Sanoq orqali ma'lumot sizdiradi. Facet sanog'i ham ma'lumot: "maosh > 10 mln: 3 ta". Filtrlangan bo'lmasa, yashirin yozuvlar soni ko'rinadi. Himoya — facet ham o'sha ruxsat filtridan keyin hisoblanadi.

9. Ko'p uchraydigan xatolar

10. Mashqlar

Mashqlar kurs/mashqlar/29/52-qidiruv/ da.

1-mashq (oson): bo'shliqlarni to'ldiring

• "So'z → hujjatlar ro'yxati" tuzilmasi —
• Bitta so'zga tegishli hujjatlar ro'yxati — posting
• Kam uchraydigan so'zga ko'proq ball beradigan qism —
• panda → pan xatosi —
• kitb va kitob orasidagi Levenshtein masofasi —

2-mashq (o'rta): "Balki siz ... demoqchimisiz?"

taklif(soz, termlar) funksiyasini yozing. U soz ga eng yaqin termni qaytarsin (Levenshtein masofasi eng kichik). Masofa 2 dan katta bo'lsa — null. Teng masofada — ro'yxatda birinchi kelgani. Darsdagi masofa funksiyasini ishlating. Termlar: ["kitob", "kino", "hisobot", "dorixona", "bozor", "sport"]. Sinang: kitb, sprot, dorxona, avtobus.

function masofa(a, b) {
  const d = Array.from({ length: a.length + 1 }, (_, i) =>
    Array.from({ length: b.length + 1 }, (_, j) =>
      i === 0 ? j : j === 0 ? i : 0,
    ),
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      const narx = a[i - 1] === b[j - 1] ? 0 : 1;
      d[i][j] = Math.min(
        d[i - 1][j] + 1,
        d[i][j - 1] + 1,
        d[i - 1][j - 1] + narx,
      );
    }
  }
  return d[a.length][b.length];
}

function taklif(soz, termlar) {
  let eng = null;
  let engMasofa = Infinity;
  for (const t of termlar) {
    const m = masofa(soz, t);
    if (m < engMasofa) {
      eng = t;
      engMasofa = m;
    }
  }
  return engMasofa <= 2 ? eng : null;
}

const termlar = [
  "kitob", "kino", "hisobot", "dorixona", "bozor", "sport",
];
for (const s of ["kitb", "sprot", "dorxona", "avtobus"]) {
  console.log(s, "→", taklif(s, termlar));
}

kitb → kitob
sprot → sport
dorxona → dorixona
avtobus → null

3-mashq (qiyin): stemming bilan indeks va AND qidiruv

qidir(sorov) yozing: hujjatlarni norm → tokenizatsiya → ildiz (darsdagi stemmer) zanjiridan o'tkazib inverted index tuzing; so'rovni ham shu zanjirdan o'tkazib, hamma so'zlari bor hujjatlar id'larini qaytaring (posting list'lar kesishmasi). Hujjatlar: 1: "Kitoblarni kutubxonaga topshirish", 2: "Kitob o‘qish", 3: "Bozordan kitob olish", 4: "Bozorga borish". So'rovlar: kitob, kitoblar bozordan, bozor, o'qish kitoblarni.

const norm = (s) =>
  s.toLowerCase().replace(/[‘’ʻʼ`]/g, "'");
const QOSHIMCHALAR = [
  "larning", "lardan", "larni", "larga",
  "ning", "dan", "lar", "ni", "ga", "da",
];
function ildiz(soz) {
  for (const q of QOSHIMCHALAR) {
    if (soz.endsWith(q) && soz.length - q.length >= 3) {
      return soz.slice(0, -q.length);
    }
  }
  return soz;
}
const termlar = (s) =>
  norm(s).split(/[^a-z0-9']+/).filter(Boolean).map(ildiz);

const hujjatlar = [
  { id: 1, matn: "Kitoblarni kutubxonaga topshirish" },
  { id: 2, matn: "Kitob o‘qish" },
  { id: 3, matn: "Bozordan kitob olish" },
  { id: 4, matn: "Bozorga borish" },
];
const indeks = new Map();
for (const h of hujjatlar) {
  for (const t of new Set(termlar(h.matn))) {
    if (!indeks.has(t)) indeks.set(t, []);
    indeks.get(t).push(h.id);
  }
}

function qidir(sorov) {
  const royxatlar = termlar(sorov).map((t) => indeks.get(t) ?? []);
  if (royxatlar.length === 0) return [];
  return royxatlar.reduce((a, b) => a.filter((id) => b.includes(id)));
}

const sorovlar = [
  "kitob", "kitoblar bozordan", "bozor", "o'qish kitoblarni",
];
for (const s of sorovlar) {
  console.log(s, "→", qidir(s));
}

kitob → [ 1, 2, 3 ]
kitoblar bozordan → [ 3 ]
bozor → [ 3, 4 ]
o'qish kitoblarni → [ 2 ]

11. Loyiha qadami: kanon tajribasi, loyihaga kirmaydi

Bu darsda vazifalar-api ga kod qo'shilmaydi. Kanon o'z inverted index va BM25'ni, MiniSearch'ni va Postgres FTS'ni bir xil 50 000 hujjatda solishtirdi. Xulosa — vazifalar-api qidiruvi 27-qismdagi tsvector + uz_normal + pg_trgm bilan qoladi. Sabab: shaxsiy vazifalar ro'yxatida facet va millionlab hujjat yo'q, alohida xizmat esa qo'shimcha server va sinxronlash degani.

O'zingiz sinab ko'ring: 3-mashq indeksiga BM25'ni ulang (posting list'da so'z sonini ham saqlang) va natijani balli tartibda qaytaring. Keyin ildiz ni o'chirib, natija qanday o'zgarishini solishtiring.

12. Real ishda

• Internet-do'kon katalogi — typo tolerance, facet (kategoriya, narx oralig'i, brend), sinonimlar ("telefon" = "smartfon"). Odatda Meilisearch, Typesense yoki Elasticsearch.
• Ichki qidiruv (CRM, vazifalar, hujjatlar) — ko'pincha Postgres FTS + pg_trgm yetadi.
• Hujjatlar sayti — MiniSearch yoki shunga o'xshash kutubxona bilan brauzerda, serversiz.
• Semantik qidiruv — so'z emas, ma'no bo'yicha (embedding va vektor). U 31-qismda AI bilan birga keladi; ko'p tizimlar BM25 va vektor natijasini birlashtiradi (hybrid search).
• Intervyuda: "Inverted index nima?", "Nega LIKE '%x%' sekin?", "BM25 qaysi omillarni hisobga oladi?", "Qachon Elasticsearch, qachon Postgres FTS?"

Xulosa

• Inverted index — "so'z → hujjatlar" ro'yxati; so'rov faqat kerakli ro'yxatlarni o'qiydi.
• Tokenizatsiya, normallash va stemming indeksda ham, so'rovda ham bir xil bo'lishi shart.
• O'zbek tili uchun tayyor stemmer yo'q; oddiy qo'shimcha kesish understemming va overstemming beradi.
• BM25 = so'z chastotasi (to'yinadi) × so'z kamyobligi × hujjat uzunligiga tuzatish.
• Typo tolerance — Levenshtein masofasi; qisqa so'zlarga xato ruxsat etilmaydi. Facet — natijani maydon bo'yicha sanash.
• Kanon: vazifalar-api uchun Postgres FTS yetarli; alohida dvigatel — katta katalog uchun.

Keyingi dars: Meilisearch va Typesense — tayyor dvigatelga 50 000 vazifani yuklab, typo tolerance, facet, filtr va har foydalanuvchiga faqat o'z hujjatlarini ko'rsatadigan tenant token bilan ishlaymiz.

Manbalar

• Robertson, Zaragoza — "The Probabilistic Relevance Framework: BM25 and Beyond" (2009): https://www.staff.city.ac.uk/~sbrp622/papers/foundations_bm25_review.pdf
• Elasticsearch — similarity (sukut BM25, k1, b): https://www.elastic.co/docs/reference/elasticsearch/index-settings/similarity
• Meilisearch — typo tolerance sozlamalari: https://www.meilisearch.com/docs/learn/relevancy/typo_tolerance_settings
• Snowball stemmerlari ro'yxati: https://snowballstem.org/algorithms/ — 2026-10-28 da tekshirildi, o'zbek tili yo'q
• MiniSearch: https://github.com/lucaong/minisearch
• Kanon tajribasi (IlmHamroh, 2026-10-27): o'z inverted index + BM25, MiniSearch 7.2.0, PostgreSQL 18.6, Node 24.21.0, Windows 11. Darsdagi kichik misollar va mashq yechimlari — biz ishga tushirdik (2026-10-28, Node 24.21.0).