Сжатие числовых последовательностей

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

Для размещения в двоичном представлении М чисел' наибольшее из которых равно N, потребуется объем памяти Q₀ = M([log₂N] + 1) раз­рядов. Для экономии объема памяти число 2 ^[log2N] разобьем на L рав ных частей. Максимальное число в полученном интервале будет не больше W = log₂ (N/L). Величина W определяет максимальную разрядность хранимых чисел Объем памяти ql для их хранения не будет превышать М-кратной величины

W: Q_l <= log₂ (N/L)

При сжатии методом записи младших разрядов в памяти будут хранить­ся адреса границ участков последовательности и порядковые номера чисел последовательности. Поскольку в последнем участке должно быть хотя бы одно число, то максимально возможное значение границы последнего участ­ка равно М-1, что при двоичном кодировании требует порядка log₂ М - 1 разрядов. Тогда общее число разрядов для хранения всех L-1 границ

Q_rp<=(L-l)*log₂M-l

Получаем, что общий объем памяти Q для хранения последовательности из М чисел с разбиением на L участков ограничен сверху:

Q(L) = Q_L + Q_rp <= log₂(N/L)+(L-l)*log₂M-l

Для того чтобы определить оптимальное число участков разбиения, не­обходимо полученную функцию Q(L) продифференцировать по L и прирав­нять производную к нулю. Получим, что

Q_опт = Мlog₂[(e*N*log_eM)/M]-log₂M-1

достигается при

L_опт=М/log_eM

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

Q_опт=М*log₂[(e*N*log_eM)/M]

При поиске информации в сжатой последовательности прежде всего опреде­ляют значение L_опти находят величину интервала между двумя границами:

C=(2^[log₂^N]+1)/L

Затем вычисляют, в каком именно из интервалов находится искомое чис­ло x:

K=x/C

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

Если используются не двоичные, а по основанию m, то отличие в расчетах будет состоять в том, что логарифмы будут по основанию m.

Пример. В памяти ЭВМ требуется рассчитать возрастающую последовательность чисел: 5, 17, 41, 126, 218, 222, 247, 257, 258, 305, 312, 370, 411, 450, 472, 500

Составить массив кодов при разбиении данной последовательности на 4 числовых участка. Оценить экономию памяти.

Решение. Количество чисел в последовательностиМ=16, наибольшее число N=500.

Величина интервала чисел на каждом участке С=500/4=125

Таким образом, в первую часть попадут числа до 125 (5, 17, 41). Поэтому первая граница С₁=3. Во вторую часть должны попасть числа от 125 до 250 (126, 218,222, 247). Следовательно С₂=3+4=7. В третьей части содержатся числа не превышающие 375 (257,258, 305, 312, 370), а в четвертой – 411, 450, 472, 500.

Код y числа x определяется по формуле y=x-C(i-1), где i – номер участка, в котором находится число х. Последовательность кодов имеет вид

5, 17, 41!! 1, 93, 97, 122!! 7, 8, 55, 62, 120!! 36, 75, 97, 125

Знаком!! отмечены границы участков.

При хранении без сжатия в двоичном представлении потребовалось бы Q=M([log₂N]+1)= 16*9=144 двоичных разряда. В сжатом виде Q=16*log₂(2.27*500*log_e16/16)-log₂(16-1)=108 двоичных разряда. Экономия памяти

144-108=36 двоичных разряда.

Подробная информация по теме занятия размещена в электронных учебниках (Lessons и «Медицинская информатика»)

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