在线协同编辑的实现
类似google doc,协同编辑就是能够让多人同时编辑同一份文档。用过版本控制的童鞋都知道,用版本控制的一个好处就是,可以方便的多人共同去做一个项目,但有时大家会对同一个文件的同一行进行了修改,这时merge代码的时候,就需要你去手工去解决冲突,而协同编辑同样也面临冲突的问题,这时候就是程序实时的自动去解决冲突了。
现在做协同编辑的已经有很多了,比如google doc,比如facebook面试喜欢用的collabedit,还有最近开源的towtruck这个东西,所以协同编辑还是深受大家欢迎的阿。这里有个英文的协同编辑的实现原理可以作参考。
协同编辑主要来说需要这么几个步骤
1、计算出当前用户的对文档作出的修改发送到服务器
2、对于所有用户对文档进行的修改进行合并以及冲突处理
3、将合并之后结果返回到前段
4、将光标移动到需要的位置
对于第一个步骤而言,就是类似于linux中的diff操作,去比较当前的文档内容和之前的文档内容,来得到用户对于文档的修改。可以对两篇文档,用动态规划的方法,找到最长公共子序列,然后除去公共部分,剩下的就可以得到差异部分了,用动态规划的方法的时间复杂度为O(n^2),网上还有些针对一些情况加速的论文比如《An Algorithm for Differential File Comparison》和《An O(ND) Difference Algorithm and Its Variations》。然后我发现google提供了很好的各种语言的实现,可以去很方便的调用。
得到差异发送到服务器我们就需要进行冲突的合并了,这个步骤叫做operational transformation。
比如用户A在文档字符数3的位置插入了test,用户B删掉了文档字符数5-7的位置,合并之后就变成了用户A在3的位置插入了test,用户B删掉了文档9-11的位置,这样对于所有用户的修改进行合并,再把所有修改告知所有的用户,来确保所有用户显示的内容始终是一样的。
最后就是移动光标的位置到相应的位置上,其实就是判断光标之前的操作都进行了什么,相应的去把光标前后移动就可以了。
基本上按照这个思路,利用comet技术等,多注意一些细节问题,就可以去自己实现一个类似google doc的在线协同编辑器了,我按照这个想法,实现放到了sae上,源代码在这里,有兴趣的可以看看。
建议继续学习:
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:isnowfy 来源: isnowfy
- 标签: 在线协同
- 发布时间:2013-05-01 22:37:49
- [65] Oracle MTS模式下 进程地址与会话信
- [64] Go Reflect 性能
- [64] 如何拿下简短的域名
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [58] 【社会化设计】自我(self)部分――欢迎区
- [58] 图书馆的世界纪录
- [56] android 开发入门
- [53] 视觉调整-设计师 vs. 逻辑
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [45] 界面设计速成