Title page for ETD etd-09102010-134203
McDonald, Andre Martin Email
The analysis of enumerative source codes and their use in Burrows‑Wheeler compression algorithms
Prof J C Olivier
In the late 20th century the reliable and efficient transmission, reception and storage of information proved to be central to the most successful economies all over the world. The Internet, once a classified project accessible to a selected few, is now part of the everyday lives of a large part of the human population, and as such the efficient storage of information is an important part of the information economy. The improvement of the information storage density of optical and electronic media has been remarkable, but the elimination of redundancy in stored data and the reliable reconstruction of the original data is still a desired goal.
The field of source coding is concerned with the compression of redundant data and its reliable decompression. The arithmetic source code, which was independently proposed by J. J. Rissanen and R. Pasco in 1976, revolutionized the field of source coding. Compression algorithms that use an arithmetic code to encode redundant data are typically more effective and computationally more efficient than compression algorithms that use earlier source codes such as extended Huffman codes. The arithmetic source code is also more flexible than earlier source codes, and is frequently used in adaptive compression algorithms. The arithmetic code remains the source code of choice, despite having been introduced more than 30 years ago.
The problem of effectively encoding data from sources with known statistics (i.e. where the probability distribution of the source data is known) was solved with the introduction of the arithmetic code. The probability distribution of practical data is seldomly available to the source encoder, however. The source coding of data from sources with unknown statistics is a more challenging problem, and remains an active research topic.
Enumerative source codes were introduced by T. J. Lynch and L. D. Davisson in the 1960s. These lossless source codes have the remarkable property that they may be used to effectively encode source sequences from certain sources without requiring any prior knowledge of the source statistics. One drawback of these source codes is the computationally complex nature of their implementations. Several years after the introduction of enumerative source codes, J. G. Cleary and I. H. Witten proved that approximate enumerative source codes may be realized by using an arithmetic code. Approximate enumerative source codes are significantly less complex than the original enumerative source codes, but are less effective than the original codes. Researchers have become more interested in arithmetic source codes than enumerative source codes since the publication of the work by Cleary and Witten.
This thesis concerns the original enumerative source codes and their use in Burrows�Wheeler compression algorithms. A novel implementation of the original enumerative source code is proposed. This implementation has a significantly lower computational complexity than the direct implementation of the original enumerative source code. Several novel enumerative source codes are introduced in this thesis. These codes include optimal fixed�to�fixed length source codes with manageable computational complexity.
A generalization of the original enumerative source code, which includes more complex data sources, is proposed in this thesis. The generalized source code uses the Burrows�Wheeler transform, which is a low�complexity algorithm for converting the redundancy of sequences from complex data sources to a more accessible form. The generalized source code effectively encodes the transformed sequences using the original enumerative source code. It is demonstrated and proved mathematically that this source code is universal (i.e. the code has an asymptotic normalized average redundancy of zero bits).
AFRIKAANS : Die betroubare en doeltreffende versending, ontvangs en berging van inligting vorm
teen die einde van die twintigste eeu die kern van die mees suksesvolle ekonomie�e in
die w�ereld. Die Internet, eens op �n tyd �n geheime projek en toeganklik vir slegs �n
klein groep verbruikers, is vandag deel van die alledaagse lewe van �n groot persentasie
van die mensdom, en derhalwe is die doeltreffende berging van inligting �n belangrike
deel van die inligtingsekonomie. Die verbetering van die bergingsdigteid van optiese en
elektroniese media is merkwaardig, maar die uitwissing van oortolligheid in gebergde
data, asook die betroubare herwinning van oorspronklike data, bly �n doel om na te
Bronkodering is gemoeid met die kompressie van oortollige data, asook die betroubare
dekompressie van die data. Die rekenkundige bronkode, wat onafhanklik
voorgestel is deur J. J. Rissanen en R. Pasco in 1976, het �n revolusie veroorsaak
in die bronkoderingsveld. Kompressiealgoritmes wat rekenkundige bronkodes gebruik
vir die kodering van oortollige data is tipies meer doeltreffend en rekenkundig meer effektief
as kompressiealgoritmes wat vroe�ere bronkodes, soos verlengde Huffman kodes,
gebruik. Rekenkundige bronkodes, wat gereeld in aanpasbare kompressiealgoritmes gebruik
word, is ook meer buigbaar as vroe�ere bronkodes. Die rekenkundige bronkode
bly na 30 jaar steeds die bronkode van eerste keuse.
Die probleem om data wat afkomstig is van bronne met bekende statistieke (d.w.s.
waar die waarskynlikheidsverspreiding van die brondata bekend is) doeltreffend te
enkodeer is opgelos deur die instelling van rekenkundige bronkodes. Die bronenkodeerder
het egter selde toegang tot die waarskynlikheidsverspreiding van praktiese data.
Die bronkodering van data wat afkomstig is van bronne met onbekende statistieke is
�n groter uitdaging, en bly steeds �n aktiewe navorsingsveld.
T. J. Lynch and L. D. Davisson het tel�bronkodes in die 1960s voorgestel. Tel�
bronkodes het die merkwaardige eienskap dat bronsekwensies van sekere bronne effektief
met hierdie foutlose kodes ge�enkodeer kan word, sonder dat die bronenkodeerder
enige vooraf kennis omtrent die statistieke van die bron hoef te besit. Een nadeel van
tel�bronkodes is die ho�e rekenkompleksiteit van hul implementasies. J. G. Cleary en
I. H. Witten het verskeie jare na die instelling van tel�bronkodes bewys dat benaderde
tel�bronkodes gerealiseer kan word deur die gebruik van rekenkundige bronkodes. Benaderde
tel�bronkodes het �n laer rekenkompleksiteit as tel�bronkodes, maar benaderde
tel�bronkodes is minder doeltreffend as die oorspronklike tel�bronkodes. Navorsers het
sedert die werk van Cleary en Witten meer belangstelling getoon in rekenkundige
bronkodes as tel�bronkodes.
Hierdie tesis is gemoeid met die oorspronklike tel�bronkodes en die gebruik daarvan in Burrows�Wheeler kompressiealgoritmes. �n Nuwe implementasie van die oorspronklike
tel�bronkode word voorgestel. Die voorgestelde implementasie het �n beduidende
laer rekenkompleksiteit as die direkte implementasie van die oorspronklike tel�bronkode.
Verskeie nuwe tel�bronkodes, insluitende optimale vaste�tot�vaste lengte tel�bronkodes
met beheerbare rekenkompleksiteit, word voorgestel.
�n Veralgemening van die oorspronklike tel�bronkode, wat meer komplekse databronne
insluit as die oorspronklike tel�bronkode, word voorgestel in hierdie tesis. The
veralgemeende tel�bronkode maak gebruik van die Burrows�Wheeler omskakeling. Die
Burrows�Wheeler omskakeling is �n lae�kompleksiteit algoritme wat die oortolligheid
van bronsekwensies wat afkomstig is van komplekse databronne omskakel na �n meer
toeganklike vorm. Die veralgemeende bronkode enkodeer die omgeskakelde sekwensies
effektief deur die oorspronklike tel�bronkode te gebruik. Die universele aard van hierdie
bronkode word gedemonstreer en wiskundig bewys (d.w.s. dit word bewys dat die kode
�n asimptotiese genormaliseerde gemiddelde oortolligheid van nul bisse het).
McDonald, AM 2010, The analysis of enumerative source codes and their use in Burrows‑Wheeler compression algorithms
, MEng dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://upetd.up.ac.za/thesis/available/etd-09102010-134203/ >