Comments 10
А как из «3H&3A» восстановить «HAHAHA&»?
Приведу алгоритм на данном примере:
«Распаковываем» RLE запись «3H&3A» в «HHH&AAA».
Изначально есть N пустых строк, где N — длина строки.
Потом последовательно выполняем действия «добавить» и «сортировать»
Добавить: к каждой строке приписываем слева один символ из записи с индексом, равным номеру строки.
Сортировать: отсортировать полученные строки.
В итоге берем строку, у которой "&" -. последний символ
«Распаковываем» RLE запись «3H&3A» в «HHH&AAA».
Изначально есть N пустых строк, где N — длина строки.
Потом последовательно выполняем действия «добавить» и «сортировать»
Добавить: к каждой строке приписываем слева один символ из записи с индексом, равным номеру строки.
Сортировать: отсортировать полученные строки.
Пример последовательных шагов
В итоге берем строку, у которой "&" -. последний символ
Как и прошлая статья в серии, эта значительно обделяет вниманием BWT семейство алгоритмов. Там ведь столько всего интересного: DC, MTF, WFT, IF, и другие, а не только bzip2, который, к слову, не так уж и прост в своей BWT реализации. С другой стороны, LZ расписано довольно подробно, и на этом спасибо!
На LZW патенты в США, Канаде, Европе и Японии вроде бы уже протухли.
>LZMW
>… Действует, как LZMW
Не может быть :)
Кстати, тем, кому интересно более глубоко заглянуть в мир алгоритмов сжатия без потерь, рекомендую книгу:
Lossless Compression Handbook // Khalid Sayood, editor — 2003 — ISBN-13: 978-0126208610 — ISBN-10: 0126208611
В ней разбирается всё: от теории через Колмогоровскую сложность, через LZ, BWT, арифметическое кодирование до алгоритмов TIFF, PNG и аспектов реализации аппаратных ускорителей сжатия.
Lossless Compression Handbook // Khalid Sayood, editor — 2003 — ISBN-13: 978-0126208610 — ISBN-10: 0126208611
В ней разбирается всё: от теории через Колмогоровскую сложность, через LZ, BWT, арифметическое кодирование до алгоритмов TIFF, PNG и аспектов реализации аппаратных ускорителей сжатия.
К арифметическому кодированию еще можно добавить интервальное. Очень близко, но в целых числах.
Sign up to leave a comment.
Алгоритмы сжатия данных без потерь, часть 2