OT算法-transform代码解析

(operational-transformations)
此篇文章写给一同在进行ot算法实践中的朋友们,希望抛砖引玉,有对ot算法感兴趣的小伙伴可以联系我一下,目前关于此算法的一些细节处理上我还有一点点的疑惑部分,希望能讨论解决

Purpose 目的

在目前的ot算法中,对我们来说就是一个黑盒,我们知道给一定的输入,它会有正确的输出,但是它是如何做到的呢?
在介绍它的实现之前,我们需要抽象一下我们的操作行为,在之前我们的描述都是

第3个字符行后面插入了一个‘d’
这里怎么转换成程序识别或者能用代码表达的呢?其实这也是OT的关键。
这里我直接揭晓答案:

所有对文本的操作都可以抽象成三个原子行为:
R = Retain,保持操作
I = Insert,插入操作
D = Delete,删除操作

那之前的行为

第3个字符行后面插入了一个‘d’
就会变成

R(3), I(‘d’)
也就是保持三个字符后插入1个‘d’,其实应该也很好理解,这里的操作就像操作数组一样,不管干什么,第一步你得先找到操作的下标。
有了这三个原子以后,我们就可以看到:

A = R(3),I(‘c’)
B = R(3), I(‘d’)

代码

一切准备就绪,我们可以开始看OT了,这里OT算法现在已经很成熟了,
我们可以看看它的核心代码(有删减,理解起来可能会比较复杂,感兴趣的可以深入思考一下):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Transform takes two operations A and B that happened concurrently and
// produces two operations A' and B' (in an array) such that
// `apply(apply(S, A), B') = apply(apply(S, B), A')`. This function is the
// heart of OT.
// 上面这个公式就是OT的核心,它产生了A',B',同时保证执行结果一致,S就是我们开始的状态,可以把这个和菱形图对应起来
// 整体执行流程有点像合并排序的过程。两个下标指针分别往前走

TextOperation.transform = function (operation1, operation2) {
// operation1, operation2就是我们的A,B

var operation1prime = new TextOperation(); // 就是A'
var operation2prime = new TextOperation(); // 就是B'
var ops1 = operation1.ops, ops2 = operation2.ops;
var i1 = 0, i2 = 0;
var op1 = ops1[i1++], op2 = ops2[i2++];
while (true) {
// At every iteration of the loop, the imaginary cursor that both
// operation1 and operation2 have that operates on the input string must
// have the same position in the input string.
// 其实这里就是说transform的核心是保证两者的下标一致,这样操作的才是同一个位置的数据
// ...
// next two cases: one or both ops are insert ops
// => insert the string in the corresponding prime operation, skip it in
// the other one. If both op1 and op2 are insert ops, prefer op1.
// 如果A是插入操作,A'一定也是插入,但是B'就不一样了,因为A是插入,不管你B是啥,你先等等,所以retain一下,保证下标一致
// 这里实际上有三种情况,A是插入,B可能是R,I,D
if (isInsert(op1)) {
operation1prime.insert(op1);
operation2prime.retain(op1.length);
op1 = ops1[i1++];
continue;
}
// 如果B也是插入,那B’就是插入,但是你的A'也得retain一下,保证下标一致
// 这里可能有两者情况,A可能是R,D
// 实例化思考一下,A [R(3),I('a')],B [I('b')],那对于A'来说就应该是[R(4),I('a')]
if (isInsert(op2)) {
operation1prime.retain(op2.length);
operation2prime.insert(op2);
op2 = ops2[i2++];
continue;
}
// ...
var minl;
if (isRetain(op1) && isRetain(op2)) {
// R和R处理
} else if (isDelete(op1) && isDelete(op2)) {
//D和D处理
} else if (isDelete(op1) && isRetain(op2)) {
// D和R处理
} else if (isRetain(op1) && isDelete(op2)) {
//R和D处理
}
}
return [operation1prime, operation2prime];
};

解释

这里就是OT的transform实现,本质上就是把用户的原子操作数组拿到以后,然后做transform操作,这里我只选了一小段来大概解析下,具体的可以看注释,其实原本的注释已经很全了。
其实上面那段代码,因为我们的原子操作只有三种,根据排列组合,最多只会有9种情况,只是上面把很多情况合并了,你要是不理解,也可以拆开,帮助理解。
其中transform才是我们理解的核心