Operational Transformation演算法圖解

Operational Transformation演算法解決的問題是如何merge基於相同的狀態產生的不同的操作序列。如下圖所示，從上往下看，基於相同的起點，左右有兩個操作OP1和OP2.為了merge兩個操作為一體，我們可以從兩個方向入手，一個方向是從OP1入手，在執行完OP1後，執行OP2；另一個方向是從OP2入手，在執行完OP2後，執行OP1.但是，簡單的將操作執行，並不正確，以OP1為例，在執行完OP1後，數據的狀態發生了變化，而OP2是基於初始的狀態，所以不能直接執行OP2，而需要將操作做一個變換，以OT（OPA，OPB）作為記號。使用OT演算法後，必須保證，左邊的執行序列OP1，OT（OP2，OP1）執行後的結果，與右邊的執行序列OP2，OT（OP1，OP2）執行後的結果相同。

上圖是對一個【元操作】的定義。真是的場景中，左邊和右邊不可能僅僅有一個操作，而是有多個操作。我們先考慮左邊有兩個操作，右邊只有一個操作。如下圖所示。

OP1和OP3最先merge。圖中到達中軸線的節點。之後，需要將OP2merge進去，必須執行OT（OP2，OP3『）== OT（OP2， OT（OP3， OP1））

再考慮左邊有三個操作，右邊只有一個操作。如下圖所示。

按照左上-右下的輔助線，把merge過程切割成若干步驟。第一步是在右操作為OP4時mergeOP1，第二步是在右操作為OP4『時mergeOP2.第三步是在右操作為OP4『』時mergeOP3。以此類推，可以將merge【左N右1】過程理解成一個遞歸演算法。

上文求解的是左邊有若干操作，右邊只有一個操作的情形。我們繼續擴展，考慮左邊有若干操作，右邊也有若干操作的情形。如下圖所示。

按照右上-左下的輔助線，我們可以將這種求解分割成若干步驟的merge【左N右1】。第一步，左N指的是OP1，OP2，右1指的是OP3.第二步，左N指的是OP1『，OP2』，右1指的是OP4.以此類推，我們可以將merge【左N右M】的過程理解成一個遞歸演算法。

至此為止，我們將最通用的merge【左N右M】的演算法一步步分解下來。下面，我們再考慮一個基本問題，OT（OPA，OPB）指的是基於OPB，對OPA做轉換，轉換的結果是OPA『。如果轉換的結果不是一個操作OPA』，而是一個操作序列「OPA1，OPA2……」呢？如下圖所示。

OT（OP4，OP1）的結果是「OP41，OP42」。求解步驟，首先是求解出OP1『，將問題縮小為左邊「OP2，OP3」，右邊為「OP41，OP42」。然後將問題抽象為【左2右2】，先求解【左2右1】，得到「OP2』，OP3『」；然後將問題縮小為【左2右1】，左為「OP2『，OP3』」，右為OP42.最終求出結果。

現在，我們分析了所有的問題種類。我們可以分析一個具體問題。

在真實場景中，操作OPA和操作OPB可能是互斥的。因此，OT演算法往往是biased OT,即以某一個方向為傾向，假設我們的OT是向右方向biased，為了保證對於互斥的操作，OT演算法的正確性，我們可以定義如圖所示的【元操作】。

因為現在的OT是向右方向傾斜的，所以對於互斥的操作，OP2更優先，所以，只能將OP1變換成空操作（null），而OT（OP2，OP1）必須撤銷OP1的影響，並施加OP2的影響。所以我們引入Reverse（）操作，即求一個操作的逆操作。

在merge【左N右M】的情形下，出現互斥的情況，就可以使用上述的元操作進行解決。

行文至此，我們通過引入Reverse()操作，解決了互斥操作的OT問題。我們繼續加以引申，既然我們接受並引入了Reverse()操作，OT演算法本身就變得足夠靈活，可以應對更複雜的操作對的OT.考慮操作OPA和OPB。有屬性如下：若OPA已執行，則OPB不可執行；若OPB已執行，則OPA可執行。正常的OT示意圖如下圖所示：

顯然，該OT組合是錯誤的。為了使OT組合正確，我們可以使用Reverse()功能。

如圖所示，我們可以發現，只要求出了右方向的OPA』,那麼我們就可以通過Reverse()操作和該OPA，組合成操作序列{Reverse(OPA), OPB, OPA}，該序列就是左方向的OT(OPB, OPA)的結果.

將該結論推廣開，我們完全只需要提供單個方向的OT變換方法，就可以自動得到另一個方向的OT變換方法。但是，代價也是高昂的，那就是，普通的OT變換結果還是一個操作，而上述方法的結果是三個操作，導致performance會有成倍的下降。實踐中，這種tradeoff往往發生在某個OT方法過於複雜時。