优化文本添加和删除列表

Question

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

     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)更快的方法？

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

Answer 1

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

• 规则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) - 基本上是带有附加停止条件的冒泡排序。我不确定是否可以降低这种复杂性，因为由于必须调整位置，标准算法在这里没有用。

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