语义搜索

小象实战讲义 · 知识图谱

前七章解决的是「怎么把知识图谱建出来」：表示、建模、抽取、存储。从本章开始解决「建好了怎么用」——当 RDF 三元组的规模达到十亿、千亿级，用户又只会输入几个关键词时，如何在图上快速、准确地搜到答案。本节是第 8 章的总览厚节，会把语义搜索的完整版图铺开：从文档检索与数据检索的分野讲起，依次穿过语义数据搜索（Semplore、Dataplorer、Hermes）、混合搜索（CE2）、交互范式（关键词查询翻译与分面搜索），最后落到一个可以运行的简化版 Facebook Graph Search 实战。

💡 核心导读

• 一条主线：语义搜索是信息检索（IR）与数据库（DB）两条技术路线在数据 Web（Data Web）上的合流——IR 贡献规模、鲁棒性与排序，DB 贡献结构化查询与精确匹配，二者从两端向中间靠拢。
• 两种检索观：文档检索（document retrieval）以关键词为查询模型、以词袋文档为数据模型、以统计匹配为匹配技术；数据检索（data retrieval）以结构化语句为查询模型、以 ER/RDF(S)/OWL 为数据模型、以精确模式匹配为匹配技术。
• 三个代表性系统：Semplore 把 RDF 转成虚拟文档复用倒排索引；Dataplorer 用结构索引做结构感知的两阶段匹配；Hermes 以 pay-as-you-go 方式完成多源知识融合与关键词搜索。
• 两类交互问题：关键词如何翻译成合取查询（本体映射 + 摘要图上的 Top-k 图探索），以及分面（facet）如何随结果集动态生成、计数与排序。
• 一个实战：以「实体」而不是「三元组」为索引单元，用 Python 标准库复刻简化版 FGS 的知识卡片、多跳查询与 AND/OR/NOT、范围条件检索，理解 Elasticsearch 中 bool、range、nested 查询背后的机制。

1. 什么是语义搜索：从文档检索到数据检索

1.1 检索三要素：查询模型、数据模型、匹配技术

课件给「搜索」下了一个中立的定义：搜索是一个从信息需求（information need）出发、在信息系统中找到满足需求的信息资源的过程。任何一个搜索系统都可以拆成三个要素来审视：

传统 Web 搜索是文档检索：不懂网页结构也能拿到按相关度排序的文档列表，还支持主题检索（topic search，借助 LDA 这类主题模型把文档聚成主题再匹配）。数据库与知识库做数据检索：查询是良构的结构化语句、返回精确答案（一张表、一组绑定），但前提是用户知道数据源、schema 与查询语言。语义搜索要回答的核心问题是：能不能像 Web 搜索一样简单地提问，又像数据库一样精确地拿到数据？

1.2 语义模型：语言学模型与概念模型

「语义」从哪里来？课件区分了两类语义模型。

第一类是语言学模型（linguistic model），在词与词之间组织语义关系，又分两种典型资源：分类体系 taxonomies（以上下位 is-a 关系为骨架，用于查询的泛化与特化）与同义词词库 thesauri（以同义/近义关系为核心，代表是 WordNet 的同义词集 synset 网络，以及把 WordNet 与 Wikipedia 多语种对齐的 BabelNet）。检索时借此做查询扩展与归一：输入「automobile」可匹配「car」，输入「狗」可泛化到「食肉目」或特化到「金毛寻回犬」。

第二类是概念模型（conceptual model）：它定义一个解释（interpretation），把查询中的语法元素（词）映射到论域（domain of discourse，即知识库所描述的世界）中的概念、个体与属性——这正是 RDFS/OWL 本体的角色：词项经本体词汇指向图中的类、实体和关系。

这里有一对贯穿全章的矛盾：表达能力（expressivity）与形式化程度（formality）。形式化越高（如 OWL DL 这类建立在可判定描述逻辑上的子集），解析过程越可计算（computable）、语义越精确，但对用户和数据的要求越苛刻；要注意 OWL Full 表达力最强却不可判定、不保证可计算。语言学资源轻量、鲁棒，却只能提供近似语义。各种语义搜索方案本质上都是在这根坐标轴上选位置。

1.3 重量级与轻量级两条路线

按「语义放在哪一层」，课件把语义搜索分成两大类：

重量级路线「语义精确但门槛高、扩展性受挑战」；轻量级路线「保留了 IR 的规模与容错，但语义是近似的」。本章的 Semplore 是轻量级路线的极致——用 IR 的倒排索引去支撑结构化查询；Dataplorer 作为原生存储代表，试图在一套引擎里把 IR 与 DB 两条路线的优点合起来，而 Hermes 并不属于原生存储，它是面向多源异构场景的 pay-as-you-go 数据 Web 搜索/整合框架（第 2.5 节）。

1.4 语义搜索的通用流程

课件给出的语义搜索通用流水线可以画成下面的样子：

用户需求
  │  查询构建 query construction（关键词 / 表单 / 自然语言 / 形式化语言）
  ▼
查询处理 query processing ── IR 风格：倒排匹配、打分
  │                        ── DB 风格：选择、连接
  │                        ── KB 风格：推理、子图匹配
  ▼
结果展示 result presentation（排序列表 / 知识卡片 / 分面 / 建议）
  │
  └── 反馈回路：隐式反馈（点击、停留）、显式反馈（评分）、激励机制（incentive）
横切关注点：文档表示 / 知识表示、语义模型、查询优化

两个工程细节：反馈分隐式与显式，点击、停留等隐式反馈才是主力，知识库质量靠激励机制（incentive，如付费维护分类目录）维持；「do you mean」纠错与相关搜索则在处理需求的不确定性。

1.5 数据 Web 搜索的三大难点

关联数据（Linked Data）把海量 RDF 知识库发布到 Web 后，传统 Web 搜索技术不能直接照搬，课件总结三大难点：

1. 可扩展性 scalability：三元组以十亿、千亿计（LOD 在 2007 年 5 月约五亿条，2011 年已数百亿），用户却要求亚秒响应，存储、索引、查询处理都要重设计。
2. 异构性 heterogeneity：各源 schema 不同，整合需两层对齐——模式层（schema-level）即本体匹配（ontology matching），数据层（data-level）即实体对齐（entity alignment/实体消解）。
3. 不确定性 uncertainty：需求往往不完整、模糊，如「Find action films directed by some Hong Kong film director and starring Chinese martial actors」没有一个实体名、全是概念约束；系统必须支持部分匹配（partial match）、结果排序与查询建议补全，而非简单返回「查无此项」。

课件同时指出文档 Web 搜索与数据 Web 搜索正在趋同：技术上搜索引擎吸收数据库的结构化能力（知识面板、实体检索），数据库吸收 IR 的排序与容错；数据上文档挂接实体、实体挂接文本，边界日益模糊。语义搜索正是 IR 与 DB 融合的焦点。

1.6 早期系统谱系与三元组存储的三条路线

进入具体系统前先建立谱系图：本体搜索（ontology search）有 Swoogle（UMBC）、Watson（英国开放大学 KMI，注意与 IBM 的 Watson 问答系统同名但无关），爬取并检索网上的本体文档；实体搜索（entity search）有 Sigma on Sindice（DERI）、FalconS（瞿裕忠团队，支持中文），按关键词检索 RDF 实体；数据 Web 搜索（data web search）有 SWSE（DERI）、Hermes（又名 SearchWebDB），直接在多源 RDF 上做关键词搜索与整合。支撑这些系统的三元组存储有三条技术路线：

Semplore、Dataplorer、Hermes 正是这张表上的三个主角，下一节逐个拆解。

2. 语义数据搜索：倒排索引、结构索引与按需整合

2.1 Semplore：把 RDF 三元组变成「虚拟文档」

Semplore（IBM 中国研究院与上海交通大学合作的工作）的核心想法非常讨巧：不重新发明存储引擎，而是把 RDF 数据转成 IR 索引能吃的形式，复用成熟的倒排索引。先回顾倒排索引四概念：文档 document 是检索单元；字段 field 是文档内分区（title/abstract/body，权重不同，分数按字段加权聚合，即多字段加权检索）；词项 term 是字段内索引词；每个词项对应一条倒排记录表 posting list（配合位置表 position list），按文档 id 升序排列，构成升序整数流（Ascending Integer Stream，AIS）。

Semplore 为每个实体构造一篇虚拟文档（virtual document），按实体在三元组中的位置映射字段：(s, rdf:type, C) 进入主体 s 的 type 字段；(s, p, o) 且 o 为字面量时进入 s 的 text 字段；关系三元组中，作为发出方的主体 s 的 subjOf 字段记录谓词 p（即”是哪个谓词的主语”）。注意课件 Page 24 的 Term index 只列出 type、text、subjOf 三个字段，并无 objOf。以课件 Page 24 为例：(Jackee_Chan, rdf:type, ChineseActor)、(Jackee_Chan, rdfs:comment, martial)、(Heart_of_Dragon, starring, Jackee_Chan) 会让 (type, ChineseActor) 包含 Jackee_Chan 与 Jet_Li、(text, martial) 落在 Jackee_Chan 的虚拟文档里、(subjOf, starring) 包含 Heart_of_Dragon 与 Hitman_(1988)。下面的代码完整实现虚拟文档构造、倒排索引与 AIS 基本操作：

# 代码块1：把 RDF 三元组转成「虚拟文档」，用 IR 倒排索引支持语义数据检索（Semplore/Dataplorer 思路）
# 只用标准库：每个实体是一篇虚拟文档，字段 field 取自三元组中实体的位置（type/text/subjOf；与课件 Page24 一致，不建 objOf）
from collections import defaultdict

# ---- 1. 内联样例三元组（主体, 谓词, 客体），对应课件 Page24/Page32 的电影域示例 ----
TRIPLES = [
    ("Jackee_Chan", "rdf:type", "ChineseActor"),
    ("Jet_Li", "rdf:type", "ChineseActor"),
    ("Donnie", "rdf:type", "ChineseActor"),
    ("Jackee_Chan", "rdfs:comment", "martial"),      # 文本描述：武术
    ("Heart_of_Dragon", "rdf:type", "ActionFilm"),   # 动作片
    ("Hitman_1988", "rdf:type", "ActionFilm"),
    ("Heart_of_Dragon", "starring", "Jackee_Chan"),
    ("Hitman_1988", "starring", "Jet_Li"),
    ("Heart_of_Dragon", "director", "Sammo_Hung"),
    ("Sammo_Hung", "rdf:type", "HongKongFilmDirector"),
]

# 给每个实体分配一个整数 id（AIS = Ascending Integer Stream，要求 id 升序）
ENTITIES = sorted({s for s, _, _ in TRIPLES} | {o for _, _, o in TRIPLES})
ID = {e: i for i, e in enumerate(ENTITIES)}

# ---- 2. 核心想法：三元组 -> 虚拟文档的 (field, term) ----
# (field, term) -> 升序 posting list（实体 id 列表，即一条 AIS）
inverted = defaultdict(list)

def add(field, term, entity):
    """向倒排索引登记：实体 entity 的 field 字段出现词项 term"""
    i = ID[entity]
    if i not in inverted[(field, term)]:
        inverted[(field, term)].append(i)

for s, p, o in TRIPLES:
    if p == "rdf:type":
        add("type", o, s)          # 主体的类型：(type, ChineseActor)
    elif p == "rdfs:comment":
        add("text", o, s)          # 字面量描述进入 text 字段
    else:
        add("subjOf", p, s)        # 主体 s 作为关系 p 的发出方（课件 Page24 仅索引 subjOf）

for key in inverted:              # 入库后统一排序，保证 AIS 升序
    inverted[key].sort()

def name(i):
    return ENTITIES[i]

# ---- 3. AIS 四种基本操作之三：基础检索 / 归并 / 关系扩展 ----
def basic(field, term):
    """基础检索 (f, t)：从倒排索引取出 posting list"""
    return sorted(inverted.get((field, term), []))

def merge(op, s1, s2):
    """归并 m(S1, op, S2)：两条升序 AIS 的交/并/差（双指针，线性时间）"""
    s1, s2, out, i, j = sorted(s1), sorted(s2), [], 0, 0
    if op == "and":
        while i < len(s1) and j < len(s2):
            if s1[i] == s2[j]:
                out.append(s1[i]); i += 1; j += 1
            elif s1[i] < s2[j]:
                i += 1
            else:
                j += 1
    elif op == "or":
        while i < len(s1) and j < len(s2):
            if s1[i] == s2[j]:
                out.append(s1[i]); i += 1; j += 1
            elif s1[i] < s2[j]:
                out.append(s1[i]); i += 1
            else:
                out.append(s2[j]); j += 1
        out += s1[i:] + s2[j:]
    elif op == "minus":
        while i < len(s1) and j < len(s2):
            if s1[i] == s2[j]:
                i += 1; j += 1
            elif s1[i] < s2[j]:
                out.append(s1[i]); i += 1
            else:
                j += 1
        out += s1[i:]
    return out

def expand(stream, pred, direction):
    """关系扩展 ⋈：沿关系 pred 从一组实体走到对端实体
    direction='obj->subj'：给出客体集合，反查主体（如演员 -> 他主演的电影）
    direction='subj->obj'：给出主体集合，正查客体（如电影 -> 导演）"""
    out = set()
    for s, p, o in TRIPLES:
        if p != pred:
            continue
        if direction == "obj->subj" and ID[o] in stream:
            out.add(ID[s])
        if direction == "subj->obj" and ID[s] in stream:
            out.add(ID[o])
    return sorted(out)

def concept(*parts):
    """概念表达式计算 λ(C)：如 λ(ChineseActor ⊓ 'martial')，每个 part 是一条 AIS"""
    stream = list(parts[0])
    for nxt in parts[1:]:
        stream = merge("and", stream, nxt)
    return stream

# ---- 4. 用深度优先遍历查询图，回答复杂查询 ----
# 查询（课件 Page32）：找到「动作片」，主演是「会武术(martial)的中国演员」，且导演是「香港电影导演」
print("== 基础检索 ==")
print("(type, ChineseActor) ->", [name(i) for i in basic("type", "ChineseActor")])
print("(text, martial)      ->", [name(i) for i in basic("text", "martial")])

print("\n== 概念表达式 λ(ChineseActor ⊓ 'martial') ==")
actors = concept(basic("type", "ChineseActor"), basic("text", "martial"))
print("会武术的中国演员 ->", [name(i) for i in actors])

print("\n== 深度优先遍历查询图 ==")
# x1 = ChineseActor ⊓ martial；x0 = 动作片 且 starring x1；x2 = x0 的导演且为香港导演
films_starring = expand(actors, "starring", "obj->subj")
x0 = merge("and", films_starring, basic("type", "ActionFilm"))
print("x1 演员主演的动作片 x0 ->", [name(i) for i in x0])
directors = expand(x0, "director", "subj->obj")
x2 = merge("and", directors, basic("type", "HongKongFilmDirector"))
print("这些影片的香港导演 x2 ->", [name(i) for i in x2])
print("\n最终答案（影片, 主演, 导演）：")
for f in [name(i) for i in x0]:
    star = [name(i) for i in expand([ID[f]], "starring", "subj->obj")]
    dire = [name(i) for i in expand([ID[f]], "director", "subj->obj")]
    print(f"  {f} <- starring {star} <- director {dire}")

运行结果：

== 基础检索 ==
(type, ChineseActor) -> ['Donnie', 'Jackee_Chan', 'Jet_Li']
(text, martial)      -> ['Jackee_Chan']

== 概念表达式 λ(ChineseActor ⊓ 'martial') ==
会武术的中国演员 -> ['Jackee_Chan']

== 深度优先遍历查询图 ==
x1 演员主演的动作片 x0 -> ['Heart_of_Dragon']
这些影片的香港导演 x2 -> ['Sammo_Hung']

最终答案（影片, 主演, 导演）：
  Heart_of_Dragon <- starring ['Jackee_Chan'] <- director ['Sammo_Hung']

这段代码对应课件定义的 AIS 四种基本操作：基础检索 (f, t) 取字段 f 含词项 t 的 posting list；归并 m(S1, op, S2) 对两条升序流做双指针线性交/并/差，对应布尔 AND/OR/NOT；概念表达式计算 λ(C)（如 λ(ChineseActor ⊓ "martial")）把类型流与文本流交归并；关系扩展 ⋈(S1, R, S2) 沿关系 R 在两组实体间连接（演员反查电影、电影正查导演）。复杂查询表示为查询图（变量 x0/x1/x2 与连接边），系统对查询图做深度优先遍历：每访问一个变量节点执行一次 AIS 操作、边对应关系扩展，逐步收窄绑定流——这就是「用倒排索引做数据库式 select/join」的秘密。

2.2 增量索引：基于块的索引扩展

LOD 数据持续增长，全量重建倒排索引不可行，而 posting list 连续存放，插入一个元素可能移动大量后续元素。Semplore 用基于块的索引扩展（block-based index expansion）解决：把 posting list 切成块（block），更新以块为单位移动并预留空间。块大小是三方权衡：块越小更新移动越少，但检索时随机 IO 增多、搜索变慢，块级元数据也更占空间。课件用索引构建时间、更新时间、索引大小三组对比说明：必须在更新时间、搜索时间、索引空间之间折衷，没有单点最优。

2.3 结构化查询效率与排序三原则

结构化查询按复杂度分五类（QC1-QC5）：QC1 纯类型；QC2 类型间连接；QC3 类型加一元谓词（属性约束）；QC4 连接加一元谓词；QC5 最复杂的组合查询。在 LUBM(1000) 与 DBpedia 上对比 Dataplorer、RDF-3X、DB2 SOR（含冷启动 cold）的响应时间，得到三结论：缓存大幅提效；查询优化显著缩短响应；效率与表达式复杂度存在折衷——查询图越复杂，归并与关系扩展的趟数越多。

光返回结果还不够，IR 的灵魂是排序，课件给出三条原则：质量传播 quality propagation——元素分数同时反映邻居质量（查与「战争」相关的总统接班人时，肯尼迪本人关联很弱，但前任艾森豪威尔是二战统帅，沿「接班」边传播后肯尼迪应靠前）；数量聚合 quantity aggregation——合格邻居越多排名越高（查「图灵奖得主工作的机构」时，CMU、UC Berkeley、IBM 因得主最多而居前）；单调性 monotonicity——证据不断并入时分数只升不降，这是提前终止与 top-k 算法正确性的前提。

落地时 Semplore 给每条 AIS 配一条打分流，成为 SAIS（Scored AIS）：词项对文档的检索状态值 RSV(t,d) 用 TF-IDF 计算并归一化到 [0,1]，归并按概率论规则组合分数；查「主演了最多著名武术演员的电影」时，Heart of Dragon 因连接的高质量武术演员最多而排第一。下面的代码演示质量传播、数量聚合与单调性：

# 代码块2：语义搜索的两条排序原则——质量传播、数量聚合，并验证单调性
# 只用标准库；打分在 [0,1] 区间，沿边传播一次后与原分取 max（保证单调）
from collections import defaultdict

# ---- 1. 质量传播（quality propagation）：元素分数同时反映邻居的质量 ----
# 课件例子：查与关键词「战争」相关的美国总统接班人，肯尼迪应靠前，
# 因为他的前任艾森豪威尔（二战盟军统帅）与「战争」高度相关。
edges = {  # successor -> predecessor（谁接班谁）
    "Kennedy": "Eisenhower",
    "Johnson": "Kennedy",
}
base_score = {"Eisenhower": 0.95, "Kennedy": 0.10, "Johnson": 0.05}  # 与「战争」的初始相关分

def quality_propagation(base, edges, decay=0.8):
    """每个节点继承前驱质量：新分 = max(自身分, decay * 前驱分)，沿传播链迭代到收敛"""
    score = dict(base)
    for _ in range(len(score)):  # 链长不超过节点数
        changed = False
        for node, pred in edges.items():
            cand = decay * score[pred]
            if cand > score[node]:
                score[node] = round(cand, 4); changed = True
        if not changed:
            break
    return score

prop = quality_propagation(base_score, edges)
print("== 质量传播：关键词「战争」下的总统排序 ==")
for person, sc in sorted(prop.items(), key=lambda kv: -kv[1]):
    print(f"  {person:<12} score={sc}")
print("  -> 肯尼迪自身分仅 0.10，经前任艾森豪威尔(0.95)传播后升至", prop["Kennedy"])

# ---- 2. 数量聚合（quantity aggregation）：邻居越多、排名越高 ----
# 课件例子：查「图灵奖获得者工作的机构」，CMU、UC Berkeley、IBM 因图灵奖得主最多而居前
winners_at = {
    "CMU": ["Newell", "Simon", "Perlis"],          # 3 位
    "UC_Berkeley": ["Gray", "Thacker", "Lampson"],   # 3 位（示意数据）
    "IBM": ["Codd", "Sammet", "Backus"],           # 3 位
    "Stanford": ["Floyd"],                         # 1 位
}
# 给每位得主一个质量分（示意：均为 1.0），机构分 = 邻居数量聚合（归一化）
raw = {org: float(len(w)) for org, w in winners_at.items()}
top = max(raw.values())
quantity = {org: round(raw[org] / top, 4) for org in raw}
print("\n== 数量聚合：图灵奖得主所在机构排序 ==")
for org, sc in sorted(quantity.items(), key=lambda kv: (-kv[1], kv[0])):
    print(f"  {org:<14} winners={len(winners_at[org])}  score={sc}")

# ---- 3. 单调性（monotonicity）：合并更多匹配证据时，分数只能上升不能下降 ----
def merge_scores(old, new):
    """SAIS 归并时的组合函数：逐元素取 max，保证单调"""
    keys = set(old) | set(new)
    return {k: round(max(old.get(k, 0.0), new.get(k, 0.0)), 4) for k in keys}

before = dict(base_score)
after = merge_scores(before, prop)
monotonic = all(after[k] >= before[k] for k in before)
print("\n== 单调性检验 ==")
print("  归并传播分后所有节点分数不减：", monotonic)
print("  Kennedy:", before["Kennedy"], "->", after["Kennedy"], "｜Johnson:", before["Johnson"], "->", after["Johnson"])

运行结果：

== 质量传播：关键词「战争」下的总统排序 ==
  Eisenhower   score=0.95
  Kennedy      score=0.76
  Johnson      score=0.608
  -> 肯尼迪自身分仅 0.10，经前任艾森豪威尔(0.95)传播后升至 0.76

== 数量聚合：图灵奖得主所在机构排序 ==
  CMU            winners=3  score=1.0
  IBM            winners=3  score=1.0
  UC_Berkeley    winners=3  score=1.0
  Stanford       winners=1  score=0.3333

== 单调性检验 ==
  归并传播分后所有节点分数不减： True
  Kennedy: 0.1 -> 0.76 ｜Johnson: 0.05 -> 0.608

2.4 Dataplorer：结构感知的分区与两阶段匹配

纯倒排索引回答「包含某词项的实体」很快，但回答结构化 select/join 时要对大量 posting list 做 union 与归并，IO 与连接次数随规模膨胀。Dataplorer（原生存储路线代表）引入结构索引（structure index）：图中大量节点结构地位相同，把它们归到一起。课件 Page 42 明确：结构索引由扩展（extensions）——即结构等价节点构成的类/分区——以及分区之间的关系组成；同一扩展内的资源具有相同的结构，即具有相同的（传入和传出）路径。两个节点是否同处一个扩展，用互模拟（bisimulation）判定：它要求双向一致——对某节点每条带标签的出边（沿原图走），对方都有同标签出边、到达的目标仍属同一扩展；同时对它每条带标签的入边（沿逆图走，即把边反向），对方也都有同标签入边、来源仍属同一扩展；该要求递归成立（既保持后继结构、又对齐”谁指向它”，比”接受相同路径标签集合”的语言等价更强）。结构索引就是这些扩展分区构成的一张小图，保留结构骨架、规模小几个数量级。

查询处理变成两阶段匹配（two-phase matching）：先在答案空间（answer space）用结构索引匹配查询图结构、圈定候选分区；再在资源空间（resource space）验证常量与标识变量（distinguished variable，SELECT 要输出的变量），把非标识变量构成的树形部分整体剪枝（它们只起连接作用），从而同时降低 IO 与 union/join 次数。课件对比结构分区（SP）与垂直分区（VP，按谓词切表）：复杂查询 SP 快 8 到 9 倍，简单查询 SP 略慢；查询过于复杂时结构索引匹配开销反超——效率与表达能力的折衷再次出现。

2.5 Hermes：pay-as-you-go 的数据 Web 搜索

Hermes（又名 SearchWebDB）面对多源异构场景：图灵奖信息在 DBpedia、雇员关系在 Freebase、个人主页在 FOAF、文献在 DBLP，要回答「Find articles from Turing Award winners at Stanford University」必须先整合再搜索。它主张 pay-as-you-go（按需付费式）整合：不追求一开始就完美对齐，而是随使用逐步加深。系统分两半：离线整合建立模式层映射（schema-level，本体/类/属性对齐）与数据层映射（data-level，实体对齐）；在线处理做关键词翻译、搜索与逐步精化。

离线核心是知识融合（knowledge fusion），挑战在效率、增量整合与运行时整合。课件 Page 50 称之为「两阶段知识融合」，落到实现上展开为索引、分块、聚类三个环节，其中真正做融合的核心两阶段是分块与聚类，索引负责前置的特征抽取：

1. 索引 indexing（前置特征抽取）：为每个实体抽取基本特征（basic features，字面属性值，如名字、标题）与扩展特征（extended features，邻居构成的关系特征）。
2. 分块 blocking（融合阶段一）：两两比较全部实体是 O(n²)，不可行；观察是共享稀有特征的两个实体更可能同指，稀有性用文档频率（document frequency）衡量（完整邮箱比「男/女」区分度高得多）。按稀有度排序特征，每个保留的倒排表就是一个块（block），只在块内两两比较；实测 125 万实体分块约 10 分钟。
3. 聚类 clustering（融合阶段二）：块内用相似度（如 Jaccard 系数）合并同指实体，准则为紧致集合（Compact Set，成员互为最近邻）与稀疏邻居（Sparse Neighborhood）。聚类复杂度高达 O(n³)，但分块把块内实体压到 500 以下后单块不到 16 秒；对照之下不分块时 1700 个实体就要 10 分钟。

在线跨源连接优先用 map join（直接查预计算的实体映射做替换，代价相当于一次本地关系扩展），而非运行时算相似度的 similarity join。预处理规模：单机（双核 3GHz、8GB 内存）处理 12 亿条三元组，产出 200 万条数据映射、1500 条模式映射。

3. 混合搜索：IR 与数据库的轻量级集成

3.1 下一代语义搜索系统与混合数据模型

课件把「结合统计 IR 排序、数据库索引与查询处理、推理技术」的系统称为下一代语义搜索系统，三特征是：结合文本/结构化/语义数据；整体管理异构资源；把文档与数据作为信息单元集成检索——即混合搜索（hybrid search）。其数据模型（Page 63）是「两部分加一座桥」：实体-关系图（类型、关系、属性）加文档（属性-值半结构、超链接），桥是实体链接/语义标注（entity linking / semantic annotation），把文档中提到的人名、机构名链接到图中实体。于是关键词与结构约束可出现在同一条查询里，如 {?x surname "Wang"; ?x type Researcher} 加关键词「apex incremental query」：先按结构锁定王姓研究员，再要求其相关文档提到增量查询技术。

3.2 CE2：资源图、原子查询分解与答案合并

CE2 是 IBM 中国研究院提出的轻量级 DB+IR 集成方案，不改引擎内核、只在其上做查询分解与合并。统一抽象是资源图（resource graph）：数据（查询）图（概念/个体/变量节点、关系边与属性边）+ 文档（查询）图（文档概念节点、超链接、关键词）+ 连接两图的标注 annotation 桥边。架构分线下线上：线下数据图存入 DBMS，但 (个体, 关键词, "xxx") 这类文本三元组单独放入实体索引 EntIdx，文档图入 DocIdx，标注入 AnnIdx；线上混合查询先分解为若干原子查询（atomic query）下发 DBMS 或 IR 引擎，再按查询树合并、排序，中间结果存入出现概率表 OPT（Occurrence Probability Table）避免重复计算。

四类原子查询与执行引擎的对应关系如下：

课件用「Richard Karp、IBM、Turing Award」例子展示答案合并三算子：关键字连接（keyword join）合并实体子查询；混合连接（hybrid join）以标注为桥连接实体与文档子查询；排序投影（rank projection）消去文档节点与无关变量，只保留目标变量及融合排序分。

3.3 实验结论与原生混合搜索的挑战

评测用四组查询集：QS1（500 个纯关键词）、QS2（1242 个带类型约束的结构化查询）、QS3（287 个含单关系的混合查询）、QS4（10 用户 20 查询的人工评测）。效果上按 P-R 曲线与 P@N，CE2 优于「DB2 + Text Extender」与纯 Lucene（同时利用结构约束与排序原则）；效率上带排序（ranking）与不带排序（no ranking）的耗时差距则因系统而异——Semplore 的差距很小，因为它直接在原生倒排索引上支持排序，排序几乎不增加额外成本；CE2 的差距比较大，因为 annotation/mapping 这类关系产生的实例（instance）极多，处理这种实例量庞大的特殊关系需要额外特殊处理。课件最后指出原生混合搜索（native hybrid search）还要啃三块硬骨头：可扩展混合存储模型；内建混合连接算子（top-k 混合连接、模糊混合连接，让结构化连接与关键词相似度连接在引擎内一次完成）；统一混合排序模型（IR 排序、DB 排序及二者集成）。

3.4 语义搜索路线图：三个阶段

课件 Page 109 用一张路线图把本章系统串成三级阶梯，箭头明确标注 From Dataplorer To Hermes，三级以能力命名（按 Page 22 分类，Semplore 与 Dataplorer 同属第一级三元组存储，CE2 是第二级混合语义搜索引擎的代表），建议记牢：

每个阶段都可以再划成离线（offline）与在线（online）两半：离线负责建索引、做融合、生成摘要；在线负责解析查询、执行匹配、产出排序与分面。

4. 交互范式：关键词如何变成结构化查询，分面如何动态生成

4.1 可用性与五种交互范式

课件强调这里的关键词是可用性（usability），不是系统在线率意义上的 availability。高效搜索数据 Web 原本要求用户知道数据源、schema、数据内容与查询语言四件事，普通用户一样都不知道，界面必须直观、透明。课件归纳五种交互范式（interaction paradigm）：

表达能力与直观性天然矛盾。早期有两类做法：一是把关键词翻译成 XML、SQL 等结构化查询，难点在于如何让用户使用复杂结构；二是把关键词转化为基于本体的查询，但基于模板的机制缺乏灵活性——具有两个以上关键词的查询就需要大量模板、组合爆炸。主流选择是后者，即把关键词翻译成本体上的合取查询（conjunctive query），下面分别讲「查询翻译」与「分面」两种课件给出明确结论的交互方式。

4.2 基于本体的关键词查询解释：三步法

课件给出把关键词翻译成结构化查询的通用三步法。

第一步：问题元素到本体元素的映射。 本体元素（ontology element）是六类元素的不相交并集：个体、数据值、概念（类）、数据范围、对象属性、数据属性。映射必须健壮（robust matching）：容忍句法变体（时态、单复数）与拼写变体，手段是本体元素索引 + 模糊搜索 + 句法相似性。

第二步：递归遍历知识库，探索元素间的连接。 映射到的元素往往分散在图上，需沿边递归遍历找出连接子图；背后假设是「本体-心智对应（Ontology-Mental Correspondence）」：几个词圈定的需求在图上对应一个彼此邻近的连通结构。

第三步：从连接子图导出系统查询。 关键词被解释为项的合取（conjunction of terms，概念 C、角色 R、变量或个体 x/y）；知识库分 TBox（术语公理，schema 层）与 ABox（断言，数据层）。匹配到概念的顶点映射为变量并加概念成员约束 e(x, c)（即 ?x rdf:type C）；匹配到个体或数据值的顶点映射为常量，加属性成员约束 e(x, y)。

以课件 Page 78 经典例子「Cimiano X-Media publications」为例：Cimiano 映射为个体（研究员），X-Media 映射为个体（项目），publications 映射为概念 Publication；连接是 Publication 经 author 连 Researcher、经 hasProject 连 Project，得到合取查询 Publication(?x) ∧ author(?x, Cimiano) ∧ hasProject(?x, X-Media)——注意 Cimiano、X-Media 映射为个体常量、不加概念成员约束，只有待求的 ?x 加 Publication 类型（与课件 Page 78 一致），即下面这条 SPARQL：

PREFIX : <http://example.org/kg81#>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT ?pub WHERE {
  ?pub rdf:type :Publication .
  ?pub :author :cimiano .
  ?pub :hasProject :xmedia .
}

多个连接子图都成立时如何排序？课件给出局部性假设（locality assumption）：连接路径越短越可能符合意图，度量取连接图最长路径长度（直径），越短越靠前。

4.3 Top-k 关键词查询：摘要图、代价导向探索与多源扩展

三步法只回答「能不能翻译」，没解决效率：在十亿级原图上枚举连通子图不可行。Top-k 关键词查询框架同样分离线与在线：离线做图摘要（summarization）、评分与术语扩展，产出图索引（graph index）与关键词索引（keyword index）。摘要图（summary graph）复用结构索引思想：一条 SPARQL 除实体与边上约束外大量内容来自 schema，用互模拟或特征规则（characteristic rules，相当于一次 schema 生成）把原图压成只含类节点与类间关系的小图，查询图先在摘要图上生成模板、再实例化回原图；在线先做关键词映射并扩充（augmentation）成扩充摘要图，再做 Top-k 图探索（graph exploration）。

图探索是代价导向（cost-directed）的分支定界（branch-and-bound）过程：从每个关键词元素出发扩展路径，每步取当前代价（cost）最小的路径生长；一旦某路径把所有关键词连成一个连通结构（collection element），就构建为候选查询图入 Top-k 队列；由于代价单调递增，当第 k 名候选的代价已低于所有待扩展路径的最低可能代价时，剩余分支不可能更优，即提前终止（early termination）。

得到查询图后按 Page 87 规则映射为合取查询：值节点（value vertex）→常量 term；类节点（class vertex）→独特变量；类-值成员边（A-edge）→谓词 e[var, term]；类-类关系边（R-edge）→谓词 e[var1, var2]，最后翻译为 SPARQL。下面的代码在最小数据上实现「映射 → 摘要图 Top-k 探索 → SPARQL 生成」：

# 代码块3：关键词查询翻译——在摘要图上做代价导向的 Top-k 图探索，并映射为合取查询/SPARQL
# 对应课件 Page78-87 的三步法：关键词映射 -> 探索连接子图 -> 导出结构化查询
import heapq

# ---- 1. 数据层（ABox 断言）与模式层（TBox 摘要图），内联最小样例 ----
# 三元组：(主体, 谓词, 客体)
TRIPLES = [
    ("cimiano", "rdf:type", "Researcher"),
    ("tran", "rdf:type", "Researcher"),
    ("xmedia", "rdf:type", "Project"),
    ("pub1", "rdf:type", "Publication"),
    ("pub2", "rdf:type", "Publication"),
    ("pub1", "author", "cimiano"),
    ("pub2", "author", "tran"),
    ("pub1", "hasProject", "xmedia"),
    ("pub2", "hasProject", "xmedia"),
]
NAMES = {  # 实体/类的可读名，用于关键词模糊匹配
    "cimiano": "Philipp Cimiano", "tran": "Thanh Tran", "xmedia": "X-Media",
    "pub1": "Paper about X-Media by Cimiano", "pub2": "Paper about X-Media by Tran",
    "Researcher": "Researcher", "Project": "Project", "Publication": "publications",
}

def klass_of(entity):
    return next((o for s, p, o in TRIPLES if p == "rdf:type" and s == entity), None)

# 摘要图（schema 层）：类节点 + 类之间的关系边；探索时无向遍历，但保留三元组原始方向
CLASSES = sorted({o for s, p, o in TRIPLES if p == "rdf:type"})
schema_edges = set()   # 元素为有向模式 (主体类cs, 谓词p, 客体类co)
for s, p, o in TRIPLES:
    if p == "rdf:type":
        continue
    schema_edges.add((klass_of(s), p, klass_of(o)))

# ---- 2. 第一步：关键词 -> 本体元素映射（健壮匹配：忽略大小写的子串匹配 + 打分）----
def keyword_mapping(keyword):
    """返回 [(元素, 种类 class/value, 分数, 所属类)]，分数越高匹配越好"""
    kw = keyword.lower()
    hits = []
    for elem, label in NAMES.items():
        if kw in label.lower():
            if elem in CLASSES:
                hits.append((elem, "class", 0.9, elem))
            else:
                hits.append((elem, "value", 1.0, klass_of(elem)))
    return hits

def map_all(keywords):
    """每个关键词取最佳映射；value 锚定到它所属的类，并记录常量"""
    anchors, constants = {}, {}
    for kw in keywords:
        hits = keyword_mapping(kw)
        if not hits:
            continue
        elem, kind, score, cls = max(hits, key=lambda h: h[2])
        anchors[cls] = anchors.get(cls, 1.0) * score   # 映射分（越接近 1 越好）
        if kind == "value":
            constants[cls] = elem
    return anchors, constants

# ---- 3. 第二步：摘要图上代价导向的 Top-k 探索（分支定界 + 提前终止）----
def adj(c):
    """无向邻接：从类 c 出发可走到的相邻类；同时返回该边的有向三元组模式 (cs,p,co)"""
    out = []
    for (cs, p, co) in schema_edges:
        if cs == c:
            out.append((co, cs, p, co))   # 正向走到 co，模式保持 cs->p->co
        elif co == c:
            out.append((cs, cs, p, co))   # 逆向走到 cs，模式仍是 cs->p->co
    return out

def topk_explore(anchors, constants, k=3, edge_cost=1.0):
    """状态 = (当前代价, 当前类, 已连接锚点掩码, 走过的类间边列表)。
    代价 = 路径边数 * edge_cost + 映射惩罚(1 - 映射分)；代价单调递增，可分支定界。"""
    anchor_list = list(anchors)
    bit = {c: 1 << i for i, c in enumerate(anchor_list)}
    full = (1 << len(anchor_list)) - 1
    heap, best = [], []   # best 放完整候选（代价, 边集）
    for c in anchor_list:
        heapq.heappush(heap, (1.0 - anchors[c], c, bit[c], []))
    seen = {}
    while heap:
        cost, cur, mask, path = heapq.heappop(heap)
        # 分支定界：已有 k 个候选且当前最小扩展代价已不低于第 k 名候选代价 -> 提前终止
        if len(best) >= k and cost >= best[-1][0]:
            break
        if (cur, mask) in seen and seen[(cur, mask)] <= cost:
            continue
        seen[(cur, mask)] = cost
        if mask == full:
            heapq.heappush(best, (cost, tuple(path)))
            best.sort()
            continue
        for nxt, cs, pred, co in adj(cur):
            new_mask = mask | bit.get(nxt, 0)
            step = edge_cost
            if nxt in bit and not (mask & bit[nxt]):   # 新抵达一个锚点类：补计它的映射惩罚(1-映射分)
                step += 1.0 - anchors[nxt]
            heapq.heappush(heap, (cost + step, nxt, new_mask,
                                  path + [(cs, pred, co)]))
    return sorted(best)[:k]

# ---- 4. 第三步：查询图 -> 合取查询（SPARQL）----
def to_sparql(rank, path, constants):
    vars_ = {}
    def var_of(c):
        if c in constants:
            return ":" + constants[c]          # value vertex -> 常量 term
        if c not in vars_:                      # class vertex -> 独特变量
            base = {"Publication": "pub", "Researcher": "r", "Project": "p"}.get(c, "x")
            tag = base if ("?" + base) not in vars_.values() else base + str(len(vars_) + 1)
            vars_[c] = "?" + tag
        return vars_[c]
    lines = []
    for cs, pred, co in path:
        lines.append(f"  {var_of(cs)} :{pred} {var_of(co)} .")
    for c, tv in vars_.items():
        lines.append(f"  {tv} rdf:type :{c} .")
    head = next((tv for c, tv in vars_.items() if c == "Publication"), "?pub")
    body = "\n".join(dict.fromkeys(lines))     # 去重保序
    return f"# 候选 #{rank}（代价越小越优）\nSELECT {head} WHERE {{\n{body}\n}}"

# ---- 5. 跑一遍：课件原例 "Cimiano X-Media publications" ----
keywords = ["Cimiano", "X-Media", "publications"]
print("查询关键词：", keywords)
anchors, constants = map_all(keywords)
print("关键词映射：锚点类 =", anchors, "｜常量 =", constants)
candidates = topk_explore(anchors, constants, k=3)
# 不同探索顺序可能产生同一合取查询，按 SPARQL 主体去重后再排名
unique, seen_body = [], set()
for cost, path in candidates:
    body = tuple(sorted((cs, p, co) for cs, p, co in path))
    if body not in seen_body:
        seen_body.add(body)
        unique.append((cost, path))
print(f"\nTop-k 图探索得到 {len(unique)} 个不同的连接子图（分支定界后终止）：")
for rank, (cost, path) in enumerate(unique, 1):
    print(f"\n{to_sparql(rank, path, constants)}")
    print(f"# 代价={cost}（路径边数 {len(path)} + 映射惩罚），倒数排名 Reciprocal Rank = {1/rank}")

运行结果：

查询关键词： ['Cimiano', 'X-Media', 'publications']
关键词映射：锚点类 = {'Researcher': 1.0, 'Project': 1.0, 'Publication': 0.9} ｜常量 = {'Researcher': 'cimiano', 'Project': 'xmedia'}

Top-k 图探索得到 1 个不同的连接子图（分支定界后终止）：

# 候选 #1（代价越小越优）
SELECT ?pub WHERE {
  ?pub :author :cimiano .
  ?pub :hasProject :xmedia .
  ?pub rdf:type :Publication .
}
# 代价=2.1（路径边数 2 + 映射惩罚），倒数排名 Reciprocal Rank = 1.0

打分与评测：候选代价融合三因素——路径长度（越短越好）、关键词匹配分（越高越好）、元素流行性 popularity（越主流越可能是目标，可用类 PageRank 预计算）。评测除精度、召回率、P@N 外还有倒数排名 Reciprocal Rank = 1/r（正确翻译排第 r 位得 1/r），跨查询平均即 MRR（Mean Reciprocal Rank）。在 DBLP、12 用户 30 查询的实验中，三因素融合后 MRR 多数接近 1（正确翻译基本排第一）；效率上比双向 BFS 基线快至少一个数量级，与 METIS 等索引方法相当。

多数据源（联邦）扩展：关键词映射到多个知识库时，再加跨库映射分 mapping score 与数据源覆盖度项 data source coverage：课件 Page 94 代价公式为 Cgq = Σ 1/(Sn · coverage(gDi))，coverage 在分母中，单个数据源对查询图覆盖得越完整、代价越低（客观上倾向用更少而更全的数据源）；流行性改造成 EF-IDF（把 TF-IDF 的词频换成实体频率 entity frequency，统计实体在语义文档中的频次与长度）。五因素融合后，讲授中的时间剖析显示大部分耗时在关键词映射阶段，摘要图足够小、图构建与查询生成占比很低。

4.4 分面搜索：随结果集动态生成的「导航面板」

分面搜索（faceted search）是电商网站最熟悉的交互：搜出商品后，左侧出现品牌、价格、类别等分面（facet），每个分面列出可选值与计数（count），点击即精化（refine）查询，也可扩展（expansion）与导航（navigation），服务于用户一开始不知要搜什么、边看边收敛的探索式搜索（exploratory search）。电商分面是预定义的，但开放集成的知识库不可能预枚举分面。课件定义：分面由 RDF 三元组定义——分面是当前结果集资源上的属性（谓词），分面值是客体（如结果集是一些人，谓词 title 是分面，值「Dr.」是分面值）。

由此产生三个难题：如何即时生成相关分面、如何实时计算并聚类分面值、点击后结果集与分面如何联动重算。关键观察是：分面计算可转化为两个特殊的关系扩展——对结果集 D 做 subjectOf 扩展（取 D 中实体作为主体的出边谓词与客体）与 objectOf 扩展（D 中实体作为客体时反查主体），直接复用第 2 节的关系扩展索引。一次检索除结果外还要算类别分面、出边分面、入边分面，结构上是 3 趟关系扩展，因此口头上常说「分面时间约为结果的 3 倍」；但课件 Page 102 的实测表显示该比值并非恒定：QS1-QS4 的结果检索为 41/88/134/210 毫秒、分面为 535/429/401/356 毫秒，比值约为 13.0/4.9/3.0/1.7 倍——课件给出的直观结论是「差距越来越小」：从简单的纯关键词查询到复杂查询，分面相对结果检索的耗时倍数逐步下降。下面的代码实现分面的动态生成、计数与排序：

# 代码块4：分面搜索——根据当前结果集实时生成分面、统计分面值计数，并按「浏览能力」排序
# 分面 = 结果集资源的属性（谓词），分面值 = 客体；subjectOf/objectOf 本质是两次特殊的关系扩展
import math
from collections import defaultdict, Counter

# ---- 1. 内联样例：一组「运动员」实体的三元组（主体, 谓词, 客体）----
TRIPLES = [
    ("姚明", "rdf:type", "运动员"), ("姚明", "国籍", "中国"), ("姚明", "运动项目", "篮球"),
    ("姚明", "性别", "男"), ("叶莉", "rdf:type", "运动员"), ("叶莉", "国籍", "中国"),
    ("叶莉", "运动项目", "篮球"), ("叶莉", "性别", "女"),
    ("科比", "rdf:type", "运动员"), ("科比", "国籍", "美国"), ("科比", "运动项目", "篮球"),
    ("科比", "性别", "男"), ("梅西", "rdf:type", "运动员"), ("梅西", "国籍", "阿根廷"),
    ("梅西", "运动项目", "足球"), ("梅西", "性别", "男"),
    ("玛塔", "rdf:type", "运动员"), ("玛塔", "国籍", "巴西"), ("玛塔", "运动项目", "足球"),
    ("玛塔", "性别", "女"),
]

def compute_facets(result_set):
    """对结果集做一次 subjectOf 扩展：收集每个资源作为主体的全部 (谓词, 客体)"""
    facet_values = defaultdict(Counter)   # 谓词 -> Counter(值 -> 计数)
    for s, p, o in TRIPLES:
        if s in result_set and p != "rdf:type":
            facet_values[p][o] += 1
    return facet_values

def browsing_score(counter):
    """分面排序的启发式（浏览能力最大化）：值分布越均匀、非单一值，越能均等引导用户。
    用值计数的香农熵近似；熵越大，该分面把结果集切得越均衡。"""
    total = sum(counter.values())
    return -sum((c / total) * math.log2(c / total) for c in counter.values())

def show(result_set, title):
    print(f"\n== 结果集 {title}（{len(result_set)} 个资源）的动态分面 ==")
    facets = compute_facets(result_set)
    ranked = sorted(facets.items(), key=lambda kv: (-browsing_score(kv[1]), kv[0]))
    for pred, counter in ranked:
        vals = ", ".join(f"{v}×{n}" for v, n in counter.most_common())
        print(f"  分面 {pred:<6} 熵={browsing_score(counter):.3f}  值: {vals}")

# ---- 2. 初始结果集：全部运动员 ----
all_athletes = {s for s, p, o in TRIPLES if p == "rdf:type" and o == "运动员"}
show(all_athletes, "全部运动员")

# ---- 3. 用户点击分面值「运动项目=篮球」后，query 被精化（refine），结果集与分面联动重算 ----
basketball = {s for s in all_athletes
              if any(p == "运动项目" and o == "篮球" for x, p, o in TRIPLES if x == s)}
show(basketball, "精化：运动项目=篮球")

# ---- 4. 分面计算量与结果计算量的关系（结构趟数；实测墙钟比值见课件 Page102 表格）----
# 结果检索 = 1 趟关系扩展；分面要额外做 category 分面 + subjectOf 扩展 + objectOf 扩展，共 3 趟
result_passes = 1
facet_passes = 3   # category facets + subjectOf facets + objectOf facets
print(f"\n结果检索需 {result_passes} 趟关系扩展，分面需 {facet_passes} 趟（类别/出边/入边各一趟），"
      f"结构扫描趟数比 = {facet_passes / result_passes:.0f}；Page102 实测墙钟比值随查询复杂度从约13倍降到1.7倍")

运行结果：

== 结果集 全部运动员（5 个资源）的动态分面 ==
  分面 国籍     熵=1.922  值: 中国×2, 美国×1, 阿根廷×1, 巴西×1
  分面 性别     熵=0.971  值: 男×3, 女×2
  分面 运动项目   熵=0.971  值: 篮球×3, 足球×2

== 结果集 精化：运动项目=篮球（3 个资源）的动态分面 ==
  分面 国籍     熵=0.918  值: 中国×2, 美国×1
  分面 性别     熵=0.918  值: 男×2, 女×1
  分面 运动项目   熵=-0.000  值: 篮球×3

结果检索需 1 趟关系扩展，分面需 3 趟（类别/出边/入边各一趟），结构扫描趟数比 = 3；Page102 实测墙钟比值随查询复杂度从约13倍降到1.7倍

分面高级特性包括动态分面值（flat 字符串做值聚类、non-flat 值借类层次组织）、层次化分面（hierarchical）、区间分面（range）与动态值分区（dynamic value partitioning）。分面很多时还要排序与隐藏，原则是最大化浏览能力（browsing capability）：以小而均等的粒度引导用户（不能切得畸轻畸重），让用户每步用最少的必需知识选出下一个聚类、最终收敛到单个感兴趣的项；上面代码用香农熵近似这一原则——熵越高分布越均衡、越优先展示。

课件对交互范式的结论（Page 108）收敛为两件事：表达式关键字查询（本体解析、摘要图 Top-k 探索、映射扩展到多源）与动态分面计算（分面排序、动态值分区）。

5. 实战：用 Python 复刻简化版 Facebook Graph Search

5.1 FGS 背景与三层查询语言

Facebook Graph Search（FGS）让用户用自然语言检索公开的人、地点、照片等图谱数据（如「我附近朋友们常去的餐馆」），查询处理分三层语言：自然语言（表层句子）→ 语义语言（预定义语法的中间表示，由实体识别、链接、消解产出）→ s-表达式（s-expression）（检索条件的交、并、差组合，落到倒排索引执行）。

以「friends in San Francisco」为例：实体识别与链接把 San Francisco 链到城市实体 id 23692（歧义时按「共同朋友最多」等上下文准则消解）；语义层得到 intersect(friend(me), residents(23692))；s-表达式层变为 (and friend:767560056 city_to_user:23692)。优化器生成多个候选解释、按概率排序让用户挑选。

5.2 Demo 的四类功能

课件实践实现四类由浅入深的查询：①实体查询，输入实体名返回知识卡片（全部属性）；②实体:属性，单跳取属性值（如「姚明:身高」）；③多跳查询 实体:属性1:属性2...（如「姚明:女儿:母亲:身高」，每跳属性值作为下一跳实体）；④多属性条件检索，给定属性条件反查实体，支持 AND/OR/NOT 与 =, >, <, >=, <=（如「篮球或足球运动员、非中国国籍、身高 180 以上」）。

5.3 索引设计：为什么以「实体」为索引单元

最关键的设计决策：不是一个三元组一个文档，而是一个实体的全部属性值对组成一篇文档（实体虚拟文档）。以三元组为文档时多条件联合检索要跨大量文档连接、效率低；以实体为文档时联合条件在同一篇文档内完成，与第 2 节 Semplore 虚拟文档思想一脉相承。字段类型再区分：height、weight 这类需范围比较的属性抽成 integer 独立字段（支持 range）；其余属性种类多、取值稀疏，统一用不分词、精确匹配的 keyword 类型，放进名为 po 的 nested object 列表，每个元素是一个 {pred, obj} 属性值对。

5.4 数据预处理、入库与同义词扩展

入库前预处理：清理无关字符；height/weight 统一量纲（厘米、公斤）；多值属性拆成多个属性值对；转成 JSON。原课用 Elasticsearch（Lucene 系分布式搜索引擎）：mapping 文件声明 index/type（demo/person）与字段类型，insert API 批量写入。查询侧做属性同义词扩展（「体重/重量/多重」→weight、「身高/多高」→height）：这发生在查询解析阶段，是属性名（字段名）映射，与 ES 分析器里作用于字段值 token 的 synonym filter 机制不同，只是借鉴了同义词扩展的思想；同义词资源可用 HowNet（知网）、同义词词林、Wikipedia、BabelNet。

5.5 查询解析与构造

三类查询分别解析：实体/属性查询用 term 匹配 subj 命中实体再取属性值；多跳查询循环解析、上一跳属性值作为下一跳实体；多 PO 条件逐条件解析为 (pred, op, obj)——height/weight 生成 range（gte/lte），其余生成 nested 内 term 精确匹配；布尔语义对应 ES bool（AND→must、OR→should、NOT→must_not），相邻 OR 先合并成 should 组再用 AND 串接 must/must_not；先做查询分类（按操作符切分后判断首词是否属性名）再走对应分支。

下面用 Python 标准库完整复刻这套机制（无需安装 Elasticsearch，概念与 ES 的 mapping/bool/range/nested 一一对应）：

# 代码块5：简化版 Facebook Graph Search（FGS）——以「实体」为索引单元的纯 Python 实现
# 复刻课件实践的核心机制：一个实体的全部属性值对组成一篇虚拟文档；
# height/weight 为整数字段（支持范围检索），其余属性进入 po 列表（精确匹配，等价 ES 的 nested object）
import re

# ---- 1. 数据预处理后的实体文档（多值属性已拆成多个 {pred,obj}，身高体重统一为 cm/kg 整数）----
DOCS = [
    {"subj": "姚明", "height": 226, "weight": 140, "po": [
        {"pred": "国籍", "obj": "中国"}, {"pred": "职业", "obj": "篮球运动员"},
        {"pred": "配偶", "obj": "叶莉"}, {"pred": "女儿", "obj": "姚沁蕾"},
        {"pred": "所属球队", "obj": "休斯顿火箭队"}]},
    {"subj": "叶莉", "height": 190, "weight": 83, "po": [
        {"pred": "国籍", "obj": "中国"}, {"pred": "职业", "obj": "篮球运动员"},
        {"pred": "女儿", "obj": "姚沁蕾"}]},
    {"subj": "姚沁蕾", "height": 160, "weight": 48, "po": [
        {"pred": "国籍", "obj": "中国"}, {"pred": "母亲", "obj": "叶莉"},
        {"pred": "父亲", "obj": "姚明"}]},
    {"subj": "科比", "height": 198, "weight": 96, "po": [
        {"pred": "国籍", "obj": "美国"}, {"pred": "职业", "obj": "篮球运动员"},
        {"pred": "所属球队", "obj": "洛杉矶湖人队"}]},
    {"subj": "乔丹", "height": 198, "weight": 98, "po": [
        {"pred": "国籍", "obj": "美国"}, {"pred": "职业", "obj": "篮球运动员"},
        {"pred": "所属球队", "obj": "芝加哥公牛队"}]},
    {"subj": "梅西", "height": 170, "weight": 72, "po": [
        {"pred": "国籍", "obj": "阿根廷"}, {"pred": "职业", "obj": "足球运动员"},
        {"pred": "所属球队", "obj": "迈阿密国际队"}]},
]
INDEX = {d["subj"]: d for d in DOCS}

# ---- 2. 属性同义词扩展（查询解析阶段的字段名映射，借鉴 ES 同义词思想；资源可用 HowNet/同义词林/BabelNet）----
ATTR_SYNONYM = {"身高": "height", "多高": "height", "体重": "weight", "重量": "weight",
                "多重": "weight"}
NUMERIC = {"height", "weight"}

def normalize_attr(attr):
    return ATTR_SYNONYM.get(attr, attr)

# ---- 3. 功能①：实体查询 -> 知识卡片 ----
def card(name):
    d = INDEX.get(name)
    if not d:
        return None
    lines = [f"【知识卡片】{d['subj']}", f"  身高 {d['height']} cm｜体重 {d['weight']} kg"]
    for kv in d["po"]:
        lines.append(f"  {kv['pred']}: {kv['obj']}")
    return "\n".join(lines)

# ---- 4. 功能②③：单跳 / 多跳属性查询（实体:属性1:属性2...，循环把属性值作为下一步实体）----
def path_query(path):
    nodes = [path[0]]
    cur = INDEX.get(path[0])
    for attr in path[1:]:
        attr = normalize_attr(attr)
        if cur is None:
            return None, nodes
        if attr in NUMERIC:
            return cur[attr], nodes                      # 数值属性：直接返回整数字段
        nxt = next((kv["obj"] for kv in cur["po"] if kv["pred"] == attr), None)
        nodes.append(nxt)
        cur = INDEX.get(nxt)                             # 属性值成为下一跳实体
    # 路径走完：最后一跳若指向 INDEX 中的实体，cur 非空，返回其名；
    # 若最后一跳是字面量/非实体值（如“国籍:中国”），cur 为 None，此时 nodes[-1] 就是该属性值，必须返回它而非 None
    if cur is not None:
        return cur["subj"], nodes
    return (nodes[-1] if nodes else None), nodes

# ---- 5. 功能④：多属性条件检索（AND/OR/NOT + =,>,<,>=,<=），等价 ES bool/range/nested 查询 ----
def parse_atom(atom):
    """解析单个条件，如 '身高>=180'、'NOT 国籍:中国'、'职业:篮球运动员'"""
    neg = False
    atom = atom.strip()
    if atom.startswith("NOT "):
        neg, atom = True, atom[4:].strip()
    m = re.match(r"([^:><=]+)(>=|<=|>|<|:|=)(.+)", atom)
    pred, op, val = m.group(1).strip(), m.group(2), m.group(3).strip()
    pred = normalize_attr(pred)
    return neg, pred, op, val

def match_atom(doc, pred, op, val):
    """单个文档是否满足条件：height/weight 走数值范围，其余走 po 精确匹配"""
    if pred in NUMERIC:
        num = doc[pred]
        rhs = float(val)
        return {">": num > rhs, "<": num < rhs, ">=": num >= rhs,
                "<=": num <= rhs, "=": num == rhs, ":": num == rhs}[op]
    if op in (">", "<", ">=", "<="):
        return False                                    # 非数值属性不支持范围
    return any(kv["pred"] == pred and kv["obj"] == val for kv in doc["po"])

def po_search(query):
    """OR 相邻子句先合并为 should（优先级更高），再用 AND 串接 must / must_not"""
    or_groups, musts = [], []
    for clause in re.split(r"\s+AND\s+", query):
        atoms = [parse_atom(a) for a in re.split(r"\s+OR\s+", clause)]
        if len(atoms) > 1:
            or_groups.append(atoms)
        else:
            musts.append(atoms[0])
    hits = []
    for doc in DOCS:
        ok = True
        for neg, pred, op, val in musts:                # AND 连接：NOT -> must_not
            if match_atom(doc, pred, op, val) == neg:
                ok = False
        for group in or_groups:                         # OR 连接：should，任一满足即可
            if not any(match_atom(doc, pred, op, val) != neg for neg, pred, op, val in group):
                ok = False
        if ok:
            hits.append(doc["subj"])
    return hits

def classify(query):
    """查询分类：含布尔连接词/比较符为多条件检索；含路径冒号（中文:）为实体属性查询"""
    if re.search(r"\b(AND|OR|NOT)\b|>=|<=|>|<", query):
        return "多属性条件检索"
    if ":" in query or "：" in query:
        return "实体属性（多跳）查询"
    return "实体查询（知识卡片）"

def answer(query):
    kind = classify(query)
    print(f"\n查询：{query}\n分类：{kind}")
    if kind == "实体查询（知识卡片）":
        print(card(query.strip()))
    elif kind == "实体属性（多跳）查询":
        path = re.split(r"[:：]", query)
        val, nodes = path_query(path)
        print("  解析路径：", " -> ".join(str(n) for n in nodes), f"-> {val}")
    else:
        print("  命中实体：", "、".join(po_search(query)) or "（无）")

# ---- 6. 演示四类查询 ----
answer("姚明")
answer("姚明:女儿:母亲:身高")
answer("姚明:国籍")
answer("职业:篮球运动员 AND 身高>=195 AND NOT 国籍:中国")
answer("职业:篮球运动员 OR 职业:足球运动员 AND NOT 国籍:中国 AND 身高>=180")

运行结果：

查询：姚明
分类：实体查询（知识卡片）
【知识卡片】姚明
  身高 226 cm｜体重 140 kg
  国籍: 中国
  职业: 篮球运动员
  配偶: 叶莉
  女儿: 姚沁蕾
  所属球队: 休斯顿火箭队

查询：姚明:女儿:母亲:身高
分类：实体属性（多跳）查询
  解析路径： 姚明 -> 姚沁蕾 -> 叶莉 -> 190

查询：姚明:国籍
分类：实体属性（多跳）查询
  解析路径： 姚明 -> 中国 -> 中国

查询：职业:篮球运动员 AND 身高>=195 AND NOT 国籍:中国
分类：多属性条件检索
  命中实体： 科比、乔丹

查询：职业:篮球运动员 OR 职业:足球运动员 AND NOT 国籍:中国 AND 身高>=180
分类：多属性条件检索
  命中实体： 科比、乔丹

多跳路径「姚明 → 姚沁蕾 → 叶莉 → 190」完整跑通；两条多条件查询中，姚明被 NOT 国籍:中国 排除、梅西因身高 170 不满足阈值被排除，最终命中科比与乔丹。原课 demo 基于 Elasticsearch（ES 服务端是 Java 实现，但课件配套的预处理/导入/查询脚本 preprocess.py、insert.py、views.py 都是用 Python 的 requests 调 ES REST API），本节统一用 Python 标准库复刻其核心机制：bool 的 must/should/must_not、range 的 gte/lte、nested 的 po 列表都能在代码里一一对应；工程上换 ES 时把内存字典换成索引、把函数换成 DSL 即可。

5.6 进阶方向：课件列出的九个问题

课件最后给出九个进阶主题，按机制归类、点到为止（反向检索与多元关系在练习中动手实现）：

1. 别名检索：实体可能有别名（绰号、曾用名），索引中增加 alias 字段，name 本身也作为可检索属性，id 作为唯一标识；
2. 概念检索：type 字段支持类检索，并借助上下位关系（hypernym）做查询扩展，如「运动员」扩展为「足球运动员 OR 篮球运动员」；
3. 属性值模糊/子串检索：把 keyword 类型改为可分词的 string 类型，按子串命中与相似度返回；
4. 不同类型值的操作推广：integer、date、string、entity 分入不同 nested object，各自支持适合的操作（数值/日期支持范围，实体支持跳转），与第 5 章的垂直分区、属性表思想一致；
5. 反向检索：存正向 PO 的同时存逆谓词（reverse-predicate）索引 RSP/SP，使「姚明:女儿:姚沁蕾」与「姚沁蕾:父亲:姚明」互为逆查；
6. 属性 path 查询：如「女儿:星座:白羊座」，本质是逆向检索加连接；
7. path 查询嵌套：如「国籍:中国 AND 女儿:星座:白羊座」，把路径条件作为 bool 查询的一个子句；
8. 多元关系（n-ary relation）：如「2000 年之后加入火箭队的篮球运动员」，按 Freebase 的 CVT（Compound Value Type，复合值类型）思路拆成多个二元关系：职业=篮球运动员 AND 所属球队=火箭队 AND 加入时间>=2000；
9. 单位统一：用正则识别「1.9m」「190cm」等量纲并换算到统一单位后再比较。

📝 动手练一练

练习 1（概念辨析）：判断下面三个需求分别属于文档检索、数据检索还是混合检索，并写出各自的查询模型、数据模型与匹配技术： ① 在 PDF 文档库中检索包含「知识图谱」关键词的文档； ② 在电影知识库中找出「香港导演执导、中国武术演员主演的动作片」； ③ 在企业知识库中找出「与某位图灵奖得主同机构、且其相关文档提到增量查询技术」的研究员。

练习 2（代码扩展）：在代码块5的人物数据上完成两件事：(a) 补建反向索引 RSP，支持「姚沁蕾:父亲」这样的反向检索；(b) 写出「职业:篮球运动员 AND 身高>=195 AND NOT 国籍:中国」对应的 bool 条件结构（must/should/must_not）并给出命中实体。

# 练习参考答案：(a) 为实体虚拟文档补建反向索引 RSP，支持反向检索；(b) 给出 bool 条件结构
# 自洽最小样例（每个代码块独立运行，这里重新声明数据）
DOCS = [
    {"subj": "姚明", "height": 226, "po": [{"pred": "国籍", "obj": "中国"},
        {"pred": "职业", "obj": "篮球运动员"}, {"pred": "女儿", "obj": "姚沁蕾"}]},
    {"subj": "姚沁蕾", "height": 160, "po": [{"pred": "国籍", "obj": "中国"},
        {"pred": "父亲", "obj": "姚明"}, {"pred": "母亲", "obj": "叶莉"}]},
    {"subj": "科比", "height": 198, "po": [{"pred": "国籍", "obj": "美国"},
        {"pred": "职业", "obj": "篮球运动员"}]},
    {"subj": "乔丹", "height": 198, "po": [{"pred": "国籍", "obj": "美国"},
        {"pred": "职业", "obj": "篮球运动员"}]},
]

# 谓词与其逆谓词（reverse-predicate）
INV_PRED = {"父亲": "女儿", "女儿": "父亲"}

# (a) 正向 PO：(主体, 谓词) -> [客体]；
#     反向 RSP（按课件 Page132 的结构）：(逆谓词, 客体) -> [主体]。
#     写入 (姚明, 女儿, 姚沁蕾) 时，除 PO[(姚明,女儿)] 外，同步写 RSP[(父亲, 姚沁蕾)]=[姚明]，
#     此时原客体 姚沁蕾 成为反向关系的主体——与课件「RSP[(父亲, 姚沁蕾)]」完全一致。
PO, RSP = {}, {}
for d in DOCS:
    for kv in d["po"]:
        PO.setdefault((d["subj"], kv["pred"]), []).append(kv["obj"])
        if kv["pred"] in INV_PRED:                      # 该谓词存在逆谓词，才需要建反向索引
            RSP.setdefault((INV_PRED[kv["pred"]], kv["obj"]), []).append(d["subj"])

def forward(entity, pred):
    return PO.get((entity, pred), [])

def reverse(entity, pred):
    """反向检索：用户查「姚沁蕾:父亲」，直接以 (逆谓词=父亲, 客体=姚沁蕾) 为键取主体。"""
    return RSP.get((pred, entity), [])

print("正向 姚明:女儿 =", forward("姚明", "女儿"))
print("反向 姚沁蕾:父亲 =", reverse("姚沁蕾", "父亲"))

# (b) “职业:篮球运动员 AND 身高>=195 AND NOT 国籍:中国” 的 bool 条件结构与命中
def hit(d):
    must = [any(kv["pred"] == "职业" and kv["obj"] == "篮球运动员" for kv in d["po"]),
            d["height"] >= 195]
    must_not = [any(kv["pred"] == "国籍" and kv["obj"] == "中国" for kv in d["po"])]
    return all(must) and not any(must_not)

print("bool 结构: must=[term(职业=篮球运动员), range(height gte 195)], must_not=[term(国籍=中国)]")
print("命中实体：", [d["subj"] for d in DOCS if hit(d)])

正向 姚明:女儿 = ['姚沁蕾']
反向 姚沁蕾:父亲 = ['姚明']
bool 结构: must=[term(职业=篮球运动员), range(height gte 195)], must_not=[term(国籍=中国)]
命中实体： ['科比', '乔丹']

本章小结

• 定位：语义搜索是 IR 与 DB 在数据 Web 上的合流。按查询模型、数据模型、匹配技术三要素区分文档检索与数据检索；语义模型分语言学模型（taxonomy/thesaurus，WordNet、BabelNet）与概念模型（本体解释）；方案分重量级（知识库内核，语义数据检索）与轻量级（IR 内核，语义文档检索）；数据 Web 搜索有可扩展性、异构性、不确定性三大难点。
• 语义数据搜索：Semplore 把三元组转成带 type/text/subjOf 字段的虚拟文档（课件 Page24 仅此三字段），用 AIS 四操作（基础检索、归并、概念表达式、关系扩展）+ 查询图深度优先遍历支撑结构化查询，以基于块的扩展支持增量索引；Dataplorer 用互模拟（原图+逆图双向）生成结构等价的扩展分区即结构索引、做答案空间/资源空间两阶段匹配，复杂查询显著优于垂直分区；排序遵循质量传播、数量聚合、单调性三原则，落地为带打分流的 SAIS。
• Hermes 以 pay-as-you-go 整合多源：离线做模式层/数据层映射，知识融合经「索引（基本/扩展特征）→ 分块（稀有特征 + 文档频率）→ 聚类（紧致集合/稀疏邻居）」提效；在线做关键词翻译与联合查询处理，跨源连接用 map join（查预计算映射，等价一次本地关系扩展）替代运行时算相似度的 similarity join。
• 混合搜索（CE2）用资源图（数据图 + 文档图 + 标注）建模，线下建 EntIdx/DocIdx/AnnIdx，线上把混合查询分解为四类原子查询，经关键字连接、混合连接、排序投影合并；路线图分三元组存储、语义搜索引擎、大规模语义搜索引擎三级阶梯。
• 交互范式：关键词经「映射本体元素 → 递归探索连接 → 导出合取查询」三步翻译，效率由摘要图 + 代价导向 Top-k 图探索（分支定界、提前终止）解决，值节点映射常量、类节点映射变量，用 MRR 评测；分面即结果集资源的谓词、分面值即客体，用 subjectOf/objectOf 两次关系扩展动态生成，结构上为 3 趟关系扩展（实测墙钟比值随查询复杂度从约 13 倍降到 1.7 倍），排序以最大化浏览能力为原则。
• 实战（用 ES 思路复刻简化版 FGS）：课件 Page 115 的实验并非 FGS 本身，而是用 Elasticsearch 实现一个能完成 FGS 最后查询（s-表达式条件组合）基本功能的简单语义数据检索引擎；其设计核心是「实体即索引文档」——范围属性抽整数字段、其余入 nested po 列表，配合同义词扩展、多跳循环、bool/range/nested 条件解析实现四类查询；进阶覆盖别名、概念扩展、模糊检索、类型化操作、反向检索、路径嵌套、多元关系（CVT 拆解）与单位统一。

📋 行动清单

• 在本机把代码块 1 到代码块 5（含练习答案块）全部跑通，然后替换成你自己领域的一组三元组数据，复现一次「虚拟文档倒排检索 → 排序 → 分面生成」全流程。
• 默画课件 Page 109 的语义搜索三级路线图（箭头 From Dataplorer To Hermes，三级阶梯为 RDF 三元组存储 → 语义搜索引擎 → 大规模语义搜索引擎；按 Page 22 分类，Dataplorer/Semplore 属第一级三元组存储、CE2 属第二级混合语义搜索引擎、Hermes 属第三级），在每一级标注它新增的能力、离线/在线各做什么，以及对应本节的哪个机制（结构索引、SAIS、OPT、知识融合两阶段）。
• 参照代码块 5 的实体虚拟文档模板，为你熟悉的一个领域（电影、书籍或商品）设计 po 字段、属性同义词表，并写出 3 条查询：一条多跳、一条 AND/OR/NOT 混合条件、一条需要反向索引才能回答的查询。

—— 小象教研组