3.5 Searching Applications：集合、字典、索引与稀疏计算

3.5 · Searching Applications覆盖 6 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“3.5 · Searching Applications”如何把集合、字典、倒排索引、稀疏向量与系统符号表归结为键值操作组合
能逐项核对查找应用、集合API、字典客户端、索引客户端、稀疏向量与矩阵、系统符号表，并区分作者站内容与本页独立补充
能按“稀疏向量点积可按较小非零集合迭代，成本 O(nnz_small × lookup)”手算一个最小输入，逐步检查“应用结果必须与所选 Set/Map 语义一致，缺失键与显式零值不得混淆”
能注入“在遍历索引时原地修改同一符号表，或把重复词频误压成集合存在性”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“3·5 · Searching Applications”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“3·5 · Searching Applications”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“3·5 · Searching Applications”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：3.5 · Searching Applications

1. 查找应用：在本页通过“选择集合或映射”连接解释、交互状态和练习验收。
2. 集合API：在本页通过“规范化输入键”连接解释、交互状态和练习验收。
3. 字典客户端：在本页通过“构建正向或倒排索引”连接解释、交互状态和练习验收。
4. 索引客户端：在本页通过“执行查询组合”连接解释、交互状态和练习验收。
5. 稀疏向量与矩阵：在本页通过“核对应用语义”连接解释、交互状态和练习验收。
6. 系统符号表：在本页通过“选择集合或映射”连接解释、交互状态和练习验收。

从“同一张表，不同的key/value含义”开始

查找应用（searching applications）不是在3.1到3.4之外再发明一种表。它要求先回答：client究竟需要membership、one value、a set of values、ordered range，还是只存nonzero coordinates；再选择满足contract的API与implementation。

先预测“电影到演员”索引能否直接回答“某演员演过哪些电影”。若只建立 movie -> SET<person>，reverse query必须扫描所有movies。要让两个方向都按key查询，构建阶段必须同步维护 movie -> people 与 person -> movies 两张ST；额外space换来query cost从全量扫描降为一次lookup。

官方3.5依次展示set APIs、dictionary clients、indexing clients、sparse vectors and matrices与system symbol table。每个案例都可用同一四步读法：

定义key equality与value meaning。
Build phase把external data转成associations。
Query phase只通过API观察结果。
让implementation choice匹配所需ordering与cost guarantee。

3.5.1 Set APIs：只保留keys，不伪造dummy values

集合API（set APIs）适用于client不关心associated value的场景。Duplicate add不改变set；contains只返回membership。

典型stream clients只差一个predicate：

DeDup：第一次看到key时输出并add，以后contains为true就跳过。
Allowlist：policy SET contains才输出。
Blocklist：policy SET不contains才输出。

SET<String> seen = new SET<String>();
while (!StdIn.isEmpty()) {
    String key = StdIn.readString();
    if (!seen.contains(key)) {
        seen.add(key);
        StdOut.println(key);
    }
}

Set union遍历两边并add到result；intersection只需遍历一边并对另一边contains。若两set规模为A与B，应遍历较小者，成本约：

T_{\cap}=\Theta(\min(A,B)\cdot C_{\mathrm{contains}})

Ordered SET还可提供min/max/floor/ceiling；unordered HashSet不能承诺iteration顺序。API命名相似不代表capabilities相同，client若需要range就必须把ordering写入contract。

3.5.2 Dictionary clients：build once，lookup many

字典客户端（dictionary clients）是最直接的ST应用。LookupCSV从command line取得file、key field与value field，逐row提取association，再读取queries：

int keyField = Integer.parseInt(args[1]);
int valField = Integer.parseInt(args[2]);
ST<String, String> st = new ST<String, String>();
 
while (in.hasNextLine()) {
    String[] tokens = in.readLine().split(",");
    st.put(tokens[keyField], tokens[valField]);
}
 
while (!StdIn.isEmpty()) {
    String query = StdIn.readString();
    if (st.contains(query)) StdOut.println(st.get(query));
    else                    StdOut.println("Not found");
}

Key field不是无害configuration：若file里key重复，standard ST语义让later row覆盖earlier value。若domain需要保留全部records，value应改为list/SET，或duplicate直接报错。CSV example用简单split展示algorithm，但production CSV含quoted commas、escaping与newlines，应使用真正parser。

Build cost是R次put，R为records；query cost是Q次contains/get。Official client先contains再get可能做两次lookup；若API能以nullable或optional result区分absent，可一次get，但必须先确认null-value contract。

Dictionary correctness不只测happy hit。要覆盖missing key、duplicate policy、empty field、malformed row、field index越界、encoding与normalization。若key需要case-insensitive，必须在build与query两侧使用同一canonicalization。

3.5.3 Indexing clients：value本身可以是SET

索引客户端（indexing clients）表面上是“一个key对应多个values”，实际仍遵守one value per key：value是一个集合。

FileIndex对每个file读取words，并维护 ST<String, SET<File>>。Term第一次出现时创建empty SET，随后add file；同一term在同一file重复出现不会产生duplicate posting。

if (!index.contains(word)) index.put(word, new SET<File>());
index.get(word).add(file);

Term query是一张posting SET；AND query是sets intersection；OR是union。Multi-word AND应先按posting size排序，从smallest set开始过滤。若要支持phrase query，仅保存file membership不够，value需升级为per-file positions；若要rank，需保存term frequency等metadata。

MovieIndex或LookupIndex展示bidirectional relation。输入一行movie与多个performers时同步更新：

movie\mapsto\{people\}, \qquad person\mapsto\{movies\}

两张表必须在同一record处理内一致更新。Round-trip certificate可检查：若person出现在movieToPeople[movie]，movie必须也出现在personToMovies[person]。只更新一侧不会立刻crash，却会让reverse results静默缺失。

Index build还要定义tokenization、case folding、stopwords、Unicode normalization与document identity。Client logic正确但normalization不一致，仍会把视觉相同的term拆成不同keys。

3.5.4 Sparse vectors and matrices：absence就是zero

稀疏向量与矩阵（sparse vectors and matrices）把dimension d与nonzero count nnz分开。Dense vector保存d个numbers；SparseVector保存 ST<Integer, Double> 中的nonzeros，memory proportional to nnz。

put(i, 0.0)必须delete association，否则zero entries会逐渐填满ST并让“sparse”退化。Get missing index返回0：

public void put(int i, double value) {
    if (i < 0 || i >= d) throw new IllegalArgumentException();
    if (value == 0.0) st.delete(i);
    else              st.put(i, value);
}
 
public double get(int i) {
    if (st.contains(i)) return st.get(i);
    return 0.0;
}

Dot product定义：

\mathbf a\cdot\mathbf b=\sum_{i=0}^{d-1}a_i b_i

Dense loop需要d次multiplication，即使绝大多数项为zero。Sparse-sparse实现遍历nnz较少的一侧，对另一ST做contains/get：

T_{\mathrm{dot}}= O\!\left(\min(nnz(a),nnz(b))\cdot C_{\mathrm{lookup}}\right)

若另一operand是dense array，只遍历当前sparse ST keys并直接访问 that[i]，成本proportional to nnz。Vector addition先copy this nonzeros，再遍历that并put sum；sum变0时put contract自动删除。

Sparse matrix可表示为rows array，每row是一条SparseVector。Matrix-vector multiply对每row做sparse dot；matrix addition逐row plus。是否按row、column或双索引存储取决于operation mix，不能看到“sparse”就默认一种layout。

3.5.5 System symbol table：从client contract选择容器

系统符号表（system symbol table）让production code通常不必重写BST或hash table，但实现选择仍决定语义：

Java TreeMap基于red-black tree，exact/ordered operations worst-case logarithmic，并提供navigation/range views。
HashMap提供expected constant exact lookup，不保证sorted iteration。
TreeSet与HashSet分别对应ordered与hashed membership。
Concurrent variants还改变atomicity、iteration consistency与null policy。

Textbook ST约定null value等价delete，而Java collections可能允许null key/value；不能把一种API的absence convention直接搬到另一种。Map.get()返回null时，若null values合法，必须用containsKey区分absent。

Implementation choice应从required operations倒推：

Client requirement	Suitable API property	Typical implementation
exact get/put only	unordered map	HashMap
floor/ceiling/range	ordered navigable map	TreeMap
membership only	set	HashSet or TreeSet
one-to-many relation	map to set/list	HashMap plus HashSet
sparse coordinate iteration	map index to nonzero	TreeMap or hash map by traversal need

Never依赖unspecified iteration order。Test在small dataset看起来保持insert order，换runtime、resize或hash seed后可能改变。若output必须deterministic，应显式sort或选择ordered collection。

3.5.6 Composition patterns：一张表常是更大结构的index

Searching applications经常把ST与另一结构组合，而不是把全部行为塞进ST：

LRU cache：ST从item映射到doubly linked-list node；list维护recency order。
Bidirectional lookup：两张ST维护正反关系。
Unique queue：SET记录ever seen，queue维护FIFO。
Indirect priority queue：ST定位item，heap维护priority order。
Concordance：ST把word映射到positions SET/list。

关键是明确每个结构拥有哪个invariant。LRU中ST负责O(1) locate，list负责oldest/newest；任何access必须同时更新两者。组合结构应有cross-certificate，而不是只测各容器内部合法。

Space也应按logical relation计算。Inverted index至少保存unique term-file pairs；bidirectional index保存每条edge两次；sparse matrix保存nonzero coordinates与per-row overhead。为了query latency复制index是有意识的tradeoff，必须在ingestion mutation中同步维护。

统一验收：从domain relation回到API observable behavior

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“3.5 · Searching Applications”的两个最小情境间切换，再逐项选择正式概念。预测“稀疏向量点积可按较小非零集合迭代，成本 O(nnz_small × lookup)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

3.5 · Searching Applications：对象、操作与不变量

把集合、字典、倒排索引、稀疏向量与系统符号表归结为键值操作组合

选择最小情境

切换正式概念

倒排索引: 文档 d1=[A,B]、d2=[B,C]，查询 B
当前观察: searching applications：返回 postings d1 与 d2，并保持文档标识去重规则

稀疏向量点积可按较小非零集合迭代，成本 O(nnz_small × lookup)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

查找应用：在实验 1 中指出对应状态，并写出一个通过条件。
集合API：在实验 2 中指出对应状态，并写出一个通过条件。
字典客户端：在实验 3 中指出对应状态，并写出一个通过条件。
索引客户端：在实验 1 中指出对应状态，并写出一个通过条件。
稀疏向量与矩阵：在实验 2 中指出对应状态，并写出一个通过条件。
系统符号表：在实验 3 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“稀疏向量点积可按较小非零集合迭代，成本 O(nnz_small × lookup)”不是孤立结论？

问题 3：故障恢复。 怎样证明“在遍历索引时原地修改同一符号表，或把重复词频误压成集合存在性”已经修复？

保存输入记录、规范化键、索引 postings、非零坐标、查询轨迹与朴素扫描结果作为正常基线；注入该故障并标记第一个违反“应用结果必须与所选 Set/Map 语义一致，缺失键与显式零值不得混淆”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

本章回顾

Searching application先定义domain key/value relation，再选择ST或SET implementation。
SET适合membership、dedup与filter，set algebra通过iteration加contains组合。
Dictionary client分build与query两阶段，duplicate key policy必须显式。
Index把key映射到SET/list；reverse query需要reverse index，不能凭空从forward ST得到。
File inverted index的multiword query是posting sets的intersection，先处理smallest posting更高效。
Sparse vector以absence表达zero，memory和arithmetic work随nnz而非dimension增长。
TreeMap/HashMap等system symbol tables的ordering、null与cost contracts不同。
组合结构需同步维护cross-invariants，并用round-trip或reference implementation验收。