Давайте поглянемо на дрібний підхід, який у багатьох випадках може бути оптимальним:
Вона складала:
- Кількість елементів у діапазоні (з 31 бітами, оскільки списки у Java обмежено 2^31 - 1) елементів.
- Слідує за 1 бітом для кожного покажчика, вказуючи чи присутній елемент у наборі, чи ні.
Це реалізація, яку мала перша версія компресора фрактального зображення для збереження даних з дроблення і об'єднання триангуляцій.
Хоча вона не була оптимальною, оскільки ітерації дроблень прогресували, кількість елементів, які зберігатимуться, зменшилася, а це стало дуже малим відсотоком від загальної кількості, у цьому випадку можна значно покращити дріб'язкове кодування.
Тепер мета полягає у тому, щоб покращити це незначне кодування, щоб побачити, чи можна отримати більш стиснуте кодування з точки зору кількості використаних бітів.
Перший підхід : Коли кількість елементів у множині набагато менша за розмір діапазону, ми можемо взяти до уваги наявність індексів.
В цьому випадку, використання таке:
- 31 біта для кількості елементів у діапазоні.
- 31 біта для кількості елементів, що є у множині.
- 31 біт * кількість елементів у множині.
Другий підхід . Ми покращуємо кількість бітів на збережений елемент:
- 31 бітів для кількості елементів у діапазоні. Кількість бітів найбільшого елемента у діапазоні ( NumBits Elem ) було б підраховано.
- 5 бітів для збереження NumBits Elem .Отже, якщо кількість елементів у діапазоні дорівнює 1023, то 10 буде зберігатися в цих 5 бітах.
- NumBits Elem біти, які слід зберегти у наборі.
- NumBits Elem біти * кількість елементів у наборі.
Ну, помаленьку ми наближаємося до кращого кодування...
Третя наближення . Ми розуміємо, що, якщо ми впорядковуємо набір у порядку зростання, дельти (розбіжності між послідовними елементами) можуть бути закодовані з меншою кількістю бітів, ніж абсолютний елемент діапазону:
- 31 біта для кількості елементів у діапазоні.
- Ми підраховуємо найменший NumBits Elem для кодування елементу.Ми також підраховуємо список дельтів (список відмінностей між послідовними елементами впорядкованого списку елементів у множині).І, нарешті, ми також підрахуємо NumBitsDelta
- 5 бітів для збереження NumBits Elem .
- 5 бітів для збереження NumBitsDelta .
- NumBits Elem біти, які слід зберегти у наборі.
- NumBitsDelta біти * кількість елементів у наборі.
Здається, ми вже досягли оптимального кодування, чи не так?
Продовжимо...
Четверте наближення Ми зосереджуємося на тому факті, що може бути набагато більше число менших дельтів, і, можливо, лише кілька набагато більших, які розбивають NumBitsDelta теперь.
Під цими обставинами, можна знайти · nonOptimumBitsDelta ⇩ менше, ніж максимальна ⇩ NumMaxBitsDelta ♫ Що у свою чергу є меншим або рівним до ♫ NumBits Elem теперь.
Але як ми закодовуємо дельта елемент, який йде nonOptimumBitsDelta А?
Ну... оскільки дельта ніколи не буде 0 (у множині немає повторюваних елементів), ми можемо використати значення 0, щоб позначити, що це особливе значення.
І після цього 0 буде значення дельти, але закодовано цього разу з ♫ NumMaxBitsDelta теперь.Загальна кількість бітів може бути обчислена таким чином:
- 31 біт для кількості елементів у діапазоні. NumBits Elem щоб мати змогу шифрувати один елемент. Ми також обчислюємо список дельтів (список відмінностей між послідовними елементами впорядкованого списку елементів у наборі).
- 31 біт, щоб зберегти кількість елементів у Сеті.
- 5 бітів для збереження nonOptimumBitsDelta .
- 5 бітів для збереження NumMaxBitsDelta .
- nonOptimumBitsDelta біти * кількість елементів у наборі.
- NumMaxBitsDelta біт * кількість дельтів, що перевищує nonOptimumBitsDelta .
Чи ми вже досягли оптимального кодування?
П' ять наближення Ну... так как мы уже все запрограммировали...Ми можемо подумати про додаткову ситуацію...Чи може бути, що кодування доповнення множини з тим самим алгоритмом призведе до створення більш стиснутих результатів?
Доповнення множини сприймається як ще одна множина, що не співвідноситься з початковою множиною, чий зв'язок з початковою множиною є цілим діапазоном.
Тобто, доповнююча множина буде мати всі елементи діапазону відсутні у початковій множині, і жодного з них не знайдено у початковій множині.
Краса в тому, що з множини легко отримати доповнюючий набір, і тому ми могли б отримати оригінальний набір, закодувавши доповнюючий набір.
Очевидною програмою є набір елементів діапазону, окрім одного або декількох...
Ну... якщо ми зберігаємо лише відсутні (доповнювальні множини), вони можуть зберігатися в значно менших розмірах, чи не так?
Кодування у цьому випадку може бути таким:
- 31 біт для кількості елементів у діапазоні. NumBits Elem для кодування елемента. Ми також обчислюємо список дельтів (список відмінностей між послідовними елементами впорядкованого списку елементів у наборі).
- 1 біт, щоб зберегти, чи ми зберігаємо оригінальну множину, чи доповнення.Це зайвий біт.
- 31 біт, щоб зберегти кількість елементів у Сеті.
- 5 бітів для збереження nonOptimumBitsDelta .
- 5 бітів для збереження NumMaxBitsDelta .
- nonOptimumBitsDelta біти * кількість елементів у наборі.
- NumMaxBitsDelta біт * кількість дельтів, що перевищує nonOptimumBitsDelta На місцях, де вони з'являються.
Ну... сейчас мы говорим.
Отже, це місце, де я застрягла... але я знаю, що якщо всі ці дива можна було б зробити, що не могло бути зроблено пошуком інших візерунків, або просто використовуючи компресор без втрат, наприклад, "застібку" або 7z...
Придется подождать, в следующий раз на заднем пальнике...
