), якому потрібно два проходи.
Huffman - Спочатку здається що створення файлу менших розмірів з вихідного без кодування послідовностей або виключення повтору байтів буде неможливою завданням. Але давайте ми змусимо себе зробити кілька розумових зусиль і зрозуміти алгоритм Гоффмана (Huffman). Втративши не так багато часу ми придбаємо знання і додаткове місце на дисках.
Стискаючи файл за алгоритмом Хаффмана перше що ми повинні зробити - це необхідно прочитати файл повністю і підрахувати скільки разів зустрічається кожен символ з розширеного набору ASCII. Якщо ми будемо враховувати всі 256 символів, то для нас НЕ буде різниці в стисненні текстового і EXE файлу.
Після підрахунку частоти входження кожного символу, необхідно переглянути таблицю кодів ASCII і сформувати уявну компоновку між кодами за зменшенням. Тобто не змінюючи місцезнаходження кожного символу з таблиці в пам'яті відсортувати таблицю посилань на них за зменшенням. Кожну посилання з останньої таблиці назвемо "Вузлом". Надалі (у дереві) ми будемо пізніше розміщувати покажчики які будуть вказує на цей "вузол". Для ясності давайте розглянемо приклад:
Ми маємо файл довжиною в 100 байт і має 6 різних символів в
собі . Ми підрахували входження кожного із символів у файл і отримали
наступне : p> + ----------------- + ----- + ----- + ----- + ----- + ---- - + ----- +
| cимвол | A | B | C | D | E | F |
+ ----------------- + ----- + ----- + ----- + ----- + ---- - + ----- |
| число входжень | 10 | 20 | 30 | 5 | 25 | 10 |
+ ----------------- + ----- + ----- + ----- + ----- + ---- - + ----- +
Тепер ми беремо ці числа і будемо називати їх частотою входження для кожного символу. Розмістимо таблицю як нижче. p> + ----------------- + ----- + ----- + ----- + ----- + ---- - + ----- +
| cимвол | C | E | B | F | A | D |
+ ----------------- + ----- + ----- + ----- + ----- + ---- - + ----- |
| число входжень | 30 | 25 | 20 | 10 | 10 | 5 |
+ ----------------- + ----- + ----- + ----- + ----- + ---- - + ----- +
Ми візьмемо з останньої таблиці символи з найменшою частотою. У нашому випадку це D (5) і який або символ з F або A (10), можна взяти будь-який з них наприклад A. Сформуємо з "вузлів" D і A новий "вузол", частота входження для якого дорівнюватиме сумі частот D і A:
Частота 30 10 5 10 20 25
Символу C A D F B E
| | p> + - + - +
+ + - +
| 15 | = 5 + 10
+ - +
Номер в рамці - сума частот символів D і A. Тепер ми знову шукаємо два символи з самими низькими частотами входження. Виключаючи з перегляду D і A і розглядаючи замість них новий "вузол" з сумарною частотою входження. Найнижча частота тепер у F і нового "вузла". Знову зробимо операцію злиття вузлів:
Частота 30 10 5 10 20 25
Символу C A D F B E
| | | p> | | | p> | + - + | | p> + - | 15 + + | p> + + - + ...
