BM25: il motore matematico della ricerca full-text

TF, IDF, ranking probabilistico, vantaggi, limiti e perché continua a essere fondamentale anche nell’era degli LLM

Digiti una parola nella barra di ricerca. Premi invio. Meno di duecento millisecondi dopo, lo schermo si popola con i documenti esatti che ti servivano.

Siamo talmente abituati a questa reattività da dare per scontato il meccanismo matematico che la rende possibile.

Spesso attribuiamo tutto il merito ai recenti sviluppi dell’intelligenza artificiale, immaginando gigantesche reti neurali che leggono e interpretano ogni testo in tempo reale. La realtà, però, è diversa e per certi versi più affascinante.

Gran parte dell’architettura di ricerca mondiale si regge ancora oggi su una formula probabilistica concepita decenni fa: l’algoritmo BM25.

Nonostante Google abbia integrato segnali ben più complessi, tecnologie come Elasticsearch, OpenSearch e la libreria Lucene continuano a utilizzarlo come motore di ranking predefinito.

Il motivo? È incredibilmente veloce, matematicamente elegante e maledettamente efficace.

Vediamo come funziona e perché, paradossalmente, l’arrivo dei Large Language Model lo ha reso ancora più indispensabile.

Il problema dell’Information Retrieval

Immaginiamo di possedere un archivio di un milione di documenti.

L’utente scrive:

reti neurali profonde

Quale documento dovrebbe comparire al primo posto?

Consideriamo due documenti.

Documento A

Le reti neurali profonde hanno rivoluzionato il deep learning.

Documento B

Le reti neurali profonde vengono utilizzate in medicina. Le reti neurali profonde permettono diagnosi migliori. Le reti neurali profonde…

Quale è più rilevante?

Intuitivamente il secondo contiene più volte le parole cercate.

Ma cosa accade se un documento ripete cento volte la stessa frase?

Sarebbe davvero cento volte più importante?

La risposta è no.

Ed è proprio qui che nasce BM25.

Il limite del semplice conteggio delle parole

Il primo approccio storico consisteva nel contare quante volte compariva un termine.

Questa misura prende il nome di Term Frequency (TF).

La formula più semplice è

[math]\text{TF} = \text{numero di occorrenze del termine}[/math]

Ad esempio:

Python è semplice. Python è potente. Python è molto diffuso.

La parola “Python” compare tre volte.

Quindi

[math]\text{TF} = 3[/math]

Sembra ragionevole.

Ma emerge subito un problema.

Documenti molto lunghi avranno naturalmente frequenze maggiori.

Un manuale di 500 pagine citerà inevitabilmente più volte la parola “database” rispetto a un articolo di tre pagine.

Non significa però che sia più pertinente.

Serve una correzione.

L’importanza della rarità: nasce IDF

Esistono parole che compaiono ovunque:

• il
• essere
• avere
• fare

Sono praticamente inutili per distinguere un documento.

Al contrario, termini come

• transformer
• genomica
• Bayes
• Lagrangiano

forniscono molta informazione.

Nasce così la Inverse Document Frequency (IDF).

L’idea è semplice.

Più un termine è raro nell’intera collezione, maggiore sarà il suo peso.

La formula classica è

[math]\displaystyle \text{IDF} = \log\left(\frac{N}{df}\right)[/math]

dove

• [math]N[/math] = numero totale di documenti
• [math]df[/math] = document frequency, cioè il numero di documenti che contengono quella parola.

Esempio.

Archivio: 100.000 documenti.

La parola “algoritmo” compare in 20.000.

La parola “CRISPR” compare in 100.

Otteniamo

[math]\text{algoritmo} \quad \text{IDF} = \log(100000/20000) = 0.69[/math]

[math]\text{CRISPR} \quad \text{IDF} = \log(100000/100) = 6.90[/math]

Il secondo termine è molto più discriminante.

TF-IDF: il predecessore di BM25

Combinando TF e IDF si ottiene

[math]\text{TF} \times \text{IDF}[/math]

Per anni questo è stato il metodo dominante.

Ma presentava ancora alcuni problemi.

Ad esempio:

• crescita lineare della frequenza
• nessuna gestione ottimale dei documenti lunghi
• ranking non probabilistico

BM25 nasce proprio per correggere questi limiti.

Le origini di BM25

BM25 significa Best Matching 25.

Fu sviluppato nell’ambito del modello probabilistico di ricerca documentale, in particolare all’interno della famiglia dei modelli Okapi, progettati presso l’Università di Londra negli anni Ottanta e Novanta.

L’obiettivo era stimare la probabilità che un documento fosse realmente rilevante per una determinata query, anziché limitarsi a contare le occorrenze delle parole.

Nonostante l’età, il modello continua a essere utilizzato perché offre un eccellente compromesso tra qualità del ranking, semplicità computazionale e velocità di esecuzione.

La formula di BM25

La formula completa è

[math]\displaystyle \begin{aligned}
\text{Score}(D, Q) = \sum_{i} \text{IDF}(q_i) \cdot
\frac{\text{TF}(q_i) \cdot (k_1 + 1)}
{\text{TF}(q_i) + k_1 \left(1 – b + b \cdot \frac{|D|}{\text{avgD}}\right)}
\end{aligned}[/math]

A prima vista può sembrare intimidatoria.

In realtà ogni componente ha un significato intuitivo.

TF con saturazione

In TF-IDF classico

• 1 occorrenza
• ↓
• 2 occorrenze
• ↓
• 3 occorrenze
• ↓
• 100 occorrenze

il punteggio cresce sempre.

BM25 invece introduce una funzione di saturazione.

Le prime ripetizioni aumentano molto il punteggio.

Poi il beneficio diminuisce progressivamente.

È il principio dei rendimenti decrescenti.

Ad esempio:

Ripetere cento volte la stessa parola non rende un documento cento volte migliore.

La normalizzazione della lunghezza

BM25 considera anche la lunghezza del documento.

Compare infatti il termine

[math]\displaystyle \frac{|D|}{\text{avgD}}[/math]

dove

• [math]|D|[/math] = lunghezza del documento
• [math]\text{avgD}[/math] = lunghezza media del corpus

Se il documento è molto lungo, il punteggio viene ridimensionato.

Questo evita che enciclopedie e manuali risultino sempre favoriti rispetto a documenti più brevi ma maggiormente focalizzati sulla query.

I parametri [math]k_1[/math] e [math]b[/math]

Due costanti governano il comportamento dell’algoritmo.

[math]k_1[/math]

Controlla la velocità della saturazione.

Valori tipici:

• 1.2
• 1.5
• 2.0

Più è alto, maggiore è l’effetto della frequenza.

[math]b[/math]

Controlla quanto correggere la lunghezza.

Valori:

• [math]0[/math] → nessuna correzione
• [math]1[/math] → correzione completa

Nella pratica

[math]0.75[/math]

è il valore più utilizzato.

Un esempio completo

Supponiamo una query

machine learning

Tre documenti:

A

Machine learning con Python.

B

Machine learning machine learning machine learning…

C

Manuale di 800 pagine sul machine learning.

TF puro favorirebbe il documento B.

BM25 invece considera:

• frequenza
• lunghezza
• rarità dei termini
• saturazione

Il ranking finale potrebbe essere:

1. Documento A
2. Documento C
3. Documento B

perché il documento A contiene i termini della query in modo compatto e informativo, mentre il documento B ripete gli stessi concetti senza aggiungere contenuto rilevante.

Perché BM25 funziona così bene?

Esistono tre motivi principali.

1. Penalizza lo spam
   Ripetere continuamente una parola non migliora il ranking oltre una certa soglia.
2. Favorisce i documenti focalizzati
   Articoli brevi ma molto pertinenti possono superare documenti enormi.
3. È estremamente veloce
   Le operazioni richieste sono: conteggi, logaritmi, moltiplicazioni. Non servono GPU né reti neurali. Per milioni di documenti il tempo di risposta resta dell’ordine dei millisecondi.

machine
   → Doc1
   → Doc5
   → Doc12

learning
   → Doc1
   → Doc3
   → Doc5

python
   → Doc1
   → Doc8

BM25 ed Elasticsearch

Uno dei motivi della diffusione di BM25 è il suo utilizzo come algoritmo di ranking predefinito in Elasticsearch e OpenSearch, basati sulla libreria Apache Lucene.

Quando si esegue una query come:

{
  "query": {
    "match": {
      "contenuto": "machine learning"
    }
  }
}

il motore:

1. individua i documenti che contengono i termini;
2. calcola il punteggio BM25 per ciascuno;
3. ordina i risultati dal più al meno rilevante.

L’intero processo è ottimizzato attraverso strutture dati come gli indici invertiti, che permettono di recuperare rapidamente i documenti candidati senza dover analizzare ogni testo.

BM25 nei sistemi RAG

Con la diffusione dei Large Language Model sembrava che BM25 fosse destinato a scomparire.

È successo l’opposto.

Nei sistemi Retrieval-Augmented Generation (RAG), BM25 viene spesso combinato con gli embedding semantici.

Uno schema tipico è il seguente:

• i documenti vengono indicizzati con BM25;
• in parallelo vengono rappresentati come vettori tramite un modello di embedding;
• una query recupera candidati sia con ricerca lessicale sia con ricerca vettoriale;
• i risultati vengono fusi (hybrid search) e, se necessario, riordinati da un cross-encoder;
• solo i documenti migliori vengono inviati al modello linguistico.

Questo approccio sfrutta il meglio di entrambi i mondi. BM25 eccelle quando la query contiene termini tecnici, codici, sigle, numeri di versione o nomi propri, mentre gli embedding catturano relazioni semantiche e sinonimi.

I limiti di BM25

Nonostante l’efficacia, BM25 presenta alcune limitazioni strutturali.

Non comprende il significato
Per BM25 le parole “automobile” e “macchina” sono termini completamente diversi. La similarità semantica non viene considerata.

Non gestisce bene i sinonimi
Una query con “tumore” potrebbe non recuperare documenti che parlano esclusivamente di “neoplasia”, se quest’ultima parola non compare nel testo.

Ignora il contesto
Le espressioni “banca del sangue” e “banca d’investimento” contengono la stessa parola, ma con significati differenti. BM25 non è in grado di distinguere automaticamente questi casi.

Non cattura relazioni concettuali
Una ricerca su “reti neurali” potrebbe non trovare un documento che parla soltanto di “Transformer”, pur essendo strettamente correlato dal punto di vista semantico.

BM25 contro gli embedding

È frequente presentare BM25 e gli embedding come tecnologie concorrenti. In realtà, sono complementari.

Per questo motivo, nei sistemi di ricerca moderni la soluzione più efficace è spesso la ricerca ibrida, che combina il punteggio lessicale di BM25 con la similarità vettoriale.

Un piccolo esperimento in Python

Con la libreria rank_bm25 è possibile costruire un motore di ricerca essenziale in poche righe.

from rank_bm25 import BM25Okapi

corpus = [
    "machine learning con Python",
    "reti neurali profonde",
    "statistica bayesiana"
]

tokenized = [doc.split() for doc in corpus]

bm25 = BM25Okapi(tokenized)

query = "machine learning".split()

scores = bm25.get_scores(query)

for documento, punteggio in zip(corpus, scores):
    print(f"{punteggio:.2f} -> {documento}")

0.89 -> machine learning con Python
0.00 -> reti neurali profonde
0.00 -> statistica bayesiana

Pur nella sua semplicità, questo esempio mostra il cuore dell’algoritmo: i documenti vengono tokenizzati, viene costruito l’indice BM25 e ogni query restituisce un punteggio di rilevanza che può essere utilizzato per ordinare i risultati.

!pip install rank_bm25

import re
from typing import List, Dict, Any, Optional, Tuple
from rank_bm25 import BM25Okapi

# 1. Definizione della struttura del Documento
class Document:
    def __init__(self, doc_id: str, content: str, metadata: Dict[str, Any]):
        self.id = doc_id
        self.content = content
        self.metadata = metadata
        
    def __repr__(self):
        return f"Doc(id={self.id}, category={self.metadata.get('category')})"

# 2. Classe Retriever pronta per la produzione
class ProductionBM25Retriever:
    def __init__(self, documents: List[Document]):
        self.documents = documents
        # Stop-word di base per l'italiano (in produzione si usa NLTK o spaCy)
        self.stopwords = {"il", "lo", "la", "i", "gli", "le", "un", "uno", "una", 
                          "di", "a", "da", "in", "con", "su", "per", "tra", "fra", 
                          "e", "o", "ma", "che", "non", "è", "sono"}
        
        # Inizializzazione dell'indice globale al momento dell'instanziazione
        print("Costruzione dell'indice BM25 globale in corso...")
        self.corpus_tokens = [self._preprocess(doc.content) for doc in self.documents]
        self.bm25 = BM25Okapi(self.corpus_tokens)
        print(f"Indice costruito con successo su {len(self.documents)} documenti.")

    def _preprocess(self, text: str) -> List[str]:
        """
        L'Analyzer: simula il comportamento di Lucene normalizzando il testo.
        """
        # Lowercasing
        text = text.lower()
        # Estrazione di sole parole (rimuove punteggiatura)
        tokens = re.findall(r'\b\w+\b', text)
        # Rimozione stop-word
        return [t for t in tokens if t not in self.stopwords]

    def retrieve(self, 
                 query: str, 
                 metadata_filter: Optional[Dict[str, Any]] = None, 
                 top_k: int = 3) -> List[Tuple[float, Document]]:
        """
        Esegue la query applicando BM25 e un filtro booleano sui metadati.
        """
        tokenized_query = self._preprocess(query)
        
        # Calcolo degli score su TUTTO il corpus per mantenere coerente l'IDF globale
        scores = self.bm25.get_scores(tokenized_query)
        
        results = []
        for i, doc in enumerate(self.documents):
            # Filtro deterministico sui metadati durante il retrieval
            if metadata_filter:
                match_filter = all(doc.metadata.get(k) == v for k, v in metadata_filter.items())
                if not match_filter:
                    continue # Salta il documento se non rispetta i metadati
            
            score = scores[i]
            # Escludiamo i documenti con score zero (nessun match lessicale)
            if score > 0:
                results.append((score, doc))
                
        # Ordinamento decrescente basato sullo score BM25
        results.sort(key=lambda x: x[0], reverse=True)
        return results[:top_k]

# ==========================================
# TEST E ESECUZIONE
# ==========================================

# Creazione di un corpus fittizio con metadati
corpus_dati = [
    Document("1", "Il machine learning con Python permette di creare modelli predittivi.", {"category": "tech", "lang": "it"}),
    Document("2", "Le reti neurali profonde sono il cuore della moderna intelligenza artificiale.", {"category": "tech", "lang": "it"}),
    Document("3", "Un'introduzione alla statistica Bayesiana per analisti di mercato.", {"category": "math", "lang": "it"}),
    Document("4", "Il Python è un serpente costrittore diffuso in Africa e Asia.", {"category": "nature", "lang": "it"}),
    Document("5", "Machine learning applicato al mercato azionario e trading algoritmico.", {"category": "finance", "lang": "it"})
]

# Istanziamo il motore
retriever = ProductionBM25Retriever(corpus_dati)

print("\n--- TEST 1: Ricerca full-text standard ---")
query_1 = "modelli di machine learning"
risultati_1 = retriever.retrieve(query_1)
for score, doc in risultati_1:
    print(f"Score: {score:.3f} | {doc} | Testo: {doc.content}")

print("\n--- TEST 2: Ricerca con filtro sui metadati (Hard Filtering) ---")
# Cerchiamo "Python", ma limitando la ricerca solo alla categoria "nature"
query_2 = "Python"
filtro = {"category": "nature"}
risultati_2 = retriever.retrieve(query_2, metadata_filter=filtro)
for score, doc in risultati_2:
    print(f"Score: {score:.3f} | {doc} | Testo: {doc.content}")

Costruzione dell'indice BM25 globale in corso...
Indice costruito con successo su 5 documenti.

--- TEST 1: Ricerca full-text standard ---
Score: 0.981 | Doc(id=1, category=tech) | Testo: Il machine learning con Python permette di creare modelli predittivi.
Score: 0.583 | Doc(id=5, category=finance) | Testo: Machine learning applicato al mercato azionario e trading algoritmico.

--- TEST 2: Ricerca con filtro sui metadati (Hard Filtering) ---
Score: 0.811 | Doc(id=4, category=nature) | Testo: Il Python è un serpente costrittore diffuso in Africa e Asia.

import re
from collections import defaultdict
from typing import List, Dict, Any, Set, Tuple
from rank_bm25 import BM25Okapi

class Document:
    def __init__(self, doc_id: str, content: str, metadata: Dict[str, Any] = None):
        self.id = doc_id
        self.content = content
        self.metadata = metadata or {}
        
    def __repr__(self):
        return f"Doc({self.id})"

# 1. La struttura dati fondamentale: L'Indice Invertito
class InvertedIndex:
    def __init__(self):
        # Mappa ogni parola a un Set di ID documento
        self.index: Dict[str, Set[str]] = defaultdict(set)
        
    def add_document(self, doc_id: str, tokens: List[str]):
        """Popola il dizionario: Token -> {DocID_1, DocID_2}"""
        for token in set(tokens): # Usiamo set() per evitare di mappare lo stesso doc più volte per la stessa parola
            self.index[token].add(doc_id)
            
    def get_candidates(self, query_tokens: List[str]) -> Set[str]:
        """Recupera l'unione dei documenti che contengono ALMENO UNO dei token"""
        candidates = set()
        for token in query_tokens:
            candidates.update(self.index.get(token, set()))
        return candidates

# 2. Il Retriever Scalabile
class ScalableBM25Retriever:
    def __init__(self, documents: List[Document]):
        self.doc_store = {doc.id: doc for doc in documents}
        self.inverted_index = InvertedIndex()
        self.stopwords = {"il", "lo", "la", "i", "gli", "le", "un", "uno", "una", 
                          "di", "a", "da", "in", "con", "su", "per", "tra", "fra", 
                          "e", "o", "ma", "che", "non", "è", "sono"}
        
        print(f"Costruzione dell'Indice Invertito per {len(documents)} documenti...")
        
        # Strutture di supporto per il calcolo BM25 custom
        corpus_tokens = []
        self.doc_id_to_idx = {} 
        
        for idx, doc in enumerate(documents):
            tokens = self._preprocess(doc.content)
            corpus_tokens.append(tokens)
            
            # Popoliamo l'Indice Invertito
            self.inverted_index.add_document(doc.id, tokens)
            
            # Mappiamo l'ID al suo indice posizionale per le statistiche BM25
            self.doc_id_to_idx[doc.id] = idx

        # Usiamo BM25Okapi SOLO per pre-calcolare IDF e lunghezze medie (fase di indicizzazione)
        self.bm25_stats = BM25Okapi(corpus_tokens)
        print("Indicizzazione completata.")

    def _preprocess(self, text: str) -> List[str]:
        text = text.lower()
        tokens = re.findall(r'\b\w+\b', text)
        return [t for t in tokens if t not in self.stopwords]

    def _score_candidate(self, doc_id: str, query_tokens: List[str]) -> float:
        """Calcola la formula BM25 solo per un documento specifico"""
        idx = self.doc_id_to_idx[doc_id]
        score = 0.0
        
        # Statistiche specifiche del documento (recuperate in O(1))
        doc_len = self.bm25_stats.doc_len[idx]
        frequencies = self.bm25_stats.doc_freqs[idx]
        
        for token in query_tokens:
            if token not in frequencies:
                continue
                
            tf = frequencies[token]
            idf = self.bm25_stats.idf.get(token, 0)
            
            # Formula Okapi BM25
            num = tf * (self.bm25_stats.k1 + 1)
            den = tf + self.bm25_stats.k1 * (1 - self.bm25_stats.b + self.bm25_stats.b * (doc_len / self.bm25_stats.avgdl))
            score += idf * (num / den)
            
        return score

    def retrieve(self, query: str, top_k: int = 3) -> List[Tuple[float, Document]]:
        query_tokens = self._preprocess(query)
        
        # FASE 1: Candidate Retrieval (Veloce, via Indice Invertito)
        candidate_ids = self.inverted_index.get_candidates(query_tokens)
        print(f"\n[DEBUG] Token di query: {query_tokens}")
        print(f"[DEBUG] Documenti candidati recuperati: {len(candidate_ids)} su {len(self.doc_store)}")
        
        if not candidate_ids:
            return []

        # FASE 2: Scoring Esatto (Lento, ma applicato solo ai candidati)
        results = []
        for doc_id in candidate_ids:
            score = self._score_candidate(doc_id, query_tokens)
            results.append((score, self.doc_store[doc_id]))
            
        # FASE 3: Ranking
        results.sort(key=lambda x: x[0], reverse=True)
        return results[:top_k]

# ==========================================
# ESECUZIONE
# ==========================================
corpus = [
    Document("1", "Il machine learning con Python permette di creare modelli predittivi."),
    Document("2", "Le reti neurali profonde sono il cuore della moderna intelligenza artificiale."),
    Document("3", "Un'introduzione alla statistica Bayesiana per analisti di mercato."),
    Document("4", "Il Python è un serpente costrittore diffuso in Africa e Asia."),
    Document("5", "Machine learning applicato al mercato azionario e trading algoritmico.")
]

motore = ScalableBM25Retriever(corpus)

query = "modelli di machine learning"
risultati = motore.retrieve(query)

for score, doc in risultati:
    print(f"Score: {score:.3f} | {doc} | Testo: {doc.content}")

Costruzione dell'Indice Invertito per 5 documenti...
Indicizzazione completata.

[DEBUG] Token di query: ['modelli', 'machine', 'learning']
[DEBUG] Documenti candidati recuperati: 2 su 5
Score: 0.981 | Doc(1) | Testo: Il machine learning con Python permette di creare modelli predittivi.
Score: 0.583 | Doc(5) | Testo: Machine learning applicato al mercato azionario e trading algoritmico.

Conclusioni

BM25 dimostra come un algoritmo relativamente semplice possa continuare a essere competitivo anche nell’epoca dell’intelligenza artificiale generativa. La sua forza non risiede nella comprensione del linguaggio, ma nella capacità di sfruttare principi statistici solidi: la frequenza dei termini, la loro rarità e la normalizzazione rispetto alla lunghezza dei documenti.

Gli LLM hanno rivoluzionato il modo in cui interagiamo con l’informazione, ma non hanno eliminato la necessità di recuperare rapidamente i documenti più pertinenti. Anzi, i sistemi RAG più efficaci utilizzano proprio BM25 come primo filtro, affidando ai modelli neurali il compito di comprendere il contesto e generare risposte.

Questa convivenza tra metodi classici e tecniche moderne rappresenta una delle lezioni più interessanti della Data Science: l’innovazione raramente sostituisce completamente ciò che funziona; più spesso lo integra e lo valorizza. Dopo oltre trent’anni dalla sua introduzione, BM25 continua a essere il motore silenzioso che rende possibile gran parte della ricerca full-text nel software moderno, confermando che una buona idea matematica può attraversare intere generazioni di tecnologie senza perdere la propria efficacia.