Page 16索引的目标索引的核心目标是建立反向映射。字典是将“词”映射到“含义”索引是将“词”映射到“这个词出现过的所有位置”。物理上就是构建一个从Key到SetLocation的映射支持“给定一个词快速找出它在哪里出现过”。Page 17-18文件索引 —— FileIndex物理问题给定一组文件建立一个索引能快速找出包含某个查询字符串的所有文件。物理结构STString, SETFile键单词String。值包含该单词的文件集合SETFile。物理构建过程遍历命令行指定的所有文件。对每个文件逐词读取。对于每个单词key检查符号表st是否已包含该键。如果否创建一个新的SETFile。把当前file对象加入该单词对应的集合中set.add(file)。物理查询用户输入单词st.get(query)直接返回包含该单词的所有文件集合。物理本质这和你在 3.5 节学的反向索引Inverted Index完全一致。它是搜索引擎的底层核心数据结构。Page 20-21索引典Concordance物理问题给定一部长篇文本如《双城记》建立索引使得查询一个单词时能快速找到它在原文中的所有出现位置并显示其前后若干个单词作为上下文Context。物理结构STString, SETInteger键单词。值该单词在文章中出现的所有位置索引Integer的集合。物理构建过程将整个文本读入String[] words数组每个元素是一个单词。遍历数组对于每个位置i取单词s words[i]。将i加入该单词对应的SETInteger中。物理查询输入查询单词query从符号表中取出其位置集合SETInteger。对于集合中的每个位置k打印words[k-4]到words[k4]范围内的单词形成上下文。物理意义这是文本分析、词典编纂和文学研究的核心工具也是最早期的“搜索引擎”雏形。这里的值是SETInteger而非Queue因为不需要按插入顺序遍历而且SET天然去重一个位置只会出现一次。底层的ST通常用红黑树或哈希表实现确保查找速度。Page 24矩阵-向量乘法的图示一个巨大的矩阵乘以一个向量结果得到一个向量。如果矩阵很稀疏大部分元素为 0用标准数组存储会浪费大量空间。Page 25稀疏矩阵-向量乘法的问题定义物理问题矩阵的维度是 10,000N10000但每行平均只有约 10 个非零元素。物理冲突如果用标准的double[][]二维数组存储这个矩阵需要N*N 100 million个存储单元。但其中 99.9% 都是 0浪费了巨大的内存和计算时间。需要一种只存储非零元素的数据结构。Page 26稀疏向量的表示 —— 一维数组 vs 符号表标准表示稠密向量使用double[]数组。访问时间O(1)。空间占用与维度N成正比即使全是 0。符号表表示稀疏向量使用符号表如HashMapInteger, Double。键索引Integer。值该索引处的数值Double。只存储非零值空间占用与非零元素个数成正比。向量点积dot操作只遍历非零元素复杂度从O(N)降为O(#非零元素)。Page 28稀疏矩阵的表示物理结构标准二维数组矩阵就是double[][]数组。空间O(N²)。稀疏矩阵表示维护一个SparseVector[]数组长度为N。数组的每个元素是一个SparseVector对象只存储该行中的非零元素。总空间占用O(N)行数组本身 O(#非零元素)所有稀疏向量存储的键值对。Page 29稀疏矩阵-向量乘法的 Java 实现物理代码逻辑javaSparseVector[] a new SparseVector[N]; // 矩阵每行是一个稀疏向量 double[] x new double[N]; // 要乘的向量 double[] b new double[N]; // 结果向量 // 初始化 a 和 x ... for (int i 0; i N; i) { b[i] a[i].dot(x); // 第 i 行向量与 x 的点积 }物理复杂度每个dot操作只遍历该行中的非零元素。因此整个矩阵-向量乘法的时间复杂度正比于矩阵中非零元素的总数。这与N无关只与数据密度有关。在 Page 25 的假设每行 10 个非零元素下复杂度为10 * N即线性级别而非平方级别。总结 Indexing Clients Sparse Vectors 的物理本质索引客户端建立“键 → 位置集合”的反向映射。FileIndex是“词 → 文件”Concordance是“词 → 文本位置”。稀疏向量用符号表替换数组只存储非零值解决了高维数据如 PageRank、自然语言处理中的词频向量存储和计算的爆炸问题。它在 DFT/EDA 中的直接应用是处理稀疏矩阵如电路网表的连接关系避免在 0 值上浪费内存和算力。它在 DFT/EDA 里的直观对应在电路网表中你可以把每个逻辑门Gate看作一个维度。信号可能在少数几个门上有效非零而在绝大多数门上为 0。如果用稠密数组存储你就要为百万个门各分配一个double无论它有没有值。用SparseVector你只需要存储少数几个活跃的索引和值其余的都隐含为 0。这在逻辑仿真和故障传播分析中是极其关键的性能优化。建立反向索引Q其实这个代码我没有太读懂你能不能给我讲讲他都在干嘛A第一部分声明数据结构javaSTString, SETFile st new STString, SETFile();物理含义这里创建了一个符号表ST它的键Key是String单词值Value是一个SETFile包含该单词的所有文件的集合。你之前在SET那一节学过——SET就是只存键、不存值的符号表。所以SETFile可以理解为一个“文件名的集合”。第二部分遍历所有输入文件外层for循环javafor (String filename : args) { File file new File(filename); In in new In(file); while (!in.isEmpty()) { String key in.readString(); // ... } }物理动作遍历命令行传入的每个文件名args是运行程序时传入的参数。对每个文件名创建一个File对象代表磁盘上的一个文件。用In打开这个文件相当于 C 的ifstream。逐词读取文件in.readString()会跳过空白字符每次读一个单词。第三部分处理每个单词核心逻辑javaString key in.readString(); if (!st.contains(key)) st.put(key, new SETFile()); SETFile set st.get(key); set.add(file);逐句拆解String key in.readString();从当前文件中读出一个单词作为键。if (!st.contains(key)) st.put(key, new SETFile());检查全局符号表st里是否已经有这个单词了。如果没有说明这是第一次遇到这个单词就为它新建一个空的SETFile放进符号表里键是单词值是一个空集合。如果有跳过这一步直接用已有的那个集合。SETFile set st.get(key);从符号表里取出这个单词对应的SETFile也就是取出那个已经存在的集合或者刚刚新建的那个空集合。set.add(file);把当前正在处理的这个文件file加入这个集合。物理本质最终效果是——对于每个单词符号表里存着一个集合集合里包含了所有出现过这个单词的文件。第四部分查询阶段javawhile (!StdIn.isEmpty()) { String query StdIn.readLine(); StdOut.println(st.get(query)); }物理动作从标准输入StdIn读取用户输入的查询单词。用st.get(query)从符号表里取出这个单词对应的SETFile。打印出来StdOut.println会自动调用SET的toString()输出包含该单词的所有文件名。物理输出如果输入import程序会打印出所有包含import这个单词的文件名列表。总结这段代码在物理上做了什么它建立了一个“反向索引”Inverted Index不是从文件找单词而是从单词找文件。数据结构STString, SETFile每个单词映射到一个文件集合。输入多个文本文件。输出给定一个单词返回所有出现过它的文件。这段代码的物理前提底层的ST必须是高效的符号表红黑树或哈希表否则在大量单词上构建索引会变慢。SET底层也必须是高效的集合同样依赖红黑树或哈希表否则查询时遍历集合也会变慢。