Cos’è BM25 e come implementare un motore di ricerca testuale in Python

C’è una differenza enorme tra una barra di ricerca che capisce esattamente cosa vuoi e una che ti restituisce una lista di risultati senza senso.

Quando digiti il nome di un prodotto su un e-commerce o cerchi un file in un archivio aziendale, non c’è una persona a interpretare la tua richiesta: c’è un algoritmo che deve prendere una decisione in frazioni di secondo.

Per decenni, e ancora oggi in moltissimi sistemi di produzione (come Elasticsearch o Lucene), il motore dietro a ricerche precise e pertinenti ha un nome specifico: BM25 (Best Matching 25).

Invece di limitarsi a contare quante volte una parola appare in un testo, il BM25 ragiona sulle proporzioni.

Capisce che termini rari sono preziosi, mentre parole comuni sono rumore di fondo. Sa anche che un documento lunghissimo non è necessariamente più rilevante di uno corto solo perché contiene più testo.

In questo articolo vedremo esattamente come ragiona questa funzione. Partiremo dalla sua struttura matematica per poi lavorare con Python: calcoleremo i punteggi su una piccola collezione, ottimizzeremo il codice per renderlo efficiente e, infine, lo avvicineremo a uno scenario reale elaborando il testo con strumenti linguistici.

Introduzione a BM25

BM25 (Best Matching 25) è una funzione di ranking ampiamente utilizzata nell’information retrieval per ordinare documenti in base alla rilevanza rispetto a una query. Si basa sul modello probabilistico e tiene conto della frequenza del termine nel documento, della lunghezza del documento (normalizzata) e della rarità del termine nell’intera collezione.

Formula base (per una query composta da termini [math]q_1, \dots, q_n[/math]):

[math]\displaystyle \text{Score}(D, Q) = \sum_{t \in Q} \text{IDF}(t) \cdot \frac{(k_1 + 1) \cdot f(t, D)}{K + f(t, D)}[/math]

dove:

• [math]f(t, D)[/math] = frequenza del termine [math]t[/math] nel documento [math]D[/math]
• [math]\displaystyle K = k_1 \cdot \left( (1 – b) + b \cdot \frac{|D|}{\text{avgdl}} \right)[/math]
• [math]|D|[/math] = lunghezza del documento (numero di termini)
• [math]\text{avgdl}[/math] = lunghezza media dei documenti nella collezione
• [math]k_1, b[/math] = parametri (tipicamente [math]k_1 = 1.2[/math], [math]b = 0.75[/math])
• [math]\displaystyle \text{IDF}(t) = \log \frac{N – n_t + 0.5}{n_t + 0.5}[/math] con [math]N[/math] = numero totale di documenti, [math]n_t[/math] = numero di documenti contenenti il termine [math]t[/math]

Questa formula premia i termini rari (IDF elevato) e normalizza l’effetto della lunghezza del documento, evitando che documenti molto lunghi ottengano punteggi eccessivi.

Negli esercizi che seguono, implementeremo BM25 in Python con approcci sempre più realistici e orientati alla produzione, affrontando problemi come l’efficienza, la gestione di campi multipli e l’integrazione in un servizio web.

Esercizio 1 – Calcolo base di BM25 su una piccola collezione

Testo

Sei un data scientist in una startup che sta sviluppando un motore di ricerca per un archivio di brevi descrizioni di prodotti. Il tuo primo compito è implementare un prototipo che calcoli il punteggio BM25 per un singolo termine di query su un insieme di soli 5 documenti. Utilizza i seguenti documenti:

1. “mouse wireless ergonomico”
2. “tastiera meccanica retroilluminata”
3. “mouse gaming con filo”
4. “tastiera wireless silenziosa”
5. “mouse ergonomico verticale”

La query è “mouse wireless”. Calcola manualmente il punteggio BM25 per ciascun documento (usa [math]k_1 = 1.2[/math], [math]b = 0.75[/math]) e poi scrivi una funzione Python che esegua lo stesso calcolo per verificare. Non preoccuparti della tokenizzazione: considera ogni documento come una lista di parole già separata.

Soluzione

1. Preprocessing

I documenti sono già tokenizzati. Calcoliamo:

[math]N = 5[/math]

Lunghezze (in termini):
doc1: 3, doc2: 3, doc3: 4, doc4: 3, doc5: 3

[math]\text{avgdl} = (3 + 3 + 4 + 3 + 3) / 5 = 16/5 = 3.2[/math]

2. Frequenze dei termini della query

Termini: “mouse” e “wireless”.

• [math]n_{\text{mouse}}[/math]: documenti che contengono “mouse”: doc1, doc3, doc5 → 3
• [math]n_{\text{wireless}}[/math]: doc1, doc4 → 2

3. Calcolo IDF

[math]\displaystyle \begin{aligned}
\text{IDF}(\text{mouse}) &= \log \frac{5 – 3 + 0.5}{3 + 0.5} = \log \frac{2.5}{3.5} \approx \log(0.7143) \approx -0.3365 \\
\text{IDF}(\text{wireless}) &= \log \frac{5 – 2 + 0.5}{2 + 0.5} = \log \frac{3.5}{2.5} = \log(1.4) \approx 0.3365
\end{aligned}[/math]

Nota: l’IDF può essere negativo se il termine compare in più della metà dei documenti. In BM25 spesso si usa la formula con smoothing per evitare valori negativi, ma per ora manteniamo la formula standard.

4. Calcolo di [math]K[/math] per ogni documento

5. Frequenze dei termini nei documenti

• doc1: “mouse”:1, “wireless”:1
• doc2: nessuno dei due → 0
• doc3: “mouse”:1, “wireless”:0
• doc4: “mouse”:0, “wireless”:1
• doc5: “mouse”:1, “wireless”:0

6. Contributo di ciascun termine per documento

Per ogni termine [math]t[/math], il contributo è:

[math]\displaystyle \text{IDF}(t) \cdot \frac{(k_1 + 1) \cdot f}{K + f}[/math]

con [math]k_1 + 1 = 2.2[/math].

mouse: [math]\text{IDF} = -0.3365[/math]

• [math]f=0[/math] → contributo 0
• [math]f=1[/math] → [math]-0.3365 \cdot \frac{2.2}{K + 1}[/math]

wireless: [math]\text{IDF} = 0.3365[/math]

• [math]f=0[/math] → 0
• [math]f=1[/math] → [math]0.3365 \cdot \frac{2.2}{K + 1}[/math]

7. Punteggio totale per documento

Interpretazione: il documento 4 (tastiera wireless) ha punteggio massimo perché contiene “wireless” ma non “mouse” (che è comune e penalizza), mentre doc1 li ha entrambi e si bilanciano.

8. Implementazione Python

import math
from collections import Counter

def bm25_single_term(corpus, query_terms, k1=1.2, b=0.75):
    N = len(corpus)
    # Lunghezze dei documenti
    doc_lengths = [len(doc) for doc in corpus]
    avgdl = sum(doc_lengths) / N
    
    # Calcolo n_t per ogni termine della query
    term_doc_counts = {}
    for term in query_terms:
        count = sum(1 for doc in corpus if term in doc)
        term_doc_counts[term] = count
    
    # Precalcolo IDF
    idf = {}
    for term in query_terms:
        n_t = term_doc_counts[term]
        idf[term] = math.log((N - n_t + 0.5) / (n_t + 0.5))
    
    scores = []
    for i, doc in enumerate(corpus):
        freq = Counter(doc)  # frequenze nel documento
        K = k1 * ((1 - b) + b * (doc_lengths[i] / avgdl))
        score = 0.0
        for term in query_terms:
            f = freq.get(term, 0)
            if f == 0:
                continue
            numerator = (k1 + 1) * f
            denominator = K + f
            score += idf[term] * (numerator / denominator)
        scores.append((i, score, doc))
    return scores

# Corpus
corpus = [
    ["mouse", "wireless", "ergonomico"],
    ["tastiera", "meccanica", "retroilluminata"],
    ["mouse", "gaming", "con", "filo"],
    ["tastiera", "wireless", "silenziosa"],
    ["mouse", "ergonomico", "verticale"]
]

query = ["mouse", "wireless"]
results = bm25_single_term(corpus, query)
for idx, score, doc in results:
    print(f"Doc {idx}: {score:.4f}  -> {' '.join(doc)}")

Output:

Doc 0: 0.0000  -> mouse wireless ergonomico
Doc 1: 0.0000  -> tastiera meccanica retroilluminata
Doc 2: -0.3053  -> mouse gaming con filo
Doc 3: 0.3453  -> tastiera wireless silenziosa
Doc 4: -0.3453  -> mouse ergonomico verticale

💡 Osservazione:

• L’IDF può essere negativo se il termine è molto frequente. In pratica si usa spesso la variante [math]\log((N – n_t + 0.5) / (n_t + 0.5))[/math] che può essere negativa; talvolta si sostituisce con [math]\max(0, \dots)[/math] oppure si usa [math]\log(1 + (N – n_t + 0.5)/(n_t + 0.5))[/math].
• La normalizzazione tramite [math]K[/math] riduce il peso dei termini nei documenti più lunghi.

Domanda di riflessione

Esercizio 2 – Classe BM25 con indicizzazione e ricerca top‑K

Testo

Ora che hai un prototipo funzionante, il tuo team ti chiede di sviluppare una classe riutilizzabile che pre‑indicizzi una collezione (ad esempio 1000 brevi descrizioni di prodotti) e offra un metodo search(query, k=10) che restituisca i primi [math]k[/math] documenti più rilevanti. La classe deve:

• Calcolare e memorizzare IDF per tutti i termini presenti nel corpus.
• Memorizzare le lunghezze dei documenti e la lunghezza media.
• Per ogni termine, tenere traccia dei documenti in cui compare (posting list) e della relativa frequenza.
• Il metodo search deve utilizzare le strutture precalcolate per calcolare velocemente i punteggi solo per i documenti che contengono almeno un termine della query.

Scrivere un esempio di utilizzo su un piccolo corpus di 10 documenti (per semplicità) e verificare che i risultati siano ordinati correttamente.

Soluzione

Implementazione della classe

import math
from collections import defaultdict, Counter

class BM25:
    def __init__(self, corpus, k1=1.2, b=0.75):
        """
        corpus: lista di liste di token (documenti già tokenizzati)
        """
        self.k1 = k1
        self.b = b
        self.corpus = corpus
        self.N = len(corpus)
        self.doc_lengths = [len(doc) for doc in corpus]
        self.avgdl = sum(self.doc_lengths) / self.N
        
        # Costruzione dell'indice: term -> {doc_id: freq, ...}
        self.index = defaultdict(dict)
        for doc_id, doc in enumerate(corpus):
            freq = Counter(doc)
            for term, f in freq.items():
                self.index[term][doc_id] = f
        
        # Precalcolo IDF per tutti i termini presenti
        self.idf = {}
        for term, postings in self.index.items():
            n_t = len(postings)
            self.idf[term] = math.log((self.N - n_t + 0.5) / (n_t + 0.5))
    
    def search(self, query_terms, top_k=10):
        """
        query_terms: lista di token
        restituisce: lista di tuple (doc_id, score)
        """
        # Per ogni termine, recupera i documenti che lo contengono
        candidate_docs = set()
        term_scores = {}  # per ottimizzare: accumuliamo punteggi per doc_id
        for term in query_terms:
            if term not in self.index:
                continue
            idf_t = self.idf[term]
            postings = self.index[term]  # dict doc_id -> freq
            # Per ogni doc che contiene il termine
            for doc_id, freq in postings.items():
                candidate_docs.add(doc_id)
                K = self.k1 * ((1 - self.b) + self.b * (self.doc_lengths[doc_id] / self.avgdl))
                numerator = (self.k1 + 1) * freq
                denominator = K + freq
                contrib = idf_t * (numerator / denominator)
                # Accumula
                if doc_id not in term_scores:
                    term_scores[doc_id] = 0.0
                term_scores[doc_id] += contrib
        
        # Ordina per punteggio decrescente
        sorted_docs = sorted(term_scores.items(), key=lambda x: x[1], reverse=True)
        return sorted_docs[:top_k]

Esempio di utilizzo

# Piccolo corpus di esempio
corpus = [
    ["il", "gatto", "nero", "salta"],
    ["il", "cane", "morde", "l'osso"],
    ["il", "gatto", "bianco", "dorme"],
    ["il", "topo", "scappa", "dal", "gatto"],
    ["il", "cane", "abbaia", "forte"],
    ["la", "tigre", "è", "un", "felino"],
    ["il", "leone", "ruggisce"],
    ["la", "gazzella", "corre", "veloce"],
    ["il", "gatto", "è", "un", "felino"],
    ["il", "cane", "è", "un", "mammifero"]
]

bm25 = BM25(corpus)
query = ["gatto", "felino"]
results = bm25.search(query, top_k=3)
for doc_id, score in results:
    print(f"Doc {doc_id}: score={score:.4f}  -> {' '.join(corpus[doc_id])}")

Output

Doc 8: score=1.4921  -> il gatto è un felino
Doc 5: score=1.1474  -> la tigre è un felino
Doc 0: score=0.3785  -> il gatto nero salta

💡 Osservazione:

• L’uso di un indice inverso (index) evita di scorrere tutti i documenti per ogni query, rendendo la ricerca efficiente anche su collezioni grandi.
• L’IDF viene precalcolato per tutti i termini, risparmiando tempo durante la ricerca.

Domanda di riflessione

Esercizio 3 – Preprocessing e gestione di query multi‑termine

Testo

La tua azienda ora vuole gestire query scritte in linguaggio naturale, come “mouse senza filo”. Devi estendere la classe BM25 per:

1. Tokenizzare il testo in modo robusto (convertire in minuscolo, rimuovere punteggiatura).
2. Rimuovere le stopword (usa una lista predefinita, es. {“il”, “lo”, “la”, “di”, “e”, “senza”, …}).
3. Applicare stemming (puoi usare una libreria come NLTK o SnowballStemmer) per ridurre le parole alla radice.
4. Gestire query con più termini, sommando i contributi di ogni termine.

Inoltre, implementa un metodo batch_search che, data una lista di query, restituisca i risultati per ciascuna.

Soluzione

Utilizzeremo nltk per tokenizzazione e stemming. Per semplicità, la tokenizzazione si limita a split su spazi e rimozione di punteggiatura con regex.

import re
import math
from collections import defaultdict, Counter
from nltk.stem import SnowballStemmer
from nltk.corpus import stopwords
import nltk
nltk.download('stopwords')  # solo la prima volta

class BM25Preprocessed(BM25):
    def __init__(self, corpus, k1=1.2, b=0.75, language='italian'):
        # corpus: lista di stringhe (testo grezzo)
        self.stemmer = SnowballStemmer(language)
        self.stopwords = set(stopwords.words(language))
        # Tokenizza e applica stemming
        tokenized_corpus = [self._preprocess(doc) for doc in corpus]
        super().__init__(tokenized_corpus, k1, b)
        self.raw_corpus = corpus  # per restituire il testo originale
    
    def _preprocess(self, text):
        # Rimuove punteggiatura, converte in minuscolo, split
        text = re.sub(r'[^\w\s]', '', text.lower())
        tokens = text.split()
        # Rimuove stopword e applica stemming
        tokens = [self.stemmer.stem(t) for t in tokens if t not in self.stopwords]
        return tokens
    
    def search(self, query_text, top_k=10):
        # Preprocessa la query
        query_tokens = self._preprocess(query_text)
        return super().search(query_tokens, top_k)
    
    def batch_search(self, queries, top_k=10):
        return {q: self.search(q, top_k) for q in queries}

Esempio

corpus = [
    "Il gatto nero salta sul muro",
    "Il cane morde l'osso con forza",
    "Il gatto bianco dorme sul divano",
    "Il topo scappa dal gatto nero",
    "Il cane abbaia forte",
    "La tigre è un felino maestoso",
    "Il leone ruggisce nella savana",
    "La gazzella corre veloce per sfuggire ai predatori",
    "Il gatto è un felino domestico",
    "Il cane è un mammifero fedele"
]

bm25p = BM25Preprocessed(corpus)
query = "gatto senza filo"
results = bm25p.search(query, top_k=3)
for doc_id, score in results:
    print(f"{doc_id}: {score:.4f}  -> {corpus[doc_id]}")

Output

8: 0.3946  -> Il gatto è un felino domestico
0: 0.3517  -> Il gatto nero salta sul muro
2: 0.3517  -> Il gatto bianco dorme sul divano

💡 Osservazione

• Lo stemming migliora il recall (rileva “gatto” anche se la query contiene “gatti”), ma può ridurre la precisione se due parole diverse vengono stemmate allo stesso modo.
• Le stopword vengono eliminate perché portano poco significato e distorcono l’IDF.

Domanda di riflessione

Perché questi esercizi riflettono il mondo reale 

L’evoluzione dei tre esercizi che abbiamo affrontato non è casuale, ma ricalca esattamente il ciclo di sviluppo di un sistema di ricerca in produzione:

Dalla scatola nera al calcolo (Esercizio 1): Spesso si usano librerie senza capirne la matematica. Calcolare il BM25 a mano è un test di sanità mentale (sanity check). Aver visto che l’IDF può diventare negativo ci insegna un dettaglio applicativo cruciale: in produzione, motori come Lucene modificano la formula (BM25L o varianti positive) per evitare che un termine molto comune applichi una penalità innaturale al documento.

L’importanza dell’Inverted Index (Esercizio 2): Questo è il cuore dell’Information Retrieval. Se calcolassimo il punteggio scorrendo ogni volta tutti i documenti (come nell’Es. 1), il nostro sistema collasserebbe con poche migliaia di righe. L’approccio dell’Esercizio 2 (scorrere solo i documenti che contengono effettivamente il termine) riduce la complessità computazionale da [math]O(N)[/math] a [math]O(\text{documenti rilevanti})[/math], rendendo possibili le ricerche in tempo reale.

La gestione del rumore umano (Esercizio 3): Gli esseri umani non cercano come le macchine. Usano plurali, congiunzioni, verbi coniugati. L’applicazione di NLP (stemming e rimozione stopword) dimostra che l’algoritmo di ranking matematico, da solo, non basta. Un buon motore di ricerca è sempre un ibrido tra matematica solida (BM25) e comprensione linguistica (NLP).

BM25 e Vector Search: Quale scegliere?