9

我有一个包含文本添加和删除位置的列表，如下所示：

     Type   Position   Text/Length
1.   +      2          ab          // 'ab' was added at position 2
2.   +      1          cde         // 'cde' was added at position 1
3.   -      4          1           // a character was deleted at position 4

为了更清楚，这就是这些操作的作用：

    1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    ---------------------------------
    t | e | x | t |   |   |   |   |  
1.  t | a | b | e | x | t |   |   |  
2.  c | d | e | t | a | b | e | x | t
3.  c | d | e | a | b | e | x | t |

动作的数量可以减少到：

     Type   Position   Text/Length
1.   -      1          1           // 't' was deleted at position 1
2.   +      1          cdeab       // 'cdeab' was added at position 1

或者：

     Type   Position   Text/Length
1.   +      1          cdeab       // 'cdeab' was added at position 1
2.   -      6          1           // 't' was deleted at position 6

这些操作将保存在我的数据库中，并为了优化这一点：如何减少为获得相同结果而要执行的操作数量？有比 O(n*n) 更快的方法吗？

请注意，这些操作是按时间顺序排列的，更改操作的顺序会产生另一个结果。

4

6 回答 6

3

不是解决方案，只是一些想法：

  • 规则 1：如果两个连续的操作没有重叠的范围，它们可以交换（调整位置）
  • 规则 2：同一位置的两个连续插入或移除可以连接
  • 规则 3：当一个插入之后是一个完全包含在插入中的移除时，它们可以被连接

我没有看到最短解决方案的简单算法。但是，使用规则 1 + 2 的启发式方法可能是：

  • 将操作“向上”移动，除非
    • 你会违反规则 1
    • 你会在移除之前移动插入
    • 职位低于前任
  • 在同一位置加入连续的插入/删除

应用于示例，这将意味着：

 + 2 ab
 + 1 cde
 - 4 1

规则 1 (2x)：

+ 2 ab
- 1 1   // position adjusted by -3
+ 1 cde

.

- 1 1  
+ 1 ab  // position adjusted
+ 1 cde

规则 2：

- 1 1
+ 1 cdeab // watch correct order!

原始实现将是 O(N*N) - 基本上是带有附加停止条件的冒泡排序。我不确定是否要降低这种复杂性，因为标准算法在这里没有用，因为必须调整位置。

但是，您可能能够显着改善事情 - 例如，您不需要“完整排序”

于 2010-01-16T16:15:13.747 回答
2

在应用所有更改之前和之后制作表示文档的二叉树。每个节点代表原始文本或插入/删除的文本；后一种节点包括要删除的原始文本数量（可能为 0）和要插入的文本字符串（可能为空）。

最初，树只有一个节点，“0 到结尾：原始文本”。尽可能将所有更改应用到它合并更改。然后从头到尾遍历树，发出最后一组编辑。这保证产生最佳结果。

  • 应用插入：在树中找到适当的点。如果它在插入文本的中间或相邻，只需更改该节点的文本到插入字符串。否则添加一个节点。

  • 应用删除：查找树中的起点和终点——与插入不同，删除可能覆盖整个现有节点范围。相应地修改开始和结束节点，并杀死中间的所有节点。完成后，检查是否有相邻的“插入/删除文本”节点。如果是这样，加入他们。

唯一棘手的一点是确保您可以在树中找到点，而不是每次进行更改时都更新整个树。这是通过在每个节点缓存由该子树表示的文本总量来完成的。然后，当您进行更改时，您只需在您更改的节点正上方的节点上更新这些缓存值。

如果您费心实现平衡树并为插入的文本使用绳索，那么对于所有输入，这对我来说严格来说是 O(n log n)。如果你放弃整个树的想法并使用向量和字符串，它是 O(n 2 )，但在实践中可能工作得很好。

工作示例。以下是该算法如何逐步应用于您的示例。我不会做复杂的ascii艺术，而是将树倒过来，按顺序显示节点，并通过缩进显示树结构。我希望这很清楚。

初始状态：

*: orig

我在上面说过，我们将缓存每个子树中的文本量。这里我只是放了一个 * 来表示字节数，因为这个节点包含整个文档，我们不知道它有多长。您可以使用任何足够大的数字，例如 0x4000000000000000L。

在位置 2 插入“ab”后：

    2: orig, 2 bytes
*: insert "ab", delete nothing
    *: orig, all the rest

在位置 1 插入“cde”后：

        1: orig, 1 byte
    5: insert "cde", delete nothing
        1: orig, 1 byte
*: insert "ab", delete nothing
    *: orig, all the rest

下一步是删除位置 4 处的字符。在这里暂停一下，看看我们如何在树中找到位置 4。

从根开始。查看第一个子节点：该子树包含 5 个字符。所以位置4必须在那里。移动到该节点。查看它的第一个子节点。这次它只包含 1 个字符。不在里面。此编辑包含 3 个字符，因此也不在此处；紧随其后。移动到第二个子节点。（这个算法大约有 12 行代码。）

在位置 4 删除 1 个字符后，你会得到这个......

    4: orig, 1 byte
        3: insert "cde", delete nothing
*: insert "ab", delete nothing
    *: orig, all the rest

...然后，注意到两个相邻的插入节点，您将它们合并。（请注意，给定两个相邻节点，一个总是在树层次结构中位于另一个之上。将数据合并到较高的节点；然后删除较低的节点并更新其间的缓存子树大小。）

    1: orig, 1 byte
*: insert "cdeab", delete nothing
    *: orig, all the rest
于 2010-01-17T13:37:54.997 回答
1

源代码控制系统中使用的“差异”工具使用的算法可以产生将一段源代码转换为另一段源代码所需的最少编辑——这可能值得研究一下。我认为它们中的大多数（最终）都基于这个算法，但是我已经有一段时间没有阅读过这个主题了。

于 2010-01-16T14:38:37.570 回答
1

我相信这可以比平均O(n²) 快得多（很可能输入可以设计为不允许快速分析）。您可以将连续添加或删除视为集合。您可以一次分析一项操作，并且必须进行一些条件转换：

  • 如果一个加法在一个加法或一组加法之后，它可能
    • 触摸（一个或多个）先前的添加：然后，您可以合并这些添加
    • 不要碰：你可以订购它们（你必须调整位置）
  • 如果在一个添加或一组添加之后删除，它可能
    • 只从加法中删除字符：然后，您可以修改加法（除非它会拆分加法）
    • 只删除不属于添加集的字符：然后，您可以将删除移动到添加集之前的位置，或者合并添加；之后，可能必须将当前添加集之前的删除集应用于之前的添加
    • 两者都做：然后，您可以先将其拆分为两个（或多个）删除并应用相应的方法
  • 如果在删除或一组删除之后删除，它可以：
    • 触摸（一个或多个）先前的删除：然后，您可以合并这些删除
    • 不要碰：你可以订购它们（你必须调整位置
    • 在任何情况下，您都必须对先前添加的新形成的删除进行分析
  • 如果在删除之后添加，则此时不需要转换

这只是初稿。有些事情可能必须以不同的方式完成，例如，总是应用所有删除可能更容易或更有效，因此结果总是只有一组删除，然后是一组添加。

于 2010-01-17T00:42:23.193 回答
0

为简单起见，我们假设只有字母 az 出现在您的文本中。

用值 a[i] = i 为 i = 1 到 N 初始化一个列表 A（你自己会弄清楚 N 应该有多大）。

在 A 上执行（模拟）所有操作。在此之后分析 A 以找到所需的操作：

首先通过查找A中缺失的数字来找到所需的删除操作（它们将形成一组连续的值，一组代表一个删除操作）。

在此之后，您可以通过查找连续字母的序列来找到所需的插入操作（一个序列是一个插入操作）。

在您的示例中：

初始化一个：

1 2 3 4 5 6 7 8 9 10

第 1 步（+:2:ab）：

1 ab 2 3 4 5 6 7 8 9 10

第2步（+：1：cde）：

cde 1 ab 2 3 4 5 6 7 8 9 10

第三步（-：4：1）：

cdeab 2 3 4 5 6 7 8 9 10

现在我们搜索丢失的数字以查找删除。在我们的例子中只有一个数字（即数字 1）丢失，所以只需要删除 1 次，所以我们有一个删除操作：-:1:1 （一般情况下可能会丢失更多的数字，每个丢失的数字序列都是一个删除操作，比如1、2、3、5、6、10都是缺失的数字，那么有3个删除操作：-:1:3、-:2:2、-:5:1。记住后面每次删除操作所有索引都会减少，您必须存储以前删除操作的总和来计算当前删除操作的索引。）

现在我们搜索字符序列来查找插入操作。在我们的示例中，只有一个序列：索引 1 处的 cdeab，因此我们有一个插入操作：+:1:cdeab

希望这足够清楚。

于 2010-01-18T14:39:15.193 回答
0

如何减少动作的数量：算法方法可以尝试对动作进行排序。我认为，排序后：

  1. 可以加入相邻动作的机会（以 Svante 和 peterchen 所展示的方式）将会增加。
  2. 这可能导致必须执行的操作最少？

下面的“position-number”代表文本插入或删除的位置。

假设可以交换两个相邻的动作（通过调整这两个动作的位置编号和文本/长度属性），我们可以将动作列表按我们喜欢的任何顺序排列。我建议将删除操作放在操作列表的前面，位置编号升序。在删除操作之后，添加操作按位置编号升序排序。

下面的例子应该说明，为什么我认为可以交换任何相邻的动作。

交换以下操作：

  1. + 2 aaa -> taaaext
  2. - 3 1   -> taaext

屈服于一个动作：

  1. + 2 aa  -> taaext

交换以下操作：

  1. + 3 aaa -> teaaaxt
  2. + 1 bb  -> bbteaaaxt

产生于：

  1. + 1 bb  -> bbtext
  2. + 5 aaa -> bbteaaaxt

交换以下操作：

  1. + 1 bb  -> bbtext
  2. - 2 2   -> bext

产生于：

  1. - 1 1   -> ext
  2. + 1 b   -> bext

如第一个示例所示，在某些情况下，交换会导致删除删除。这是一个有益的副作用。这也是为什么我建议将所有删除内容移到前面的原因。

我希望我没有忘记一些事情并考虑所有情况。

于 2010-01-18T21:06:02.743 回答