Курсовая работа: Методы сжатия цифровой информации Метод Лавинского

если рядом стоящие буквы попадают в одну зону, то номер зоны пишется только один раз, а буквы чередуем.

В некоторых случаях можно использовать сочетание из двух и более букв в таблице, разделенные по зонам, принцип разделения можно оставить тем же.

Любой из перечисленных методов сжатия используется тогда, когда он дает максимальный эффект, который определяется величиной коэффициента сжатия или объемом сэкономленной памяти.

3. Выбор и обоснование решения задачи

4. Теоретическое обоснование метода Лавинского

Данный метод предполагает сжатие последовательности чисел путём разбиения последовательности на равномерные интервалы и отыскание числа не в его натуральном виде путем перебора всех подряд, а с помощью порядкового номера отсчета от ближайшей границы.

Сам метод состоит в следующем. Пусть имеем некоторое количество чисел М и максимальное по длине число L. Очевидно, что для хранения в натуральном виде этих чисел необходимо следующее количество ячеек

Q = M * log 2 L (1)

Лавинский предложил множество М разбить на N интервалов. Интервалы между собой равные и тогда очевидно, что для хранения самих чисел необходим следующий объем памяти

Q’ = M * log 2 (L / N) (2)

И нам необходимо хранить информацию об этих самых границах

Q” = (M – 1) * log 2 (N - 1) (3)

В целом объем памяти необходимый для самих чисел и памяти будет следующим

Q = Q’ + Q” (4)

Взяв производную из (4), для нахождения оптимального разбиения последовательности и приравняв ее нулю, получим

N ОПТ = М / ln M (5)

Формула (5) определяет оптимальное количество интервалов. Для определения величины самого интервала мы все количество возможных вариантов относим к количеству самого интервала, то есть для определения количества символов в интервале используем следующую формулу

C = 2 [log2 N] / N (6)

Для нахождения самого интервала (номер границы) используем следующее отношение

К = Х / С (7),

где Х – искомое число в натуральном виде.

После этого само число записывается, как порядковый отсчет этой границы и определяет экономию памяти как

D Q = QИСХ – QОПТ (8)

Пусть интервал 128, Х = 200, тогда К = 1.56. К лежит 2> K> 1, значит код числа составит 200 – 127 = 73.

5 П рограммная реализация

Для разработки программы был выбран язык программирования высокого уровня Delphi 5.0 (Object Pascal).

Он весьма полно выражает идеи структурного программирования. Это проявляется в том, что Delphi может успешно использоваться для записи программ на разных уровнях ее детализации, не прибегая к помощи блок-схем или специального языка проектирования программ. Средства языка Delphi позволяют осуществлять достаточный контроль правильности использования данных различных типов и программных объектов как на этапе трансляции, так и на этапе ее выполнения.

Delphi позволяет без особых трудностей реализовать удобный пользовательский интерфейс, не пребегая к написанию низкоуровневого кода.