Nøgleordssøgning

Den centrale datastruktur er det inverterede indeks: en termordbog (i Lucene komprimeret som en finite-state transducer), der knytter hver term til en postingliste med dokument-ID'er, som regel med termfrekvenser og positioner, gemt deltakodet og komprimeret. En forespørgsel slår postingerne op for hver term og scorer kun dokumenter, der optræder på mindst én liste. Positioner muliggør frase- og nærhedsforespørgsler; indeks pr. felt gør det muligt at begrænse til eller vægte felter som titel frem for brødtekst. Top-k-evaluering undgår at score hvert match ved hjælp af dynamiske beskæringsalgoritmer som WAND og Block-Max WAND, der springer dokumenter over, hvis højest mulige score ikke kan nå ind i den aktuelle top k.

BM25, der stammer fra Okapi-systemet ved City University London og er formaliseret i den probabilistiske relevansramme (Robertson og Zaragoza, 2009), scorer et dokument D for forespørgslen Q som Σ IDF(q) · f(q, D) · (k₁ + 1) / (f(q, D) + k₁ · (1 − b + b · |D| / avgdl)). Termfrekvensdelen mættes: De første forekomster af en term bidrager mest, og yderligere gentagelser bidrager mindre og mindre, hvor k₁ styrer hvor hurtigt (typiske værdier 1,2-2,0). Parameteren b (typisk 0,75) normaliserer for dokumentlængden i forhold til gennemsnittet avgdl, så lange dokumenter ikke belønnes blot for at indeholde flere ord. Lucenes IDF er ln(1 + (N − n + 0,5) / (n + 0,5)) for N dokumenter, hvoraf n indeholder termen, så sjældne termer dominerer. Lucene gjorde BM25 til standard-similarity i version 6.0 (2016) i stedet for klassisk TF-IDF, med k₁ = 1,2 og b = 0,75; BM25F udvider formlen til vægtede felter. PostgreSQL's indbyggede ts_rank er derimod ikke BM25 og bruger ingen IDF på tværs af korpusset.

Kvaliteten afhænger lige så meget af analysekæden som af formlen: tokenisering, små bogstaver, Unicode-foldning, stopord, stemming eller lemmatisering og synonymer. Dansk kræver særlig omhu. Snowballs danske stemmer håndterer bøjninger, men den produktive orddannelse betyder, at "sygedagpengeloven" ikke matcher "sygedagpenge" eller "loven" uden ordbogsbaseret opsplitning af sammensatte ord, og æ, ø og å må ikke foldes til ASCII på en måde, der slår forskellige ord sammen. Den samme analyzer skal bruges ved indeksering og forespørgsel, ellers matcher termer ikke, uden at nogen opdager det.

Den klassiske svaghed er ordforrådsmismatch: Relevante dokumenter, der bruger andre ord, scorer nul. Afhjælpning omfatter synonymlister, udvidelse af forespørgslen med pseudo-relevance feedback (fx RM3), fuzzy match efter redigeringsafstand ved stavefejl og i dag kombination af den leksikalske rangering med dense retrieval i hybrid søgning. Styrkerne er forklarlighed (hver score kan opdeles i bidrag pr. term), intet behov for træning, billige løbende opdateringer og sletninger samt robusthed på ukendte domæner, og derfor er BM25 stadig standardbasislinjen i benchmarks for informationssøgning.