Kalit so’z qidiruvi

Kalit so’z yordamida qidiruv birmuncha sekin, aldamay, anchagina sekin. Eng muhimi so’zlar hajmi ortgani sayin qidiruv sekinlashadi. Qo’lingizda kitob bor, aytaylik Monteskye “Qonunlar ruhi” kitobi. Siz kitob ichidan “istibdod” so’zini topib berishingiz kerak. Nima qilasiz? Har bir varoqni, har bir so’zni o’qib chiqasiz. Agar so’z birinchi betda uchrab qolsa, sizni omadingiz, yo’qsa kitob tahminan 500 varoq. Demak eng yomon holatda 500 varoqlashingiz kerak…

LIKE %so'z% - bu sql qidiruv, o’xshashlarini topadigan. WHERE ProductName LIKE 'App%' agar shu holatda yozsak, “APP” bilan boshlanuvchi barcha bo’laklarni izlaydi, bunga qancha vaqt ketadi? Aytaylik 100 ta so’zga ega matndan bu so’zni izlashga qancha vaqt ketadi?

LIKE 'App%' yordamida biroz tezroq. Bu turdagi qidiruv B-tree indeks yordamida ishlaydi (Postgresni oldik). U O(log n) shunday tartibda o’sadi

• n = qatorlar soni
• k = qidiruv soni
• Bitta qidiruv vaqti ≈ C·log₂(n)
• k ta qidiruv vaqti ≈ k·C·log₂(n)
• C – serverning ichki ishlash tezligiga bog’liq doimiy

100 ta matn (n = 100), log₂(100) ≈ 7

Agar server 1 ta solishtirishni 1 mikrosekundda bajarsa:

• bitta qidiruv vaqti ≈ 7 µs
• k = 1000 ta qidiruv bo’lsa: 1000 · 7 µs = 7000 µs = 7 ms

n = 1 000 000 bo’lsa, log₂(1000000) ≈ 20

• Bir qidiruv vaqti ≈ 20 µs
• k = 1000 bo’lsa ≈ 20 ms

Demak tushundik, matn ko’paysa qidiruv sekinlashishi oshadi.

LIKE '%App%': Indeks ishlamaydi demak vaqt = k × C × n (O(n)) - barcha varoqlarni o’qib chiqadi.

Inverted Index

Elasticsearch kabi tizimlar inverted index ishlatishdi. Ular har bir so’zni indexlaydi. Tahminan quyidagicha: avval so’zlar tokenizatsiya va normalizatsiya qilinadi va indexlanadi.

tokenizatsiya - matnni bo’lak (token) larga aylantiradi:

"Men chegirmagoni quryapman." -> ["Men", "chegirmagoni", "quryapman"]

normalizatsiya - so’zlarni standart holatga keltiradi (katta kichik harflarni bir xilda qilish, qo’shimchalarni olib tashlash):

["men", "chegirmago", "qurmoq"]

Har bir so’z indexlanadi. Yuqoridagi kitobni izlang. Siz “istibdod” so’zini izlash uchun har bir varoqni o’qib chiqdingiz endi esa tasavvur qiling, kimdir shu so’zni qayerdaligini kitobni orqasidagi mundarijaga yozib qo’ygan. Endi topish osonroqmi? Shu indexlashga misol.

Foydalanuvchi “chegirma” deb qidirganda, tizim millionlab hujjatlarni titkilamaydi. U shunchaki jadvaldan “chegirma” so’zini topadi va darhol [2, 5] natijani qaytaradi. Bu jarayon O(1) hisoblanadi ya’ni ma’lumot hajmi ortgani bilan qidiruv vaqti deyarli o’zgarmaydi. Bu tezmi? Ha bu judayam tez.

Semantik qidiruv

Lekin doim ham nima izlayotganimizni bilmaymiz. Meni qornim och payt youtubedan shunchaki “ovqat” deb izlayman va youtube menga “mastava”, “osh” tavsiya qiladi? Qanday? Qanday qilib tizim ovqat deb izlanganda mastavani tavsiya qilish kerakligini tushundi?

Bu yerdagi kalit so’z - tushundi. Tizim so’zning aynan ma’nosini tushunmadi, shunchaki ovqat so’zining vektor fazodagi o’rni mastavaga yaqin ekanini hisobladi va menga natijani yubordi.

So’zlarni qanday ma’nosini tushunib, ularni joylashtirib chiqish mumkin? Buni neyron tarmoqlar (masalan OpenAI text-embedding-3) eplaydi. Model milliardlab matnlarni o’qib, so’zlarning kontekstini o’rganadi. Qaysi o’rinlarda ko’p uchrashiga qarab ma’nosini ba’misoli “tushunib” oladi. Model “olma” so’zi ko’pincha “yeyish”, “shirin”, “meva” so’zlari bilan, “iPhone” so’zi esa “telefon”, “zaryad”, “ekran” so’zlari bilan kelishini statistik jihatdan o’rganib oladi.

Matn: "Ovqat"

Vektor: [0.12, -0.58, 0.03, 0.91, ...]

Bu raqamlar osmondan olinmagan. Ular har bitta so’zga muvofiq keladi. Har bir raqam ma’noning qandaydir qirrasini (masalan jonsizlik, rang, hissiyot, mavhumlik) ifodalaydi. Buni modelni o’zi aniqlaydi. Men ham uncha tushunmadim bu qismiga.

Vektor fazosi

Vektor fazosi — bu barcha embeddinglar (vektorlarda shu) joylashtirilgan ko’p o’lchovli koordinatalar tizimi.

kordinata — nuqtaning joylashuvini raqamlar orqali ifodalash. Xaritadan davlatlarning, shaharlarning manzillarini aniqlaymiz-ku, o’sha.

“Mushuk”, “It”, “Ot” so’zlarining nuqtalari fazoning bir burchagida to’planadi (Hayvonlar tarafida). “Mashina”, “Avtobus”, “Poyezd” esa butunlay boshqa burchakda to’planadi (Transport tarafida).

Semantik qidiruv ishlashi

Bu qidiruv turi kalit so’zlar mosligiga emas, ma’no yaqinligiga asoslanadi.

Ishlash algoritmi:

1. Vektorlash: barcha matn oldindan vektorga aylantirilib, ma’lumotlar omborida saqlanadi (Postgresqlda pgvector masalan)

2. So’rov: foydalanuvchi qidiruvga yozadi: “mazza qilib yeydigan narsa”

3. Encoder: qidiruv so’rovi ayni o’sha model orqali vektorga aylantiriladi

4. Eng yaqin qo’shnini qidirish: tizim so’rov vektorini olib, fazoda unga eng yaqin turgan matn vektorlarini qidiradi

5. Natija: tizim “Olma” yoki “Osh” haqidagi matnni topadi. Qiziq tarafi, so’rovda “Olma” so’zi yo’q, lekin vektor fazosida “mazza qilib yeydigan narsa” vektori “Olma” vektoriga juda yaqin joylashgan bo’ladi. Shuning uchun olmani qaytarish bu to’g’ri qaror.

Masofani o’lchash

Model “o’xshash”likni qanday hisoblaydi? Vektor fazosida ikki nuqta orasidagi masofani o’lchashning eng yaxshi usuli — Kosinus o’xshashligi (Cosine Similarity).

Xullas:

• Agar burchak 0° bo’lsa (Kosinus = 1): Vektorlar ustma-ust tushadi → Ma’no bir xil
• Agar burchak 90° bo’lsa (Kosinus = 0): Vektorlar perpendikulyar → Aloqasi yo’q
• Agar burchak 180° bo’lsa (Kosinus = -1): Vektorlar qarama-qarshi → Ma’no teskari

Qidiruv tizimi har bir hujjat uchun shu formulani hisoblab chiqadi va natijasi 1 ga eng yaqin bo’lgan hujjatlarni foydalanuvchiga ko’rsatadi.

Endi tasavvur qiling, indexlangan matn va ma’nosiga qarab qidirishlar bittada. Aynan shu narsa hozirgi katta tarmoqlar ishlatadigan uslub. Aynan mavjud youtube kanal izlasangiz o’shani topasiz, ovqat desangiz osh, mastavani ko’rsata oladi.