122
sequence,suchamoveorcopydestinationisasignaltotraversethepartoftheinsertion
segmentstructurecorrespondingtothesourceoftheoperation.
ThesegmentlistalsoprovidesawaytospeedthecomparisonofPalimpsestaddresses,by
makingiteasytodeterminetherelativeorderingofthedestinationsofalloperations.Each
destinationhasaplaceinthelistofsegments,andtheserelativelocationscanbeusedto
speedthecomparisonofdestinations,bymaintainingintegerlabelsontheelementsofthe
list.Maintainingsuchlabelsonlistitems(toenablecomparisoninanunkeyedsequence)is
lnownastheordermaintenanceproblemanditcanbesolved(DietzandSleator1987)forn
segmentsinO(1)amortizedtimeatthecostofsomeimplementationcomplexity,orvery
simplyinO(logn)time.Eachinsertionintothesegmentlistusesavariantofthisalgorithm
tomaintainorderinglabelsonalladdressescontainedinstoredchanges.
6.5 Trackingdeletions
Deletionsmustbestoredsoasenablequickdeterminationofwhetheraparticularposi-
tionisdeleted,andaftersuchaninitialsearch,shouldprovidequickenumerationoffol-
lowingdeletedsegments.Sincedeletionswillbeaddedandoccasionallyundone,thesetof
intervalsrepresentingthedeletedsegmentsmustbedynamic.Efficientintervaloverlap
testingispossiblewithanumberofquerystructures.
Oneofthemostflexiblestructurestomaintainsuchinformationwithgoodaccesstime
istheprioritysearchtree(McCreight1985).Thebalancedvariantofthisdatastructurecan
insertanddeleteinO(log n)timefornsegmentsand,givenaquerysegment,canenumer-
atealloverlappingsegmentsinO(log n + k)timeforkresultsegments.Aprioritysearchtree
canbeusedsothatthefirstoverlappingsegmentfoundinanysearchwillbetheonewith
thelargestrightendpoint.Thisendpointisagoodstartingpointinsearchingforthenext
deletioninthesequence.Inthecaseofmanyoverlappingregions,itisaproblemtoperform
123
evenalogarithmictimesearchforeachdeletionfound.Intheworstcase,manyintervals
mayhavetobeexaminedwithoutevennecessarilyadvancinginthesequence.
Figure6.4showsonepatternthatcausesinefficiencyinenumeratingdeletions.Changes
1,2,and3alloverlapinsuchawaythateachmustbeexaminedindividually,requiringthat
3deletionsbefoundandtested,eventhoughtheentireregionU1isinfactdeleted.
1
234
U1 U2
F F F F iii ig g g gu u u ur r r re e e e 6666....4444:::: OOOOvvvveeeerrrrllllaaaappppppppiiiinnnngggg ddddeeeelllleeeettttiiiioooonnnnssss aaaannnndddd uuuunnnniiiioooonnnn rrrreeeeggggiiiioooonnnnssss
Inpractice,thecostofcheckingmultipledeletionsisprobablynottoobad,butanalter-
nativeapproachispossible,whichmakesdeletionandenumerationofdeletedintervalsfast,
attheexpenseofspeedfor(themuchmoreinfrequent)undooperation.Thebasicideaisto
retainafullintervaltreeofallactivedeletionsinaversion,buttoaugmentthiswithan
indexedlistofdisjointunionsegments,likeU1andU2.Sincethesesegmentsaredisjoint,
logarithmicupdateandsearchtimecanbeguaranteedbyindexingthembystartingpoint,
withoutanyneedforfanciersearchstructures.Newdeletionscanbeaddedinlogarithmic
timebyfindingtheuniquesegment,ifany,thatoverlapsthestartingpointofthenewseg-
mentaswellastheonethatoverlapsitsendingpoint.Ifthesesegmentsexist,thenthey
aredeletedinlogarithmictime,andanewsegmentrepresentingtheunionofallthreeis
insertedinlogarithmictime.
Whenadeletionisundone,itwillshortenorsplitaunionsegment.Thesectionofthe
disjointdeletionlistcoveredbythedeletionbeingundonewillbecomeinvalidbecauseof
theunknownnumberofoverlappingdeletionsintheintervalitcovered.Theindexcouldbe
rebuiltimmediately,orincrementally.ExecutiontimeforrebuildingthefromscratchisO(n
logn)foranactiveversionwithndeletions.
Previous Page Next Page