Алгоритм сжатия
Автор Hj hj задал вопрос в разделе ВУЗы, Колледжи
перечислите и охарактеризуйте основные алгоритмы сжатия данных и получил лучший ответ
Ответ от Monika messi[гуру]
Алгоритмы сжатия данных
[править] Алгоритмы сжатия без потерь
* Преобразование Барроуза — Уилера (также известен как англ. BWT) — предварительная обработка данных для улучшения сжатия без потерь
* Преобразование Шиндлера (англ. ST) — модификация преобразования Барроуза — Уилера
* Алгоритм DEFLATE — популярный свободный алгоритм сжатия (используется в библиотеке zlib)
* Дельта-кодирование — эффективно для сжатия данных, в которых последовательности часто повторяются
* Инкрементное кодирование — дельта-кодирование применяемое к последовательности строк
* Алгоритм сжатия PPM
* Кодирование длин серий (Групповое кодирование, также известен как англ. RLE) — последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений
* Алгоритм SEQUITUR (англ. ) — сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных
* Вейвлет-кодирование на основе вложенных нуль-деревьев (англ. ) (EZW-кодирование)
* Энтропийное кодирование — схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов
o Алгоритм Шеннона — Фано — самый простой алгоритм кодирования
o Алгоритм Хаффмана — алгоритм построения кода при помощи кодовых деревьев
+ Адаптивное кодирование Хаффмана (англ. ) — техника адаптивного кодирования, основывающаяся на коде Хаффмана
o Усечённое двоичное кодирование (англ. ) — используется для однородного вероятностного распределения с конечным алфавитом
o Арифметическое кодирование — развитие энтропийного кодирования
+ Адаптивное арифметическое кодирование — техника адаптивного кодирования, основывающаяся на арифметическом кодировании
o Кодирование расстояний (англ. ) — метод сжатия данных, который близок по эффективности к арифметическому кодированию
* Энтропийное кодирование с известными характеристиками
o Унарное кодирование — код, который представляет число n в виде n единиц с замыкающим нулём
o дельта|гамма|омега-кодирование Элиаса (англ. Elias coding) — универсальный код, кодирующий положительные целые числа
o Кодирование Фибоначчи — универсальный код, который кодирует положительные целые числа в двоичные кодовые слова
o Кодирование Голомба — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
o Кодирование Райса (англ. ) — форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением
[править] Алгоритмы сжатия с потерями
* Линейное предсказывающее кодирование (англ. ) — сжатие с потерями, представляющее спектральную огибающую цифрового сигнала речи в сжатом виде
* А-закон — стандартный алгоритм компандирования. Применяется в РФ.
* Мю-закон — стандартный алгоритм компандирования
* Фрактальное сжатие — метод, использующий фракталы для сжатия изображений
* Трансформирующее кодирование (англ. ) — тип сжатия данных для «естественных» данных, таких как аудиосигналы или фотографические изображения
* Векторное квантование — техника, часто используемая в сжатии данн