Higher Compression from the Burrows-Wheeler Transform with New Algorithms for the List Update Problem

Higher Compression from the Burrows-Wheeler Transform with New Algorithms for the List Update Problem

Date: August 2001
Creator: Chapin, Brenton
Description: Burrows-Wheeler compression is a three stage process in which the data is transformed with the Burrows-Wheeler Transform, then transformed with Move-To-Front, and finally encoded with an entropy coder. Move-To-Front, Transpose, and Frequency Count are some of the many algorithms used on the List Update problem. In 1985, Competitive Analysis first showed the superiority of Move-To-Front over Transpose and Frequency Count for the List Update problem with arbitrary data. Earlier studies due to Bitner assumed independent identically distributed data, and showed that while Move-To-Front adapts to a distribution faster, incurring less overwork, the asymptotic costs of Frequency Count and Transpose are less. The improvements to Burrows-Wheeler compression this work covers are increases in the amount, not speed, of compression. Best x of 2x-1 is a new family of algorithms created to improve on Move-To-Front's processing of the output of the Burrows-Wheeler Transform which is like piecewise independent identically distributed data. Other algorithms for both the middle stage of Burrows-Wheeler compression and the List Update problem for which overwork, asymptotic cost, and competitive ratios are also analyzed are several variations of Move One From Front and part of the randomized algorithm Timestamp. The Best x of 2x - 1 family includes Move-To-Front, ...
Contributing Partner: UNT Libraries
Relating Boolean Gate Truth Tables to One-Way Functions

Relating Boolean Gate Truth Tables to One-Way Functions

Date: March 3, 2008
Creator: Gomathisankaran, Mahadevan & Tyagi, Akhilesh
Description: In this paper, the authors present a schema to build one way functions from a family of Boolean gates. Moreover, the authors relate characteristics of these Boolean gate truth tables to properties of the derived one-way functions.
Contributing Partner: UNT College of Engineering
Data Compression Using a Multi-residue System (Mrs)

Data Compression Using a Multi-residue System (Mrs)

Access: Use of this item is restricted to the UNT Community.
Date: August 2012
Creator: Melaedavattil Jaganathan, Jyothy
Description: This work presents a novel technique for data compression based on multi-residue number systems. The basic theorem is that an under-determined system of congruences could be solved to accomplish data compression for a signal satisfying continuity of its information content and bounded in peak-to -peak amplitude by the product of relatively prime moduli,. This thesis investigates this property and presents quantitative results along with MATLAB codes. Chapter 1 is introductory in nature and Chapter 2 deals in more detail with the basic theorem. Chapter 3 explicitly mentions the assumptions made and chapter 4 shows alternative solutions to the Chinese remainder theorem. Chapter 5 explains the experiments in detail whose results are mentioned in chapter 6. Chapter 7 concludes with a summary and suggestions for future work.
Contributing Partner: UNT Libraries