Show simple item record  

dc.contributor.authorNevill-Manning, Craig G.
dc.contributor.authorWitten, Ian H.
dc.date.accessioned2008-11-13T00:45:06Z
dc.date.available2008-11-13T00:45:06Z
dc.date.issued2000
dc.identifier.citationNevill-Manning, C.G. & Witten, I.H. (2000). Online and offline heuristics for inferring hierarchies of repetitions in sequences. Proceedings of the IEEE, 88(11), 1745-1755.en_US
dc.identifier.urihttps://hdl.handle.net/10289/1319
dc.description.abstractHierarchical dictionary-based compression schemes form a grammar for a text by replacing each repeated string with a production rule. While such schemes usually operate online, making a replacement as soon as repetition is detected, offline operation permits greater freedom in choosing the order of replacement. In this paper, we compare the online method with three offline heuristics for selecting the next substring to replace: longest string first, most common string first, and the string that minimized the size of the grammar locally. Surprisingly, two of the offline techniques, like the online method, run in time linear in the size of the input. We evaluate each technique on artificial and natural sequences. In general, the locally-most-compressive heuristic performs best, followed by most frequent, the online technique, and, lagging by some distance, the longest-first technique.en_US
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.publisherIEEE, New Yorken_US
dc.relation.urihttp://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/5/19320/00892710.pdf?arnumber=892710en_US
dc.rightsThis article has been published in the journal: Proc IEEE, ©2008 IEEE.en_US
dc.subjectdictionary compressionen_US
dc.subjecthierarchical compressionen_US
dc.subjectgrammar inferenceen_US
dc.titleOnline and offline heuristics for inferring hierarchies of repetitions in sequencesen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1109/5.892710en_US
dc.relation.isPartOfProceedings of the IEEEen_NZ
pubs.begin-page1745en_NZ
pubs.elements-id41836
pubs.end-page1755en_NZ
pubs.issue11en_NZ
pubs.volume88en_NZ


Files in this item

This item appears in the following Collection(s)

Show simple item record