Web 数据压缩与搜索

📊 课程难度与压力分析

COMP9319 是计算机系公认的‘智商与耐力’的双重巅峰。难点不在于代码量，而在于‘位级别的精确度 (Bit-level precision)’。当你手写一个算术编码器并涉及高精度浮点数转二进制区间时，如果你错了一位，你的整个解压过程就会报错。压力主要来自于 FM-index 项目，你需要在一个只有几十 MB 内存的虚拟环境中搜索几 GB 的文本，如果你的辅助数组（如 Occ 数组）设得太大，你的程序会因为‘内存溢出’而挂掉。及格极难，拿 HD 需要你对‘时间空间权衡 (Space-Time Trade-off)’有像素级的掌控力。挂科风险显著存在于对‘BWT 逆变换’物理本质的模糊认知上。

🎯 备考重点与高分策略

高分秘籍：‘得 FM-index 搜索路径者得 Distinction，得小波树证明者得 HD’。期末考试中，手动执行一个带 LCP 数组的后缀数组区间搜索是必考的 30 分大题。一定要练到能秒写出‘LF-mapping 的递归定义’。重点攻克‘如何利用 Rank/Select 操作优化 BWT 的 Occ 统计’，那是区分普通码农与顶级高性能算法专家的标志。备考时，教材《Compact Data Structures》(Gonzalo Navarro) 是唯一的圣经。对于项目，HD 的关键在于‘极简存储’——不仅功能对，还要通过代码证明你使用了 Bit-packing 来压榨每一位空间。重视 Tutorial 里的每一道熵权计算题。

📚 学习建议与资源推荐

神级资源：Gonzalo Navarro 的个人主页，那里有全球最先进的紧凑数据结构论文。如果 BWT 理解不了，强烈推荐去 YouTube 搜‘MIT - Algorithms for DNA Sequencing’专题。最重要的建议：养成‘先推导位掩码 (Bitmask)，再写实现’的习惯。利用好 C++ 的 `std::bitset` 或手写位操作库。学会使用 `Valgrind --tool=massif` 监控你的堆内存占用。加入 UNSW 的算法研究组探讨高性能计算。

⚠️ 作业与 Lab 避坑指南

项目避坑：千万不要在第 10 周才去集群提交代码！由于评测环境通常基于特定的 Linux 内核和位宽，你的代码在 Mac 上能跑但在评测机上可能会报错。Assignment 写作中，严禁有任何冗余的数据结构副本，尽量使用‘原地 (In-place)’算法。此外，注意 Final 考试有 Hurdle，关于‘前缀编码基本定义’的基础证明如果错太多会直接挂。考试时，带好直尺和各色铅笔，画出的后缀树拓扑图必须清晰标准。注意：分清‘压缩搜索’与‘先解压再搜索’在效率上的数量级差异。

💬 过来人经验分享

学长建议：这门课是为你进入 Google 搜索架构部、Illumina 测序研发组或顶级量化交易（处理海量历史数据）拿的‘神谕通行证’。学完后，你眼中的数据不再是字节，而是一个由熵增限制、位流分布和后缀链接定义的完美信息压缩体。建议找一个同样追求‘算法极致美感’的队友共同打磨代码。拿 HD 的关键：在报告中展现出你对‘自索引结构在非易失性内存 (NVM) 中的潜在优化’的深刻理解。坚持住，通关 9319，你就真正具备了挑战计算科学最核心难题——效率——的底层基因。这张成绩单是进入全球顶级高性能开发部最有力的金字牌。记住：最好的存储，是能直接搜索的压缩。