СЖАТИЕ ИНФОРМАЦИИ.

Сжатие информации представляет собой операцию, в результате которой данному коду или сообщению ставится в соответствии более короткий код или сообщение1.

Сжатие информации имеет целью – ускорение и удешевление процессов механизированной обработки, хранение и поиск информации, экономия памяти ЭВМ. При сжатии следует стремиться к минимальной неоднозначности сжатых кодов при максимальной простоте алгоритмов сжатия. Рассмотрим наиболее характерные методы сжатия информации.

Сжатие информации делением кода на части, меньше некоторых наперед заданной величины А, заключается в том что исходный код делится на части, меньше А, после чего полученные части кода складываются между собой либо по правилам двоичной арифметике, либо по модулю 2. например исходный код 101011010110, А=4

	1 0 1 0		1 0 1 0
+ 1 1 0 1			1 1 0 1
	0 1 1 0		0 1 1 0
	1 1 1 0 1	- сжатый код	0 0 0 1

Сжатие информации с побуквенным сдвигом в каждом разряде [5], как и предыдущий способ, не предусматривает восстановление сжимаемых кодов, а применяется лишь для сокращения адреса либо самого кода сжимаемого слова в памяти ЭВМ.

Предположим исходное слово «газета» кодируется кодом, в котором длина кодовой комбинации буквы l = 8:

г – 0000111; а – 11110000; з – 01100011; е – 00010111; т – 11011000;

Полный код слова «Газета»

010001111111000001100011000101111101100011110000.

Сжатие осуществляется сложением по модулю 2 двоичных кодов букв сжимаемого слова с побуквенным сдвигом в каждом разряде,

Рис.8.

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

, (88)

где - максимально допустимая длина (количество двоичных разрядов) сжатого кода; N – возможное количество адресов в ЗУ.

Если представить процесс побуквенного сдвига, как показано на рис. 8, а, то длина сжатого кода

,

где k ­– число побуквенных сдвигов; l – длина кодовой комбинации букв.

Так как сдвигаются все буквы, кроме первой, то и число сдвигов k = L – 1, где L – число букв в слове. Тогда

.

В русском языке наиболее длинные слова 23 – 25 букв. Если принять L_макс = 23, с условием осуществления побуквенного сдвига с каждым шагом равно на один разряд, для n и l могут быть получены следующие соотношения

Если значение n_макс не удовлетворяет неравенству (88), можно конечные буквы слова складывать по модулю 2 без сдвига относительно предыдущей буквы, как это показано на рис. 8, б.

Например, если для предыдущего примера со словом «Газета» n_макс = 11, сжатый код будет иметь вид:

	1 1 1 1 0 0 0 0
	1 1 0 1 1 0 0 0
	0 0 0 1 0 1 1 1
		0 1 1 0 0 0 1 1
	1 1 1 1 0 0 0 0
	0 1 0 0 0 1 1 1
	0 0 1 1 1 0 1 0 0 1 1

Метод сжатия информации на основе исключения повторения в старших разрядах последующих строк массивов одинаковых элементов старших разрядов предыдущих строк массивов основа на том, что в сжатых массивах повторяющиеся элементы старших разрядов заменяются некоторым условным символом.

Очень часто обрабатываемая информация может быть представлена в виде набора однородных массивов, в которых элементы столбцов или строк массивов расположены в нарастающем порядке. Если считать старшими разрядами разряды расположенные левее данного элемента, а младшими расположенные правее, то можно заметить, что во многих случаях строки матриц отличаются друг от друга в младших разрядах. Если при записи каждого последующего элемента массива отбрасывать все повторяющиеся в предыдущем элементы, например в строке стоящие подряд элементы старших разрядов, то массивы могут быть сокращены от двух до десяти и более разрядов [2].

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

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

Для примера рассмотрим следующий массив:

9 5 7 0 1 2 4

9 5 7 0 1 2 5

9 5 7 0 3 8 6

9 5 7 0 3 9 0

1 2 3 4 5 6 7

1 2 3 4 5 9 1

1 2 3 4 5 9 3

Свернутый массив будет иметь вид:

9 5 7 0 1 2 4

5 3 8 6

9 0 1 2 3 4 5

6 7 9 1 3

Расшифровка* (развертывание) происходит с конца массива. Переход на следующую строку происходит по двум условиям: либо по заполнению строки либо при встрече .

9 5 7 0 1 2 4

. . . . . . 5

. . . . 3 8 6

. . . . . 9 0

1 2 3 4 5 6 7

. . . . . 9 1

. . . . . . 3

Пропущенные цифры заполняются автоматически по аналогичным разрядам предыдущей строки. Заполнение производится с начала массива. Этот метод можно развить и для свертывания массива, в которых повторяющееся разряды встречаются не только с начала строки. Если в строке один повторяющийся участок то кроме добавляют дополнительный символ К, означающий конец строки. Расшифровка ведется от К до К. длина строки известна. Нужно чтобы оставшиеся между К цифры вместе с пропущенными разрядами составляли полную строку. При этом нам все равно, в каком месте строки выбрасываются повторяющееся

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

Исходный массив		Свернутый массив
1 2 3 4 5 6 7		1 2 3 4 5 6 7
1 2 3 4 5 8 6		К 8 6 К 2 1
2 1 3 4 5 6 4		2 4 К 9 К
2 1 3 4 5 2 9		4 2 9 К К
4 2 9 4 5 2 9		К 5 1 К
4 2 9 4 5 2 9
4 2 9 4 5 2 9
5 2 9 4 5 2 1

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

Процесс развертывания массива осуществляется следующим образом: переход на следующую строку происходит при встрече К

1 2 3 4 5 6 7

. . . . . 8 6

2 1 . . . 2 4

. . . . . . 9

4 2 9 . . . .

. . . . . . .

. . . . . . .

5 . . . . . 1

Пропущенные цифры заполняются по аналогичным разрядам предыдущей строки начиная с конца массива.

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

Например, если обозначить количество пропусков, X – 2; Y – 3; Z – 5, то исходный и свернутый массивы будут иметь вид:

Исходный массив		Свернутый массив
1 9 7 1 1 3 7 4 3 0		1 9 7 1 1 3 7 4 3 0
1 9 7 1 1 3 7 4 3 1		Z X X 1 Z X X 2 Y 2
1 9 7 1 1 3 7 4 3 2		Y X 0 Z X X 1 Z X X 2
1 9 7 2 1 3 7 4 3 0
1 9 7 2 1 3 7 4 3 1
1 9 7 2 1 3 7 4 3 2

Процесс развертывания массива осуществляется следующим образом: длина известна, количество пропусков определяется символами X, Y, Z

1 9 7 2 1 3 7 4 3 0

. . . . . . . . . 1

. . . . . . . . . 2

. . . 2 . . . . . 0

. . . . . . . . . 1

. . . . . . . . . 2

Пропущенные цифры заполняются по аналогичным разрядам предыдущей строки. Условием перехода на следующую строку является заполнение предыдущей строки.

Метод Г.В. Лавинского основан на том что в памяти машины хранятся сжатые числа, разрядность которых меньше разрядности реальных чисел. Эффект сжатия достигается за счет того, что последовательность предварительно упорядоченных чисел разбиваются на ряд равных отрезков, внутри которых отчет ведется не по их абсолютной величине, от границы предыдущего отрезка. Разрядность чисел получаемых таким образом, меньше разрядности соответствующих им реальных чисел[18,21].

Для размещения в памяти ЭВМ М кодов, в которых наибольшее из кодируемых чисел равно N, необходим объем памяти .

С ростом N кодовой комбинации будет расти как .

Для экономии объема памяти Q, число , где выражение в скобках – округленное значение до ближайшего целого числа разбивают на L равных частей. Максимальное число в полученном интервале чисел будет не больше . Величина определяет разрядность хранимых чисел, объем памяти для их хранения будет не больше М . Если в памяти ЭВМ хранить адреса границ отрезков и порядковые номера хранимых чисел, отсчитываемых от очередной границы, то определяет разрядность чисел для выражения номера границы (в последнем интервале должно быть хотя бы одно число); объем памяти для хранения номеров границ будет (L-1) , (L-1) – число границ между отрезками (это число всегда на единицу меньше чем число отрезков). Общий объем памяти при этом будет не больше

. (89)

Чтобы найти, при каких L выражение (89) принимает минимальное значение достаточно продифференцировать его по L и прировнять производную к нулю. Нетрудно убедиться, что Q_мин будет при

. (90)

если подставить значение в выражение (89), то получим значение объема памяти при оптимальном количестве зон, на которые разбиваются хранимые в памяти ЭВМ числа,

. (91)

Для значений М > 100 при вычислениях можно пользоваться приближенной формулой

. (92)

При поиске информации в памяти ЭВМ прежде всего определяют значения L_О.ПТ и находят величину интервала между двумя границами.

Затем определяют, в каком именно из интервалов находится искомое число х .

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

---

1 кодирование от сжатия отличается тем, что коды почти всегда длиннее кодируемых сообщений, так как число качественных признаков вторичного алфавита (кода) обычно не бывает больше числа качественных признаков первичного алфавита (кодированных сообщений). Говоря «сжатый код», будем иметь ввиду комбинацию, представляющую кодируемое понятие после процедуры сжатия.

Предлагаю ознакомиться с аналогичными статьями: