Алгоритмы сжатия данных без потерь, часть 2

[kenoma]

А как из «3H&3A» восстановить «HAHAHA&»?

[DeMoN_MIPT]

Приведу алгоритм на данном примере:
«Распаковываем» RLE запись «3H&3A» в «HHH&AAA».
Изначально есть N пустых строк, где N — длина строки.
Потом последовательно выполняем действия «добавить» и «сортировать»
Добавить: к каждой строке приписываем слева один символ из записи с индексом, равным номеру строки.
Сортировать: отсортировать полученные строки.

Пример последовательных шагов

В итоге берем строку, у которой "&" -. последний символ

[kvark]

Как и прошлая статья в серии, эта значительно обделяет вниманием BWT семейство алгоритмов. Там ведь столько всего интересного: DC, MTF, WFT, IF, и другие, а не только bzip2, который, к слову, не так уж и прост в своей BWT реализации. С другой стороны, LZ расписано довольно подробно, и на этом спасибо!

[demitsuri]

На LZW патенты в США, Канаде, Европе и Японии вроде бы уже протухли.

[f1ac]

>LZMW
>… Действует, как LZMW

Не может быть :)

[SLY_G]

Да, запутался в аббревиатурах… Исправил.

[Atakua]

Кстати, тем, кому интересно более глубоко заглянуть в мир алгоритмов сжатия без потерь, рекомендую книгу:
Lossless Compression Handbook // Khalid Sayood, editor — 2003 — ISBN-13: 978-0126208610 — ISBN-10: 0126208611

В ней разбирается всё: от теории через Колмогоровскую сложность, через LZ, BWT, арифметическое кодирование до алгоритмов TIFF, PNG и аспектов реализации аппаратных ускорителей сжатия.

[kvark]

А я бы нашу родную порекомендовал:
«Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео» ISBN 5-86404-170-X; 2003 г.

Написана титанами отечественного архиваторостроения.

[rimpocha]

Ватолин, Ратушняк, Смирнов, Юкин «Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео.» — М.: Диалог-МИФИ, 2002

Хорошая книга. Делал по ней практическую реализацию арифметического кодирования.

[AterCattus]

К арифметическому кодированию еще можно добавить интервальное. Очень близко, но в целых числах.