併發編輯合併

Question

我試圖實現簡單的併發編輯模型。向文件添加和刪除數據由事件處理。事件的 過程：

1. 詢問變化ID（基本上是時間戳）
2. 從服務器獲取ID
3. 發送改變到服務器與ID（變化由索引的，事件類型（ADD，刪除），（對於ADD））
4. 服務器得到改變
5. 事件隊列是先到先得（多變化可以有相同的原始字符串）可選字符，所以我申請活動內容
6. 新的內容應該是下一個事件庫，所以下一個事件索引需要移動（合併）。

問題是如何合併新的內容和基礎（多個事件可以有相同的基礎）。

服務器具有字符串："Hello Worl"

2客戶端想改變，都得到這樣的基地。 C1增加 「」 索引5（從0開始計數） C2加 「d」 來索引10.

因爲 「」 然後加入 「d」 將導致"Hello, Wordl"。 索引應該移動+1（在這種情況下）。

一般情況下我們可以同時有更多的事件，所以合併會更加複雜。差異可能是+10或-5等

什麼是一個很好的方法來檢測基地索引X之前的內容有多少變化？

我正在使用python。

編輯：

我想過這個問題，我想我知道這將是解決這個問題的好辦法。 可以說我們有字符串abcdefg和abdeg。我現在想擴展第二個字符串，以便它匹配第一個字符串：abcdefg --ab＃de＃g。從這我可以看到變化在哪裏。我不在乎替換隻能插入和刪除。這個東西在大多數情況下都能正常工作，但會出現像aaaaaa和aa這樣的問題，但這些字符串在我的系統中是不太可能的。任何人都知道我應該用什麼來實現這個目標？

Answer 1

我能想到的唯一方法是跟蹤鏈表。服務器可以通過在新節點周圍重新附加列表來在節點之後插入字符，並且刪除類似。您不需要發送索引，而是向服務器發送節點ID /地址

如果某人刪除了您想要插入的節點後該怎麼辦？爲了不破壞模型，刪除的節點需要保持連接到列表（幻影），因此服務器在插入這樣一個被刪除節點後可以插入節點之前的節點（或之前如果兩個被刪除等）。

這將需要在服務器上清理一些垃圾清理，以便偶爾刪除幻像節點，使任何具有以前時間戳的客戶端請求無效。

空間明智這不是更多 - 每個字符需要兩個更多的指針，也許有點開銷。如果你想要一些代碼建議評論。