3

我试图传达两个字节流之间的区别。我想尽量减少补丁中的字节数。

（我不一定要最小化差异中的“变化”数量，这是 levenshtein 距离计算中的最佳补丁会给我的。）

理想情况下，补丁的格式应使得在给定源字节流和差异的情况下，很容易重建目标字节流。

有没有一个很好的算法来做到这一点？

编辑：为了记录，我尝试发送“在点 506，插入以下字节......”形式的更改，我从 levenshtein 距离算法创建一个更改列表。

我遇到的问题是 levenshtein 距离算法给了我很多变化，例如：

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]
...

这是因为 lev 距离算法试图最小化变化的数量。然而，就我的目的而言，这个指令集是浪费的。如果算法只是说，可能会更好，

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

可能有一些方法可以修改 lev 距离以支持这些类型的更改，但这似乎有点棘手。我可以在获得变更列表后合并替换（我将尝试这样做），但也可能有机会合并删除/插入，而且如何正确地做到这一点不太明显。

只是想知道是否有专门的算法来解决这个问题（或者是否有人已经对 lev 距离进行了修改以支持这些类型的更改）。

4

4 回答 4

2

您可以使用具有仿射间隙成本的成对对齐来执行此操作，这两个长度分别为 n 和 m 的字符串需要 O(nm) 时间。

首先是一件事：就使用的位或字节而言，无法找到可证明的最小补丁。那是因为如果有这样的方法，那么shortest_patch(x, y)计算它的函数可以s通过调用它来找到任何给定字符串的可证明最小压缩shortest_patch('', s)，并且 Kolmogorov 复杂性告诉我们给定字符串的最短可能压缩在形式上是不可计算的. 但是，如果编辑倾向于在空间中聚集，就像它们似乎在这里一样，那么肯定有可能找到比使用通常的 Levenshtein 距离算法生成的更小的补丁。

编辑脚本

补丁在 CS 中通常称为“编辑脚本”。x找到用于将一个字符串转换为另一个字符串的最小（就插入次数加上删除次数而言）编辑脚本y等效于找到最佳成对对齐方式，其中每对相等的字符都有值 0，每对不相等的字符都有值-inf，并且一个字符串中的字符与-间隙字符对齐的每个位置的值都为 -1。对齐很容易可视化：

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

这些是字符串sting和的 2 个最佳对齐方式strong，每个在模型下的成本为 -3。如果不等字符对的值是 -1 而不是 -inf，那么我们得到的对齐成本等于 Levenshtein 距离（插入的数量，加上删除的数量，加上替换的数量）：

st-ing    sti-ng
strong    strong

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

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

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

增加聚束

现在如果我们有像mississippiand这样的字符串tip，我们会发现这两个对齐

mississippi
------tip--

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

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

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

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

于 2012-12-09T07:47:00.043 回答
1

解决此类问题有两种方法：

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），这样每个命令前面都有一个重复计数，并且我们删除了尾随=的 s

27=1Ib1Ia1In1Ia1In1Ia2D1=1D1=1D

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

最后，我们使用 zlib 来压缩生成的字符串。我不打算在这里这样做，只是为了说明它可能会产生的压缩类型：

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

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

Liv-Zempell 非常擅长发现和优化意外重复。事实上，我们可以直接使用它而不是执行中间 RLE 步骤，但经验表明，在 RLE 非常有效的情况下，LZ 比源更好。但是值得尝试两种方法来查看对您的应用程序更好的方法。

于 2012-12-08T20:45:27.223 回答
0

使用很少字节（尽管不一定是理论上的最佳字节数）的常见方法如下：

  1. 用一些字符（可能为零）填充字节，直到它们具有相同的长度。
  2. XOR 两个流在一起。这将导致字节流在所有字节相同的地方为零，否则为非零。
  3. 使用任何压缩算法压缩 XORed 流，可能类似于 LZW。

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

要应用补丁，您只需解压缩 XORed 字符串，然后将其与字节流 XOR 以进行补丁。这计算

原始异或（原始异或新）=（原始异或原始）异或新=新

因为 XOR 是关联和自反转的。

希望这可以帮助！

于 2012-12-08T18:41:13.007 回答
0

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

于 2015-04-08T07:17:33.797 回答