大字符串快速近似匹配技术

Question

我正在尝试量化两个字符串之间的差异，以便作为变化监控系统的一部分。

我的问题在于，这些字符串很大 - 我经常处理100K+字符的字符串。

我目前使用Levenshtein距离，但计算大字符串的Levenshtein距离非常低效。即使是最好的实现也只能处理O(min(mn))。

由于两个字符串长度大致相同，距离计算过程可能需要花费多秒钟的时间。

我不需要高精度。 1/1000（例如0.1％）的变化分辨率对于我的应用来说已经足够了。

有哪些更有效的字符串距离计算选项？

- Fake Name

---

有趣的问题！您是通过创建矩阵实现Levenstein距离吗？这可能会很慢。现在您还没有写明使用哪种语言，但如果您为每个字符串创建一个字节数组，也许您可以直接迭代它们？我的意思是，如果您只需要处理获取一个数字d - 字符之间的差异，那么10万次迭代应该相当快。我认为您无法获得更低的时间复杂度，但是如果您使用例如Java，您可能会获得恒定的内存，这将产生更快的实际实现。 - Johan S

顺便问一下，你的时间复杂度真的正确吗？ - Johan S

@JohanS - 看起来正确。朴素的字符串比较不适用，因为在字符串开头删除一个字符会导致后面的每个字符都不匹配。 - Fake Name

我找到了这篇论文，但它纯粹是学术性的，我必须承认我现在完全无法理解其中的数学内容，而且我也没有看到任何实现。 - Fake Name

@JohanS - 我还在思考这个问题。我花了一些时间研究那篇论文，据我所知，他们的改进基本上是对其中一种字符串的访问进行限制。他们的模型显然假设其中一个字符串访问代价高，而另一个则免费。 - Fake Name

Answer 1

如果您可以容忍一些误差，可以尝试将字符串分成较小的块，并计算它们之间的配对L距离。

该方法显然会产生准确的替换结果，插入和删除将根据块数产生精度惩罚（最坏情况下，距离为2 * <number of insert/deletes> * <number of chunks>而不是<number of insert/deletes>）

下一步可能是使该过程自适应，我看到两种方法可以做到这一点，具体取决于更改的预期性质：

1. 首先尝试较小的块大小，然后逐渐转向较大的块，并观察每次迭代之间的降幅。这样可以帮助您估计测得距离中有多少误差（虽然我还没有完全搞清楚如何估算）。
2. 一旦找到两个块之间的差异，请尝试确定差异是什么（总共添加/删除了多少字符），并相应地将下一个块向左或向右移动。

- biziclop