（计算机应用技术专业论文）计算机协同编辑系统中若干关键技术的研究.pdf

浙江大学硕士学位论文 摘要 计算机协同编辑系统是计算机支持协同工作( c s c w ) 系统中的一种。它允 许多个用户通过网络同时对同一文档进行编辑。与单用户编辑系统相比，协同编 辑系统能降低开发时问、减少开发成本和提高丌发效率。计算机协同编辑系统可 分为文本和图案( 包括图形和图像) 两种。目前国际上对于文本协同编辑系统的 研究己比较成熟，对图形协同编辑系统的研究正处于热点中，而对图像协同编辑 系统的研究尚未展开。l ， 本文在国际最新研究成果的基础上，对图案协同编辑系统进行了多项深入研 究。具体内容有：1 、一个新的基于多版本的图形协同编辑系统一致性维护算法。 对现有的一致性维护算法进行了改进，提高系统的运行效率；2 、图形协同编辑 系统的语义保持模型。现有的对图形协同编辑系统的研究基本局限于研究文档的 一致性维护问题，即语法保持问题。本文提出了语义保持的概念以及一个语义保 持模型，以提高协同工作的效率；3 、图像协同编辑系统中的致性维护和u n d o 。 图像协同编辑系统的研究在上世纪9 0 年代中期已经基本停止，本文提出了图像 协同编辑系统中进行一致性维护和u n d o 的算法，在增加少量时间开销的基础上 极大地减少了空间开销，首次实现了一个真正基于复制结构的图像协同编辑系 统，论文在a c mc s c w2 0 0 2 会议上发表。这是我国首次在c s c w 领域的主要 会议上发表论文。 ，通过对计算机协同编辑中多个关键技术的研究，以及建立了新一代基于 i n t e m e l 的图案协同编辑原型系统，为今后实现真正的图案协同编辑系统打下了 基础。，卢，、一。 厂1厂 关键字：唾s c w 一萌匿二面编辑系统寸蓬受受三二三面语义保持亍 关键字：r c群件图形协局编辑系统、侈该本一致性! 鲥抄语义保持3 、一，- 、一 ) 、一 ， 图像协同编辑系统) 瓯 l 浙江大学硕士学住论文 a b s t r a c t r e a l - t i m ec o l l a b o r a t i v e e d i t i n gs y s t e m s a r eac l a s so f c o m p u t e r - s u p p o r t e d c o o p e r a t i v ew o r k ( c s c w ) s y s t e m s i nt h e s es y s t e m s ，u s e r sc a nv i e wa n de d i tt h e s a m ed o c u m e n tf r o mg e o g r a p h i c a l l yd i s t r i b u t e ds i t e sc o n n e c t e db yw e b t h e yh a v e m a n ya p p l i c a t i o n s s u c ha st e x t i l e p a t t e md e s i g n ，e l e c t r o n i c c o n f e r e n c e a n d c o l l a b o r a t i v ed o c u m e n t a t i o ne d i ti no r d e rt os h o r t e n i n gt h et i m e ，r e d u c i n gt h ec o s t ， a n d i m p r o v i n g t h eq u a l i t y t h e r ea r et w o c a t e g o r i e so f c o l l a b o r a t i v ee d i t i n gs y s t e m s ：t e x ta n dg r a p h i c s ( i n c l u d i n g o b j e c t b a s e da n db i t m a p - b a s e d ) c o l l a b o r a t i v et e x te d i t i n gs y s t e m sh a v eb e e nw i d e l y r e s e a r c h e da n dw e l l u n d e r s t o o d ，o b j e c t b a s e dc o l l a b o r a t i v eg r a p h i c se d i t i n gs y s t e m s a r eu n d e r r e s e a r c h i n g ，a n db i t m a p b a s e dc o l l a b o r a t i v eg r a p h i c se d i t i n gs y s t e m sh a v e n o ty e tb e e nt o u c h e d t h i sd i s s e r t a t i o nc a r r i e so u ts e v e r a lf u r t h e rr e s e a r c h e si nc o l l a b o r a t i v ee d i t i n ga r e a , w h i c hi sb a s e do nt h en e w e s tr e s e a r c hd e p l o y e di nt h ew o r l d t h ec o n t e n ta r ea s f o l l o w s ： 1 an e wm u l t i v e r s i o nb a s e dc o n s i s t e n c ym a i n t e n a n c ea l g o r i t h mf o ro b j e c t - b a s e d c o l l a b o r a t i v e g r a p h i c se d i t i n gs y s t e m s t h i sa l g o r i t h mi m p r o v e s t h e e x i s t i n g m u l t i - v e r s i o nb a s e dc o n s i s t e n c ym a i n t e n a n c ea l g o r i t h m ，a n dt h es y s t e m s r u n t i m e e f f i c i e n c yi se n h a n c e d 2 an e ws e m a n t i cp r e s e r v a t i o nm o d e lf o ro b j e c t e d b a s e dc o l l a b o r a t i v e g r a p h i c s e d i t i n gs y s t e m s e x i s t i n gr e s e a r c h e s o nt h i st y p eo fs y s t e m sa r ef o c u sm a i n l yo n s y n t a c t i cp r e s e r v a t i o n ( i e c o n s i s t e n c ym a i n t e n a n c e ) i nt h i sp a p e r , t h ec o n c e p to f s e m a n t i cp r e s e r v a t i o ni s p r o p o s e da n dt h ec o r r e s p o n d i n gm o d e li s c o n s t r u c t e dt o e n h a n c et h ee f f i c i e n c yo f c o l l a b o r a t i v ew o r k 3 c o n s i s t e n c yp r e s e r v a t i o na n d u n d oi nb i t m a p b a s e dc o l l a b o r a t i v eg r a p h i c se d i t i n g r e s e a r c h e so nb i t m a p b a s e dc o l l a b o r a t i v eg r a p h i c se d i t i n gs y s t e m sh a v eb e e nc e a s e d s i n c e19 9 4 t h i sr e s e a r c hr e s o l v e dt h ec o n s i s t e n c yp r e s e r v a t i o na n du n d oi s s u e si n t h e s es y s t e m s t h es p a c ec o s ti sg r e a t l yr e d u c e dw h i l eo n l yal i t t l et i m ec o s ti sa d d e d i i 塑兰垄兰塑主兰竺垒墨 t h i sr e s e a r c hf i r s ta c h i e v e sar e a lb i t m a p b a s e dc o l l a b o r a t i v e g r a p h i c se d i t i n gs y s t e m i nt h ew o r l d ，a n dap a p e rw a s p u b l i s h e db ya c m c o n f e r e n c eo nc s c w2 0 0 2 t h i s p a p e r i st h ef i r s tp a p e re v e r a c c e p t e db y m a i nc o n f e r e n c e si nc s c w a r e a t h r o u g hr e s e a r c h i n go nc o l l a b o r a t i v eg r a p h i c se d i t i n gs y s t e m sa n d c o n s t r u c t i n gn e w g e n e r a t i o ni n t e r n e t b a s e dc o l l a b o r a t i v eg r a p h i c se d i t i n gp r o t o t y p es y s t e m ，a g e n u i n e c o l l a b o r a t i v eg r a p h i c s e d i t i n gs y s t e m w i l lb ec o n s t r u c t e di nt h en e a rf u t u r e k e y w o r d s ：c s c w , g r o u p w a r e , o b j e c t b a s e dc o l l a b o r a t i v eg r a p h i c se d i t i n gs y s t e m ， m u l t i 。v e r s i o n ，c o n s i s t e n c ym a i n t e n a n c e ，s e m a n t i c p r e s e r v a t i o n ，b i t m a p b a s e d c o l l a b o r a t i v eg r a p h i c s e d i t i n gs y s t e m ，u n d o i l l 浙江大学硕士学位论文 1 1 c s c w 概述 第1 章绪论 计算机支持协同 作( c s c w ) 是计算机科学的一个重要研究领域。它主要研究和开发 川丁- 小组( s m a l lg r o u p ) 、项目( p r o j e c t ) 和组织( o r g a n i z a t i o n ) 防同工作的关键技术，包 括人与人之间的通讯、协调、合作甚至竞争。同时，c s c w 是一门多学科交叉融合的产物， 包括计算机科学、社会学、人类学、心理学、组织学和经济学等。它的主要应用领域有网络 会议系统、1 办同著作系统、电子邮件系统、c a d c a m 、c a s e 、并行工程、工作流管理、 远程教育、远程医疗等。 1 1 1c s c w 的历史 1 9 8 4 年，p a u l c a s h m a n 和i r e n e g r i e f 组织了一个由不同学科的学者组成的w o r k s h o p ， 主要研究人们是如何进行协同： 作，以及如何使技术来支持人们协同工作。在这次会议上， 他们提出了计算机支持协同工作( c s c w ) 这一词来描述会议的主题。从此，数以千计的研 究发人员对这一领域进行了研究 1 】，并于1 9 8 6 年在美国成功地举办了第一届c s c w 国际会 议。 在1 9 8 4 年以前，甲| 期的c s c w 属于办公自动化( o f f i c ea u t o m a t i o n ) 这个研究领域。 2 0t 日= 纪6 0 年代中期，一些支持协同工作的系统，如航空公司订座系统和： 资单打印系统等 被相继开发山来。7 0 年中期，随着微机的出现和酱及，办公自动化的概念开始出现，当时 由r 许多单用户软件如文字处理和电子表格软件已成功应用，于是办公自动化开始尝试将这 些单朋户软件整合起来以支持多人协同工作。随着时间的发展，为了更好地理解协同：i ：作的 内窬，研发人员开始将社会学、人类学、心理学、组织学和经济学等学科的专家吸引到这一 领域，形成一个独立的多学科交叉融合的领域，并开发出许多应用系统，如网络会议系统、 协同并作系统、屯子邮件系统、c a d c a m 、c a s e 、并行工程、工作流管理、远程教育、 远程医疗等。 对丁c s c w 的研究可以分戏两个方面：一方面是研究小组、项目和组织协同 徘的特 性卉+ 建立一些原型系统，即对c s c w 的本身进行研究；另一方面是研究商业化的协同工作 技术和软件，称为群什( g r o u p w a r e ) 。 目前，c s c w 研究主要集中在北美和欧洲，澳人利亚、南美、亚洲也有许多研究机构。 北美和欧洲每两年交替举办c s c w 领域最高水平的国际会议。北美由a c m 主办，称为 c s c w 会议；欧洲由一些研究机构组织主办，称为e c s c w 。其它与c s c w 相关的会议有 浙江大学硕士学位论文 a c m 土办的c h i 、u i s t 、p o d c 等。c s c w 的主要刊物有a c mt r a n s a c t i o n 0 n c o m p u t e 卜h u m a n i n t e r a c t i o n ( t o c h i ) 和c o m p u t e r s u p p o s e d c o o p e r a t i v e w o r k ：aj o u r n a lo f c o l l a b o r a t i v ec o m p u t i n g ( j c s c w ) 。 国内对丁c s c w 的研究主要集中于分布式多媒体领域，清华人学、国防科技人学、南 京大学展早开始了对会议系统和协同编辑系统的研究 2 】。从1 9 9 5 年起，我国开始全面引进 c s c w 的基本概念、系统结构、关键技术及典型赢用，并于1 9 9 8 年在清华大学举办了第一 次全国c s c w 学术会议。 1 1 2 c s c w 的分类 在c s c w 系统中，人们围绕着共同完成的任务进行通信( c o m m u n i c a t i o n ) 、协作 ( c o l l a b o r a t i o n ) 和协调( c o o r d i n a t i o n ) 。f 面我们根据群件系统的工作目标、工作环境、 群体规模、交互方式和地理位置分布对c s c w 系统进行分类。 按群件的工作目标可将系统划分为集中和分散两种。例如，分布式的编程系统要求用户 能够共同专注于同一个工作目标，而在传统的分时系统中，用户则很少会对同一个目标进行 l 。作。 按群件的工作环境可将系统划分为共同和独立两种。例如，远程教育系统要求用户在同 一个环境下进行 ：作，而在电子邮件系统中，用户的工作环境则相互独立。 按群件的群体规模可将系统划分为小组( s m a l lg r o u p ，约2 5 人) 、项目( p r o j e c t ，约 5 - - 5 0 人) 和组织( o r g a n i z a t i o n ，约5 0 人以上) 。 按群体的交互方式可将系统划分为同步方式和异步方式两种。例如，远程会议系统要求 刖户在同步方式下进行交流，而在电子邮件系统中，用户通常只能在异步方式下进行工作。 按群件用户的地理位置分布可将系统划分为本地和异地两种。 f 表为群件按交互方式和地理位置的分类的结果。 i 同步异步 i本地会议工作流系统 l异地协同著作系统电子邮件系统 1 1 3c s c w 的应用系统 c s c w 的研究领域非常广泛。一般来说，只要是介于单用户和大型支持社团 ( c o m m u n i t y ) 级_ 【i j 户( 如大型计算机系统) 之间，且_ l j 户需要互相交流以完成同一工作目 标、并具有统一的用户界面的系统，均是c s c w 的研究对象。总的来说，c s c w 有以下一 些主要的应_ 【 j 系统： 消息系统( m e s s a g es y s t e m s ) 2 浙江大学硕士学位论丈 此类系统支持用户之间异步地交换各类信息，例如电子邮件、论坛和一些及时 通讯软件等。一些消息系统还能向用户提供消息过滤的机制，以提高工作效率。 协同著作系统( c o l l a b o r a t i v e a u t h o r i n g ) 此类系统支持用户对文档进行操作。例如实时协同编辑系统支持_ l l j 户同时对某 一文档进行操作，并通过某种机制( 如并发控制、加锁、服务器管理等) 来保证文 档的一致性，同时通过某种方式来感知其它用户。文档包括文本、图形、图像和图 案等。 会议系统( c o m p u t e rc o n f e r e n c i n g ) 此类系统支持用户的在线会议，包括即时传递图形、图像、动画、视频和声音 等信息，并支持用户之间的交互，提高工作和决策的效率。 c a d c a m ( c o m p u t e r - a s s i s t e dd e s i g n m a n u f a c t u r i n g ) 此类系统支持在分布式网络环境下，用户进行协同计算机辅助设计或制造，以 提高设计效率、缩短设计周期、降低成本。 c a s e ( c o m p u t e r _ a s s i s t e ds o f t w a r ee n g i n e e r i n g ) 此类系统支持在分布式网络环境下，用户进行协同系统分析、系统设计、编程、 测试和程序审核等工作，以提高开发效率和开发进度，降低开发成本。 并行工程( c o n c u r r e n te n g i n e e r i n g ) 此类系统支持产品设计开发的并行工作，是在计算机集成制造系统( c i m s ) 基础上发展起来的面向制造的新一代c i m s 技术，通过多方的并行工作来降低产品 的开发周期，以期尽早占领市场。 1 ：作流管理( w o r k f l o wm a n a g e m e n t ) 此类系统将工作流程计算机化也就是说，在一个工作群组中，为完成某一个 共同目标，通过多人协作以循序或并行工作的形式来共同完成。 远程教育( d i s t a n c e l e a r n i n g ) 此类系统借助多种类型的信息网络，实现远程交互式授课、交互式讨论、辅导 等，一方面使得人们可以不受地域和时间的限制来使用各类优秀的教学资源；另一 方面使得这些资源能够创造更好的社会与经济效益。 远程医疗( t e l e m e d i c i n e ) 此类系统支持计算机化就诊，特别是远程专家会诊、远程手术指导，使得危重 病人及时得到抢救，使边远地区的病人也能获得同城市一样的医疗条件。 电子商务( e c o m m e r c e ) 此类系统支持用户通过网络以电子方式进行的商务活动，通过网络处理商务， 参与各方的协调和协作。其主要形式有个人对个人( c t o c ) 、商业对个人( b t o c ) 和商业对商业( b t o b ) 。 电子政务( e - g o v e r n m e n t ) 电子政务系统支持政府办公的电子化，通过与迅速发展的i n t r a n e t e x t r a n e t 技 3 塑兰查兰塑圭堂竺笙墨 术和群件技术相结合，提高政府的办公效率。电子政务已经成为一种未来的政府办 公的重要手段。 1 1 4 c s c w 涉及的学科和领域 c s c w 是一i j 多学科交叉融合的产物。一般米说，c s c w 至少涉及五个主要的学科或 领域的内容：分布式系统、通讯、人机交互、人i ：智能和社会学。一般来说，一个给定的群 什系统包含两个或两个以上学科或领域的内容。 在c s c w 领域中，分布式系统( d i s t r i b u t e d s y s t e m ) 主要是指在多用户系统中，用户处 于不同的位置。它强调系统的数据和控制呈分布式状态，并着眼于仅通过观察和操纵本地的 数据来保证整个系统的一致性。 通讯( c o m m u n i c a t i o n s ) 强调远程系统之间的信息交互。主要涉及网络的连通性、带宽 以及传播文本、图案、声音和视频的通讯协议。 人机交互( h u m a n - c o m p u t e ri n t e r a c t i o n ) 强调用户界面在系统中的重要性。人机交互同 样是一个多学科交叉融合的领域，如平面设计、工业设计、计算机图形学、认知科学等。 人 ：智能( a r t i f i c i a li n t e l l i g e n c e ) 强调系统具有类似人的行为的属性，也就是通过积累 和分析人的行为，使计算机能更好地适合协同工作。该领域的加入使系统不再是被动地处理 和提供数据，而是主动地参与交互活动。 社会学( s o c i o l o g y ) 强调了社会科学在设计群件系统时的重要性。多用户系统具有许 多和单h i 户系统不同的特点，不能靠仅仅将单用户简单叠加来建立一个多用户系统。同时， 不同的小组使朋同一系统，或者同一小组使用同一系统完成不同的任务，其协同工作的方式 也会不同。 1 1 5 c s c w 的主要研究问题 在设计一个具体的c s c w 应用系统即群件系统时，有许多问题需要解决。总的来说， 这些问题可分为以f j l 类：界面和交互、过程控制、并发控制及其它【3 】。分析如下： 用户界面与交互( g r o u p i n t e r f a c e s ) 多h j 户系统的界面不同于单用户系统，它需要考虑多用户交互对系统的影响。其中 一个基本的问题是：如何管理因多用户协同工作带来的复杂的交互和并发活动? 用户界 面必须能够处理好这些复杂活动。以下为界面与交互方面的一些问题： 所见即所得问题：该问题要求系统的上f 文在所有用户界面上的显示都是一致的， 同时川户能够独立地管理这些上下文( 例如定制窗口显示的信息，改变窗口大小、风格 等等) 。 4 浙江大学硕士学位论文 注意力问题：一个好的用户界面应当能够很好地表现整个团队的活动，以避免某些 川户的注意力被过分分散。例如当一个用户创建、滚动、打开或关闭某些窗口时，其它 用户的注意力很容易被分散。注意力问题是多_ l i j 户和单h j 户系统界面的一个主要区别。 j l j 户活动问题：多用户界面应当能够恰当地匹配用户的使用模式。例如，单州户文 本编辑系统中，只有该用户操作后，字符才会被插入或删除：而在多用户文本编辑系统 中，文本与用户之间有某种独立性，因此需要内容更丰富的界面。 屏幕空间问题：由于屏幕的大小有限，如果每个用户都可以创建一些窗口，那就需 要一些机制来管理这些窗口。 用户界面工具问题：多用户系统的界面工具不能仅仅是单用户系统的扩展，相反， 他们必须提供新的方式来更好地适合多用户协同 作。 过程管理( g r o u p p r o c e s s ) 过程管理可以增加协同工作的效率，但也需要用户之间的相互协调。以下为过程管 理的一些问题： 协议：协议可以分为两种，可被植入软件或硬件系统中称为技术协议；由用户白行 遵守的称为社会协议。每种协议均有其优缺点，技术协议可以保证过程的一致性、使用 户活动更有秩序以及帮助训练没有经验的用户，但它会过分限制用户的活动。社会协议 更鼓励用户之间的协作，使群件更具灵活性，更适合用户需要，但会带来资源分配不公、 注意力分散和效率降低等问题。因此这两者之间应仔细分析来加以取舍。 用户操作：用户的协作能更好地完成一些任务，例如打篮球和灭火。但对用户操作 的管理会有一些问题，例如异常操作、操作协调和非结构化活动等。 组织和社会因素：建立一个给定功能的系统不难，但问题是如何使其在不同的环境 卜均能有效地发挥作_ j 。 用户活动的集成：对于一个大型的团队任务，同步和异步的协同工作会成为它的一 个组成部分。过程管理工具的设计者应当考虑到子团队目标和它在大型的团队任务中的 位置。 并发控制( c o n c u r r e n c yc o n t r 0 1 ) 群件系统需要采用并发控制来解决用户同时生成的操作。如协同文本编辑系统中， 在一个用户删除一句话的同时，另一个用户可能同时在其中增加了一些字符，当彼此的 操作发给对方后，可能会带来文档不一致的问题。以下为并发控制中的一些问题。 响应：对于同步的群件系统，响应有两个关键指标：1 、反应时阀( r e s p o n s e t i m e ) 。 即响应本人操作的时间；2 、通知时间( n o t i f i c a t i o nt i m e ) 。即响应其它用户操作的时间。 界面：用户界面应当是w y s i w i s ，并且所有用户的窗口应当相同或类似，以保证 某一用户的操作能正确地在所有用户窗口中显示并可见。 h j 户分布：对于广域网系统，要考虑响应时间的影响和错误恢复。 数据复制：为提供短的响应时间，数据必须被复制到每一个用户系统中，以减少通 讯的数据量。 浙江大学硕士学位论丈 健壮性：群件系统要有很强的错误恢复机制，以及解决后加入的问题。 其它 通讯协议：有效的通讯协议是成功的群件系统的基础。例如，对丁卢音和视频传输， 少量的数据丢失是可以接受的，但要保证响应时间的稳定和及时。 存取控制：有效的存取控制机制对于群件系统是十分重要的。一个好的存取控制系 统应当是宽松的、易于用户操作和调整的。 通知：在单_ h j 户系统中，当某些限制被违反或者触发了其它操作时，系统必须通 过某种机制来通知用户。在多t l i = j 户系统中，这些通知机制更为重要，冈为每个用户必须 了解其它用户的操作对自身工作的影响。 1 2 计算机支持协同编辑系统概述 计算机支持协同编辑( c o l l a b o r a t i v ee d i t i n g ) 是计算机支持协同编辑领域的一个重要研 究方向，它是指多个用户通过计算机对同一个文档进行编辑。基本的文档类型主要有文本、 图形和图像，在此基础上也有一些混合的文档，如文本和图形混合、图形和图像混合等。协 同编辑可分为同步和异步。对于异步的协同编辑，由于同一时间内只有一个用户处于编辑状 态，其主要问题是，如何保证每个用户进行编辑时文档的版本必须是最新的并且是一致的。 异步协同编辑的问题比较简单，并已得到较好的解决，类似的软件有m i c r o s o f t s u a l s o u r c e s a f e 等。因此，本文以下对协同编辑的讨论，若无特别说明，均指同步的协同编辑。 1 2 1 协同编辑系统的发展与研究内容 计算机支持协同编辑系统主要从单用户的编辑系统发展而来，目的是为了通过协同一l ：作 提高效率、节约时间和降低成本。它有着r 泛的应用领域，如商业、科学研究和出版领域的 协同著作系统，c a d ，c a m 领域的图案协同编辑系统、软件开发领域的协同程序设计和平面 设计领域的协同图像设计系统等。 协同编辑系统主要研究多个用户同时编辑同一个文档时所产生的并发控制、用户界面的 设计与交互、多通道感知、存取控制和语义协同等问题。它涉及了计算机科学、社会学、人 类学平认知心理学等多门学科。 一个好的协同编辑系统有两个主要特征：1 、实时性，对本地操作的响应要足够快( 类 似r 单瑚户系统) ，对远程操作的响应要足够小( 仅有网络传输的延时) ；2 、分布式，用户 在不同的机器上通过网络进行协同编辑。另外，一个好的协同编辑系统应该能够提供一些辅 助机制使用户能够自然、流畅地进行工作。 协同编辑系统可分为集中式和分布式两种。早期的协同编辑系统多采用集中控制方式， 一塑兰查兰翌主兰竺笙圭 即客户机月务器方式。j h 户在客户机上操作，操作首先发送给服务器，通过服务器再将操 作发送给所有用户。h j 户只和服务器发生交互，和其它j 【 j 户不直接进行通讯。由于用户操作 始终以相同的顺序发送给所有用户因此能够保证文档的一致性。该结构的缺点有：所有用 户都必须与服务器直接通讯，会出现通讯瓶颈现象；由于操作必须首先传送到服务器以保证 一致性，系统的响应时间较慢；如果用户要对某一个对象进行操作时，必须首先对该对象加 锁以避免操作冲突，从而限制了用户对对象的操作。 分布式协同编辑系统又称为复制结构系统。在这类系统中，没有服务器对用户操作进行 一致性管理，每台客户机上均保留一份所有用户的操作。用户生成的操作在本地执行后直接 发送给其它用户，用户通过分析本地和远端的操作以及一些辅助信息来保证文档的一致性。 由于用户之间直接通讯，没有服务器作中间媒介，因此出现传输瓶颈的可能性较小，系统的 响应时间较快。目前的协同编辑系统基本采用此结构。复制结构系统能够满足实时性和分布 式的要求，但它的主要缺点是解决一致性维护和并发控制的方法比较复杂。 1 2 2 协同编辑系统的主要研究问题 协同编辑系统需要研究的问题很多，一些问题已经得到较好的解决，而还有一些问题尚 需寻找好的方法。具体分析如下： 一致性维护和并发控制( c o n s i s t e n c y m a i n t e n a n c ea n d c o n c u r r e n c y c o n t r 0 1 ) 一致性维护和并发控制的作用是保证在用户并发操作时文档的一致性。它主要包含 三个一致性问题：1 、结果一致( c o n v e r g e n c e ) ，当同一操作集合在所有的站点上执行 后，这些站点上的文档应当是一致的；2 、因果一致( c a u s a l i t yp r e s e r v a t i o n ) ，对于任 意两个操作o 。和o b ，如果在初始的站点上o a 在o b 生成前已被生成或执行，则在所有 站点上o 。都因早于o b 被执行；3 、意图一致( i n t e n t i o np r e s e r v a t i o n ) ，对于任意操作o ， 其在所有站点上的执行效果都应保持o 的意图同时。的执行效果不影响那些与。独 立( 1 e 因果关系) 的操作的执行效果。结果一致保证了协同编辑结束时晟后文本的一致 性，闪果一致保证了相关联( 因果) 操作之间的执行顺序，意图一致保证了操作在远程 和庄本地执行效果的一致性以及独立操作的执行效果不会互相影响。一般来说，如果以 上二个条件满足，我们认为文档的一致性得到保证，也就是一致性维护和并发控制问题 得到了解决。 现有的解决一致性维护和并发控制的方法有如下几种： 1 、服务器直接将收到的操作转发给其它用户，不提供任何的一致性维护机制。该 方式最为简单，出现在最早期的协同编辑系统中。这些系统主要在局域网内使用，计算 机的响应速度很快出现操作冲突的可能性很小( 几乎可以忽略) 【4 】。类似的系统有 w e - m e t s ，w s c r a w l 6 ，c r y s t a l b o a r d 7 和o r o u p s k e t c h 8 。例如，w s c m w l 是一个基 于x w i n d o w s 的多用户绘图软件，服务器跟踪每一个用户的输入流和显示。对于每一个 7 浙江大学硕士学位论文 输入事件( 例如鼠标画线时的m o u s e m o v e 事件) ，服务器根据事件的类型更新所有屏幕 显示的内容。 2 、简单加锁机制。加锁是一种简单的避免并发操作的方法，它要求用户必须在操 作对象前对其进行加锁，得到其他用户的同意后才能对对象进行操作。加锁机制有三个 主要的弊端，一是请求和批准加锁的开销较大，降低了系统的响应时间，二是加锁粒度 的问题，例如当用户打算在文本中插入一个字符时，加锁的方式可以是附近的字母、单 词、句子或者整个段落，如果粒度较小，则系统开销增大，如果粒度较人，则用户的操 作会受到较人的限制，三是请求加锁和释放的时间，例如在文本编辑中，应当在移动光 标还是在按键时加锁等。简单加锁机制有一些改进措施，如t i c k l el o c k s g 允许在一段空 闲时间后将锁自动释放，s o f tl o c k s 1 0 允许通过强制命令来取消锁，g r a c e 1 1 】提供了一 种后锁机制，即在用户对对象进行操作的同时将加锁命令发送给其它用户，如产生冲突 则h j 其它方法解决，其它采用加锁机制的系统有m a c e 1 2 、s h r e d i t 1 3 、s a s s e 1 4 和d i s t e d i t 1 5 等。 u n d o u n d o 是协同编辑系统一个不可缺少的功能，同时也是一个困难的问题。在单用户 系统中，当用户误操作、发现文档中的错误、试图恢复到先前状态或者想尝试另一种方 法时，都需要进行u n d o 。在协同编辑环境下，除上述的要求外，一个用户的工作很容 易被另一个用户破坏，因此更有必要用u n d o 来恢复原有的状态。 在协同编辑环境下，由于d o 和u n d o 是并发的，一个用户在u n d o 的同时，可能 有另一个刖户正在改变这个u n d o 前的状态，这样给u n d o 带来很大的困难。一般来说， u n d o 按范围可分为局部和全局两种，局部u n d o 只是对本地用户的操作进行u n d o ，有 一定的局限性，使用得比较少，全局u n d o 是指对所有用户的操作均可进行u n d o ，绝大 部分系统均采用此模式。u n d o 按方法可分为单步u n d o ( s i n g l e s t e pu n d o ) 、逆时间序 u n d o ( c h r o n o l o g i c a lu n d o ) 和选择性u n d o ( s e l e c t i v eu n d o ) 。单步u n d o 指的是每次 只能对操作序列的最后一个操作进行u n d o ，逆时间序u n d o 指的是按操作序列的逆序对 多个操作同时进行u n d o ，它可以看成一次执行多个单步u n d o ，选择性u n d o 指的是可 以对操作序列中的任何一个操作进行u n d o ，只要操作之间没有相关性。具体实现u n d o 的系统有d i s t e d i t 1 5 、a d o p t e d 1 6 ，1 7 和r e d u c e i8 】。 界面设计与交互( u s e ri n t e r f a c e ) 界面与交互问题与上文c s c w 的研究问题一节中的问题相同，参见1 1 5 节。 感知( a w a r e n e s s ) 感知是协同编辑系统的一个重要问题，在单用户编辑系统中，对文档的修改是由单 个i 户所控制的，也就是说，文档的修改是单个用户操作的结果，用户可以预期文档的 变动。而在多用户系统中，文档的修改可以是本地或者远端用户操作的结果，因此，用 户无法预期文档的变动。同时，由于协同编辑是一个用户相互协作的过程，也需要提供 某种机制米支持用户的协同工作。感知技术作为协同编辑的一种辅助手段，对加强用户 一堑兰垄兰塑主兰竺堡圭 之间的协作、提高协同工作的效率有着重要的作州。 感知的方法可基本分成两种，一种是外部的感知通道，如提供文本、语音或视频通 道供用户交流或观察其它的行为。另一种是内部的感知机制，如设置对象之间的触发机 制、对象操作提示等。 存取控制( a c c e s sc o n t r 0 1 ) 存取控制与并发控制均属于对数据的控制，区别是存取控制用来防j p 未授权的操作 而并发控制朋来防j r 已被授权但不致的操作。 存取控制将决定哪些用户有权对某一特定的对象进行哪些操作，因此存取控制通常 是一个对象和操作的二维矩阵。存取控制应当提供相当的灵活性，如可动态改变存取权 限、用户可拥有多个角色、动态改变对象的拥有者、允许操作之间的触发、方便用户使 _ e j 以及对象和权限应相互独立等，同时存取控制应对所有操作进行检查以避免未授权的 操作，保证系统的安全。 语义保持 语义保持是协同编辑领域一个尚待解决的问题。其目的是通过对用户操作语义的理 解米提高协同工作的设率。每一个用户操作必然包含有用户特定的设计意图，即操作语 义，它是无法仅仅通过维护文档的一致性来表达的。例如，在文本协同编辑系统中，如 果用户共同撰写一篇学术论文，那么论文的格式、术语以及自然语言的语法均属于论文 编辑过程中的隐含规则，如果每一个用户均理解并能遵守这些规则，那么用户之间就能 做到理解彼此操作的目的，从而提高协同编辑的效率。同样在图案协同编辑系统中也有 语义保持的问题。 1 2 3 协同编辑系统的研究现状 对丁协同编辑系统的研究主要可分为文本、图形和图像三类。目前对于文本协同编辑系 统的研究已日趋成熟，其文本一致性的问题已基本解决，研究已向应用方向发展，例如将文 本协同编辑系统与现有的即时通讯工具相结合，建立基于x m l 的w e b 文本协同编辑系统以 及进行一些语义保持的研究等 1 9 ，2 0 ，2 1 ，2 2 。对于图形协同编辑系统的研究正在展开之中， 对下其中的一致性维护问题，目前最新的是d a v i d c h e n 和c h e n g z h e n g s u n 提出的多版本算 法【2 3 1 ，另外对于其语义保持的问题也有不少研究成果 2 4 1 。对于图像协同编辑系统的研究 在9 0 年代中期已经停止，而且并未真正在分布式控制下解决文档的一致性问题，目前最新 的研究成果是本文提出的一个解决一致性和u n d o 的算法【2 5 ，2 6 。而对于集图形和图像为一 体的图案协同编辑系统的研究国内外均尚未正式展开。 目前协同编辑系统的主要研究机构有美国的密歇根大学，北卡罗林纳大学教堂山分校， 弗占尼哑理1 ：学院，德克萨斯农工大学以及澳大利孤的g r i f f i t h 大学，另外欧洲、日本和中 国也有一些机构止进行这方面的研究。 浙江大学硕士学位论文 1 3 本文研究工作的内容和意义 图案( 图形和图像) 协同编辑系统是单用户图案编辑系统的延伸，它能够使用户在不同 的地点同时对同一个图案文档进行编辑工作。随着i n t e r n e t 技术的迅速发展，依靠计算机技 术和网络通讯技术来支持和加强设计者间协同 作效率和质量的需求显得日益迫切。新世纪 中，在这个瞬息万变的世界里，人们需要在高科技的支持下跨越时间与空间的限制，以最优 的合作方式、最快的设计速度，生产出优质的产品以适应和占领市场。图案协同编辑系统 能够使这一切成为可能，因此它的研究和实现对于许多行业如轻纺、平面设计、建筑等行业 有着重要意义。 通过以上对于c s c w 和协同编辑系统的分析可以看出，对于图案协同编辑系统的研究 尚处丁：起步阶段，对基本的一致性维护和u n d o 问题尚未得到很好的解决。至于其它的感知、 存取控制和语义保持等问题更有待进一步研究。 我们建立了一个原型系统c o d e s i g n 来实现本文中所提及的图案协同编辑中的多项关键 技术。鉴r 原来的图案协同编辑系统c o d e s i g n 中还存在一系列的问题，在研究国内外相关 协同编辑系统技术的基础上，我们研究并开发了新一代基于i n t e m e t 的图案协同编辑系统 c o d e s i g n 。系统适应i n t e m e t 应用所要求的可靠性、及时性等特点，建立基于复制的体系结 构，并在此基础上对本文所提及的多项关键技术进行了测试，达到良好效果。并可在此基础 上进行图案协同编辑的深入研究。 本文分为以f 几章： 第一章：绪论，介绍本文的研究背景。包括c s c w 和协同编辑的发展、研究内容、涉 及学科、主要问题以及研究现状等。 第二章：图案协同编辑系统c o d e s i g n 的框架模型。介绍系统的设计目标和功能模型。 第二二章：图形协同编辑中的一致性维护。通过对图形协同编辑特性的分析，提出了一个 新的基丁二多版本的一致性维护算法。 第四章：图形协同编辑的语义保持。通过对图形协同编辑系统中用户操作语义的分析， 提出了一个用户语义