最小差异补丁算法

Question

我正在试图传达两个字节流之间的差异。我希望尽量减少补丁中的字节数。

（我不一定想要最小化差异中“更改”的数量，这是莱文斯坦距离计算中最优补丁给我的东西。）

补丁最好采用这样的格式，即在给定源字节流和差异的情况下，容易重构目标字节流。

是否有一个好的算法可以做到这一点？

---

编辑：为了记录，我已经尝试发送“在位置506处插入以下字节…”形式的更改，其中我从莱文斯坦距离算法创建了更改列表。

我的问题是莱文斯坦距离算法给我很多类似于：

at spot 506 substitute [some bytes1]
at spot 507 do nothing
at spot 508 substitute [some bytes2]
at spot 509 do nothing
at spot 510 substitute [some bytes3]
...

这是因为Levenshtein距离算法试图最小化更改的数量。然而，对于我的需求来说，这个指令集是浪费的。如果一个算法只是说，“...”可能会更好。

At spot 506 substitute [some bytes1, [byte at spot 507], some bytes2, [byte at spot 509], some bytes3, ...]

也许有一些方法可以修改Lev Distance以更喜欢这些类型的更改，但这似乎有点棘手。我可以在获取更改列表后合并替换（我将尝试这样做），但也许还有机会合并删除/插入，而如何正确地执行这种操作则不那么明显。

只是想知道是否有专门针对此类问题的算法（或者是否已经对Lev Distance进行了修改以更喜欢这些类型的更改）。

- user1435114

Answer 1

您可以使用带有亚线性间隙成本的 两两比对来实现这一点，对于长度分别为 n 和 m 的两个字符串，时间复杂度为 O(nm)。

首先声明：没有一种方法可以找到一个可证明的最小补丁（以使用的位或字节计）。那是因为如果有这样的方法，那么可以使用计算它的函数 shortest_patch(x，y)来通过使用shortest_patch（''，s）调用它来找到任何给定字符串s的可证明最小压缩，而科尔莫夫复杂性告诉我们，给定字符串的最短可能压缩在形式上是不可计算的。但是，如果编辑倾向于在空间中聚集，就像在这里看起来一样，那么肯定可以找到比使用传统的Levenshtein距离算法产生的更小的补丁。

编辑脚本

在计算机科学中，补丁通常称为“编辑脚本”。找到将一个字符串x转换为另一个字符串y的最小（以插入和删除次数计算）编辑脚本相当于在最优两两比对中找到每一对相等字符的值为0，每一对不相等字符的值为-inf，并且每个位置上，在一个字符与-间隙字符对齐的情况下，值为-1。比对很容易可视化：

st--ing    st-i-ng
stro-ng    str-ong

这是两个字符串 sting 和 strong 的最优对齐方式，根据该模型，每个对齐的成本为-3。如果将不相等字符对的值设为-1而不是-inf，则可以得到一个成本等于Levenshtein距离的对齐（插入数量加上删除数量再加上替换数量）：

st-ing    sti-ng
strong    strong

这是新模型下的两个最佳对齐方式，每个对齐方式的成本为-2。

为了看到它们如何与编辑脚本相对应，我们可以将顶部字符串视为“原始”字符串，将底部字符串视为“目标”字符串。包含不相等字符对的列对应于替换，顶行包含-的列对应于字符插入，底行包含-的列对应于字符删除。您可以通过使用“指令”(C)复制，(D)删除，(I)插入和(S)替换来从对齐中创建编辑脚本。每个指令后面跟着一个数字，表示要从对齐中消耗的列数，在I和S的情况下，还有要插入或替换的相应数量的字符。例如，前面2个对齐的编辑脚本为

C2, I1"r", S1"o", C2     and     C2, S1"r", I1"o", C2

增加成串

现在，如果我们有像 mississippi 和 tip 这样的字符串，我们发现这两个对齐方式：

mississippi
------tip--

mississippi
t---i----p-

两者得分相同，都是-9：它们都需要相同数量的插入、删除和替换。但我们更喜欢上面那个，因为它的编辑脚本可以更简洁地描述：D6，S1“t”，C2，D2。第二个的编辑脚本将是S1“t”，D3，C1，D4，C1，D1。

为了让对齐算法也“偏爱”第一个对齐，我们可以调整间隙成本，使“开始间隙块”的成本高于“继续现有间隙块”。如果我们使包含间隙的列成本为-2而不是-1，当前一列不包含间隙时，则我们实际上正在惩罚连续间隙块的数量（因为每个连续间隙块显然必须有一个第一个位置）。在这种模型下，上面的第一个对齐现在成本为-11，因为它包含两个连续的间隙块。第二个对齐现在成本为-12，因为它包含三个连续的间隙块。换句话说，算法现在更喜欢第一个对齐。

这种模型，在其中每个包含间隙的对齐位置的成本为g，而任何连续的间隙列中的第一个位置的成本为g + s，称为仿射间隙成本模型，并且Gotoh在1982年提出了一个O（nm）算法： http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf。增加间隙开放成本s将导致对齐片段聚集在一起。您可以尝试使用各种成本参数，直到获得看起来合适且足够小的对齐（对应于补丁）。

- j_random_hacker

Answer 2

解决这种问题有两种方法：

1）建立一种语言，用于 X（在此情况下为编辑脚本），并找出如何将适用句子的长度最小化；或者，

2）计算某种最小表示形式，用于 Y（字符串差异），然后想出一种以最短形式表示这种差异的方法。

Myers 论文证明，对于特定的语言，找到最小变更集合和找到变更表示的最小长度是相同的问题。

显然，改变语言可能会使该假设失效，某些变更可能非常难以正确应用（例如，假设语言包括原语 kP，表示删除下一个索引为质数的 k 个字符。对于某些差异，使用该原语可能会产生巨大收益，但这类应用场景可能相当罕见。我知道这是一个荒谬的例子，但它展示了从一种语言开始的困难之处。)

因此，我建议从最小更改列表开始，该列表识别插入和删除。我们以直接的方式将其转换为一系列命令字符串，其中恰好有三个命令。这里没有索引。想法是我们从原始字符串的开头开始，然后按顺序执行命令。这些命令是：

=  Advance the cursor without altering the character it points to
Ic Insert the character `c` before the cursor.
D  Delete the character at the cursor.

虽然我说过有确切的三个命令，但事实并非如此；实际上有 A+2 个命令，其中 A 是字母表的大小。

这可能会得到像这样的字符串：

=========================IbIaInIaInIaDD=D=D============================

现在，让我们尝试压缩这个。首先，我们运行长度编码（RLE），以便每个命令都在重复计数之前，并且我们删除尾随的=。

27=1Ib1Ia1In1Ia1In1Ia2D1=1D1=1D

（实际上，RLE 重新创建索引，尽管它们是相对而不是绝对的。）

最后，我们使用 zlib 压缩生成的字符串。我这里不会做，但只是为了给出一些压缩可能产生的想法：

27=1Ib1Ia1In||2D1=1D|
      ______+|  ____+
      ___<---+

（尝试显示反向引用。这不是很好的ASCII艺术，抱歉。）

Liv-Zempell非常擅长查找和优化意外的重复。事实上，我们本可以直接使用它而不需要执行中间的RLE步骤，但经验表明，在RLE非常有效的情况下，最好对RLE进行LZ编码而不是源。但尝试两种方式以查看哪种更适合您的应用程序将是值得的。

- rici

Answer 3

这是一种常见的方法，使用非常少的字节（虽然不一定是理论上最优的字节数）：

1. 用某个字符（例如零）填充字节，直到它们具有相同的长度。
2. 将两个流进行异或操作。这将导致一个字节流，在其中字节相同时为零，在其他情况下为非零。
3. 使用任何压缩算法（例如LZW）压缩异或后的流。

假设您拥有的补丁是文件的一小部分的本地化更改，那么这将导致非常短的补丁，因为文件的大部分都是零，可以有效地压缩。

要应用补丁，只需解压缩异或字符串，然后将其与要打补丁的字节流进行异或运算。这将计算出：

原始XOR（原始XOR新）=（原始XOR原始）XOR新=新

因为XOR是可结合和自反的。

希望这能帮到您！

- templatetypedef

---

嗯，我不知道压缩算法有多好，但我的字节流平均为1k字节。许多对只涉及微小更改（在1到5个字节的范围内）。异或字符串的长度将为1k...假设99％的压缩，我仍然使用10个字节来传达1个字节的更改。似乎我们可以通过形式为“在位置506插入0101010”的指令做得更好。（也许这需要5个字节）我需要传达很多补丁，因此这种差异实际上很重要。（此外，99％的压缩可能过于乐观。） - user1435114

我更新了原始答案以更好地反映我目前所做的。 - user1435114

Answer 4

有一种新的有前途的变化检测方法。 序列比对问题被视为协作文本编辑中变化检测的抽象模型，旨在最小化合并冲突的可能性。定义了一种新的成本函数，作为检测到的变化与随机字符串之间交集的概率。 结果应更类似于补丁长度最小化而不是其他已知方法。 它避免了LCS和其他方法的已知缺点。 已提出了三次算法。 http://psta.psiras.ru/read/psta2015_1_3-10.pdf

- Сергей Знаменский