想要做一个多人协同文档编辑器，请问有什么算法可以判断出文档中修改了那部分内容吗？
black11black · 2020-01-16 00:44:04 +08:00 · 2019 次点击这是一个创建于 1759 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题，昨天在折腾 websocket 的 demo，折腾好了以后想做点什么项目
web 聊天好像没啥意思，然后想了想似乎做一个多人协同在线编辑文档不错。 有一个技术上的问题想不明白就是，多人同时连线到一个文档，ws 发送到同步服务器的内容肯定是增量更新，不可能编辑一个大文档把整个文档都发过去，所以快速地查找到哪里修改了些什么是前端必须要做的，
简单想了一下算法，想不太懂。之前用过 beyond compare 那种对比软件，可以光速查找出来两个文档的差异，还有 github 上也是，之前就不太懂是怎么做的。 我想比如你用 lsc，虽然可以 dp 优化，但复杂度仍然是 O(m^2)，一万字的文档时间复杂度是一亿，实在是太过匪夷所思，基本上可以确定 github 和 beyondcompare 不是这么实现的。
那么到底咋做啊？ 求教求教
 |
1
agagega 2020-01-16 01:21:50 +08:00 via iPhone  1
为什么一定要 diff ？虽然我不知道这些系统是如何实现的，但是把编辑的动作建模成一个个事件，然后用类似事件溯源的模式来在另一个客户端上重放事件应该也可以？而且这样要解决冲突似乎要方便点？
|
|
2
agagega 2020-01-16 01:23:00 +08:00 via iPhone
而且 diff 的 lsc 也不是以字符为单位的吧
|
 |
3
casparchen 2020-01-16 02:38:24 +08:00 via iPhone
Operational transformation
|
 |
4
Austaras 2020-01-16 06:27:00 +08:00
存 diff
|
 |
5
learnshare 2020-01-16 09:22:47 +08:00
有论文，可以去研究
|
 |
6
passerbytiny 2020-01-16 09:30:33 +08:00 1
这种东西，你不能用常规的增删改查思路去做。文档差异化对比的方式，不止是性能问题，一致性也保证不了的。你可以考虑 Event Soucring + CQRS。
|
 |
7
RyuZheng 2020-01-16 10:12:01 +08:00 1
|
 |
8
black11black OP @agagega
想了一下，这种追溯操作有递归性，你影响一个后面的全变了。实际情况比如网络突然中断，丢了一个包之类的 |
|
9
agagega 2020-01-18 00:49:26 +08:00 via iPhone
@black11black 能合并的就合并，不能合并的就当作冲突呗，类似 Git merge 一样
|
Select Language