并发编辑合并

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 /地址

如果某人删除了您想要插入的节点后该怎么办？为了不破坏模型，删除的节点需要保持连接到列表（幻影），因此服务器在插入这样一个被删除节点后可以插入节点之前的节点（或之前如果两个被删除等）。

这将需要在服务器上清理一些垃圾清理，以便偶尔删除幻像节点，使任何具有以前时间戳的客户端请求无效。

空间明智这不是更多 - 每个字符需要两个更多的指针，也许有点开销。如果你想要一些代码建议评论。