Page 125 - 4496

розрядів. А якщо всі числа менші N = 10, то достатньо буде
вже 4 розрядів, оскільки log 210 = 3.322.
Розіб’ємо число N на L рівних частин. Тоді найбільше
N
число буде меншим і для збереження такого числа в
L
N
пам’яті буде достатньо log 2 двійкових розрядів, а
L
N
загальний обсяг потрібної пам’яті становитиме M  log 2 .
Тепер визначимо обсяг потрібної пам’яті L для
зберігання значень границь між окремими відрізками пам’яті.
Найбільше можливе значення границі принаймні на одиницю
менше M, оскільки останній відрізок має зберігати хоча б одне
число. Тому для зберігання значення границі потрібно log 2M
двійкових розрядів. Кількість границь на одиницю менша
кількості відрізків і становить L-1.
Таким чином, загальний обсяг потрібної пам’яті для
зберігання стиснутих чисел складає
N
Q = M log + (L - 1) log M .
Б 1 2 L 2
Знайдемо значення L, при якому обсяг пам’яті Q 1
приймає найменше значення. Для цього продиференціюємо Q 1
по L і прирівняємо похідну до нуля. Одержимо:
Q = M  log N - M log L + L log M - log M ;
2
2
1
2
2
1 ln M
Q 1 = - M  ln 2  L + ln 2 = 0;
M
L = .
ln M
Оцінимо ефективність розглянутого методу стиснення.
Якщо підставити отримане оптимальне значення L у вираз для
Q 1, то одержимо мінімальний обсяг пам’яті Q min для
розміщення M чисел. Економія обсягу пам’яті складає Q=Q-
Q min. Коефіцієнт стиснення визначається як відношення
обсягу пам’яті, потрібної для нестиснутих чисел, до обсягу
пам’яті, що займають стиснуті числа
K = Q / Q min.

122