Алгоритм сжатия исторической информации
Категория реферата: Рефераты по информатике, программированию
Теги реферата: книга изложение, конспект зима
Добавил(а) на сайт: Jellina.
Предыдущая страница реферата | 1 2 3 | Следующая страница реферата
При этом каждая цифра ai < li, а каждый i-ый разряд имеет весовой коэффициент:
В работе В.И. Амелькина[5] сформулирована теорема существования и единственности такого разложения.
Использование полиадической системы счисления позволяет построить следующий алгоритм упаковки. Пусть задана целочисленная матрица A=ai,j , i=1,..,m, j=1,..,n.
С помощью преобразования
где
эту матрицу можно заменить двумя векторами N=nj и L=li, причем существует обратное преобразование
ai,j = [ nj / ri ] - [ nj / (lj*ri) ] * li , (6)
позволяющее по N и L восстановить любой элемент ai,j с погрешностью E=0. (Квадратными скобками здесь обозначена операция выделения целой части). Так как для хранения векторов N и L требуется меньше двоичных единиц, чем для хранения исконой матрицы, коэффициент сжатия
оказывается больше единицы. Здесь So- число двоичных единиц, требуемых для хранения исходной матрицы, Si- число двоичных единиц, требуемых для хранения элементов векторов N и L.
Как показали приведенные нами численные эксперименты, описанный выше алгоритм не обладает высокой эффективностью. К его недостаткам можно также отнести сложности, возникающие при реализации программ- упаковщиков на его основе.
В этой связи, мы поставили перед собой задачу совершенствования описанного алгоритма с целью повышения его эффективности и создания таких его версий, которые легко реализовывались бы в виде программ.
В нашем алгоритме кодируемая информация представляется в виде множества значений переменных байтового типа. Значения объединены в группы по четыре числа. Пусть таких групп в исходном информационном массиве выделено m (m>>4).
Выполнив для указанного массива описанную выше процедуру кодирования, получим два вектора - N с m элементами и L, состоящий из 4-х элементов.
Для повышения эффективности алгоритма (а под эффективностью мы здесь и в дальнейшем понимаем, в первую очередь, повышение коэффициента сжатия), выполним следующее преобразование.
Каждый из элементов полученного вектора N представим в виде 4-х разрядного двухсотпятидесятишестиричного числа и к полученной 4-х строчной матрице вновь применим процедуру полиадиического кодирования.
Многократно повторив описанную последовательность шагов, можно существенно повысить коэффициент сжатия исходной информации. В приведенных ниже таблицах показаны этапы сжатия исходной информации, представляющей собой некоторый набор латинских литер.
Таблицы рассчитывались с помощью табличного процессора из интегрированного пакета Works 2.0.
Приведенный пример подтверждает высокую эффективность описанного алгоритма.
Очевидно также, что на базе описываемого подхода могут быть реализованы быстрые и эффективные программы-упаковщики.
Таблица 1. Пример нумерационного кодирования
Исходный массив Компоненты вектора L
Рекомендуем скачать другие рефераты по теме: сочинение 7 класс, конспект урока в школе.
Предыдущая страница реферата | 1 2 3 | Следующая страница реферата