8.1 倒排索引的建立#

import re
from collections import defaultdict

DOCS = {
    1: "演算法是處理資料的方法，資料結構支撐演算法。",
    2: "深度學習是演算法的一種，需要大量資料。",
    3: "資料結構與演算法是電腦科學的核心課程。",
    4: "搜尋引擎使用倒排索引與排名演算法。",
}

def analyze(text):
    """中文用「單字＋相鄰二字詞（bigram）」索引，英文用完整詞——無需分詞器"""
    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

class InvertedIndex:
    def __init__(self):
        self.postings = defaultdict(lambda: defaultdict(list))  # 詞 -> doc -> [pos]
        self.doc_len = {}

    def add(self, doc_id, text):
        toks = []                                # (詞, 原文字元位置)
        for m in re.finditer(r"[\u4e00-\u9fff]+|[A-Za-z0-9]+", text.lower()):
            run, base = m.group(), m.start()
            if not "\u4e00" <= run[0] <= "\u9fff":
                toks.append((run, base))
            else:
                for i in range(len(run)):
                    toks.append((run[i], base + i))
                    if i + 1 < len(run):
                        toks.append((run[i:i + 2], base + i))
        self.doc_len[doc_id] = len(toks)
        for t, cp in toks:
            self.postings[t][doc_id].append(cp)

    def docs(self, term):
        return sorted(self.postings.get(term, {}))

    def intersect(self, terms):
        lists = [self.docs(t) for t in terms]
        if not lists: return []
        ptrs, out = [0] * len(lists), []
        while all(p < len(l) for p, l in zip(ptrs, lists)):
            ids = [l[p] for p, l in zip(ptrs, lists)]
            if len(set(ids)) == 1:
                out.append(ids[0])
                ptrs = [p + 1 for p in ptrs]
            else:
                m = min(ids)
                ptrs = [p + 1 if l[p] == m else p for p, l in zip(ptrs, lists)]
        return out

    def phrase(self, words):
        cand = self.intersect(words)
        out = []
        for d in cand:
            pos0 = self.postings[words[0]][d]
            if all(any(p + i in self.postings[w][d]
                       for p in pos0) for i, w in enumerate(words[1:], 1)):
                out.append(d)
        return out

ix = InvertedIndex()
for d, text in DOCS.items():
    ix.add(d, text)

print("『演』出現於:", ix.docs("演"))
print("『演算法』(二字詞交集):", ix.intersect(["演算", "算法"]))
print("『演算法』AND『資料』:", ix.intersect(["演算", "算法", "資料"]))
print("片語『倒排索引』:", ix.phrase(["倒排", "排索", "索引"]))
print("片語『資料結構』:", ix.phrase(["資料", "料結", "結構"]))