ноді виявляється досить ефективним. Саме подібний алгоритм використовується для стиснення зображень у файлах PCX. Він полягає в наступному: будь-якій послідовності повторюваних вхідних символів ставиться у відповідність набір з трьох вихідних символів: перший-байт префікса, що говорить про те, що зустрілася вхідна актуальна послідовність, другий-байт, що визначає довжину вхідної послідовності, третій-сам вхідний символ - < ; prefix, length, symbol>. Найкраще роботу алгоритму пояснити на конкретному прикладі. p align="justify"> Наприклад: нехай є (шістнадцятковий) текст виду
05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FF FF FF
з 20 байт. Виберемо як префікса байт FF. Тоді на виході архіватора ми отримаємо последовательность06 05 FF 1 лютого FF 3 червня FF 1 Травня FF 1 березня FF 04 FF
Її довжина-18 байт, тобто досягнуто деяке стиснення. Однак, неважко помітити, що при кодуванні деяких символів розмір вихідної коду зростає (наприклад, замість 1 січня - FF 1 лютого). Очевидно, одиночні або двічі (тричі) повторювані символи кодувати не має сенсу - їх треба записувати в явному вигляді. Отримаємо нову послідовність: 5 червня 1 січня FF 3 червня 3 травень FF 04 FF
довжиною 13 байт. Досягнута ступінь стиснення: 13/20 = 65%. p align="justify"> Неважко помітити, що префікс може співпасти з одним із вхідних символів. У цьому випадку вхідний символ може бути замінений своїм префіксним поданням, наприклад: те ж саме, що і FF 01 FF (три байти замість одного).
Тому, від правильного вибору префікса залежить якість самого алгоритму стиснення, так як, якщо б у нашому початковому тексті часто зустрічалися поодинокі символи FF, розмір вихідної тексту міг би навіть перевищити вхідний. Загалом, випадку в якості префікса слід вибирати найрідкісніший символ вхідного алфавіту. p align="justify"> Можна зробити наступний крок, підвищуючий ступінь стиснення, якщо об'єднати префікс і довжину в одному байті. Нехай префікс-число F0 ... FF, де друга цифра визначає довжину length від 0 до 15. У цьому випадку вихідний код буде двухбайтного, але ми звужуємо діапазон представлення довжини з 255 до 15 символів і ще більш обмежуємо себе у виборі префікса. Вихідний же текст для нашого прикладу буде мати вигляд: 05 F2 01 F6 03 5 березня F4 FF
Довжина-10 байт, ступінь стиснення-50%.
Далі, так як послідовність довжиною від 0 до 3 ми умовами не кодувати, код length зручно використовувати зі зміщенням на три, тобто 00 = 3, 0F = 18, FF = 258, упаковуючи за один раз більше довгі ланцюжки.
Якщо одиночні символи зустрічаються досить рідко, хорошою може виявитися модифікація алгоритму RLE взагалі без префікса, тільки . У цьому випадку одиночні символи також обов'я...
