一种高效率的实时协同编辑中的意图保持操作转换算法

作者：蔡维纬; 何发智; 吕晓

来源：计算机学报, 2015, 38(10): 2041-2053.

• 实时协同编辑
• 并发控制
• 操作转换
• 社交网络

作为一类高级分布式系统,实时协同编辑系统允许不同地点的用户同时编辑共享文档,具有高响应性和高并发性的特点.操作转换(Operational Transformation,OT)算法能够保留所有用户操作的效果并维护数据的一致性,是协同编辑系统首选的并发控制方法.为了提高远程操作的响应时间,文中提出了一种意图保持的OT算法(Merging Operations based Operational Transformation,MOOT).该算法基于这样一个事实,大多数情况下,协同编辑中插入操作的数量明显多于删除操作.因此,MOOT构造了一种优化的操作历史结构,即删除操作排在插入操作前面,避免算法的计算时间依赖于大多数操作.更进一步,MOOT在重构过程中移除无效操作,有效的压缩了操作历史的大小.为了验证算法的有效性,在不同插入比例情况下,将MOOT算法与当前性能最优的ABT算法进行了对比实验.实验结果表明,MOOT算法具有更高的计算效率,在合理的比例情况下,其计算时间大约是ABT算法的计算时间的十分之一.

• 单位
  软件工程国家重点实验室