知识卡片
匹配索引换压缩速度
为窗口片段保存哈希位置,可先定位候选,再比较实际字节延长匹配,避免逐位置完整扫描。Snappy按短固定片段寻找匹配,强调吞吐而非最高压缩率;原书32KB块和每次滑动4字节是历史实现概括,不能当格式永久规则或每次操作的精确描述。书中速度值亦非当前硬件基准。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 大数据常用的算法与数据结构 · 查看原书依据
在实际实现LZ系列算法时,一个影响系统效率的步骤是如何快速地在滑动窗口中找到最长匹配字符串。这里一个常用的技巧是:将滑动窗口内字符串的各种长度片段存入哈希表,哈希表的值记载其在滑动窗口的出现位置。比如假设滑动窗口内的字符串为ABC,那么可以在哈希表中记录AB、ABC、BC字符串片段的起始位置。有时为了简化问题,可以设定字符串片段为固定长度,比如设定为2,那么只需要存储AB和BC即可,这样当滑动窗口较长的时候便能有效地减少数据量。在进行匹配时,首先对前向缓冲区的起始字符串查询哈希表,如果在哈希表中找到,说明有匹配字符串,并可以直接定位其位置,在此基础上再进行最长匹配,这样能有效加快匹配速度。
参考来源
- 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html)
- 结论依据:原文以“将滑动窗口内字符串的各种长度片段存入哈希表”所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。
- 原始内容:在实际实现LZ系列算法时,一个影响系统效率的步骤是如何快速地在滑动窗口中找到最长匹配字符串。这里一个常用的技巧是:将滑动窗口内字符串的各种长度片段存入哈希表,哈希表的值记载其在滑动窗口的出现位置。比如假设滑动窗口内的字符串为ABC,那么可以在哈希表中记录AB、ABC、BC字符串片段的起始位置。有时为了简化问题,可以设定字符串片段为固定长度,比如设定为2,那么只需要存储AB和BC即可,这样当滑动窗口较长的时候便能有效地减少数据量。在进行匹配时,首先对前向缓冲区的起始字符串查询哈希表,如果在哈希表中找到,说明有匹配字符串,并可以直接定位其位置,在此基础上再进行最长匹配,这样能有效加快匹配速度。
- 边界对照:[LevelDB实现说明](https://raw.githubusercontent.com/google/leveldb/main/doc/impl.md)、[Bitcoin原论文](https://bitcoin.org/bitcoin.pdf)、[SILT原论文](https://www.cs.cmu.edu/~dga/papers/silt-sosp2011.pdf);用于校正原书简化,未将书外观点伪作原文。