知识卡片
前端编码：排序字典里的相邻词共享前缀
内容
字典按字母序排序后，相邻词大概率共享前缀（如jerusalem、jerusalemites），前端编码只存”共享前缀长度”加”剩余后缀”，不重复存公共部分。字典越大，公共前缀期望越长，真实语言前缀分布比随机假设更集中，经验值能省约40%字典空间。代价是牺牲了直接二分查找的能力，折中方案是每隔几个词保留一个完整未压缩词作跳转锚点，这是[[分块压缩与随机访问的权衡]]在字典结构里的重演。
参考来源
- 位置：第4章《查询》「前端编码」小节（源文件：_chapter-text/ch04.txt，对应_epub-src/OEBPS/text00010.html）
- 结论依据：原文明确说明前端编码利用排序字典相邻词共享前缀，只存前缀长度+后缀，并给出《圣经》字典实测节省2.6字节/词的数据，直接支持卡片论点。
- 原始内容："前端编码是一项颇有价值的改进，众所周知，在一个已排序的字符串列表中相邻的单词可能包含共同的前缀……在《圣经》中平均前缀长度为3.6，平均字符串长度为6.1。这将在存放字符串的7.1个字符中净节约2.6字节。"