我试图量化两个字符串之间的差异，作为变更监控系统的一部分。
我遇到的问题是字符串很大- 我经常可以处理 100K+ 个字符的字符串。
我目前正在使用 Levenshtein 距离，但计算大字符串的 levenshtein 距离非常低效。即使是最好的实现也只能管理O(min(mn)).
由于两个字符串的长度大致相同，因此距离计算过程可能需要很多秒。
我不需要高精度。千分之一的变化分辨率（例如 0.1%）对于我的应用程序来说已经足够了。
有哪些选项可以更有效地计算字符串距离？
问问题
143 次
1 回答
0
如果您可以容忍一些错误，您可以尝试将字符串分成更小的块，并计算它们的成对 L 距离。
该方法显然会为替换、插入和删除产生准确的结果，这会根据块的数量产生准确性损失（最坏的情况会给你一个距离2 * <number of insert/deletes> * <number of chunks>而不是<number of insert/deletes>）
下一步可能是使流程具有适应性，我看到了两种方法，具体取决于更改的预期性质：
- 首先尝试一个小的块大小，然后移动到越来越大的块，并观察每次迭代之间的下降。这应该可以帮助您估计测量距离中有多少是错误的（尽管我还没有确切地知道如何计算）。
- 一旦发现两个块之间的差异，请尝试确定差异是什么（确切地添加/删除了总共多少个字符），并将下一个块相应地向左或向右移动。
于 2015-04-16T18:25:03.153 回答