Сжатие числовых массивов

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

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

Пример 2.11. Имеется массив:

После сжатия он будет иметь вид:

р5р386р

67р91рЗ

Восстановление (развертывание) массива выполняется в два этапа. Пер­вый этап осуществляется с конца (назовем его обратным ходом). Переход на следующую строку производится при выполнении одного из двух условий: либо в случае полного заполнения предыдущей строки, либо при встрече символа р.

Применительно к рассматриваемому примеру результат этого этапа вы­глядит следующим образом (символом о обозначены еще не восстановленные числа):

9570124 000000 5 0000386 00000 90 1234567 0000091 000000З

Заключительный этап (прямой ход) развертывания массива состоит в ко­пировании вместо символа о элементов из соответствующих разрядов бли­жайшей сверху заполненной строки, просмотр массива при этом ведется сверху вниз: вначале символы 957012 копируются из первой строки в соот­ветствующие разряды второй, затем 9570 - из второй строки в третью и т.д. до заполнения всего массива.

Этот метод можно обобщить для сжатия массивов, в которых повто­ряющиеся разряды встречаются в середине строки. Тогда наряду с сим­волом, определяющим начало повторяющегося участка, необходимо ввести еще один дополнительный символ k для отметки конца строки: разверты­вание будет вестись от k до k. Если повторяющихся участков несколько в одной строке, то потребуется ввести специальные символы для обозначе­ния числа пропусков. Общий же принцип сжатия и восстановления остается прежним.

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

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

Прямой ход осуществляется также копированием элементов верхней стро­ки в соответствующие пропущенные разряды нижней строки.

Пример 2.13. В исходном массиве имеются по несколько повторяю­щихся участков в строке. Вводим дополнительные символы: повторяющиеся участки из 2 символов обозначим х, из трех - у, из пяти - z.

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

Не нашли, что искали? Воспользуйтесь поиском: