← 返回卡片

原书出处

大数据日知录_架构与算法

03 大数据常用的算法与数据结构

2014年9月第1版 · 核验版本的摘录快照 · 导入于 2026-10-24T04:14:12.118Z

在实际实现LZ系列算法时,一个影响系统效率的步骤是如何快速地在滑动窗口中找到最长匹配字符串。这里一个常用的技巧是:将滑动窗口内字符串的各种长度片段存入哈希表,哈希表的值记载其在滑动窗口的出现位置。比如假设滑动窗口内的字符串为ABC,那么可以在哈希表中记录AB、ABC、BC字符串片段的起始位置。有时为了简化问题,可以设定字符串片段为固定长度,比如设定为2,那么只需要存储AB和BC即可,这样当滑动窗口较长的时候便能有效地减少数据量。在进行匹配时,首先对前向缓冲区的起始字符串查询哈希表,如果在哈希表中找到,说明有匹配字符串,并可以直接定位其位置,在此基础上再进行最长匹配,这样能有效加快匹配速度。

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html

EPUB SHA-256:e45b74c4bdd8959aef24f2a5183280eb73ec5f173108f8679a4bbf44bbd5b34d