134
Thisisonecriticaldifferencebetweenthe“deletion”ofasubsequencecausedbyamove
andthatcausedbyanexplicitdeletionoperation,andyetanotherwayinwhichmoveis
logicallydistinctfromcopyplusdeletion.However,despitethepossibilitythattheposition
ofthezero-lengthsegmentrepresentingdeletedtextisdifferentthanmightotherwisebe
expected,deletionisquitesimilarbetweenPalimpsestandVTML.Deletedsegmentsinone
sequencecanberepresentedascorrespondingtozero-lengthsegmentsintheother.
Correspondingregionsinthathavebeenmovedcanalsoberepresentedasacorrespon-
dencebetweensubsequencesjustasinthecaseofdeletedsubsequences.Thepairsofcorre-
spondingsegmentswillhavetwodifferentsortedordersdependingonwhethertheyarear-
rangedinsequenceaccordingtotheirorderinonedocumentortheotherone.The
Palimpsestaddressesofmovedsegmentsaredifferentinbothversions,sincethePalimpsest
addresseswillcontaintheIDsofanyactivemovesthataffectanaddress.Thecommonin-
formationintheseaddressesmakesthecorrespondencesexplicit.
Copyintroducesadifferentrelationship,onethatisinternaltoeachinstanceofaP-
sequence:thatofduplication(perhapsalsomodifiedbyotherchanges).Copyrelationships
couldpotentiallyintroduceagreatdealofcomplexityintocomparisonreporting,iftherela-
tionshipsbetweenallcopiesofagivensectionweretobeconsideredincalculatingthere-
sultsofacomparison.Considerasinglesubsequencethathasduplicatedbycopyingmultiple
times.Ifacomparisonreportthatrecognizedarelationshipbetweeneverysequenceinei-
therdocumentthatshareddata,theneachcopyinonedocumentwouldhavetoberelated
toeachcopyintheotherdocument.Thisisbad.Itisbadnotonlybecausecomparisonre-
portsshouldnothavespacerequirementsofO(n
2
)foradocumentwithncopies,butbecause
theinformationinquestionisalmosttotallyuseless,sinceitisimplicitintheinternalcopy
relationshipsofeachdocument.Therefore,theonlysensiblecorrespondencebetweencopy
resultsintwoversionsistheonethatresultswhentheaddressesbeingcomparedareidenti-
cal.

135
ThecomparisonoftwoP-sequencescanbeperformedpurelybyexaminingtheaddresses
theycontain.Sincesegmentsrepresentcontiguousportionsoftheaddressspace,thecom-
parisonprocessneedonlyexaminetheinitialaddressesoftherelevantsegments.Theproc-
essmustexamineeverysegmentthatappearsineitheroftheversions.
Thesimplestmethodofcomparisonisfirsttogeneratealistofallthesegmentsinoneof
thedocuments,intheorderthattheyoccur.Thepathportionsoftheaddressesofeachof
thesesegmentsmustbenormalizedforcomparison,sothatcorrespondingaddresseswillbe
equal.Pathsthatconsistonlyofinsertionsremainintact,becausedatathatissharedbe-
tweensequencesshouldcorrespond.Pathswithinitialmoveoperationsneedthemremoved
fromthepath,sincedatacorrespondsregardlessofwhatmoveoperationsmayhaveaffected
it.Becausecopyoperationsshouldonlycountasamatchwhentheyareidenticallypresent
inbothsequences,copyoperationsshouldnotberemovedfrompaths.Furthermore,move
operationsinthesourceofcopyoperationsshouldalsobepreserved;theycorrespondto
movesthatwereexecutedintheoriginofthecopy,andthatalreadymatchinthatcontext.
Anyaddressesthatareequalaftertheremovalofinitialmoveoperationsrepresentle-
gitimatecorrespondencesbetweenthetwoversions.Anyaddressespresentinoneversion
butnottheotherrepresentdeleteddata.Whilethisbasicsetofcorrespondencesisade-
quate,anapplicationmightwellprefertosorttheaddressrangesbypositionofoccurrence
inoneofthesequencesandtomergepairsthatareadjacentinbothorders,soastohave
correspondencesofmaximumlength.
6.8 Summary
Thischapterhasreviewedthesimplerchange-orientedsystemVTML2.0,anextensionof
jointworkundertakenwithFabioVitali(VitaliandDurand1995).CreatingaVTMLimple-
mentationhasseveralissuessimilartothoseinvolvedinaPalimpsestimplementation.The
managementofafragmentedsequencewithaglobalorderingisthemostsignificantsimi-