Page 124 - 4496

Залишимо значення чисел, що потрапили до першого
відрізка, без змін. Значення чисел, що потрапили до другого
відрізка, будемо відраховувати від межі першого. При цьому у
другому відрізку одержимо (2, 6, 9, 12, 18, 19). Значення
чисел, що потрапили до третього відрізка, будемо
відраховувати від межі другого. При цьому у третьому
відрізку одержимо (0, 8, 9, 16, 20). Оскільки у кожному
відрізку числа менші значення h=21, то для їх подання
достатньо 5 розрядів, і для їх зберігання потрібно вже не 96, а
5  16 = 80 двійкових розрядів.
Щоб знати, скільки чисел потрапило до кожного
відрізку, користуються значеннями границь. Для трьох
відрізків потрібні значення двох границь, які становлять
відповідно 5 (кількість чисел, що потрапили до першого
відрізка) і 11 (кількість чисел, що потрапили до першого і
другого відрізків). Для зберігання цих двох значень необхідно
ще 2  4 = 8 двійкових розрядів.
Таким чином, при застосуванні розглянутого методу
економія пам’яті складає 96 - (80 + 8) = 8 двійкових розрядів.
Даний приклад показує, що ефект стиснення залежить
від кількості відрізків, що впливає на кількість границь між
ними. Ефект стиснення зв’язаний також з шириною відрізка h,
оскільки від цього залежить кількість розрядів двійкового
подання чисел. Наприклад, при h = 16, коли всі числа у
відрізку менші 16, для їх подання достатньо 4 двійкових
розряди, і для зберігання всіх чисел потрібно тепер 4  16 = 64
розряди. Крім того, корисно, щоб величина h була степенем 2.
Дійсно, якби у нашому прикладі для ширини відрізка замість
5
значення h = 21 взяти значення h = 32 = 2 , то для зберігання
чисел потрібні були б ті ж самі 5  16 = 80 двійкових розряди,
але кількість відрізків зменшилась би до двох (0..31 і 32..63).
Припустимо, що в пам’яті необхідно розмістити M
впорядкованих за зростанням чисел. При цьому відомо, що
найбільше з них менше деякого N. При поданні цих чисел
звичайним двійковим кодом необхідний обсяг пам’яті
становить (в двійкових розрядах)
Q = M  log 2N.
7
Наприклад, якщо всі числа менші N = 128 = 2 , то для
7
зберігання кожного з них достатньо log 22 = 7 двійкових
121