穿越小说排行榜,择天记,小说

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

對前端來說開發(fā)一個在線文檔需要啥技術(shù)？

前言

最基礎的文本編輯功能(哦？好像textarea就可以完成，那如果是富文本呢？)我們需要一個文檔模型來描述文檔；
富文本編輯器，提供富文本的編輯和渲染能力；
協(xié)同功能，不同的用戶對同一份文檔的編輯需要保持大家看到的都是一樣的；
協(xié)同網(wǎng)絡模型，保證服務器和客戶端之間的文檔模型一致；

名詞解釋

OT：一種解決協(xié)同問題的算法；

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名申請、網(wǎng)絡空間、營銷軟件、網(wǎng)站建設、宜都網(wǎng)站維護、網(wǎng)站推廣。

OP：operation的簡稱，在OT中指的是一次操作；

etherpad: 一個實現(xiàn)文檔協(xié)同功能的開源庫；

easysync: etherpad中實現(xiàn)文檔協(xié)同的核心算法，是OT算法的一種，主要用來處理文本協(xié)同；

ot-json：ot算法的一種，顧名思義，是主要用來處理結(jié)構(gòu)化數(shù)據(jù)；

Changeset: 一種描述文檔更改的數(shù)據(jù)格式，用來表示整個文檔的一次修改；

ClientVars ：表示一篇文檔的初始化數(shù)據(jù)，一般由連續(xù)的changeset組合而成；

符號解釋

??|?? ：移動光標；

??·??：疊加；

正文

OT算法

什么是OT算法呢？我們先從頭說起，如果要實現(xiàn)一個多人共同編輯文檔的功能，我們最簡單暴力的做法是啥？

編輯鎖

顧名思義，假如A在編輯文檔，服務端直接將這個文檔加鎖，B如果在這個時候也加入了編輯，由于鎖的存在，B的編輯直接被丟棄。可以看出，這種編輯鎖的實現(xiàn)方式非常粗暴，體驗極其糟糕，當然了，在很多公司(比如我們的某死對頭公司)的一些wiki系統(tǒng)就是用這種實現(xiàn)方式，由于這種實現(xiàn)方式比較簡單，而且體驗很糟糕(內(nèi)容丟失
& 無法實時)，我們這里就不做討論了。

Linux中的diff-patch

Linux中有兩個命令：diff和patch；如果我們能在JS中實現(xiàn)這套算法，那么多人協(xié)同編輯可以這樣做：

用戶打開文檔后和服務端建立長鏈接，保存文檔副本；
用戶編輯的時候如果有停頓(比如3s)，則將現(xiàn)有的文檔和副本進行diff對比，將結(jié)果傳給服務端，更新副本；
服務端更新文檔，將diff結(jié)果通過長鏈接通知到其它用戶，其它用戶使用patch方法更新本地的文檔；

我們來測試下：

# 本地文檔
$ echo '復仇者聯(lián)盟
鋼鐵俠
美國隊長' > test-local.txt
# 生成用戶A編輯后的文檔
$ echo '復仇者聯(lián)盟
鋼鐵俠
綠巨人' > test-userA.txt
# diff兩個文檔
$ diff test-local.txt test-userA.txt > diff-test.patch
# 查看diff-test.patch內(nèi)容
$ cat diff-test.patch
3c3
< 美國隊長
---
> 綠巨人

從diff-test.patch內(nèi)容可以看出，已經(jīng)找出了兩個文檔不同的地方，然后我們再模擬下用戶B的行為：

# 生成用戶B編輯的文檔
$ echo '復仇者聯(lián)盟
黑寡婦
美國隊長' > test-userB.txt
# patch方法更新文檔
$ patch test-userB.txt < diff-test.patch
# 查看test-userB.txt內(nèi)容
$ cat test-userB.txt
復仇者聯(lián)盟
黑寡婦
綠巨人

可以看到，用戶B文檔的第三行已經(jīng)更新為了用戶A修改后的“綠巨人”。但這種實現(xiàn)方式有個問題，因為他是基于行來進行對比的，就會導致很容易出現(xiàn)沖突，比如：

# 生成文件1
$ echo '復仇者聯(lián)盟' > local.txt
# 生成文件2
$ echo '復仇者聯(lián)盟鋼鐵俠' > userA.txt
# diff對比
$ diff local.txt userA.txt > diff.patch

查看diff.patch內(nèi)容：

1c1
< 復仇者聯(lián)盟
---
> 復仇者聯(lián)盟鋼鐵俠

這就意味著如果兩個人同時修改同一行，那必然就會產(chǎn)生沖突，我們測試下:

# 生成文件3
$ echo '復仇者聯(lián)盟美國隊長' > userB.txt
# patch
$ patch userB.txt < diff.patch

以上我們發(fā)現(xiàn)，假如原始文檔是“復仇者聯(lián)盟”，用戶A修改為“復仇者聯(lián)盟鋼鐵俠”，將diff結(jié)果傳給服務端，服務端傳給用戶B，而用戶B只是將文檔改為了“復仇者聯(lián)盟美國隊長”，直覺上我們可以看出，這兩處是不沖突的，完全可以合并成“復仇者聯(lián)盟鋼鐵俠美國隊長”，但實際上的patch結(jié)果卻是這樣的：

$ cat userB.txt.rej
***************
*** 1
- 復仇者聯(lián)盟
--- 1 -----
+ 復仇者聯(lián)盟鋼鐵俠

因此這種基于行的算法還是比較粗糙，體驗上比編輯鎖雖然好了一點，但實際弊端還是比較大，既然基于行的實現(xiàn)無法滿足需求，那有木有可能去基于字符進行diff呢？

diff-patch算法

diff-match-patch^[1]是另一種diff-patch算法的實現(xiàn)，它是基于字符去進行diff的，這里不介紹該算法的細節(jié)了，它的算法在這：diff-match-patch JS實現(xiàn)源碼^[2]。我們直接測試下它的效果

// 示例1
const localText = '復仇者聯(lián)盟';
const userAText = '復仇者聯(lián)盟鋼鐵俠';
const userBText = '復仇者聯(lián)盟美國隊長';

// 結(jié)果為：復仇者聯(lián)盟鋼鐵俠美國隊長
// 示例2
const localText = '復仇者聯(lián)盟';
const userAText = '復仇者聯(lián)盟美國隊長';
const userBText = '復仇者聯(lián)盟鋼鐵俠';

// 結(jié)果為：復仇者聯(lián)盟鋼鐵俠美國隊長
// 示例3
const localText = '復仇者聯(lián)盟';
const userAText = '復仇者聯(lián)盟 美國隊長';
const userBText = '復仇者聯(lián)盟 鋼鐵俠';

// 結(jié)果為：復仇者聯(lián)盟 美國隊長 鋼鐵俠

如上示例已經(jīng)解決了Linux的diff-patch基于行diff的弊端，但仍然存在問題，如上的示例1和示例2如果沒有符號分割，那么結(jié)果是一樣的。

const localText = '復仇者 Iron Man';
const userAText = 'Iron Man 鋼鐵俠';
const userBText = '復仇者 Caption';
// 結(jié)果為：Caption

原始文檔為“復仇者 Iron Man”，用戶A修改為了“Iron Man 鋼鐵俠”，用戶B修改為了“復仇者 Caption”，直覺上其實可以合并為“Caption 鋼鐵俠”，但實際上卻修改為了“Caption ”(注意Caption后面有個空格，鋼鐵俠沒了)，

也就是說diff-match-patch存在丟字符的情況，這個富文本格式的文檔中會是致命的問題，比如丟失了某個 > 可能整個文檔都會亂掉，那么有木有既解決了行匹配沖突問題又解決了丟字符問題的解決方案呢？答案就是本文的重點——OT算法

operation transformation

示例

ot.js^[3]是針對純文本的一種JS實現(xiàn)，我們看下它的實現(xiàn)效果，針對同樣的示例：

const str = '復仇者 Iron Man';
const operation0 = new ot.TextOperation().delete('復仇者 ').retain(8).insert(' 鋼鐵俠');
const operation1 = new ot.TextOperation().retain(4).delete('Iron Man').insert('Captain');

const op = ot.TextOperation.transform(operation0, operation1);
// 結(jié)果：Captain 鋼鐵俠

可以看到這正是符合我們預期的結(jié)果。

原理

看了很多講OT的文檔，基本每一篇都很長，云山霧罩，但其實它的核心原理很簡單。在OT中，我們將文檔的操作分為三個類型，通過組合這三個原子操作完成對整個文檔的編輯工作：

insert(插入字符)；
delete(刪除字符)
retain(保持n個字符，也就是移動光標)；

注：實際上diff-match-patch算法也將操作分為三類：insert，delete，equal(不變的字符)，insert、delete和OT中含義類似，equal是指對比diff過程中那些沒有改變的字符，diff-match-patch會給這些不同類型的字符打標，后面patch的時候再根據(jù)不同類型的字符做對應的邏輯處理。

insert

|
復仇者聯(lián)盟|

如上|代表的是光標的位置，從上到下模擬用戶操作的行為，以上操作使用ot.js來描述：

const str = '';
const operation = new ot.TextOperation().insert('復仇者聯(lián)盟');
const result = operation.apply(str); 
console.log(result); // 復仇者聯(lián)盟

op創(chuàng)建時會有一個虛擬光標位于字符的開頭，在一個op結(jié)束時，光標一定要在字符串的末尾，其中insert會自動移動光標位置，因此我們這里不需要手動去移動光標；

retain

|復仇者聯(lián)盟
復仇者聯(lián)盟|
復仇者聯(lián)盟鋼鐵俠|

如上過程用ot.js來描述：

const str = '復仇者聯(lián)盟';
const operation = new ot.TextOperation().retain(5).insert('鋼鐵俠');
const result = operation.apply(str); 
console.log(result);// 復仇者聯(lián)盟鋼鐵俠

delete

|復仇者聯(lián)盟鋼鐵俠
復仇者聯(lián)盟|鋼鐵俠
復仇者聯(lián)盟|

如上過程用ot.js描述：

const str = '復仇者聯(lián)盟鋼鐵俠';
const operation = new ot.TextOperation().retain(5).delete('鋼鐵俠');
const result = operation.apply(str); 
console.log(result);// 復仇者聯(lián)盟

刪除字符時可以輸入字符，也可以輸入字符數(shù)，實際上源碼中是直接取的??'鋼鐵俠'.length?? 因此對于delete中字符串而言，只要長度正確就可以達到目的，上面代碼改成??delete('123')??不會有任何影響。

transform

前面的代碼我們看到過ot.js的這個方法，正是這個方法實現(xiàn)了diff-match-patch的丟失字符的問題，而transform正是OT中的核心方法。我們先不羅列他的源碼，先看幾個例子：

示例1

原始文檔內(nèi)容(空白文檔)：|
用戶A編輯后的文檔內(nèi)容：鋼鐵俠
用戶B編輯后的文檔內(nèi)容：雷神

對應代碼實現(xiàn)：

const str = ' ';
const operation0 = new ot.TextOperation().insert('鋼鐵俠');
const operation1 = new ot.TextOperation().insert('雷神');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString()); 
// transform后op操作：insert '鋼鐵俠', retain 2  |  retain 3, insert '雷神'
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str))); 
// transform后操作后的字符串： 鋼鐵俠雷神  |  鋼鐵俠雷神

最終結(jié)果是“鋼鐵俠雷神”；

transform的操作過程：

循環(huán)次數(shù)	op1	op2	operation1prime	operation2prime
1	3	2	insert('鋼鐵俠')	retain(3)
2	undefined	2	retain(2)	insert('雷神')

示例2

原始文檔：復仇者聯(lián)盟
用戶A：復仇者鋼鐵俠聯(lián)盟
用戶B：復仇者聯(lián)盟美國隊長

對應代碼實現(xiàn)：

const str = '復仇者聯(lián)盟';
const operation0 = new ot.TextOperation().retain(3).insert('鋼鐵俠').retain(2);
const operation1 = new ot.TextOperation().retain(5).insert('美國隊長');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString());
// transform后op操作：retain 3, insert '鋼鐵俠', retain 6  |  retain 8, insert '美國隊長'
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform后操作后的字符串： 復仇者鋼鐵俠聯(lián)盟美國隊長  |  復仇者鋼鐵俠聯(lián)盟美國隊長

最終結(jié)果是“復仇者鋼鐵俠聯(lián)盟美國隊長”；

transform的操作過程：

循環(huán)次數(shù)	op1	op2	operation1prime	operation2prime
1	3	5	retain(3)	retain(3)
2	'鋼鐵俠'	2	insert('鋼鐵俠')	retain(3)
3	2	2	retain(2)	retain(2)
4	undefined	'美國隊長'	retain(4)	insert('美國隊長')

示例3

原始文檔：復仇者聯(lián)盟鋼鐵俠美國隊長
用戶A：復仇者聯(lián)盟鋼鐵俠
用戶B：復仇者聯(lián)盟美國隊長

對應代碼實現(xiàn)：

const str = '復仇者聯(lián)盟鋼鐵俠美國隊長';
const operation0 = new ot.TextOperation().retain(5).delete('鋼鐵俠').retain(4);
const operation1 = new ot.TextOperation().retain(8).delete('美國隊長');
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString());
// transform后op操作：retain 5, delete 3  |  retain 5, delete 4
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform后操作后的字符串： 復仇者聯(lián)盟  |  復仇者聯(lián)盟

最終結(jié)果是“復仇者聯(lián)盟”；

操作過程：

循環(huán)次數(shù)	op1	op2	operation1prime	operation2prime
1	5	8	retain(5)	retain(5)
2	-3	3	delete(3)	-
3	4	-4	-	delete(4)

最終結(jié)果是“復仇者聯(lián)盟”；

示例4

原始文檔：復仇者聯(lián)盟鋼鐵俠美國隊長'
用戶A：復仇者聯(lián)盟
用戶B：復仇者聯(lián)盟美國隊長

對應代碼實現(xiàn)：

const str = '復仇者聯(lián)盟鋼鐵俠美國隊長';
const operation0 = new ot.TextOperation().retain(5).delete('鋼鐵俠美國隊長');
const operation1 = new ot.TextOperation().retain(5).delete('鋼鐵俠').retain(4);
const op = ot.TextOperation.transform(operation0, operation1);
console.log('transform后op操作：', op[0].toString(), ' | ', op[1].toString());
//transform后op操作：retain 5, delete 4  |  retain 5
console.log('transform后操作后的字符串：', op[0].apply(operation1.apply(str)), ' | ', op[1].apply(operation0.apply(str)));
// transform后操作后的字符串： 復仇者聯(lián)盟  |  復仇者聯(lián)盟

最終結(jié)果是“復仇者聯(lián)盟”；

操作過程：

循環(huán)次數(shù)	op1	op2	operation1prime	operation2prime
1	5	5	retain(5)	retain(5)
2	-7	-3	-	-
3	-4	4	delete(4)	-

ot.js中transform的源碼如下：

TextOperation.transform = function (operation1, operation2) {
    // ...
    var operation1prime = new TextOperation();
    var operation2prime = new TextOperation();
    var ops1 = operation1.ops, ops2 = operation2.ops;
    var i1 = 0, i2 = 0;
    var op1 = ops1[i1++], op2 = ops2[i2++];
    while (true) {
      //...
      // 對應示例1第一次循環(huán)的操作邏輯
      if (isInsert(op1)) {
        operation1prime.insert(op1);
        operation2prime.retain(op1.length);
        op1 = ops1[i1++];
        continue;
      }
      // 對應示例1第二次循環(huán)的操作邏輯
      if (isInsert(op2)) {
        operation1prime.retain(op2.length);
        operation2prime.insert(op2);
        op2 = ops2[i2++];
        continue;
      }
      // ...

      var minl;
      // 對應示例2循環(huán)
      if (isRetain(op1) && isRetain(op2)) {
        if (op1 > op2) {
          minl = op2;
          op1 = op1 - op2;
          op2 = ops2[i2++];
        // 對應示例2第三次循環(huán)的操作邏輯
        } else if (op1 === op2) {
          minl = op2;
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        // 對應示例2的第一次循環(huán)操作邏輯
        } else {
          minl = op1;
          op2 = op2 - op1;
          op1 = ops1[i1++];
        }
        operation1prime.retain(minl);
        operation2prime.retain(minl);
       // 對應示例4的第二次循環(huán)
      } else if (isDelete(op1) && isDelete(op2)) {
        if (-op1 > -op2) {
          op1 = op1 - op2;
          op2 = ops2[i2++];
        } else if (op1 === op2) {
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        } else {
          op2 = op2 - op1;
          op1 = ops1[i1++];
        }
      // 示例3的第二次循環(huán)
      } else if (isDelete(op1) && isRetain(op2)) {
        if (-op1 > op2) {
          minl = op2;
          op1 = op1 + op2;
          op2 = ops2[i2++];
        } else if (-op1 === op2) {
          minl = op2;
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        } else {
          minl = -op1;
          op2 = op2 + op1;
          op1 = ops1[i1++];
        }
        operation1prime['delete'](minl "'delete'");
      // 示例3的第三次循環(huán)
      } else if (isRetain(op1) && isDelete(op2)) {
        if (op1 > -op2) {
          minl = -op2;
          op1 = op1 + op2;
          op2 = ops2[i2++];
        } else if (op1 === -op2) {
          minl = op1;
          op1 = ops1[i1++];
          op2 = ops2[i2++];
        } else {
          minl = op1;
          op2 = op2 + op1;
          op1 = ops1[i1++];
        }
        op                                                

                                                新聞標題：對前端來說開發(fā)一個在線文檔需要啥技術(shù)？                                                

                                                文章分享：http://fisionsoft.com.cn/article/dhohpig.html

新聞中心

前言

名詞解釋

符號解釋

正文

OT算法

編輯鎖

Linux中的diff-patch

diff-patch算法

operation transformation

示例

原理

insert

retain

delete

transform

其他資訊