8.2 TF-IDF與排名演算法#

概念說明#

倒排索引回答「哪些文件含有這些詞」，但使用者要的是「最相關的排在最前」。排名（ranking）就是相關性的量化：給定查詢 q 與文件 d，算一個分數 score(q, d)，由大到小排序。

TF-IDF 是最經典的權重方案，兩個直覺各據一半：

TF（詞頻）：詞 w 在文件 d 中出現越多次，d 與 w 越相關。但相關性不是線性的——出現 10 次不代表比 1 次相關 10 倍，常用對數壓縮：tf = 1 + log(count)。
IDF（逆文件頻率）：出現在越多文件中的詞越沒有區別力。「演算法」在我們的小語料中每篇都有，IDF≈0；「倒排索引」只有一篇有，IDF 高。idf(w) = log(N / df(w)) + 1（N 為文件總數、df 為含 w 的文件數）。

向量模型：把文件與查詢都表示為「各詞的 TF-IDF 權重」構成的向量，相關性 = 餘弦相似度 cos(θ) = (q·d)/(‖q‖‖d‖)。除以長度是關鍵：否則長文件天然占便宜。查詢向量也做同樣加權，讓稀有詞在查詢中更重要。

BM25（Robertson & Spärck Jones 系列工作）是現代標準（Elasticsearch、Lucene 預設），對 TF-IDF 的兩個修正是：

詞頻飽和：分數隨 tf 增長但有上界——tf 出現 3 次後，第 4 次的邊際貢獻趨近 0。tf 貢獻 = tf·(k₁+1) / (tf + k₁)，k₁≈1.2 控制飽和速度。
文件長度正規化：除以 (1 − b + b·|d|/avgdl)，b≈0.75——太長的文件不能無限占優，但也不該一刀切懲罰（b=0 就是不管長度）。

評估：排名好壞用標準 IR 指標——Precision@k（前 k 名中相關的比例）、MAP、NDCG。這讓排名演算法可以像分類器一樣被量化比較。

語義擴展：TF-IDF 只懂「字面」。現代搜尋加上向量檢索：查詢與文件都編碼成語義向量（7.3 節的延伸），用餘弦相似度召回「詞面不同但義近」的文件（查「筆電」也召回「膝上型電腦」），與 BM25 分數融合（hybrid search）。再疊上 8.3 節的重要性訊號與點擊回饋，就是完整引擎的輪廓。

演算法步驟#

對每份文件分詞，統計詞頻與文件長度；統計每詞的 df。
建索引（8.1 節），同時存 tf 於 posting。
對查詢分詞，取各詞 posting 交集得候選文件。
對每個候選文件 d：score = Σ_{w∈q} tfidf(w,d) × tfidf(w,q)（向量模型）或 BM25 分式和。
除以向量範數（餘弦模型需要），依分數排序輸出前 k 名。

Python 程式碼範例#

import math, re
from collections import Counter

DOCS = {  # 延續 8.1 節語料
    1: "演算法是處理資料的方法，資料結構支撐演算法。",
    2: "深度學習是演算法的一種，需要大量資料。",
    3: "資料結構與演算法是電腦科學的核心課程。",
    4: "搜尋引擎使用倒排索引與排名演算法。",
}
def analyze(text):
    """與 8.1 節一致：中文單字＋二字詞，英文完整詞"""
    out = []
    for run in re.findall(r"[\u4e00-\u9fff]+|[A-Za-z0-9]+", text.lower()):
        if not "\u4e00" <= run[0] <= "\u9fff":
            out.append(run)
        else:
            for i in range(len(run)):
                out.append(run[i])
                if i + 1 < len(run):
                    out.append(run[i:i + 2])
    return out

tf, doc_len = {}, {}
for d, text in DOCS.items():
    tf[d] = Counter(analyze(text))
    doc_len[d] = len(tf[d])
N = len(DOCS)
df = Counter(w for c in tf.values() for w in c)
def idf(w): return math.log(N / df[w]) + 1 if df[w] else 0.0

def tfidf_vector(counter):
    return {w: (1 + math.log(c)) * idf(w) for w, c in counter.items()}

def cosine(q_vec, d_vec):
    dot = sum(s * d_vec.get(w, 0) for w, s in q_vec.items())
    nq = math.sqrt(sum(s * s for s in q_vec.values()))
    nd = math.sqrt(sum(s * s for s in d_vec.values()))
    return dot / (nq * nd) if nq and nd else 0

def search_tfidf(query, top=3):
    q = tfidf_vector(Counter(analyze(query)))
    scores = {d: cosine(q, tfidf_vector(c)) for d, c in tf.items()}
    return sorted(scores.items(), key=lambda x: -x[1])[:top]

def bm25(query, k1=1.2, b=0.75, top=3):
    avgdl = sum(doc_len.values()) / N
    scores = {}
    for d in DOCS:
        s = 0
        for w in analyze(query):
            f = tf[d].get(w, 0)
            if f:
                s += idf(w) * f * (k1 + 1) / (f + k1 * (1 - b + b * doc_len[d] / avgdl))
        scores[d] = s
    return sorted(scores.items(), key=lambda x: -x[1])[:top]

for q in ["資料結構 演算法", "搜尋引擎 倒排索引", "深度學習 資料"]:
    print(q, "TF-IDF:", [(d, round(s, 3)) for d, s in search_tfidf(q)])
    print(q, "BM25  :", [(d, round(s, 3)) for d, s in bm25(q)])

複雜度分析#

離線：df/tf 統計 O(總詞數)；向量正規化常數預先算好存起來，查詢期免重算。
查詢：取 posting 交集 O(Σ串列長)；對候選計分 O(|q| × |候選|)；總複雜度與命中集大小成正比——排名只在候選集上做，不必掃全庫，這就是索引化排名。
BM25 vs TF-IDF：同量級；BM25 有兩個可調參數 k₁、b，且對長文件更穩健，故成為預設。
極大規模時用 WAND / Block-Max WAND 剪枝：維護分數上界，跳過不可能進前 k 名的文件，實務可省一個數量級。

練習#

構造兩份文件：短文件精確命中查詢一次、長文件出現查詢詞五次但夾雜大量無關內容；分別用「純 TF」（無 IDF、無長度正規）與 BM25 排名，展示後者為何較合理。
實作 NDCG@5：為 8.1 節的語料手工標註相關度（0–3），計算 TF-IDF 與 BM25 的 NDCG，比較誰贏。
把 7.3 節的詞向量接進來：對查詢中每個詞找最近的 2 個同義詞加入查詢（查詢擴展），觀察「筆電 vs 膝上型電腦」類查詢的召回變化；寫下擴展何時反而傷害精確率。