25.7-dars: Embeddinglar va semantik qidiruv

EMBEDDING:
  f(matn) -> R^d vektor, d = 16 ... 4096
  yaqin ma'noli matnlar -> yaqin vektorlar

QAYERDAN KELADI:
  23.6: so'z embeddinglari (word2vec g'oyasi) - so'z darajasi
  LSA: TF-IDF matritsasi -> SVD -> k o'lchamli zich vektorlar
       (bu dars; sinonimlar o'xshash kontekstda uchraydi - taqsimot gipotezasi)
  neyron modellar: Transformer encoder (24.8 BERT kabi) + pooling,
       juft matnlarda kontrastiv o'rgatilgan (savol <-> javob yaqin)
  API: embedding endpointi (provayderlar alohida model sifatida taklif qiladi)

TAQSIMOT GIPOTEZASI (1-misol, 3-bo'lim):
  'karta' va 'plastik' bir matnda birga 0 marta uchragan,
  lekin bir xil kontekst so'zlari bilan (bankomat, chip) -> cos = 0.983
  bog'liq bo'lmagan juftlar: cos(karta, chegirma) = 0.054

SIYRAK va ZICH:
  TF-IDF: o'lcham = lug'at hajmi (minglab), ko'p nol, so'z mosligi
  embedding: o'lcham kichik (d), hamma koordinata ma'noli, ma'no yaqinligi

SKALYAR KO'PAYTMA:  a . b = sum a_i b_i          - uzunlikka bog'liq
KOSINUS:            cos(a, b) = a . b / (|a| |b|) - faqat yo'nalish
MASOFA:             |a - b|                       - uzunlikka bog'liq

UZUNLIK TUZOG'I (1-misol, so'z sanoqlari bilan):
  "karta haqida umumiy ma'lumot" x 6 - dot 6.0 (1-o'rin!), kosinus 0.354
  "karta bloklash bo'limi: ..."       - dot 4.0,             kosinus 0.816
  uzun va takroriy hujjat skalyar ko'paytmada "yutadi"

L2 NORMALLASH: a <- a / |a|
  keyin: a . b = cos(a, b)
         |a - b|^2 = 2 - 2 cos(a, b)
  -> dot, kosinus va masofa AYNAN bir xil tartib beradi (1-misol: [3, 0, 2, 1])

AMALDA:
  vektorlarni bir marta normallab saqlang -> qidiruv = E @ q (matritsa ko'paytmasi)
  ba'zi modellar allaqachon normallangan vektor qaytaradi - hujjatini tekshiring
  hujjat va so'rov BIR XIL model va bir xil normallash bilan kodlanadi

KALIT SO'Z (siyrak):
  TF-IDF, BM25 (23.4 + so'z chastotasining to'yinishi va uzunlik normallashi)
  + aniq terminlar, ismlar, kodlar, raqamlar ("xato 0x80070005", "INN")
  + tushunarli, tez, o'rgatish kerak emas
  - sinonim va parafrazni ko'rmaydi

BELGI N-GRAMLARI (char 3-5):
  + qo'shimchalar: 'kartamni' va 'karta' umumiy n-gramlarga ega
  - sinonim baribir yo'q

SEMANTIK (zich):
  + sinonim, parafraz ("plastik" ~ "karta")
  - aniq terminlarni "xiralashtiradi"; lug'atdan tashqari so'zlar (OOV)
  - model domenidan tashqarida zaif

2-MISOL (60 FAQ, test: 120 kalit so'z + 120 parafraz so'rov, MRR):
  usul              kalit   parafraz
  BM25              0.63    0.29
  TF-IDF so'z       0.62    0.29
  TF-IDF belgi      0.99    0.28
  LSA so'z k=16     0.48    0.93
  LSA belgi k=64    0.99    0.21
  gibrid            0.96    0.94

BALLARNI BIRLASHTIRISH:
  ball = w * ball_kalit + (1 - w) * ball_semantik    (ikkalasi ham [0, 1] da)
  2-misol: w = 0.5 -> kalit 0.96, parafraz 0.94 (o'rtacha 0.954 - eng yaxshi)

RRF (Reciprocal Rank Fusion) - ballar shkalasi mos kelmasa:
  ball(d) = sum_usul 1 / (60 + o'rin_usul(d))
  faqat o'rinlarga tayanadi; normallash shart emas

HALOL SOLISHTIRISH (2-misol):
  gibrid - TF-IDF belgi (kalit):   -0.028, SE 0.015 - sezilarli emas
  gibrid - LSA (parafraz):         +0.016, SE 0.012 - sezilarli emas
  ya'ni gibrid har biri o'z sohasida eng yaxshisidan sezilarli yomon emas
  va ikkala sohada ham yaxshi -> qaror qoidasi bo'yicha tanlanadi

O'LCHAM d:
  xotira = N_hujjat * d * bayt       (float32: 4 bayt)
  qidiruv ishi ~ N_hujjat * d
  3-misol, 1 mln hujjat: d=16 -> 64 MB, d=64 -> 256 MB

KATTA d HAR DOIM YAXSHI EMAS (3-misol, val MRR):
  k=4 0.256, k=8 0.457, k=16 0.694, k=32 0.677, k=64 0.449
  LSA da kichik k - umumlashtirish (sinonimlar birlashadi),
  katta k - TF-IDF ga qaytish (sinonimlar yana ajraladi)
  neyron modellarda boshqacha egri chiziq - lekin o'lchash usuli bir xil

QAROR QOIDASI:
  eng yaxshisidan sezilarli yomon bo'lmagan eng kichik o'lcham
  3-misol: k=16 va k=32 farqi +0.017, SE 0.026 -> k=16

MODEL TANLASHDA SAVOLLAR:
  til: o'zbek tilini qanchalik yaxshi biladi? (o'z so'rovlaringizda o'lchang)
  domen: bank / tibbiyot / huquq terminlari
  narx: API - token boshiga; lokal model - GPU/CPU vaqti
  maksimal kirish uzunligi (uzun hujjat -> chunking, keyingi dars)
  model ALMASHSA - butun indeks qayta hisoblanadi (vektorlar mos emas)

OOV (so'z darajasidagi model):
  3-misol: kalit so'z so'rovlarining 85% ida lug'atda yo'q so'z bor ('kartamni')
  'kriptovalyuta hamyonini ochish' - hamma so'z notanish -> vektor normasi 0
  subword tokenizatsiyali 23.3-bob neyron modellarda bu muammo ancha kichik

float32 -> float16:  2 barobar kam xotira, aniqlik deyarli o'zgarmaydi
float32 -> int8:     4 barobar kam; har vektor o'z shkalasi bilan: x ~ s * q
binar (1 bit):       32 barobar kam; odatda qayta saralash bilan birga

3-MISOL (k = 16, test MRR):
  float32  0.706
  float16  0.706    top-1 100.0% bir xil
  int8     0.706    top-1  98.8% bir xil, 16 bayt/vektor

VEKTOR BAZA VAZIFASI:
  vektorlarni saqlash + tez yaqin qo'shni qidiruvi + metadata filtrlash
  + qo'shish/o'chirish/yangilash

FAISS (kutubxona, Meta):
  IndexFlatIP        - aniq qidiruv (normallangan vektorlarda kosinus)
  IndexIVFFlat       - IVF (4-misoldagi g'oya), nlist va nprobe
  IndexHNSWFlat      - graf asosidagi ANN
  IndexIVFPQ         - IVF + mahsulot kvantlash (xotira juda kam)

pgvector (PostgreSQL kengaytmasi):
  vector(d) ustun turi; <=> kosinus masofasi operatori
  ivfflat va hnsw indekslari
  afzallik: vektor va oddiy ma'lumot bir bazada, SQL filtrlar, tranzaksiyalar

BOSHQALAR: Chroma, Qdrant, Weaviate, Milvus, Elasticsearch/OpenSearch (gibrid)

QACHON ALOHIDA BAZA SHART EMAS:
  ~100 000 gacha vektor - numpy matritsa va E @ q yetarli (4-misol: 20 000 ta)

ANIQ QIDIRUV: har so'rovga N ta skalyar ko'paytma -> N katta bo'lsa sekin

IVF (inverted file):
  QURISH: k-means bilan nlist ta markaz; har hujjat eng yaqin markaz ro'yxatiga
  QIDIRUV: so'rovga eng yaqin nprobe ta markaz -> faqat shu ro'yxatlar ichida aniq qidiruv
  ish = nlist (markazlar) + ko'rilgan ro'yxatlardagi hujjatlar

NIMA YO'QOTILADI:
  haqiqiy qo'shni boshqa klaster chegarasida bo'lsa - topilmaydi
  recall@k = ANN top-k dagi haqiqiy top-k ulushi (aniq qidiruvga nisbatan)

4-MISOL (20 000 hujjat, d = 32, 300 so'rov):
  nlist  nprobe  recall@10  masofalar   tejash
  64       1      0.795        460       43.4x
  64       4      0.987       1334       15.0x
  256      4      0.964        620       32.3x
  256     16      1.000       1531       13.1x

TUGMALAR:
  nprobe oshsa - recall oshadi, tezlik tushadi
  nlist oshsa - ro'yxatlar kichik, lekin to'g'ri klasterni "o'tkazib yuborish" osonroq
  maqsad recall (masalan 0.95) -> eng arzon sozlama

BOSHQA ANN: HNSW (graf), LSH (xeshlash), PQ (kvantlash) - g'oya bir xil:
  hammasini emas, ehtimoliy nomzodlarni tekshirish

import numpy as np
from sklearn.decomposition import TruncatedSVD
from sklearn.feature_extraction.text import TfidfVectorizer

# ---- LSA embedding ----
tf = TfidfVectorizer(sublinear_tf=True).fit(korpus)
svd = TruncatedSVD(16, random_state=0).fit(tf.transform(korpus))


def emb(matnlar):
    z = svd.transform(tf.transform(matnlar))
    return z / np.maximum(np.linalg.norm(z, axis=1, keepdims=True), 1e-12)   # L2


E = emb(hujjatlar)                       # (N, d), bir marta hisoblanadi
ball = emb([sorov])[0] @ E.T             # kosinus
top = np.argsort(-ball)[:5]

# ---- gibrid ----
ball = 0.5 * ball_belgi_tfidf + 0.5 * ball_lsa

# ---- int8 kvantlash ----
shkala = np.abs(E).max(1, keepdims=True) / 127
E8 = np.round(E / shkala).astype(np.int8)          # tiklash: E8 * shkala

# ---- FAISS (o'rnatilgan bo'lsa) ----
import faiss

indeks = faiss.IndexFlatIP(E.shape[1])             # aniq, kosinus (normallangan)
indeks.add(E.astype(np.float32))
D, I = indeks.search(Q.astype(np.float32), 10)
kvant = faiss.IndexFlatIP(E.shape[1])
ivf = faiss.IndexIVFFlat(kvant, E.shape[1], 256, faiss.METRIC_INNER_PRODUCT)
ivf.train(E.astype(np.float32))
ivf.add(E.astype(np.float32))
ivf.nprobe = 4

# ---- pgvector (SQL) ----
# CREATE EXTENSION vector;
# CREATE TABLE hujjat (id bigserial PRIMARY KEY, matn text, emb vector(16));
# CREATE INDEX ON hujjat USING hnsw (emb vector_cosine_ops);
# SELECT id, matn FROM hujjat ORDER BY emb <=> '[...]' LIMIT 5;

embedding = ma'no -> vektor; faqat o'rgatilgan qonuniyatlarni biladi
L2 normallash: dot = kosinus, masofa bilan bir xil tartib
kalit so'z - aniq terminlar; belgi n-gram - qo'shimchalar; semantik - sinonimlar
gibrid - aralash so'rovlarga xavfsiz
o'lcham va vaznlarni VAL da tanlang; testda bir marta baholang
kvantlash: float16 / int8 - xotira 2-4x kam, ta'sirini o'lchang
ANN (IVF): nlist, nprobe; recall ni aniq qidiruvga nisbatan o'lchang
kichik korpus - numpy yetarli

"""Embedding va o'xshashlik: skalyar ko'paytma, kosinus, masofa va L2 normallashtirish."""

import random
import warnings

import numpy as np
from sklearn.decomposition import TruncatedSVD
from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer

TUSHUNCHALAR = {
    "karta": (["karta", "plastik", "bank kartasi"], ["bankomat", "chip", "amal qilish"]),
    "parol": (["parol", "maxfiy kod", "pin kod"], ["kirish", "xavfsizlik", "unutdim"]),
    "bloklash": (["bloklash", "muzlatish", "to'xtatib qo'yish"], ["o'g'irlandi", "yo'qoldi", "vaqtincha"]),
    "otkazma": (["o'tkazma", "pul jo'natish", "transfer"], ["qabul qiluvchi", "rekvizit", "yubordim"]),
    "kredit": (["kredit", "qarz", "nasiya"], ["grafik", "oylik to'lov", "kafil"]),
    "foiz": (["foiz", "ustama", "stavka"], ["yillik", "hisoblanadi", "miqdori"]),
    "ilova": (["ilova", "mobil dastur", "app"], ["yangilash", "smartfon", "yuklab olish"]),
    "hisob": (["hisob raqam", "schyot", "balans"], ["qoldiq", "ko'chirma", "mablag'"]),
    "komissiya": (["komissiya", "xizmat haqi", "ushlanma"], ["tarif", "ushlab qolindi", "summa"]),
    "yetkazish": (["yetkazish", "kuryer", "dostavka"], ["olib keladi", "eshikkacha", "manzilga"]),
    "qaytarish": (["qaytarish", "almashtirish", "vozvrat"], ["nuqson", "chek", "sifatsiz"]),
    "buyurtma": (["buyurtma", "zakaz", "xarid"], ["savat", "rasmiylashtirish", "mahsulot"]),
    "chegirma": (["chegirma", "aksiya", "skidka"], ["promokod", "arzonlashtirish", "bayram"]),
    "valyuta": (["valyuta", "dollar", "xorijiy pul"], ["kurs", "ayirboshlash", "konvertatsiya"]),
    "bonus": (["keshbek", "bonus", "qaytim ball"], ["to'plash", "sarflash", "hamyon"]),
    "muddat": (["muddat", "necha kun", "qancha vaqt"], ["kutish", "ish kuni", "tez"]),
}
AMALLAR = ["qanday o'zgartiraman", "qayerdan bilaman", "qanday rasmiylashtiraman",
           "bekor qilsa bo'ladimi", "qanday tekshiraman", "nima uchun ishlamayapti"]
QOSHIMCHALAR = ["", "", "", "ni", "im", "imni", "ga", "da", "lar"]


def niyatlar(rng, n=60):
    nomlar = sorted(TUSHUNCHALAR)
    juftlar = set()
    while len(juftlar) < n:
        a, b = rng.sample(nomlar, 2)
        juftlar.add((a, b, rng.choice(AMALLAR)))
    return sorted(juftlar)


def shakl(tushuncha, i):
    return TUSHUNCHALAR[tushuncha][0][i]


def faq_hujjat(niyat, rng):
    a, b, amal = niyat
    ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
    return (f"{shakl(a, 0)} {shakl(b, 0)} {amal}? Javob: {shakl(a, 0)} bo'yicha {rng.choice(ka)} "
            f"va {shakl(b, 0)} uchun {rng.choice(kb)} bo'limiga qarang.")


def qoshimcha(ibora, rng):
    return ibora + rng.choice(QOSHIMCHALAR)


def sorov_kalit(niyat, rng):
    a, b, amal = niyat
    return f"{qoshimcha(shakl(a, 0), rng)} {qoshimcha(shakl(b, 0), rng)} {amal}"


def sorov_parafraz(niyat, rng):
    a, b, amal = niyat
    return f"{shakl(a, rng.choice([1, 2]))} {shakl(b, rng.choice([1, 2]))} {amal}"


def fon_korpus(rng, n=4000):
    """Suhbat loglari: sinonimlar bir xil kontekst so'zlari bilan uchraydi (taqsimot gipotezasi)."""
    nomlar = sorted(TUSHUNCHALAR)
    matnlar = []
    for _ in range(n):
        a, b = rng.sample(nomlar, 2)
        ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
        matnlar.append(f"{shakl(a, rng.randrange(3))} {rng.choice(ka)} {rng.choice(ka)} "
                       f"{shakl(b, rng.randrange(3))} {rng.choice(kb)} {rng.choice(AMALLAR)}")
    return matnlar


def kosinus(a, b):
    return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b)))


def main() -> None:
    print("=== 1. Uzunlik tuzog'i: skalyar ko'paytma va kosinus ===")
    hujjatlar = ["karta bloklash uchun ilovaga kiring",
                 "kredit foizi yillik hisoblanadi",
                 "karta haqida umumiy ma'lumot " * 6,            # uzun, takroriy hujjat
                 "karta bloklash bo'limi: karta yo'qolsa bloklash tugmasini bosing"]
    sorov = "karta bloklash"
    cv = CountVectorizer(token_pattern=r"[a-z']+").fit(hujjatlar + [sorov])
    X = cv.transform(hujjatlar).toarray().astype(float)
    q = cv.transform([sorov]).toarray()[0].astype(float)
    print("  hujjat                                   dot    kosinus  masofa")
    for h, x in zip(hujjatlar, X):
        print(f"  {h[:38]:<38} {x @ q:>6.1f} {kosinus(x, q):>9.3f} {np.linalg.norm(x - q):>7.2f}")
    print(f"  dot bo'yicha 1-o'rin: {int(np.argmax(X @ q))}, kosinus bo'yicha: "
          f"{int(np.argmax([kosinus(x, q) for x in X]))}")

    print("\n=== 2. L2 normallashdan keyin uchala o'lchov bir xil tartib beradi ===")
    Xn = X / np.linalg.norm(X, axis=1, keepdims=True)
    qn = q / np.linalg.norm(q)
    dot_t = np.argsort(-(Xn @ qn), kind="stable")
    kos_t = np.argsort(-np.array([kosinus(x, qn) for x in Xn]), kind="stable")
    mas_t = np.argsort(np.linalg.norm(Xn - qn, axis=1), kind="stable")
    print(f"  dot {dot_t.tolist()}, kosinus {kos_t.tolist()}, masofa {mas_t.tolist()}")
    c = Xn @ qn
    print(f"  ||a - b||^2 = 2 - 2 cos: {np.allclose(np.linalg.norm(Xn - qn, axis=1) ** 2, 2 - 2 * c)}")

    print("\n=== 3. LSA so'z vektorlari: sinonimlar yaqinmi? (fon korpusda o'rgatilgan) ===")
    rng = random.Random(0)
    fon = fon_korpus(rng)
    tf = TfidfVectorizer(token_pattern=r"[a-z']+", sublinear_tf=True).fit(fon)
    svd = TruncatedSVD(16, random_state=0).fit(tf.transform(fon))
    W = (svd.components_ * svd.singular_values_[:, None]).T       # har so'zga 16 o'lchamli vektor
    s2i = tf.vocabulary_
    juftlar = [("karta", "plastik"), ("keshbek", "bonus"), ("transfer", "o'tkazma"),
               ("skidka", "chegirma"), ("karta", "chegirma"), ("kredit", "dostavka")]
    for a, b in juftlar:
        print(f"  cos({a}, {b}) = {kosinus(W[s2i[a]], W[s2i[b]]):+.3f}")
    birga = sum(("karta" in m.split()) and ("plastik" in m.split()) for m in fon)
    print(f"  'karta' va 'plastik' bir matnda birga uchragan: {birga} marta")

    print("\n=== 4. Embedding matritsasi va qidiruv = matritsa ko'paytmasi ===")
    E = np.random.default_rng(0).normal(size=(10000, 64)).astype(np.float32)
    E /= np.linalg.norm(E, axis=1, keepdims=True)
    savol = E[123] + 0.3 * np.random.default_rng(1).normal(size=64).astype(np.float32)
    savol /= np.linalg.norm(savol)
    ball = E @ savol                                                # 10 000 ta kosinus bir amalda
    top = np.argsort(-ball)[:3]
    print(f"  E: {E.shape}, {E.nbytes / 1e6:.2f} MB (float32); top-3: {top.tolist()}, "
          f"ballar {', '.join(f'{x:.3f}' for x in ball[top])}")
    print("  \u2b50 Normallangan vektorlarda kosinus = skalyar ko'paytma; qidiruv = E @ q")


if __name__ == "__main__":
    with warnings.catch_warnings():
        warnings.simplefilter("ignore")
        main()

=== 1. Uzunlik tuzog'i: skalyar ko'paytma va kosinus ===
  hujjat                                   dot    kosinus  masofa
  karta bloklash uchun ilovaga kiring       2.0     0.632    1.73
  kredit foizi yillik hisoblanadi           0.0     0.000    2.45
  karta haqida umumiy ma'lumot karta haq    6.0     0.354   11.58
  karta bloklash bo'limi: karta yo'qolsa    4.0     0.816    2.45
  dot bo'yicha 1-o'rin: 2, kosinus bo'yicha: 3

=== 2. L2 normallashdan keyin uchala o'lchov bir xil tartib beradi ===
  dot [3, 0, 2, 1], kosinus [3, 0, 2, 1], masofa [3, 0, 2, 1]
  ||a - b||^2 = 2 - 2 cos: True

=== 3. LSA so'z vektorlari: sinonimlar yaqinmi? (fon korpusda o'rgatilgan) ===
  cos(karta, plastik) = +0.983
  cos(keshbek, bonus) = +0.969
  cos(transfer, o'tkazma) = +0.981
  cos(skidka, chegirma) = +0.976
  cos(karta, chegirma) = +0.054
  cos(kredit, dostavka) = +0.075
  'karta' va 'plastik' bir matnda birga uchragan: 0 marta

=== 4. Embedding matritsasi va qidiruv = matritsa ko'paytmasi ===
  E: (10000, 64), 2.56 MB (float32); top-3: [123, 7329, 3371], ballar 0.572, 0.468, 0.433
  ⭐ Normallangan vektorlarda kosinus = skalyar ko'paytma; qidiruv = E @ q

"""Semantik va kalit so'z qidiruvi: BM25, TF-IDF (so'z, belgi), LSA va gibridni FAQ korpusida taqqoslash."""

import math
import random
import re
import warnings

import numpy as np
from sklearn.decomposition import TruncatedSVD
from sklearn.feature_extraction.text import TfidfVectorizer

TUSHUNCHALAR = {
    "karta": (["karta", "plastik", "bank kartasi"], ["bankomat", "chip", "amal qilish"]),
    "parol": (["parol", "maxfiy kod", "pin kod"], ["kirish", "xavfsizlik", "unutdim"]),
    "bloklash": (["bloklash", "muzlatish", "to'xtatib qo'yish"], ["o'g'irlandi", "yo'qoldi", "vaqtincha"]),
    "otkazma": (["o'tkazma", "pul jo'natish", "transfer"], ["qabul qiluvchi", "rekvizit", "yubordim"]),
    "kredit": (["kredit", "qarz", "nasiya"], ["grafik", "oylik to'lov", "kafil"]),
    "foiz": (["foiz", "ustama", "stavka"], ["yillik", "hisoblanadi", "miqdori"]),
    "ilova": (["ilova", "mobil dastur", "app"], ["yangilash", "smartfon", "yuklab olish"]),
    "hisob": (["hisob raqam", "schyot", "balans"], ["qoldiq", "ko'chirma", "mablag'"]),
    "komissiya": (["komissiya", "xizmat haqi", "ushlanma"], ["tarif", "ushlab qolindi", "summa"]),
    "yetkazish": (["yetkazish", "kuryer", "dostavka"], ["olib keladi", "eshikkacha", "manzilga"]),
    "qaytarish": (["qaytarish", "almashtirish", "vozvrat"], ["nuqson", "chek", "sifatsiz"]),
    "buyurtma": (["buyurtma", "zakaz", "xarid"], ["savat", "rasmiylashtirish", "mahsulot"]),
    "chegirma": (["chegirma", "aksiya", "skidka"], ["promokod", "arzonlashtirish", "bayram"]),
    "valyuta": (["valyuta", "dollar", "xorijiy pul"], ["kurs", "ayirboshlash", "konvertatsiya"]),
    "bonus": (["keshbek", "bonus", "qaytim ball"], ["to'plash", "sarflash", "hamyon"]),
    "muddat": (["muddat", "necha kun", "qancha vaqt"], ["kutish", "ish kuni", "tez"]),
}
AMALLAR = ["qanday o'zgartiraman", "qayerdan bilaman", "qanday rasmiylashtiraman",
           "bekor qilsa bo'ladimi", "qanday tekshiraman", "nima uchun ishlamayapti"]
QOSHIMCHALAR = ["", "", "", "ni", "im", "imni", "ga", "da", "lar"]


def niyatlar(rng, n=60):
    nomlar = sorted(TUSHUNCHALAR)
    juftlar = set()
    while len(juftlar) < n:
        a, b = rng.sample(nomlar, 2)
        juftlar.add((a, b, rng.choice(AMALLAR)))
    return sorted(juftlar)


def shakl(tushuncha, i):
    return TUSHUNCHALAR[tushuncha][0][i]


def faq_hujjat(niyat, rng):
    a, b, amal = niyat
    ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
    return (f"{shakl(a, 0)} {shakl(b, 0)} {amal}? Javob: {shakl(a, 0)} bo'yicha {rng.choice(ka)} "
            f"va {shakl(b, 0)} uchun {rng.choice(kb)} bo'limiga qarang.")


def qoshimcha(ibora, rng):
    return ibora + rng.choice(QOSHIMCHALAR)


def sorov_kalit(niyat, rng):
    a, b, amal = niyat
    return f"{qoshimcha(shakl(a, 0), rng)} {qoshimcha(shakl(b, 0), rng)} {amal}"


def sorov_parafraz(niyat, rng):
    a, b, amal = niyat
    return f"{shakl(a, rng.choice([1, 2]))} {shakl(b, rng.choice([1, 2]))} {amal}"


def fon_korpus(rng, n=4000):
    """Suhbat loglari: sinonimlar bir xil kontekst so'zlari bilan uchraydi (taqsimot gipotezasi)."""
    nomlar = sorted(TUSHUNCHALAR)
    matnlar = []
    for _ in range(n):
        a, b = rng.sample(nomlar, 2)
        ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
        matnlar.append(f"{shakl(a, rng.randrange(3))} {rng.choice(ka)} {rng.choice(ka)} "
                       f"{shakl(b, rng.randrange(3))} {rng.choice(kb)} {rng.choice(AMALLAR)}")
    return matnlar


def tokenlar(matn):
    return re.findall(r"[a-z']+", matn.lower())


class BM25:
    """Okapi BM25 noldan: k1 - so'z chastotasining to'yinishi, b - hujjat uzunligi normallashi."""

    def __init__(self, hujjatlar, k1=1.5, b=0.75):
        self.docs = [tokenlar(h) for h in hujjatlar]
        self.k1, self.b = k1, b
        self.ortacha = np.mean([len(d) for d in self.docs])
        df = {}
        for d in self.docs:
            for w in set(d):
                df[w] = df.get(w, 0) + 1
        n = len(self.docs)
        self.idf = {w: math.log(1 + (n - c + 0.5) / (c + 0.5)) for w, c in df.items()}

    def ball(self, sorov):
        q = tokenlar(sorov)
        natija = np.zeros(len(self.docs))
        for i, d in enumerate(self.docs):
            for w in q:
                f = d.count(w)
                if f:
                    natija[i] += self.idf[w] * f * (self.k1 + 1) / (
                        f + self.k1 * (1 - self.b + self.b * len(d) / self.ortacha))
        return natija


def olchovlar(ballar, togri):
    """ballar: (sorovlar, hujjatlar); togri: har so'rovning to'g'ri hujjat indeksi."""
    tartib = np.argsort(-ballar, axis=1, kind="stable")
    orin = np.array([int(np.where(t == g)[0][0]) for t, g in zip(tartib, togri)])
    return {"R@1": (orin == 0).astype(float), "R@5": (orin < 5).astype(float),
            "MRR": 1.0 / (orin + 1)}


def lsa(v, matnlar, k):
    """LSA embedding: TF-IDF -> TruncatedSVD(k) -> L2 normallash."""
    svd = TruncatedSVD(k, random_state=0).fit(v.transform(matnlar))

    def emb(qs):
        z = svd.transform(v.transform(qs))
        return z / np.maximum(np.linalg.norm(z, axis=1, keepdims=True), 1e-12)
    return emb


def main() -> None:
    rng = random.Random(0)
    niyat = niyatlar(rng)
    faq = [faq_hujjat(n, rng) for n in niyat]
    fon = fon_korpus(rng)
    togri = [i for i in range(len(niyat)) for _ in range(2)]
    sorovlar = {}
    for qism, urug in [("val", 1), ("test", 2)]:          # k ni val da tanlaymiz, testda baholaymiz
        r = random.Random(urug)
        sorovlar[qism] = ([sorov_kalit(niyat[i], r) for i in togri],
                          [sorov_parafraz(niyat[i], r) for i in togri])

    print("=== 1. Korpus va so'rovlar ===")
    print(f"  FAQ hujjatlar {len(faq)}, fon matnlar (suhbat loglari) {len(fon)}")
    print(f"  hujjat:   {faq[0][:78]}")
    print(f"  kalit:    {sorovlar['test'][0][1]}")
    print(f"  parafraz: {sorovlar['test'][1][1]}")

    tf = TfidfVectorizer(token_pattern=r"[a-z']+", sublinear_tf=True).fit(faq + fon)
    tfc = TfidfVectorizer(analyzer="char_wb", ngram_range=(3, 5), sublinear_tf=True).fit(faq + fon)
    F, Fc = tf.transform(faq), tfc.transform(faq)

    print("\n=== 2. LSA o'lchami k ni VALIDATSIYA so'rovlarida tanlash (MRR) ===")
    eng_k, eng = None, -1.0
    for k in (8, 16, 32, 64):
        emb = lsa(tf, faq + fon, k)
        E = emb(faq)
        m = [olchovlar(emb(q) @ E.T, togri)["MRR"].mean() for q in sorovlar["val"]]
        print(f"  k={k:<3} kalit {m[0]:.3f}, parafraz {m[1]:.3f}, o'rtacha {np.mean(m):.3f}")
        if np.mean(m) > eng:
            eng_k, eng = k, np.mean(m)
    print(f"  tanlandi: k = {eng_k}")

    bm = BM25(faq)
    emb = lsa(tf, faq + fon, eng_k)
    E = emb(faq)
    embc = lsa(tfc, faq + fon, 64)
    Ec = embc(faq)
    L = f"LSA so'z k={eng_k}"
    usullar = {
        "BM25": lambda qs: np.array([bm.ball(q) for q in qs]),
        "TF-IDF so'z": lambda qs: (tf.transform(qs) @ F.T).toarray(),
        "TF-IDF belgi": lambda qs: (tfc.transform(qs) @ Fc.T).toarray(),
        L: lambda qs: emb(qs) @ E.T,
        "LSA belgi k=64": lambda qs: embc(qs) @ Ec.T,
    }
    usullar["gibrid"] = lambda qs: 0.5 * usullar["TF-IDF belgi"](qs) + 0.5 * usullar[L](qs)

    print("\n=== 3. TEST: 120 kalit so'z va 120 parafraz so'rov ===")
    print("  usul             kalit R@1  R@5   MRR  | parafraz R@1  R@5   MRR")
    natija = {}
    for nom, fn in usullar.items():
        a, b = (olchovlar(fn(q), togri) for q in sorovlar["test"])
        natija[nom] = (a, b)
        print(f"  {nom:<15} {a['R@1'].mean():>9.2f} {a['R@5'].mean():>5.2f} {a['MRR'].mean():>5.2f}  |"
              f" {b['R@1'].mean():>12.2f} {b['R@5'].mean():>5.2f} {b['MRR'].mean():>5.2f}")

    print("\n=== 4. Juftlashgan farq (MRR, so'rovlar bo'yicha, SE) ===")
    for a, b, j in [(L, "TF-IDF so'z", 1), ("TF-IDF belgi", "TF-IDF so'z", 0),
                    ("BM25", "TF-IDF so'z", 0), ("gibrid", "TF-IDF belgi", 0), ("gibrid", L, 1)]:
        f = natija[a][j]["MRR"] - natija[b][j]["MRR"]
        se = f.std(ddof=1) / math.sqrt(len(f))
        print(f"  {['kalit', 'parafraz'][j]:<8} {a} - {b}: {f.mean():+.3f}, SE {se:.3f} -> "
              f"{'sezilarli' if abs(f.mean()) > 2 * se else 'sezilarli emas'}")

    print("\n=== 5. Xulosa (natijadan) ===")
    ort = {n: (natija[n][0]["MRR"].mean() + natija[n][1]["MRR"].mean()) / 2 for n in natija}
    eng_usul = max(ort, key=ort.get)
    print(f"  ikkala so'rov turida o'rtacha eng yaxshi: {eng_usul} (MRR {ort[eng_usul]:.3f})")
    print("  belgi n-gramlari qo'shimchalarni, LSA sinonimlarni ushlaydi - biri ikkinchisini almashtirmaydi")
    print("  \u2b50 Semantik qidiruv kalit so'z qidiruvini to'ldiradi; o'z so'rovlaringizda o'lchang")


if __name__ == "__main__":
    with warnings.catch_warnings():
        warnings.simplefilter("ignore")
        main()

=== 1. Korpus va so'rovlar ===
  FAQ hujjatlar 60, fon matnlar (suhbat loglari) 4000
  hujjat:   bloklash keshbek nima uchun ishlamayapti? Javob: bloklash bo'yicha o'g'irlandi
  kalit:    bloklash keshbekimni nima uchun ishlamayapti
  parafraz: to'xtatib qo'yish bonus nima uchun ishlamayapti

=== 2. LSA o'lchami k ni VALIDATSIYA so'rovlarida tanlash (MRR) ===
  k=8   kalit 0.294, parafraz 0.621, o'rtacha 0.457
  k=16  kalit 0.439, parafraz 0.949, o'rtacha 0.694
  k=32  kalit 0.579, parafraz 0.774, o'rtacha 0.677
  k=64  kalit 0.578, parafraz 0.320, o'rtacha 0.449
  tanlandi: k = 16

=== 3. TEST: 120 kalit so'z va 120 parafraz so'rov ===
  usul             kalit R@1  R@5   MRR  | parafraz R@1  R@5   MRR
  BM25                 0.47  0.82  0.63  |         0.10  0.50  0.29
  TF-IDF so'z          0.47  0.82  0.62  |         0.10  0.50  0.29
  TF-IDF belgi         0.98  1.00  0.99  |         0.09  0.53  0.28
  LSA so'z k=16        0.33  0.68  0.48  |         0.87  1.00  0.93
  LSA belgi k=64       0.98  1.00  0.99  |         0.07  0.33  0.21
  gibrid               0.94  1.00  0.96  |         0.89  1.00  0.94

=== 4. Juftlashgan farq (MRR, so'rovlar bo'yicha, SE) ===
  parafraz LSA so'z k=16 - TF-IDF so'z: +0.643, SE 0.028 -> sezilarli
  kalit    TF-IDF belgi - TF-IDF so'z: +0.368, SE 0.035 -> sezilarli
  kalit    BM25 - TF-IDF so'z: +0.004, SE 0.023 -> sezilarli emas
  kalit    gibrid - TF-IDF belgi: -0.028, SE 0.015 -> sezilarli emas
  parafraz gibrid - LSA so'z k=16: +0.016, SE 0.012 -> sezilarli emas

=== 5. Xulosa (natijadan) ===
  ikkala so'rov turida o'rtacha eng yaxshi: gibrid (MRR 0.954)
  belgi n-gramlari qo'shimchalarni, LSA sinonimlarni ushlaydi - biri ikkinchisini almashtirmaydi
  ⭐ Semantik qidiruv kalit so'z qidiruvini to'ldiradi; o'z so'rovlaringizda o'lchang

"""Embedding modelini tanlash: o'lcham, sifat, xotira, kvantlash va lug'atdan tashqari so'zlar."""

import math
import random
import warnings

import numpy as np
from sklearn.decomposition import TruncatedSVD
from sklearn.feature_extraction.text import TfidfVectorizer

TUSHUNCHALAR = {
    "karta": (["karta", "plastik", "bank kartasi"], ["bankomat", "chip", "amal qilish"]),
    "parol": (["parol", "maxfiy kod", "pin kod"], ["kirish", "xavfsizlik", "unutdim"]),
    "bloklash": (["bloklash", "muzlatish", "to'xtatib qo'yish"], ["o'g'irlandi", "yo'qoldi", "vaqtincha"]),
    "otkazma": (["o'tkazma", "pul jo'natish", "transfer"], ["qabul qiluvchi", "rekvizit", "yubordim"]),
    "kredit": (["kredit", "qarz", "nasiya"], ["grafik", "oylik to'lov", "kafil"]),
    "foiz": (["foiz", "ustama", "stavka"], ["yillik", "hisoblanadi", "miqdori"]),
    "ilova": (["ilova", "mobil dastur", "app"], ["yangilash", "smartfon", "yuklab olish"]),
    "hisob": (["hisob raqam", "schyot", "balans"], ["qoldiq", "ko'chirma", "mablag'"]),
    "komissiya": (["komissiya", "xizmat haqi", "ushlanma"], ["tarif", "ushlab qolindi", "summa"]),
    "yetkazish": (["yetkazish", "kuryer", "dostavka"], ["olib keladi", "eshikkacha", "manzilga"]),
    "qaytarish": (["qaytarish", "almashtirish", "vozvrat"], ["nuqson", "chek", "sifatsiz"]),
    "buyurtma": (["buyurtma", "zakaz", "xarid"], ["savat", "rasmiylashtirish", "mahsulot"]),
    "chegirma": (["chegirma", "aksiya", "skidka"], ["promokod", "arzonlashtirish", "bayram"]),
    "valyuta": (["valyuta", "dollar", "xorijiy pul"], ["kurs", "ayirboshlash", "konvertatsiya"]),
    "bonus": (["keshbek", "bonus", "qaytim ball"], ["to'plash", "sarflash", "hamyon"]),
    "muddat": (["muddat", "necha kun", "qancha vaqt"], ["kutish", "ish kuni", "tez"]),
}
AMALLAR = ["qanday o'zgartiraman", "qayerdan bilaman", "qanday rasmiylashtiraman",
           "bekor qilsa bo'ladimi", "qanday tekshiraman", "nima uchun ishlamayapti"]
QOSHIMCHALAR = ["", "", "", "ni", "im", "imni", "ga", "da", "lar"]


def niyatlar(rng, n=60):
    nomlar = sorted(TUSHUNCHALAR)
    juftlar = set()
    while len(juftlar) < n:
        a, b = rng.sample(nomlar, 2)
        juftlar.add((a, b, rng.choice(AMALLAR)))
    return sorted(juftlar)


def shakl(tushuncha, i):
    return TUSHUNCHALAR[tushuncha][0][i]


def faq_hujjat(niyat, rng):
    a, b, amal = niyat
    ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
    return (f"{shakl(a, 0)} {shakl(b, 0)} {amal}? Javob: {shakl(a, 0)} bo'yicha {rng.choice(ka)} "
            f"va {shakl(b, 0)} uchun {rng.choice(kb)} bo'limiga qarang.")


def qoshimcha(ibora, rng):
    return ibora + rng.choice(QOSHIMCHALAR)


def sorov_kalit(niyat, rng):
    a, b, amal = niyat
    return f"{qoshimcha(shakl(a, 0), rng)} {qoshimcha(shakl(b, 0), rng)} {amal}"


def sorov_parafraz(niyat, rng):
    a, b, amal = niyat
    return f"{shakl(a, rng.choice([1, 2]))} {shakl(b, rng.choice([1, 2]))} {amal}"


def fon_korpus(rng, n=4000):
    """Suhbat loglari: sinonimlar bir xil kontekst so'zlari bilan uchraydi (taqsimot gipotezasi)."""
    nomlar = sorted(TUSHUNCHALAR)
    matnlar = []
    for _ in range(n):
        a, b = rng.sample(nomlar, 2)
        ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
        matnlar.append(f"{shakl(a, rng.randrange(3))} {rng.choice(ka)} {rng.choice(ka)} "
                       f"{shakl(b, rng.randrange(3))} {rng.choice(kb)} {rng.choice(AMALLAR)}")
    return matnlar


def mrr(Q, E, togri):
    ball = Q @ E.T
    orin = (ball > ball[np.arange(len(togri)), togri][:, None]).sum(1)   # to'g'ri hujjatdan yuqorilar
    return 1.0 / (orin + 1)


def normalla(z):
    return z / np.maximum(np.linalg.norm(z, axis=1, keepdims=True), 1e-12)


def int8_kvant(E):
    """Har vektor o'z shkalasi bilan: x ~ shkala * q, q in [-127, 127]."""
    shkala = np.abs(E).max(axis=1, keepdims=True) / 127
    q = np.round(E / shkala).astype(np.int8)
    return q, shkala.astype(np.float32)


def main() -> None:
    rng = random.Random(0)
    niyat = niyatlar(rng)
    faq = [faq_hujjat(n, rng) for n in niyat]
    fon = fon_korpus(rng)
    togri = np.array([i for i in range(len(niyat)) for _ in range(2)])
    sorov = {}
    for qism, urug in [("val", 1), ("test", 2)]:
        r = random.Random(urug)
        sorov[qism] = [sorov_kalit(niyat[i], r) for i in togri] + \
                      [sorov_parafraz(niyat[i], r) for i in togri]
    togri2 = np.concatenate([togri, togri])
    tf = TfidfVectorizer(token_pattern=r"[a-z']+", sublinear_tf=True).fit(faq + fon)

    print("=== 1. O'lcham k: sifat (val MRR) va 1 mln hujjat uchun xotira ===")
    print("  k     val MRR   xotira float32   bitta so'rov (1 mln hujjat)")
    val, modellar = {}, {}
    for k in (4, 8, 16, 32, 64):
        svd = TruncatedSVD(k, random_state=0).fit(tf.transform(faq + fon))
        modellar[k] = svd
        emb = lambda qs, svd=svd: normalla(svd.transform(tf.transform(qs)))
        val[k] = mrr(emb(sorov["val"]), emb(faq), togri2)
        print(f"  {k:<4} {val[k].mean():>8.3f} {1e6 * k * 4 / 1e6:>12.0f} MB "
              f"{2 * k * 1e6 / 1e6:>14.0f} mln amal")

    print("\n=== 2. Qaror: eng yaxshisidan sezilarli yomon bo'lmagan eng kichik k ===")
    eng = max(val, key=lambda k: val[k].mean())
    tanlov = None
    for k in sorted(val):
        f = val[eng] - val[k]
        se = f.std(ddof=1) / math.sqrt(len(f))
        yomon = f.mean() > 2 * se
        print(f"  k={k:<3} eng yaxshi (k={eng}) dan farq {f.mean():+.3f}, SE {se:.3f} -> "
              f"{'sezilarli yomon' if yomon else 'sezilarli emas'}")
        if not yomon and tanlov is None:
            tanlov = k
    print(f"  tanlandi: k = {tanlov}")

    print("\n=== 3. Kvantlash: float32 -> float16 -> int8 (TEST, tanlangan k) ===")
    emb = lambda qs: normalla(modellar[tanlov].transform(tf.transform(qs)))
    Q, E = emb(sorov["test"]), emb(faq).astype(np.float32)
    asos = mrr(Q, E, togri2)
    q8, shkala = int8_kvant(E)
    for nom, Ek, bayt in [("float32", E, 4), ("float16", E.astype(np.float16).astype(np.float32), 2),
                          ("int8", q8.astype(np.float32) * shkala, 1)]:
        m = mrr(Q, Ek, togri2)
        top_mos = np.mean(np.argmax(Q @ Ek.T, 1) == np.argmax(Q @ E.T, 1))
        print(f"  {nom:<8} MRR {m.mean():.3f} (farq {m.mean() - asos.mean():+.4f}), "
              f"top-1 float32 bilan bir xil {top_mos:.1%}, xotira {bayt * tanlov} bayt/vektor")

    print("\n=== 4. Lug'atdan tashqari so'zlar (OOV): so'z darajasidagi model chegarasi ===")
    tokenlar = [s.split() for s in sorov["test"][:120]]
    oov = np.mean([any(w not in tf.vocabulary_ for w in t) for t in tokenlar])
    print(f"  kalit so'z so'rovlarining {oov:.0%} ida kamida bitta so'z lug'atda yo'q (qo'shimcha: 'kartamni')")
    yangi = ["plastikka pul tushmadi", "kriptovalyuta hamyonini ochish", "zakazimni bekor qilish"]
    for s in yangi:
        z = modellar[tanlov].transform(tf.transform([s]))
        yoq = [w for w in s.split() if w not in tf.vocabulary_]
        print(f"  {s!r:<36} lug'atda yo'q: {', '.join(yoq) or '-'}; vektor normasi {np.linalg.norm(z):.3f}")
    print("  \u2b50 O'lchamni val da tanlang, kichigini afzal ko'ring; model lug'ati va domeni muhim")


if __name__ == "__main__":
    with warnings.catch_warnings():
        warnings.simplefilter("ignore")
        main()

=== 1. O'lcham k: sifat (val MRR) va 1 mln hujjat uchun xotira ===
  k     val MRR   xotira float32   bitta so'rov (1 mln hujjat)
  4       0.256           16 MB              8 mln amal
  8       0.457           32 MB             16 mln amal
  16      0.694           64 MB             32 mln amal
  32      0.677          128 MB             64 mln amal
  64      0.449          256 MB            128 mln amal

=== 2. Qaror: eng yaxshisidan sezilarli yomon bo'lmagan eng kichik k ===
  k=4   eng yaxshi (k=16) dan farq +0.438, SE 0.027 -> sezilarli yomon
  k=8   eng yaxshi (k=16) dan farq +0.236, SE 0.024 -> sezilarli yomon
  k=16  eng yaxshi (k=16) dan farq +0.000, SE 0.000 -> sezilarli emas
  k=32  eng yaxshi (k=16) dan farq +0.017, SE 0.026 -> sezilarli emas
  k=64  eng yaxshi (k=16) dan farq +0.244, SE 0.034 -> sezilarli yomon
  tanlandi: k = 16

=== 3. Kvantlash: float32 -> float16 -> int8 (TEST, tanlangan k) ===
  float32  MRR 0.706 (farq +0.0000), top-1 float32 bilan bir xil 100.0%, xotira 64 bayt/vektor
  float16  MRR 0.706 (farq +0.0000), top-1 float32 bilan bir xil 100.0%, xotira 32 bayt/vektor
  int8     MRR 0.706 (farq +0.0003), top-1 float32 bilan bir xil 98.8%, xotira 16 bayt/vektor

=== 4. Lug'atdan tashqari so'zlar (OOV): so'z darajasidagi model chegarasi ===
  kalit so'z so'rovlarining 85% ida kamida bitta so'z lug'atda yo'q (qo'shimcha: 'kartamni')
  'plastikka pul tushmadi'             lug'atda yo'q: plastikka, tushmadi; vektor normasi 0.387
  'kriptovalyuta hamyonini ochish'     lug'atda yo'q: kriptovalyuta, hamyonini, ochish; vektor normasi 0.000
  'zakazimni bekor qilish'             lug'atda yo'q: zakazimni; vektor normasi 0.522
  ⭐ O'lchamni val da tanlang, kichigini afzal ko'ring; model lug'ati va domeni muhim

"""Taxminiy yaqin qo'shni (ANN): noldan IVF (k-means klasterlar) va aniq qidiruv bilan taqqoslash."""

import random
import warnings

import numpy as np
from sklearn.decomposition import TruncatedSVD
from sklearn.feature_extraction.text import TfidfVectorizer

TUSHUNCHALAR = {
    "karta": (["karta", "plastik", "bank kartasi"], ["bankomat", "chip", "amal qilish"]),
    "parol": (["parol", "maxfiy kod", "pin kod"], ["kirish", "xavfsizlik", "unutdim"]),
    "bloklash": (["bloklash", "muzlatish", "to'xtatib qo'yish"], ["o'g'irlandi", "yo'qoldi", "vaqtincha"]),
    "otkazma": (["o'tkazma", "pul jo'natish", "transfer"], ["qabul qiluvchi", "rekvizit", "yubordim"]),
    "kredit": (["kredit", "qarz", "nasiya"], ["grafik", "oylik to'lov", "kafil"]),
    "foiz": (["foiz", "ustama", "stavka"], ["yillik", "hisoblanadi", "miqdori"]),
    "ilova": (["ilova", "mobil dastur", "app"], ["yangilash", "smartfon", "yuklab olish"]),
    "hisob": (["hisob raqam", "schyot", "balans"], ["qoldiq", "ko'chirma", "mablag'"]),
    "komissiya": (["komissiya", "xizmat haqi", "ushlanma"], ["tarif", "ushlab qolindi", "summa"]),
    "yetkazish": (["yetkazish", "kuryer", "dostavka"], ["olib keladi", "eshikkacha", "manzilga"]),
    "qaytarish": (["qaytarish", "almashtirish", "vozvrat"], ["nuqson", "chek", "sifatsiz"]),
    "buyurtma": (["buyurtma", "zakaz", "xarid"], ["savat", "rasmiylashtirish", "mahsulot"]),
    "chegirma": (["chegirma", "aksiya", "skidka"], ["promokod", "arzonlashtirish", "bayram"]),
    "valyuta": (["valyuta", "dollar", "xorijiy pul"], ["kurs", "ayirboshlash", "konvertatsiya"]),
    "bonus": (["keshbek", "bonus", "qaytim ball"], ["to'plash", "sarflash", "hamyon"]),
    "muddat": (["muddat", "necha kun", "qancha vaqt"], ["kutish", "ish kuni", "tez"]),
}
AMALLAR = ["qanday o'zgartiraman", "qayerdan bilaman", "qanday rasmiylashtiraman",
           "bekor qilsa bo'ladimi", "qanday tekshiraman", "nima uchun ishlamayapti"]
QOSHIMCHALAR = ["", "", "", "ni", "im", "imni", "ga", "da", "lar"]


def niyatlar(rng, n=60):
    nomlar = sorted(TUSHUNCHALAR)
    juftlar = set()
    while len(juftlar) < n:
        a, b = rng.sample(nomlar, 2)
        juftlar.add((a, b, rng.choice(AMALLAR)))
    return sorted(juftlar)


def shakl(tushuncha, i):
    return TUSHUNCHALAR[tushuncha][0][i]


def faq_hujjat(niyat, rng):
    a, b, amal = niyat
    ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
    return (f"{shakl(a, 0)} {shakl(b, 0)} {amal}? Javob: {shakl(a, 0)} bo'yicha {rng.choice(ka)} "
            f"va {shakl(b, 0)} uchun {rng.choice(kb)} bo'limiga qarang.")


def qoshimcha(ibora, rng):
    return ibora + rng.choice(QOSHIMCHALAR)


def sorov_kalit(niyat, rng):
    a, b, amal = niyat
    return f"{qoshimcha(shakl(a, 0), rng)} {qoshimcha(shakl(b, 0), rng)} {amal}"


def sorov_parafraz(niyat, rng):
    a, b, amal = niyat
    return f"{shakl(a, rng.choice([1, 2]))} {shakl(b, rng.choice([1, 2]))} {amal}"


def fon_korpus(rng, n=4000):
    """Suhbat loglari: sinonimlar bir xil kontekst so'zlari bilan uchraydi (taqsimot gipotezasi)."""
    nomlar = sorted(TUSHUNCHALAR)
    matnlar = []
    for _ in range(n):
        a, b = rng.sample(nomlar, 2)
        ka, kb = TUSHUNCHALAR[a][1], TUSHUNCHALAR[b][1]
        matnlar.append(f"{shakl(a, rng.randrange(3))} {rng.choice(ka)} {rng.choice(ka)} "
                       f"{shakl(b, rng.randrange(3))} {rng.choice(kb)} {rng.choice(AMALLAR)}")
    return matnlar


def normalla(z):
    return z / np.maximum(np.linalg.norm(z, axis=1, keepdims=True), 1e-12)


def kmeans(X, k, rng, iter_=15):
    """Oddiy k-means (kosinus uchun: markazlar ham normallanadi)."""
    C = X[rng.choice(len(X), k, replace=False)].copy()
    for _ in range(iter_):
        tayin = np.argmax(X @ C.T, axis=1)
        for j in range(k):
            a = X[tayin == j]
            if len(a):
                C[j] = a.mean(0)
        C = normalla(C)
    return C, np.argmax(X @ C.T, axis=1)


class IVF:
    """Inverted file: har hujjat eng yaqin markaz ro'yxatiga; so'rovda nprobe ta ro'yxat ko'riladi."""

    def __init__(self, X, nlist, rng):
        self.X = X
        self.C, tayin = kmeans(X, nlist, rng)
        self.royxat = [np.where(tayin == j)[0] for j in range(nlist)]

    def qidir(self, q, k, nprobe):
        markaz = np.argsort(-(self.C @ q))[:nprobe]
        nomzod = np.concatenate([self.royxat[j] for j in markaz])
        ball = self.X[nomzod] @ q
        top = nomzod[np.argsort(-ball, kind="stable")[:k]]
        return top, len(self.C) + len(nomzod)            # hisoblangan masofalar soni


def main() -> None:
    rng = random.Random(0)
    hujjat = fon_korpus(rng, n=20000)
    sorov = fon_korpus(random.Random(99), n=300)
    tf = TfidfVectorizer(token_pattern=r"[a-z']+", sublinear_tf=True).fit(hujjat)
    svd = TruncatedSVD(32, random_state=0).fit(tf.transform(hujjat))
    X = normalla(svd.transform(tf.transform(hujjat))).astype(np.float32)
    Q = normalla(svd.transform(tf.transform(sorov))).astype(np.float32)
    k = 10

    print("=== 1. Aniq qidiruv (brute force) ===")
    B = Q @ X.T
    aniq = np.argsort(-B, axis=1, kind="stable")[:, :k]
    chegara = np.take_along_axis(B, aniq, 1)[:, -1]      # 10-o'rindagi ball (teng ballar uchun)
    print(f"  hujjatlar {X.shape[0]}, o'lcham {X.shape[1]}, so'rovlar {len(Q)}")
    print(f"  bitta so'rovga {X.shape[0]} ta kosinus hisoblanadi")

    print("\n=== 2. IVF: nlist va nprobe bo'yicha recall@10 va ish hajmi ===")
    print("  nlist  nprobe   recall@10   masofalar/so'rov   aniqdan tejash")
    npr = np.random.default_rng(0)
    natija = {}
    for nlist in (64, 256):
        ivf = IVF(X, nlist, npr)
        hajm = [len(r) for r in ivf.royxat]
        for nprobe in (1, 2, 4, 8, 16):
            rec, ish = [], []
            for i, q in enumerate(Q):
                top, n = ivf.qidir(q, k, nprobe)
                rec.append(np.mean(X[top] @ q >= chegara[i] - 1e-6) if len(top) == k else len(top) / k)
                ish.append(n)
            natija[nlist, nprobe] = (np.mean(rec), np.mean(ish))
            print(f"  {nlist:<6} {nprobe:>6} {np.mean(rec):>11.3f} {np.mean(ish):>18.0f} "
                  f"{X.shape[0] / np.mean(ish):>14.1f}x")
        print(f"  (nlist={nlist}: ro'yxat hajmi min {min(hajm)}, o'rtacha {np.mean(hajm):.0f}, "
              f"max {max(hajm)})")

    print("\n=== 3. Qaror: recall >= 0.95 bo'lgan eng arzon sozlama ===")
    mos = [(v[1], key) for key, v in natija.items() if v[0] >= 0.95]
    if mos:
        ish, (nl, npb) = min(mos)
        print(f"  nlist={nl}, nprobe={npb}: recall {natija[nl, npb][0]:.3f}, "
              f"{ish:.0f} masofa (aniq qidiruvdan {X.shape[0] / ish:.1f} barobar kam)")
    else:
        print("  hech bir sozlama 0.95 ga yetmadi")

    print("\n=== 4. Xulosa (natijadan) ===")
    a, b = natija[64, 1], natija[64, 16]
    print(f"  nprobe 1 -> 16 (nlist 64): recall {a[0]:.3f} -> {b[0]:.3f}, ish {a[1]:.0f} -> {b[1]:.0f}")
    print("  \u2b50 ANN - recall va tezlik orasidagi tugma; recall ni aniq qidiruvga nisbatan o'lchang")


if __name__ == "__main__":
    with warnings.catch_warnings():
        warnings.simplefilter("ignore")
        main()

=== 1. Aniq qidiruv (brute force) ===
  hujjatlar 20000, o'lcham 32, so'rovlar 300
  bitta so'rovga 20000 ta kosinus hisoblanadi

=== 2. IVF: nlist va nprobe bo'yicha recall@10 va ish hajmi ===
  nlist  nprobe   recall@10   masofalar/so'rov   aniqdan tejash
  64          1       0.795                460           43.4x
  64          2       0.927                788           25.4x
  64          4       0.987               1334           15.0x
  64          8       0.998               2342            8.5x
  64         16       1.000               4754            4.2x
  (nlist=64: ro'yxat hajmi min 39, o'rtacha 312, max 752)
  256         1       0.761                364           54.9x
  256         2       0.899                455           43.9x
  256         4       0.964                620           32.3x
  256         8       0.989                925           21.6x
  256        16       1.000               1531           13.1x
  (nlist=256: ro'yxat hajmi min 8, o'rtacha 78, max 331)

=== 3. Qaror: recall >= 0.95 bo'lgan eng arzon sozlama ===
  nlist=256, nprobe=4: recall 0.964, 620 masofa (aniq qidiruvdan 32.3 barobar kam)

=== 4. Xulosa (natijadan) ===
  nprobe 1 -> 16 (nlist 64): recall 0.795 -> 1.000, ish 460 -> 4754
  ⭐ ANN - recall va tezlik orasidagi tugma; recall ni aniq qidiruvga nisbatan o'lchang

ball = X @ q                                                        # ⚠️
Xn = X / np.linalg.norm(X, axis=1, keepdims=True)                   # ✅
ball = Xn @ (q / np.linalg.norm(q))

E = eski_model.emb(hujjatlar); q = yangi_model.emb([sorov])         # ⚠️
E = model.emb(hujjatlar); q = model.emb([sorov])                    # ✅ bir xil model/versiya

k = max(ks, key=lambda k: mrr(test, k))                             # ⚠️
k = max(ks, key=lambda k: mrr(val, k)); natija = mrr(test, k)       # ✅

ball = emb(q) @ E.T                                                 # ⚠️
ball = 0.5 * belgi_tfidf(q) + 0.5 * emb(q) @ E.T                    # ✅ gibrid

z = emb([sorov])[0]                                                 # ⚠️
z = svd.transform(tf.transform([sorov]))[0]                         # ✅
if np.linalg.norm(z) < 1e-9:
    z = None                                                        # kalit so'z qidiruviga o'tish

top = ivf.qidir(q, 10, nprobe=1)[0]                                 # ⚠️
aniq = np.argsort(-(X @ q))[:10]                                    # ✅ namuna so'rovlarda
recall = len(set(top) & set(aniq)) / 10

recall = len(set(top) & set(aniq)) / 10                             # ⚠️ dublikatlar ko'p bo'lsa
recall = np.mean(X[top] @ q >= chegara_10 - 1e-6)                   # ✅

1.  # a = [3, 4], b = [6, 8]: skalyar ko'paytma va kosinus?
2.  # normallangan a, b uchun |a - b|^2 ni cos orqali ifodalang
3.  # 'plastik' so'zli so'rov 'karta' so'zli FAQ ni TF-IDF bilan topadimi?
4.  # 'kartamni' so'zi so'z darajasidagi TF-IDF lug'atida 'karta' ga mos keladimi?
5.  # nega LSA da k ni oshirish parafraz sifatini pasaytirishi mumkin?
6.  # 1 mln hujjat, d = 768, float32 - xotira?
7.  # xuddi shu int8 da?
8.  # IVF da nprobe = nlist bo'lsa, natija nimaga teng?
9.  # nlist 64 dan 256 ga oshsa, bir xil nprobe da recall odatda?
10. # hamma so'zi OOV bo'lgan so'rovning LSA vektori?
11. # gibridda ballar turli shkalada bo'lsa nima qilish kerak?
12. # embedding modelini almashtirsak, indeks bilan nima qilamiz?

1.  ball = X @ q
    top = np.argsort(-ball)[:5]

2.  ks = [8, 16, 32, 64]
    eng_k = max(ks, key=lambda k: mrr(test_sorovlar, k))
    print("test MRR:", mrr(test_sorovlar, eng_k))

3.  E = model_v1.emb(hujjatlar)
    ...  # olti oydan keyin
    q = model_v2.emb([sorov])
    top = np.argsort(-(E @ q[0]))[:5]

4.  top = ivf.qidir(q, 10, nprobe=1)[0]
    print("IVF aniq qidiruv bilan bir xil")

5.  E = svd.transform(tf.transform(hujjatlar))
    q = svd.transform(tf.transform([sorov]))[0]
    top = np.argsort(-(E @ q))[:5]