模式匹配在计算机科学中被视为核心操作之一，尤其是基于著名的Burrows-Wheeler变换（BWT）的解决方案。BWT的成功源于其模式匹配算法——反向搜索，这一算法不仅在RAM模型中接近最优，还能直接在输入字符串的压缩表示上运行。
近期，反向搜索被推广至Wheeler确定性有限自动机（DFA），这一子类的标准DFA在保持接近最优的时间效率的同时，找到了在生物信息学中的应用。研究表明，特定的人类染色体全基因组图可以转化为Wheeler DFA，并使用这一策略进行索引。
然而，这种基于BWT的Wheeler DFA索引继承了反向搜索的一个显著缺点，即在算法执行过程中触发大量的I/O操作，最坏情况下这些操作的数量下限由模式的长度决定。为了解决这一限制，本文提出了第一个专门为Wheeler DFA设计的缓存友好算法。我们的新数据结构通过采用类似于后缀数组的策略，减少了I/O操作的数量：它将二分搜索与自动机的快速顺序扫描交错进行。
我们通过在真实的Wheeler全基因组图上运行算法，实证验证了这一新的索引策略。结果表明，尽管我们的数据结构可能需要反向搜索的15倍空间，但速度可快达500倍，并且能够在不到3纳秒的时间内处理单个字符模式。
博主点评： 本文提出的算法通过有效减少I/O操作，显著提升了Wheeler DFA的性能，为生物信息学中的模式匹配问题提供了新的解决方案，展现了理论与实践结合的潜力。值得关注的是其对空间复杂度的权衡，未来的研究可以进一步优化此算法以适应更广泛的应用场景。