- 一种改进的算法可以解决(k, k^(1+o(1)))-gap编辑距离问题，时间复杂度为O(n/k + k^2)。 - 通过利用字符串的分块周期性和断点的概念，可以优化算法的运行时间。 - 该算法将问题分解为多个子问题，每个子问题的块周期性较小。 - 通过对断点进行采样，可以确定每个子问题的匹配位置。 - 该算法在一定条件下可以达到近似最优的效果，对于较大的k值，优于之前的算法。 - 该算法的时间复杂度在理论上是接近最优的，但仍存在一些开放问题。 - 一种用于有界块周期性的算法的证明。 - 该算法使用树距离框架，将编辑距离的计算分解为独立的子任务。 - 树距离定义了一棵分区树，将字符串X和Y分成多个子串，并定义了限制在[-L, L]范围内的树距离。 - 引理4.3证明了树距离与编辑距离之间的关系，给出了树距离的下界和上界。 - 引理4.4给出了树距离的上界，限制了Yv,s和Y'v之间的差异。 - 这些结果为后续的算法提供了基础。 - Lemma 4.6: 精确采样引理保证从分布中准确近似抽取的值。 - Lemma 4.7: 计算平移值的最小值的算法。 - Lemma 4.8: 确定两个字符串是否接近的匹配测试算法。 - Lemma 4.9: 确定字符串是否具有p周期性的p-周期性测试算法。 - Lemma 4.11: 用于近似周期字符串之间编辑距离的快速平移ED算法。 - Lemma 4.12: 解决树距离问题的算法3的正确性。 - Lemma 4.13: 当编辑距离小于或等于k时，分区树中未匹配节点的数量。 - Lemma 4.14: 当编辑距离小于或等于k时，分区树中活动节点的数量。 - Lemma 4.15: 解决树距离问题的算法3的运行时间。 - Lemma 3.1: 解决字符串X和Y上的GapED问题的有界块周期性算法。 - Theorem 5.1: 动态近似ED算法，用于维护和近似字符串之间的编辑距离。 - Corollary 5.2: 具有简化参数的动态近似ED算法。 - Lemma 5.3: 计算模式和文本子串之间编辑距离的近似值。 - Lemma 5.4: 两个p周期性字符串之间编辑距离的3近似值。 - Lemma 4.10提供了一种计算具有给定周期的两个字符串之间编辑距离的近似值的方法。 - 其中一个字符串的长度可以改变而不影响距离。 - 该算法使用加权图来计算近似值。 - 算法的运行时间主要由Lemma 5.3的应用决定。 - 算法的正确性基于Lemma 5.4。 - 提供了与编辑距离近似算法相关的各种参考文献。