Основной недостаток алгоритма заключается в пустом расходе числового пространства при частичном заполнении словаря. Эту проблему можно решить дожимая выходной поток с помощью Хафман или Арифметического кодирования. То и другое достаточно легко реализуется, так как интервалы или динамическое дерево Хафмана, можно встроить непосредственно в элементы словаря. Правда мои попытки записывать выход через хаффман коды, показали что заметного выигрыша это не дает, хотя возможно что я не достаточно аккуратно это делал. Ещё один вид избыточности можно показать на примере. Допустим в нашем словаре есть цепочка символов 'ABC', и мы считали символы 'AB', так как следующий символ будет либо символ 'C' либо конец и начало другой цепочки. Следовательно после символов 'AB' не может идти цепочек, дерево которых начинается на 'C'. Этот факт можно учитывать при арифметическом сжатии. Да в принципе и без него. Если в этот момент перенумеровать все символы начинающиеся не на 'C', то можно впихнуть большее количество элементов словаря, чем позволяет текущая разрядность.

Ещё одно предположение по поводу увеличения степени сжатия. К сожалению эксперимент на эту тему я не довёл до конца. Мысль заключалась в том чтобы не очищать словарь в момент переполнения, а просто удалять конец той цепочки, которая использовалась реже всего. Для этого можно использовать двусвязный список, точнее говоря очередь. В начало очереди мы кладём все используемые цепочки, включая их части. Из конца очереди мы берём токены, которые хотим удалить в случае нехватки места. Любую цепочку и её части, которые замечены в выходном потоке, должны изыматься из середины очереди, и добавляются в её начало. Таким образом в конце очереди долны оказаться те элементы словаря, которые дольше всего не использовались. В момент нехватки места можно удалять даже те цепочки, которые являются частью более длинных цепочек. Например я нас есть цепочка QWERTY, которая часто используется в файле, но её префикс QWER по отдельности не попадается ни разу. Для удобства назовём такие префиксы теневыми. В этом случае префикс можно просто не хранить в словаре, а вынести всё что к нему относится за его пределы, освободив тем самым дополнительные числа для выходного потока. Кроме того словарь который успел изучить цепоку QWERTY, ничего не сможет сделать если ему попадётся хвост этой же цепочки (RTY). Недостатки по сравнению с LZSS очевидны. Во время сжатия моего тестового .xml файла, я посчитал цепочки словаря которые использовались более одного раза, но префиксы которых использовались лишь один раз во время роста словаря и в дальнейшем не вызывались. При словаре в 65536 элементов, который подвергается регулярному сбросу, таких теневых цепочек, в среднем было 11%. В одном месте перед сбросом их накопислось 14%. Но это только относительно размеров самого словаря. Если считать их в выходном потоке, соотношение будет куда более сильное. Если же посчитать количество цепочек, которые просто не разу небыли задействованы. Точнее были замечены всего один раз в момент роста, но не более. То таких было около 50% словаря.

Если по простому, то можно не делать словарь ввиде дерева, а делать таблицу и в чистом виде хранить в ней растущие строки. Выкидывать самые старые строки из таблицы, когда не хватает места в таблице. Получается достаточно простой исходник, практически никакого проигрыша по скорости (если написать нормально).

Ещё одна проблема заключается в так называемой жадности алгоритма. Каждый новый символ входящих данных увеличивает последнюю цепочку данных. Если каким образом в словаре конец более короткой цепочки пересекается с началом более длинной, то во время анализа данных мы не сможем ухватить начало этой цепочки. Известны так же модификации в которых используются не стыковка слова и символа, а конкатенация двух слов (LZMW). Можно попытатся усложнить стратегию обучения словаря, сделав её более гибкой и обучаемой. Очень интересный эффект получается при более агресивном обучении, когда оборваную цепочку в словаре дополняют используя не только следующий символ, а два последующих. Даже при частичной реализации этой мысли, мой проверочный XML файл, сжался сильнее в 1.34 раза. Даже на .exe файлах, разница очень ощутимая. Но перед тем как стереть исходник, я забыл кое проверить. Вполне возможно что агрессия попросту способствует сбросу словаря в те моменты когда он становится мало эффективен и других функций у неё нет. Если вы выкидываете старые строки то можно применять более сложные способы обучения и роста цепочек, про которые лучше писать отдельно.

int old_code=0; ... for(;;) { sym=fgetc(in); if(sym==EOF) break; if(code) index=Find(code,sym); else index=sym+1; if(index) { code=index; if(old_code) old_code=0; }else{ if(old_code) Update(old_code,sym); // обновление препоследнего кода WriteCode(out,code); ... old_code=count; // код получится при обновлении (code,sym) Update(code,sym); // обновление последнего кода } }

LZW без сбросов

lzw_adapt1.cpp

В качестве очереди используется кольцевой список (с ним проще оперировать). Один элемент обозначен как конец очереди. Все выходящие коды алгоритма, а так же их составные изымаются из очереди и добавляются в её начало. В случае нехватки места, берётся один элемент из конца очереди и удаляется из словаря, как наименее используемый. Теневые цепочки пока что не удаляются. Поскольку писал я не очень вдумчиво, в архив добавляется контрольная сумма.

Можно не класть в очередь составные части цепочек, а только непосредственно коды, замеченные в выходном потоке. А так же создать с словаре теневую зону, коды которой не попадают в выходной поток. И когда не хватает места, перемещать в неё цепочки, которые являются составными частями более длинных цепочек, которые очередь определила, как уже не встречающиеся в выходном потоке.

Как уже намекалось выше. Я проверил словарь после работы и заметил что в нём есть огромное количество цепочек, которые полностью совпадают с концами других, более длинных цепочек. Или почти воспадают, отличаясь один только символом на конце. Более эффективно работать словарь наверное не заставишь. Зато очевидно что две цепочки не могли строится одновременно, хотя бы потому что символ они получают по очереди. Следовательно, в процессе работы можно находить цепочки, концы которых совпадают или хотя бы те которые полностью совпадают с концом другой цепочки. И сделать так чтобы символ попадающий в одну из таких цепочек, паралельно использовался для обучения второй. Возможно возникновение ненужных цепочек, но если LZW работает без сбросов, то они будут быстро отсеяны.

p.p.s. сразу прошу прощения, за невнятность этого рассказа и прочие косяки. Я свою писанину не перечитывал.