主题索引
时空效率与复杂度分析
比较渐近复杂度、摊销分析、基准测试以及以抽象换空间、局部性等时间与空间效率的权衡。
来源书籍
7/7
Skill 版本:v1
本次实际使用规则:book-notes v8(2026-09-25 v8 复核:49 张卡标题压到 15 字内并同步文件名与链接,摘录严格复核更正 36 张,补登记类别“信息检索/搜索引擎类”,补实践卡进度与主题索引维护),详见 _workflow.md。
类别:信息检索/搜索引擎类
四象限结论:经典原理(高浓度 + 高稳定性)
评级理由: 本书是信息检索领域的经典教材(Ian H. Witten, Alistair Moffat, Timothy C. Bell 著,曾是斯坦福大学信息检索课程首选教材)。全书围绕”如何用最小空间存储海量文档,同时提供最快的关键词检索”这一核心矛盾展开,逐章拆解为压缩、索引、查询、索引构造、图像压缩五大问题域。
例外:附录A(mg系统指南)是纯操作步骤(安装命令、环境变量设置),附录B(新西兰数字图书馆)主要是功能截图与 UI 描述,两者信息浓度低,按”略读”处理。
| 章节号 | 章节标题 | 精读/略读 | 状态 | 卡片数 |
|---|---|---|---|---|
| 前言/译者序等 | 非正文(书名页/版权页/原著赞誉/译者序/前言) | 略读 | done | 0 |
| ch01 | 第1章 概览 | 精读 | done | 7 |
| ch02 | 第2章 文本压缩 | 精读 | done | 11 |
| ch03 | 第3章 索引 | 精读 | done | 11 |
| ch04 | 第4章 查询 | 精读 | done | 11 |
| ch05 | 第5章 索引构造 | 精读 | done | 6 |
| ch06 | 第6章 图像压缩 | 精读 | done | 4 |
| ch07 | 第7章 文本图像 | 精读 | done | 3 |
| ch08 | 第8章 混合图文 | 精读 | done | 2 |
| ch09 | 第9章 系统实现 | 精读 | done | 3 |
| appA | 附录A mg系统指南 | 略读 | done | 0 |
| appB | 附录B 新西兰图书馆 | 略读 | done | 0 |
(EPUB spine 文件对应关系:ch01→text00007.html,ch02→text00008.html,ch03→text00009.html, ch04→text00010.html,ch05→text00011.html,ch06→text00012.html,ch07→text00013.html, ch08→text00014.html,ch09→text00015.html,appA→text00016.html,appB→text00017.html)
| 术语名 | 出现章节 | 一句话语境 |
|---|---|---|
| trie树(数字搜索树) | 第2章 | 用于加速LZ77查找匹配子串或LZ78语法分析短语的多叉树结构,书中仅一句话带过未展开原理 |
| 序号 | 实践标题 | 实践方式 | 状态 | 关联章节 | 产出 |
|---|---|---|---|---|---|
| 1 | 用cardbox真实FTS5搜索验证TF-IDF单调性原则 | 实现深读 | done | 第4章 | 检索实验记录与单调性核对表(计划) |
| 2 | 用本仓库真实文本实测哈夫曼编码与算术编码的压缩率差距 | 横向学习 | done | 第2章 | 压缩率对比表(计划) |
实践卡仅为计划,未执行。 | 1 | 用cardbox真实FTS5搜索验证TF-IDF单调性原则 | 实现深读 | done | TF-IDF相关章节 | 真实检索排序结果记录 | | 2 | 用本仓库真实文本实测哈夫曼编码与算术编码的压缩率差距 | 横向学习 | done | 编码方法相关章节 | gzip/bzip2压缩率对比与熵估算 |
| 维度 | 覆盖状态 | 关联卡片标题或未覆盖理由 |
|---|---|---|
| 压缩模型选择(统计/字典模型取舍) | 已覆盖 | 符号方法与字典方法的本质区别、静态、半静态、自适应建模的取舍 |
| 索引结构设计(倒排文件等) | 已覆盖 | 布尔查询即列表运算、三种索引同压稀疏矩阵、文档间隔让列表可压 |
| 查询处理策略(布尔/排名查询) | 已覆盖 | 合取查询先短列表、分块索引找回二分查找、n-gram索引先过滤 |
| 相关性排序模型 | 已覆盖 | TF-IDF两条单调原则、向量模型比方向、相关反馈修正查询 |
| 索引构造的空间-时间权衡 | 已覆盖 | 建索引的三方取舍、倒排化为外部排序、压缩临时文件更快 |
| 检索效果评价方法 | 已覆盖 | 召回与精确两种切法、网页搜索重精确率 |
| 分布式检索策略 | 已覆盖 | 分布式排名两阶段 |
7⁄7 维度已全部覆盖,无需补充生成卡片。
| 标题 | 类型 | 出现章节 | 一句话语境 |
|---|---|---|---|
| Text Compression(John G. Cleary, Ian H. Witten, Timothy C. Bell 著) | 书 | 前言 | 第2章文本压缩内容的完整扩展版,专讲压缩方法 |
| Modern Information Retrieval(R. Baeza-Yates, B. Ribeiro-Neto 著,简称MIR) | 书 | 译者序 | 与本书并列为全球信息检索课程主要教材之一 |
本书围绕全文检索的压缩、索引、查询与图像压缩展开;新建文本压缩、倒排索引、相关性排序与图像压缩 4 个主题,并把索引构造的空间时间取舍并入已有时空效率主题。
| 卡片标题 | 结论 | 主题文件或原因 |
|---|---|---|
| 检索的空间速度矛盾 | 已创建 | notes/_topics/inverted-index-query.md |
| 基于指针复用的压缩原理 | 已创建 | notes/_topics/text-compression-coding.md |
| 分块压缩与随机访问的权衡 | 已创建 | notes/_topics/text-compression-coding.md |
| 停用词的压缩经济学 | 已创建 | notes/_topics/inverted-index-query.md |
| 有损压缩与无损压缩的边界 | 已创建 | notes/_topics/text-compression-coding.md |
| 全文检索与传统数据库的根本差异 | 已创建 | notes/_topics/inverted-index-query.md |
| memex以联想代目录 | 已创建 | notes/_topics/relevance-ranking-evaluation.md |
| 信息量与熵:压缩的理论下限 | 已创建 | notes/_topics/text-compression-coding.md |
| 静态、半静态、自适应建模的取舍 | 已创建 | notes/_topics/text-compression-coding.md |
| 符号方法与字典方法的本质区别 | 已创建 | notes/_topics/text-compression-coding.md |
| 哈夫曼编码的整数位长天花板 | 已创建 | notes/_topics/text-compression-coding.md |
| 范式哈夫曼利于随机访问 | 已创建 | notes/_topics/text-compression-coding.md |
| 算术编码的优势与代价 | 已创建 | notes/_topics/text-compression-coding.md |
| PPM用转义逐阶降级 | 已创建 | notes/_topics/text-compression-coding.md |
| 块排序压缩:先重排文本再压缩 | 已创建 | notes/_topics/text-compression-coding.md |
| LZ77与LZ78的取舍 | 已创建 | notes/_topics/text-compression-coding.md |
| 同步点连接随机访问 | 已创建 | notes/_topics/text-compression-coding.md |
| 压缩率不等于解码快 | 已创建 | notes/_topics/text-compression-coding.md |
| 索引粒度的取舍 | 已创建 | notes/_topics/inverted-index-query.md |
| 布尔查询即列表运算 | 已创建 | notes/_topics/inverted-index-query.md |
| 预处理拿准确换召回 | 已创建 | notes/_topics/inverted-index-query.md |
| 文档间隔让列表可压 | 已创建 | notes/_topics/inverted-index-query.md |
| 编码即隐含概率假设 | 已创建 | notes/_topics/inverted-index-query.md |
| 全局与局部模型之争 | 已创建 | notes/_topics/inverted-index-query.md |
| 词的出现是成簇的 | 已创建 | notes/_topics/inverted-index-query.md |
| 插值编码用双向边界 | 已创建 | notes/_topics/inverted-index-query.md |
| 签名文件只给可能匹配 | 已创建 | notes/_topics/inverted-index-query.md |
| 三种索引同压稀疏矩阵 | 已创建 | notes/_topics/inverted-index-query.md |
| 压缩后停用词收益缩水 | 已创建 | notes/_topics/inverted-index-query.md |
| 前端编码共享前缀 | 已创建 | notes/_topics/inverted-index-query.md |
| 最小完美哈希免冲突 | 已创建 | notes/_topics/inverted-index-query.md |
| n-gram索引先过滤 | 已创建 | notes/_topics/inverted-index-query.md |
| 合取查询先短列表 | 已创建 | notes/_topics/inverted-index-query.md |
| 分块索引找回二分查找 | 已创建 | notes/_topics/inverted-index-query.md |
| TF-IDF两条单调原则 | 已创建 | notes/_topics/relevance-ranking-evaluation.md |
| 向量模型比方向 | 已创建 | notes/_topics/relevance-ranking-evaluation.md |
| 召回与精确两种切法 | 已创建 | notes/_topics/relevance-ranking-evaluation.md |
| 网页搜索重精确率 | 已创建 | notes/_topics/relevance-ranking-evaluation.md |
| 相关反馈修正查询 | 已创建 | notes/_topics/relevance-ranking-evaluation.md |
| 分布式排名两阶段 | 已创建 | notes/_topics/inverted-index-query.md |
| 建索引即转置矩阵 | 已创建 | notes/_topics/inverted-index-query.md |
| 倒排化为外部排序 | 已创建 | notes/_topics/inverted-index-query.md |
| 压缩临时文件更快 | 已创建 | notes/_topics/inverted-index-query.md |
| 预分配按最坏情况 | 已创建 | notes/_topics/inverted-index-query.md |
| 建索引的三方取舍 | 已创建 | notes/_topics/inverted-index-query.md、notes/_topics/time-space-efficiency.md |
| 动态集合摊销更新 | 已创建 | notes/_topics/inverted-index-query.md |
| 上下文建模扩到二维 | 已创建 | notes/_topics/image-compression.md |
| 超视力压缩估上界 | 已创建 | notes/_topics/image-compression.md |
| 例外模式保护结构 | 已创建 | notes/_topics/image-compression.md |
| JPEG先丢后编码 | 已创建 | notes/_topics/image-compression.md |
| 文本图像的字典压缩 | 已创建 | notes/_topics/image-compression.md |
| 用预测代价量相似 | 已创建 | notes/_topics/image-compression.md |
| 残差图统一有损无损 | 已创建 | notes/_topics/image-compression.md |
| Hough变换投票找线 | 已创建 | notes/_topics/image-compression.md |
| 页面切分两条路线 | 已创建 | notes/_topics/image-compression.md |
| 哈夫曼码长易溢出 | 已创建 | notes/_topics/text-compression-coding.md |
| 裁剪字典省解码内存 | 已创建 | notes/_topics/text-compression-coding.md |
| 压缩倒排空间时间双赢 | 已创建 | notes/_topics/inverted-index-query.md |
从本书的主题进入跨书阅读,对照其他书籍的讲解。下方数量包含主题关联的全部卡片与书籍。
主题索引
比较渐近复杂度、摊销分析、基准测试以及以抽象换空间、局部性等时间与空间效率的权衡。
主题索引
比较全文检索的索引粒度、倒排列表压缩、签名文件与位图、布尔查询加速与索引构造算法,以及压缩索引如何同时省空间和提速。
主题索引
比较以熵为下限的文本压缩方法:哈夫曼与算术编码、静态与自适应建模、PPM、块排序与LZ字典压缩,以及压缩与随机访问、解码速度的取舍。
主题索引
比较TF-IDF、向量空间模型与相关性反馈等排序依据,以及召回率与精确率在不同检索场景中的取舍。
主题索引
比较二值图像的上下文建模、有损与无损压缩、JPEG、文本图像的字典压缩与版面切分方法。