Compror: Compression with a Factor Oracle

Compror is a text compression method using a factor oracle [1]. The factor oracle of a word x is a space economical index structure which represents at least all the factors of x. It is an automaton which representation, in addition to x, consists in only a small number of transitions (see g. 1). It can be constructed on-line in linear time and space. It is also possible to compute, with the same complexities, a position and a length of a long repeated suAEx for each position of x [2]. This enables to compute a factorization of x. This factorization is used during the encoding process as follo ws:x = uv where the pre x u of x as already been encoded and the suAEx v has to be encoded. The current state in the oracle is q, corresponding to juj. Then the characters of v are parsed through the oracle, from state q, as long as the length of the repeated suAEx is greater than the pre x of v being processed. Each time a new letter is encountered, it is encoded as a letter, otherwise a repeated segment of x is encoded as a pair (starting position,length). For instance, the word aabbabbabbab is encoded b ya(1; 1)b(3; 1)(2; 8).