ИННОВАЦИИ БИЗНЕСУ

Результат выполнения научно-исследовательской работы.

Анализ распределения вероятностей числовых значений смещений, полученных в результате применения «deflate»-метода (разновидность lz77, используемая утилитами компрессии формата zip) показывает, что оно близко к геометрическому типу, характерному для распределения интервалов между последовательными появлениями сообщения с вероятностью , или более точно, представляет собой композицию множества распределений данного типа для строковых фрагментов с различной вероятностью. Вид распределения естественно объясняется интервальным характером смещений текстовых фрагментов в методе lz77 и, как показали проведенные экспериментальные исследования, типичен для большинства компьютерных файлов. Основные неоднородности относительно типично «гладкой» экспоненциально убывающей функции геометрического распределения наблюдаются в области малых смещений. На эту же область приходится большая часть строковых фрагментов lz77. Следовательно, здесь целесообразно применение вероятностных адаптивных кодеров, дающих при кодировании алфавитов небольшой мощности низкую избыточность. С другой стороны, выполненные нами модельные вычислительные эксперименты показали, что при геометрическом характере статистического распределения вероятностей уже при значениях энтропии 7,5 бит на сообщение прямой (т.е. без применения каких либо перестановочных схем типа mtf) параметрически адаптивный кодер [1,2] дает меньшие, чем арифметический в среднем на 0,1 бит значения избыточности. При этом не требуется память для хранения каких-либо структур данных и используется лишь целочисленная арифметика. Это обстоятельство делает целесообразным его использование для кодирования в области относительно больших смещений.

Для эффективного в целом адаптивного кодирования по схеме "deflate" без ограничения величины окна просмотра и длин строк предлагается алгоритм кодирования, в котором также как и в базовом варианте "deflate" для кодирования длин и смещений используются отдельные деревья Хаффмана, но в отличие от последнего, во-первых, используется динамическое кодирование Хаффмана и, во-вторых, в каждом дереве одно кодовое слово с максимальным индексом закрепляется в качестве идентификатора следующего вслед за ним прямого параметрически адаптивный кода [1,2], используемого для кодирования значений, превышающих соответствующий указанному кодовому слову Хаффмана максимальный индекс. Такая схема позволяет с одной стороны сохранить малую избыточность, присущую точным вероятностным кодерам в области малых значений энтропии и параметрически адаптивному кодеру в области больших ее значений, а с другой стороны, получить достаточно высокую эффективность по параметрам память/время вследствие ограничения размера дерева Хаффмана. При этом параметры эффективности становятся независимыми от размера скользящего окна, что позволяет снять ограничения как на максимальную длину строки, так и на ее смещение.

Алгоритм кодирования:

1.

Здесь - кодируемое число; - последний индекс в дереве Хаффмана, на единицу меньший числа поддерживаемых деревом кодов.

2.Кодировать по Хаффману и вывести его код в выводной поток.

3.

3.1.

3.2.Сформировать параметрически адаптивный с параметром

код и вывести его в выводной поток.

3.3. Настроить параметр по значению .

4. Конец.

Алгоритм декодирования:

1.Декодировать очередной код Хаффмана из вводного потока

и присвоить его переменной .

2.

2.1. Считать из вводного потока параметрически адаптивный

с параметром код и присвоить его переменной .

2.2. Настроить параметр по значению .

2.3.

3.Конец.

Литература:

1. Гаджиев Ю.А. Параметрически адаптивный ранговый код. Вестник Дагестанского государственного технического университета. Технические науки. Вып. 1., Махачкала, 1997, стр. 3033.

2. Гаджиев Ю.А. Об избыточности кодирования в параметрически адаптивной ранговой схеме. Вестник Дагестанского государственного технического университета. Технические науки. Вып. 2., Махачкала, 1998, стр. 23-26.