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

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

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

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

Алгоритм LZW

Алгоритм кодирования последовательности неодинаковых символов.

Предложен Дж. Зивом (J.Ziv), А. Лемпелом (A. Lempel) 1977 г., доработан Терри А. Велчем (Terry A.Welch) 1984 г.

Основан на кодировании подстроки в строке.

Создается таблица строк:

Таблица 4.2.1 – Проинициализированная таблица строк

Элемент	Префикс	Суффикс
…	-1 -1 -1 … -1	…

Из однобайтных значений в столбце “Суффикс” алгоритм по мере прохождения файла строит многобайтовые образцы.

Пример.

Пусть обрабатывается строка: Going, going, gone!

После инициализации таблицы строк программа сжати читает букву “G” (код 71) из входного файла и записывает 71 в выходной файл.

Затем читается “o” (код 111) и ищется в таблице строк элемент с префиксом 71 и суффиксом 111. Так как такого элемента нет, то он добавляется в таблицу и выводится суффикс 111 в выходной файл. Послде этого суффикс 111 переносится в префикс и читается новое значение суяяикса из входного файла.

Следующая буква “i” (код 105) становится новым суффиксом. Ищется элемент с префиксом 111 и суффиксом 105. Так как такого элемента нет, то он добавляется в таблицу, а суффикс - в выходной файл. Теперь таблица строк содержит 258 элементов, а выходной файл содержит значения 71, 11, 105:

Таблица 4.2.2 – Таблица из 258 элементов

Элемент	Префикс	Суффикс	Строка
…	-1 -1 -1 … -1	…	Go oi

Программа будет добалять двух симольные последовательности в балицу, пока не дойдет до 9 – й буквы (“o” во втором слове going ). В этой точке балица содержит 264 элемента:

Таблица 4.2.3 – Таблица из 264 элементов

Элемент	Префикс	Суффикс	Строка
…	-1 -1 -1 … -1	…	Go oi in ng g, ,# #g go

Суффикс 111 (из элемента 263) перемещается в префикс и читается новый суффикс “i” (код 105) из входного файла. При поиске элемента с префиксом 111 и суффиксом 105 находится совпадение в элементе 257. Поэтому программа делает сжатие:

- значение 257 назначается префиксу и читается новый суффикс “n” (код 110) из входного файла.

Не найдя в таблице строк элемента с префиксом 257 и суффиксом 110, программа добавляет его в таблицу.

Окончательная таблица будет иметь следующий вид:

Таблица 4.2.4 – Окончательная таблица после обработки всей строки

Элемент	Префикс	Суффикс	Строка
…	-1 -1 -1 … -1	… -1	Go oi in ng g, ,# #g go oin ng, ,#g gon ne e! !

Чтобы получить выходной файл нужно просмотреть содрежимое столбца “Префикс”, начиная с элемента 256 и заканчивая последним.

Наш выходной файл будет содержать 15 – ть значений вместо 20 – ти.

Достоинство LZW:

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