CM is the static context modeling archiver. (C) Bulat Ziganshin 1993, 97, 98 My email addresses: FIDO 2:5049/36.26 bulatz@fort.tatarstan.ru ============================ The algorithm: 1. A context tree of the depth set by the -o option is built, and the frequency of each character in each context is noted. 2. All the context-character pairs with the frequency that is less than the one given by the -n option are removed from the tree. The frequencies of such pairs are given to the ESCAPE-code of their respective contexts and to the combination "parent context-character". 3. The remaining tree is coded and written to the output file. 4. The source is coded using the tree. Deficiencies: 1. All the memory - for the text and for the tree is allocated once at the start of the program (its amount is confugurable by the -t and -m options). A more flexible memory allocation strategy is needed. 2. The command-line interface is dumb. Future directions: 1. The tree depth to be made adjustable depending on the actual frequencies of particular contexts. 2. The deletion of an element from the tree to be done if and only if the element is not beneficial (number of bits saved in coding text is greater than number of bits used in coding the tree). 3. Tree coding to be made smarter. When compiled with Visual C++ 5.0 the program works faster than HAP 4; compression ratio is approximately the same. The first group of #define's (in the source code) denotes compilation modes. To switch modes, add or remove the letter N, e.g. ARITH <-> NARITH. ============================ Алгоритм: 1. Строится дерево контекстов заданной глубины (опция -o), отмечается частота появления каждого символа в каждом из контекстов 2. Из дерева удаляются пары контекст/символ, сочетание которых имеет частоту меньше заданной (-n). Частота каждой пары отдается в ESCAPE-код этого контекста и сочетанию родительский_контекст/символ 3. Дерево, оставшееся после этой чистки, кодируется и записывается в файл 4. Исходный текст кодируется с помощью этого дерева Hедоделки: 1. Вся память - под текст и под дерево выделяется один раз в начале работы программы (регулируется опциями -t и -m). Hужен более гибкий алгоритм. 2. Дурацкий command-line interface Future directions: 1. Построение дерева переменной глубины, в зависимости от частоты конкретных контекстов 2. Удаление из дерева тех и только тех элементов, которые не принесут нам выигрыша при кодировании (сэкономленные биты при кодировании текста минус потраченные биты при кодировании дерева) 3. Еще более умное кодирование дерева При компиляции с помощью Visual C++ 5.0 программа работает быстрее HAP 4; степень сжатия у них примерно одинакова. Первая группа define's является переключателями, для компиляции с противоположным значением добавьте или уберите букву N, например ARITH<->NARITH ===================================