OT算法（Operational Transformation） #

一、保证内容一致性 #

当前内容为：123

• 客户端a：在 "3" 前面插入 “X”（在位置2插入X），Insert(2, 'X')，变成“123X”。
• 客户端b：在 "1" 前面插入 “S”（在位置0插入S），Insert(0, 'S')，变成“S123”。

a接受b的操作，变成“S12X3”；b接受a的操作，变成“S1X23”；操作顺序的不同导致结果不一致。

正确的做法是：a接受b的操作，没有影响，继续原操作；b接受a的操作，发现前面插入了内容，索引发生了改变（+1），Insert(2, 'X')应该变成Insert(3, 'X')，应用新操作后，结果为“S12X3”，实现内容一致性。

通过转换方法产生一个新的操作，使当前字符串应用到转换算法之后两个浏览器的内容保持一致。

二、撤销操作 #

初始内容：“12”

• 客户端a：在“2”后面插入“Y”（在位置2插入Y），O1 = Insert(2, 'Y')，变成“12Y”。
• 客户端b：在“1”前面插入“X”（在位置0插入X），O2 = Insert(0, 'X')，变成“X12Y”。

当前内容：“X12Y”

此时，a撤回操作，Undo(O1)，如果直接执行逆向操作，则结果为“X1Y”，结果不正确。 由于b插入了“X”，导致索引发生变化，Delete(2)应该变成Delete(3)，结果为X12，正确。

撤销操作需要正确执行自己操作的逆向操作，还要保留其他客户端传来的执行结果。

三、操作压缩 #

初始内容：“123”

客户端a进行了四次操作：

• O1 = Insert(2, 'X') => "12X3"
• O2 = Insert(1, 'abc') => "1abc2X3"
• O3 = Insert(2, 'Y') => "1aYbc2X3"
• O4 = Delete(7) => "1aYbc23"

我们希望，这四次操作通过尽可能少的内容和次数给到客户端b，减少数据传输的时间，我们需要对四次操作进行转化。

我们用L = (O1, O2, O3, O4)来代表最后的结果。将O4挪到O2的位置，O4' = Delete(7 - 1 - 1 - 3) = Delete(2)，与O1正好抵消，O2、O3不需要变化，所以L' = (O2, O3)；接着合并O2和O3，得到O2' = Insert(1,'aYbc')；所以L'' = O2'。