Storing Text Using Integer Codes

STORING TEXT USING INTEGER CODES Raja Noor Ainon Computer Centre University of Malaya 59100 Kuala Lumpur, Malaysia. Abstract Traditionally, text is stored on computers as a stremn of characters. The goal of this research is to store text in a form that facilitates word manipu- lation whilst reducing storage space. A word list with syntactic linear ordering is stored and words in a text are given two-byte integer codes that point to their respective positions in this list. The imple- mentation of the encoding scheme is described and the perfomnance statistics of ~lis encoding scheme is presented. 1.0 Introduction This research aims at storing text in a form that facilitates word manipulation whilst saving storage space. Although there are many text compre- ssion algorithnts currently in use, the word manipula- tion capability has yet to be incorporated. Harris [2], in his research, compiled a 40,000 word list with syntactic linear ordering and suggested that words in a text be given two-byte integer codes that point to their respective positions in this list. In this way the coded text has inherent syntactic information, thereby making it useful for many applications including statistical linguistics and question-answering systems. In this paper, we show how such a scheme can achieve optimal compression results and present its efficient implementation. Three text compression techniques that have been tested on English texts include (i) the Huffman variable-length encoding schemes [3] which achieve tight packing of data by giving variable-length bit code for each character, with more frequently- occurring words having shorter codes, (2) the Adaptive pattern substitution algorithm, also known as the Lempel-Ziv or LZW algorithm (see [7], [8], [9]) which converts variable-length strings of input symbols into fixed length codes by first looking for con~non patterns of two or more bytes occurring frequently, and then substituting an unused byte for the common long one, and (3) another technique, due to Hahn [i] encodes non-blank characters in groups of a fixed size as unique fixed point ntunbers. For measuring text compression two definitions are used in this paper. One is the compression ratio defined as the ratio of size of the original text to that of the coded text. ~he other is the compression percentage, defined as (Size of original text - Size of coded text)% (Size of original text) of its size, is treated a~ a unit and is represented in computers in the form of a computer word (usually 4 bytes) or part of a word. It is addressable, hence it does not require a delii~ter like a space to distinguish it from a neighbouring number. For this encoding scheme, we endeavour to store text as a stream of fixed length computer words which is distinguishable by the computer. This can be achieved by keeping an external list of all words in the dictionary includ]mg derived ones, and assigning a unique integer code for each entry. Instead of words separated by delimiters the coded text represents words as numbers, thereby dispensing the need for representing …

Content truncated to 500 words