ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Iassenev                     2:5020/400     06 May 2003  12:46:36
 To : Alexey Panin
 Subject : Re: Сжатие
 -------------------------------------------------------------------------------- 
 

 > Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо
 
 более
 
 > давнюю, нежели история развития вычислительной техники, которая (история)
 > обычно шла параллельно с историей развития проблемы кодирования и шифровки
 > информации.
 > Сжатие способом кодирования серий (RLE)
 > Алгоритм Хаффмана
 > Арифметическое кодирование
 > Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)
 > LZ-compression.
 
 Я бы ещё добавил к этому списку следующие методы
 
 - PPM сжатие (predict by partial matching) - суть арифметическое кодирование
 (или Хаффмэн), но вероятности символов расчитываются учитывая не только
 информацию об одиночных символах, но и двойках, тройках и т.д., нынешние PPM
 архиваторы используют порядок контекстной модели в районе 6 (пример -
 архиватор HA и один из методов в 3-м RARe) и являются лучшими упкаовщиками,
 но очень медленными, причём как при сжатии, так и при расжатии, т.к.
 операции выполняются абсолютно те же самые.
 
 - сжатие с помощью преобразования Барроуза-Уиллера, т.н block-sorting
 compression (поищите информацию по Burrows-Wheeler-Transformation, потому
 как объяснить почему оно вообще расжимает и почему ещё и сжимает хорошо
 довольно непросто). Пример архиваторов - BZip, Compressia. Очень
 качественные упаковщики + быстрее, чем PPM, но медленнее, чем LZ-77. По
 сути, метод является (это очень-очень неочевидно) PPM с бесконечной
 контекстной моделью.
 
 С уважением,
 Дмитрий Ясенев.
 
 P.S. Всё-таки чуть-чуть расскажу о BWT. Суть его в том, что строка делится
 на большие блоки (допустим, по мегабайту). Далее, сортируем все циклические
 сдвиги блока влево, запоминаем номер исходной строки в отсортированной
 последовательности циклических сдвигов, берём последний столбец матрицы, в
 которой отсортированные циклические сдвиги являются строками и его и сжимаем
 (стандартно сначала применяют MTF (Move-to-Front), а затем пытаются
 эффективно кодировать последовательности нулей (или арифметическое
 кодирование, или 1-2-coding, или что-нибудь своё)).
 --- ifmail v.2.15dev5
  * Origin: Unknown (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Сжатие   Dmitriy Iassenev   06 May 2003 12:46:36   Сжатие   Aleksey Vaneev   06 May 2003 20:17:23