半外存储高效近似模式匹配：空间优势与Landau-Vishkin算法的改进

本文主要探讨了半外存储近似模式匹配（Approximate Pattern Matching, APM）的方法及其在理论计算机科学领域的应用。精确模式匹配是一个广泛应用于文档检索、文本编辑等场景的关键问题，但当涉及到允许一定数量的错误时，问题的复杂性会有所提升，这促使研究者们寻求更高效的解决方案。 Ilie、Navarro和Tinta在2016年提出了一个基于著名Landau-Vishkin算法的改进方案，该算法在解决精确模式匹配问题上展现了优异的速度性能。然而，这个算法的一个主要限制是其对内存的需求，因为结果数组必须全部存储在内存中，这对于处理大规模数据时显得不切实际。针对这一挑战，本文作者Daniel Saad Nogueira Nunes和Mauricio Ayala-Rincón提出了一种实用的半外存储方法，它借鉴了Ilie等人的直接比较变换策略，旨在减少对内存的依赖。 通过实验，当处理的实际数据长度不超过2GB时，新提出的半外存储方法显示出显著的空间效率优势，相比Ilie等人的方法，其空间效率提升了大约5倍。这意味着在处理大型数据集时，这种方法能够在保证算法效率的同时，显著节省宝贵的内存资源，这对于资源有限的系统来说是一项重要的进步。 值得注意的是，这项工作得到了CNPqUniversal 476952/2013-1基金的资助，并且两位作者的部分工作还获得了CNPq高生产力补助金的支持。此外，相关论文可以在《理论计算机科学电子笔记》(Theoretical Computer Science Electronic Notes)的324期（2016年）107-122页找到，可以通过www.sciencedirect.com或www.elsevier.com/locate/entcs进行在线获取。 总结起来，本文的核心贡献在于提供了一种新的、内存友好的半外存储近似模式匹配方法，它在保持算法高效的同时，显著提高了空间效率，对于在实际应用中处理大量文本数据的场景具有重要的实践价值。