Исключение повторения строк в последующих строках

Сжатие информации

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

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

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

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

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

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

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

r 5 r 3 8 6 r

9 0 1 2 3 4 5

6 7 r 9 1 r 3

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

9 5 7 0 1 2 4

...... 5

.... 3 8 6

..... 9 0

1 2 3 4 5 6 7

..... 9 1

...... 3

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

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

Пример.

Исходный массив Свернутый массив

1 2 3 4 5 6 7 1 2 3 4 5 6 7

1 2 1 3 4 8 6 К r 8 6 К 2 1

2 1 3 4 5 2 4 r 2 4 К r 9 К

2 1 3 4 5 2 9 4 2 9 r К r К

4 2 9 4 5 2 9 r К 5 r 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

4 2 9....

.......

.......

5..... 1

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

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

Например, если обозначить количество пропусков, соответственно X - 2, Z - 3, Y - 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 XX 2 Y2

1 9 7 1 1 3 7 4 3 2 Y X 0 Z X X1 ZXX

1 9 7 2 1 3 7 4 3 0 2

1 9 7 2 1 3 7 4 3 1

1 9 7 2 1 3 7 4 3 2

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

1 9 7 2 1 3 7 4 3 0

......... 1

......... 2

... 2..... 0

......... 1

......... 2

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

Дата добавления: 2014-01-06