[發明專利]一種基于操作轉換的文本編輯實時協同方法

有效

• 申請號: 201410362735.9
• 申請日: 2014-07-28
• 公開（公告）號: CN104077425A
• 公開（公告）日: 2014-10-01
• 發明（設計）人: 何發智;蔡維緯;呂曉
• 申請（專利權）人: 武漢大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 張火春

技術領域

本發明涉及計算機支持的協同領域，尤其涉及一種基于操作轉換的文本編輯實時協同方法。

背景技術

公知，協同編輯是計算機支持的協同工作中的一個重要應用領域。協同編輯作為一種分布式系統，允許地理位置上分散的用戶共同編輯同一對象。為了實現實時協同編輯，每個站點都復制了一個相同的對象，以便達到最短的操作響應時間。然而在網絡環境下，不同用戶的操作必然會發生沖突，并發控制方法就是為了解決高并發情況下的沖突事件能夠無沖突的執行，達成共同的目標。

目前實時協同編輯工作中并發控制策略的主要使用的是操作轉換(Operational?Transformatiopn,OT)的方法。OT是一種樂觀的并發控制方法，允許沖突的發生，通過把操作轉換成另一種執行形式得到一致的結果。具體來說，對本地操作立即執行，因此能夠很好的滿足實時性的要求；對接收到的遠程操作，首先要將該操作對已執行的并發操作進行轉換，然后才執行轉換的結果。OT能夠確保即使在不同站點執行的操作順序不同，最終也能得到一致的結果。

OT從協同編輯系統中抽象出兩個元操作(插入操作，刪除操作),并且認為操作的對象是線性排列結構。最初提出的OT算法被應用于協同文本編輯，即操作的對象是文本對象(字符)。實際上，由于OT轉換的是操作對象的位置，OT可以支持任何線性排列的復雜對象。本發明提出的OT算法同樣可以適用于其他復雜對象的協同。

OT算法通常包含操作轉換函數和控制過程。操作轉換函數負責定義操作之間如何轉換，控制過程主要負責定義某個該操作與哪些操作進行轉換。

基于Lamport定義的“happened-before”[1]理論定義操作之間的先后關系：

定義1因果關系給定任意兩個分別位于站點i和站點j上的操作OP_a和OP_b，稱OP_a和OP_b存在因果關系(記作OP_a→OP_b)，當且僅當OP_a和OP_b滿足下列三個條件之一：(1)i＝j并且操作OP_a發生在OP_b之前；(2)i≠j并且操作OP_a在站點j的執行先于操作OP_b的產生；(3)存在操作OP_x，并且有OP_a→OP_x和OP_x→OP_b。

定義2并發關系給定任意兩個操作OP_a和OP_b，稱OP_a和OP_b存在并發關系(記做OP_a||OP_b)，當且僅當OP_a和OP_b既不滿足OP_a→OP_b，又不滿足OP_b→OP_a。

OT的一致性模型要求能夠保持操作之間的因果關系，結果的一致性以及意圖保持。實際情況下，大多數OT算法利用控制過程對操作施加全序達到唯一的轉換路徑，從而實現結果一致，但是這種方法未能考慮操作之間的位置關系，并不能保證實現意圖保持。圖2描述了全序OT算法不能實現意圖保持的實例。

當出現Ins(p+1,c)操作，對并發的操作序列{Del(p),Ins(p)}進行轉換的時候會出現兩種結果，因此這是一種潛在的導致結果不一致和違背用戶意圖的因素。為了克服上述現有技術的不足，本發明提供了一種基于操作轉換的文本編輯實時協同方法，能夠實現結果一致和意圖保持。其中，意圖保持遵守Lidu[2]提出的保持操作之間的位置關系。

參考文獻：

[1]Lamport?Leslie.Time,clocks,and?the?ordering?of?events?in?a?distributed?system.Communication?of?ACM,1978,21(7):558-565.

[2]Li?Du,Li?Rui.An?admissibility-based?operational?transformation?framework?for?collaborative?editing?systems.Computer?Supported?Cooperative?Work(CSCW),2010,19(1):1-43.

發明內容