česky
previous main page content next

ACB (Associative Coder of Buyanovsky)

Main features

Description

Description of algorithm

  1. Current context is compared with items in dictionary (with their context part) (comparison from right to left).
  2. Actual content is compared with contents in dictionary (comparison from left to right).
  3. The triplet (d, count, ch) goes to the output.
    • d - distance between the best context and the best content.
    • count - number of matched symbols.
    • ch - first unmatched symbol in look-ahead buffer.
  4. The dictionary is updated (new phrases are inserted, contents are updated).
  5. Look-ahead buffer is shifted for count + 1 positions to the right.

Structure of dictionary

  • It consists of items made up of context and content.
  • It keeps sorted history of all contexts and contents of source text.
  • New entries are inserted to the position according to their lexographical order (comparison from right to left).

State of dictonary

  • It is the same for compression and decompression.
  • Directory is organized as a list of pointers to the text.

Characteristics of method

  • Maximal length of context.
  • Maxaximal length of content.

Coding output

  • We can encode triplet (d, count, ch) for example by Huffman coding.

Pseudo-code


 1:  begin
 2:     initialize look-ahead buffer
 3:     while (!EOF) do
 4:      begin
 5:        int i = position of the best matching context in dictionary 
 6:        int j = position of the best matching content in dictionary 
 7:        int count = count of first matched chars in found content
 8:        char ch = first mismatching character 
 9:        output(j-i, count, ch) 
10:        update of dictionary (insert new phrases, update contents)  
11:        shift look-ahead buffer by count + 1 positions to the right;
12:      end 
13:  end

References

  1. D. Salomon: Data Compression - Springer, New York, 1997.
  2. G. Buyanovsky: Asociative coding - Monitor, 8:10-19, 1994.
  3. Josef Troch: ACB Algorithm.

Example