поділ частот окремих букв англійського алфавіту показано на рис.1. Такий розподіл може бути побудовано і для російської мови. Таблиці кодування створюються заздалегідь і мають обмежений розмір. Цей алгоритм забезпечує найбільшу швидкодію і найменші затримки. Для отримання високих коефіцієнтів стиску статистичний метод вимагає великих обсягів пам'яті.
Рис. 1. Розподіл англійських букв по їх частоті використання
Величина стиснення визначається надмірністю оброблюваного масиву біт. Кожен з природних мов володіє певною надмірністю. Серед європейських мов російська володіє однією з найвищих рівнів надмірності. Про це можна судити за розмірами російського перекладу англійського тексту. Зазвичай він приблизно на 30% більше.
Якщо мова йде про віршованому тексті, надмірність може бути до двох разів вище.
У 1977 році Абрахам Лемпелю і Якоб Зів запропонували алгоритм стиснення даних, названий пізніше LZ77. Цей алгоритм використовується в програмах архівування текстів compress, lha, pkzip і arj. Модифікація алгоритму LZ78 застосовується для стискування двійкових даних. Ці модифікації алгоритму захищені патентами США. Алгоритм передбачає кодування послідовності біт шляхом розбиття її на фрази з подальшим кодуванням цих фраз. Суть алгоритму полягає в наступному.
Якщо в тексті зустрінеться повторення рядків символів, то повторні рядки замінюються посиланнями (покажчиками) на вихідну рядок. Посилання має формат lt; префікс, відстань, довжина gt ;. Префікс в цьому випадку дорівнює 1. Поле відстань ідентифікує слово в словнику рядків. Якщо рядки в словнику немає, генерується код символ виду lt; префікс, символ gt ;, де поле префікс=0, а поле символ відповідає поточному символу вихідного тексту. Звідси видно, що префікс служить для розділення кодів покажчика від кодів символ. Введення кодів lt; символ gt; дозволяє оптимізувати словник і підняти ефективність стиснення. Головна алгоритмічна проблема тут полягає в оптимальному виборі рядків, так як це передбачає значний обсяг переборовши.
Альтернативою статистичному алгоритмом стала схема стиснення, заснована на динамічно змінюваному словнику (напр., алгоритми Лембеля-Зива). Даний метод передбачає заміну потоку символів кодами, записаними в пам'яті у вигляді словника (таблиця перекодування). Співвідношення між символами і кодами змінюється разом зі зміною даних. Таблиці кодування періодично змінюються, що робить метод більш гнучким. Розмір невеликих словників лежить в межах 2-32 кілобайт, але більш високих коефіцієнтів стиску можна досягти при помітно великих словниках до 400 кілобайт.
Реалізація алгоритму можлива у двох режимах: безперервному і пакетному. Перший використовує для створення і підтримки словника безперервний потік символів. При цьому можливий мультипротокольний режим (наприклад, TCP/IP і DECnet). Словники стиснення і декомпресії повинні змінюватися синхронно, а канал повинен бути достатньо надійний (напр., X.25 або PPP), що гарантує відсутність спотворення словника при пошкодженні або втраті пакета. При спотворенні одного зі словників обидва ліквідуються і повинні бути створені знову.
Пакетний режим стиснення також використовує потік символів для створення і підтримки словника, але потік тут обмежений одним пакетом і з цієї причини синхронізація словників обмежена межами кадру. Для пакетного режиму достатньо мати словник обсягом, порядку 4 Кбайт. Безперервний режим забезпечує найкращі коефіцієнти стиснення, але затримка отримання інформації (сума часів стиснення і декомпресії) при цьому більше, ніж в пакетному режимі.
При передачі пакетів іноді застосовується стиснення заголовків, наприклад, алгоритм Ван Якобсона (RFC - 1 144). Цей алгоритм використовується при швидкостях передачі менше 64 Kбит/с. При цьому досяжно підвищення пропускної спроможності на 50% для швидкості передачі 4800 біт/с. Стиснення заголовків залежить від типу протоколу. При передачі великих пакетів на понад високих швидкостях по регіональних мережах використовуються спеціальні канальні алгоритми, незалежні від робочих протоколів. Канальні методи стиснення інформації не можуть використовуватися для мереж, що базуються на пакетної технології, SMDS (Switched Multi-megabit Data Service), ATM, X.25 і Frame Relay. Канальні методи стиснення дають хороші результати при з'єднанні за схемою точка-точка, а при використанні маршрутизаторів виникають проблеми - адже потрібно виконувати процедури стиснення/декомпресії в кожному маршрутизаторі, що помітно збільшує сумарний час доставки інформації. Виникає і проблема сумісності маршрутизаторів, яка може бути усунена процедурою ідентифікації при у становленні віртуального каналу.
Іноді для стиснення інформації використовують апаратні засоби. Такі...
