Перетворення «переміщення на початок» (move-to-front transform) — це кодування даних (зазвичай потоку байтів ), призначене для покращення продуктивності методів ентропійного кодування під час стиснення. За ефективної реалізації це кодування достатньо швидке, що обґрунтовує його включення як додатковий крок в алгоритм стиснення даних.

Цей алгоритм був вперше запропонований Борисом Рябком під назвою "стос книжок" у 1980 році. Згодом він був перевідкритий Дж. Бентлі та ін. у 1986, як це зазначено у письмовому поясненні.

Перетворення. Ідея. Основна ідея полягає у тому, що кожен символ у даних замінюється на його індекс у стеку «нещодавно використаних символів». Наприклад, довгі послідовності однакових символів замінюються на відповідну кількість нулів, тоді як символ, що не використовувався тривалий час, замінюється на велике число. Зрештою, дані перетворюються на послідовність цілих чисел; якщо даним притаманна значна локальна кореляція, ці числа зазвичай є малими.

Надамо точний опис. Для простоти вважатимемо, що символами у даних є байти. Кожне значення байта кодується його індексом у списку байтів, який змінюється в процесі роботи алгоритму. Спочатку список упорядкований відповідно до значень байтів: (0, 1, 2, 3, ..., 255). Як наслідок, перший байт завжди кодується власним значенням. Однак після кодування байта це значення переміщується на початок списку (у стос) перед тим, як алгоритм переходить до наступного байта.

Приклад проллє більше світла на власне перетворення. Уявіть,що замість байтів ми кодуємо літери від 'а' до 'я'. Всього 33 літери українського алфавіту. Будемо кодувати наступну послідовність, де назву металу продублюємо останньою літерою для показовості прикладу: оловооо Згідно із домовленістю, список початково має наступний вигляд:(абвгґдеєжзиіїйклмнопрстуфхцчшщьюя). Перша літера в послідовності — 'о', яка з'являється з індексом 19, оскільки список індексується від 0 до 32. Ми додаємо 19 до вихідного потоку: 19 Літера 'о' переміщується на початок списку, утворюючи (оабвгґдеєжзиіїйклмнпрстуфхцчшщьюя). Наступна літера — 'л', яка тепер з'являється під індексом 16. Отже, ми додаємо 16 до вихідного потоку. Маємо: 19,16, після цього ми переміщуємо літеру 'л' на початок списку. Продовжуючи, отримуємо наступну закодовану послідовність: 19,16,1,4,1,0,0 Ітерація Послідовність Список оловооо 19 (абвгґдеєжзиіїйклмнопрстуфхцчшщьюя) оловооо 19,16 (оабвгґдеєжзиіїйклмнпрстуфхцчшщьюя) оловооо 19,16,1 (лоабвгґдеєжзиіїйкмнпрстуфхцчшщьюя) оловооо 19,16,1,4 (олабвгґдеєжзиіїйкмнпрстуфхцчшщьюя) оловооо 19,16,1,4,1, (волабгґдеєжзиіїйкмнпрстуфхцчшщьюя) оловооо 19,16,1,4,1,0 (овлабгґдеєжзиіїйкмнпрстуфхцчшщьюя) оловооо 19,16,1,4,1,0,0 (овлабгґдеєжзиіїйкмнпрстуфхцчшщьюя) Фінал 19,16,1,4,1,0,0 (овлабгґдеєжзиіїйкмнпрстуфхцчшщьюя) Легко переконатися, що це оборотне перетворення. Для декодування достатньо використати ідентичний список і замінювати кожен індекс у закодованому потоці на літеру, що знаходиться під цим індексом у списку. Зверніть увагу на відмінність від методу кодування: для декодування індекс використовується безпосередньо за призначенням, замість того, щоб обраховувати індекс для кожної літери.

Іншими словами, ви знову починаєте зі списку (абвгґдеєжзиіїйклмнопрстуфхцчшщьюя). Берете '19' із закодованого блоку та знаходите це значення в списку, що дає літеру 'о'. Потім переміщуєте 'о' на початок, отримуючи (оабвгґдеєжзиіїйклмнпрстуфхцчшщьюя). Після цього берете наступний індекс '16', знаходите його в списку — це дає літеру 'л', переміщуєте 'л' на початок… і так далі.

Впровадження алгоритму Деталі реалізації мають важливе значення для швидкодії, особливо під час декодування. Для кодування використання зв’язаного списку не дає явної переваги, тому цілком прийнятно використовувати масив для зберігання списку. У такому разі обчислювальна складність у найгіршому випадку становить $O(nk)$, де $n$ — довжина даних для кодування, а $k$ — довжина алфавіту (зазвичай це константа для конкретної реалізації).

Середня швидкодія є кращою, оскільки символи, що вживаються часто, з більшою ймовірністю опиняються на початку списку, що забезпечує швидше знаходження відповідностей. На цій ідеї ґрунтується принцип .

Однак для декодування ми можемо використовувати спеціальні структури даних для значного покращення швидкодії. [ потрібен приклад]

Python Далі наведена реалізація алгоритму «переміщення на початок» у Python .from collections.abc import Generator, Iterable

class MoveToFront: """ >>> mtf = MoveToFront() >>> list(mtf.encode("Wikipedia")) [87, 105, 107, 1, 112, 104, 104, 3, 102] >>> mtf.decode([87, 105, 107, 1, 112, 104, 104, 3, 102]) 'Wikipedia' >>> list(mtf.encode("wikipedia")) [119, 106, 108, 1, 113, 105, 105, 3, 103] >>> mtf.decode([119, 106, 108, 1, 113, 105, 105, 3, 103]) 'wikipedia' """ def __init__(self, common_dictionary: Iterable[int] = range(256)): """ Замість передачу словнику з алфавітом, зазвичай легше домовитися щодо початкового списку. Тут ми використовуємо 256 можливих значень байта. """ # використаємо ітераторний об'єкт, щоб його можна було перевикористати # потрібну кількість разів self.common_dictionary = list(common_dictionary)

def encode(self, plain_text: str) -> Generator[int]: # редагування алфавіту це погана практика. # Натомість, змінюйте його копію. dictionary = list(self.common_dictionary)

# Читаємо кожен символ. Змінюємо на байти для 256 значень. for c in plain_text.encode("latin-1"): # Знаходимо індекс для конкретного символа # [ обчислювальна складність O(k)] rank = dictionary.index(c) # закодований символ yield rank

# Оновлюємо словник [Θ(k) для вставки] dictionary.pop(rank) dictionary.insert(0, c)

def decode(self, compressed_data: Iterable[int]) -> str: """ Оборотна функція для декодування """ dictionary = list(self.common_dictionary) plain_text = []

# Читаємо кожен індекс у закодованій послідовності for rank in compressed_data: # Видаляємо цей символ зі словника e = dictionary.pop(rank) plain_text.append(e)

# Вставляємо символ на початок словника dictionary.insert(0, e)

# Повертаємо початкову послідовність. return bytes(plain_text).decode("latin-1") У цьому прикладі ми бачимо, як код MTF використовує перевагу трьох повторюваних літер «i» у вхідному слові. Проте загальний словник тут далекий від ідеалу, оскільки він ініціалізований друкованими символами ASCII, що стоять після маловживаних керуючих кодів. Це суперечить самій концепції MTF — тримати символи, що часто вживаються, на початку. Якщо змінити порядок у словнику (циклічно зсунути його), поставивши вживаніші символи на перші позиції, можна отримати краще кодування:from itertools import chain

def block32(x): return range(x, x+32)

class MoveToFrontMoreCommon(MoveToFront): """ >>> mtf = MoveToFrontMoreCommon() >>> list(mtf.encode("Wikipedia")) [55, 10, 12, 1, 17, 9, 9, 3, 7] """ def __init__(self): super().__init__( chain( # Сортуємо блоки ASCII: block32(ord("a") - 1), # спершу малий регістр, block32(ord("A") - 1), # поміт великий, block32(ord("!") - 1), # числа, пунктуація, block32(0), # контрольні коди, range(128, 256), # й не-ASCII коди ) )

if __name__ == "__main__": import doctest doctest.testmod()

Використання в алгоритмах стиснення даних Дане перетворення використовує локальну кореляцію символів для перерозподілу їхніх частот, що дозволяє ефективніше використовувати подальше ентропійне кодування. [ потрібне уточнення] Справді, щойно використані літери групуватимуться на початку списку. У випадку, коли використання літер демонструє локальні кореляції, це призведе до великої кількості малих чисел, таких як «0» та «1» у виводі.

Однак не всі дані мають такий тип локальної кореляції, і для деяких повідомлень це перетворення може фактично збільшити емпіричну ентропію (зробити розподіл частот менш передбачуваним для подальшого кодування). [ потрібне уточнення ]

Важливим застосуванням цього перетворення є стиснення на основі перетворення Барроуза — Вілера (BWT). Перетворення Барроуза — Вілера дуже ефективно створює послідовності з локальною кореляцією частот із текстів та деяких інших специфічних типів даних. Ефективність стиснення значно зростає, якщо застосовувати перетворення «переміщення на початок» після перетворення Барроуза — Вілера безпосередньо перед фінальним етапом ентропійного кодування.

Приклад Як приклад, уявімо, що ми хочемо стиснути монолог Гамлета («Бути чи не бути...»). Ми можемо порахувати, що розмір цього повідомлення становить 7033 біти. Спробувавши застосувати перетворення «переміщення на початок» безпосередньо, ми отримаємо повідомлення розміром 7807 бітів (що більше за оригінал). Причина полягає в тому, що англійська мова загалом не має високого рівня локальної кореляції частот. Однак, якщо ми спочатку застосуємо перетворення Барроуза — Вілера, а потім перетворення «переміщення на початок», то отримаємо повідомлення розміром 6187 бітів. Зауважте, що перетворення Барроуза — Вілера не зменшує ентропію повідомлення; воно лише перевпорядковує байти таким чином, щоб зробити перетворення MTF ефективнішим.

Однією з проблем базового перетворення «переміщення на початок» є те, що воно вносить однакові зміни для будь-якого символу, незалежно від його частоти. Це може призвести до погіршення стиснення, оскільки рідкісні символи можуть витісняти часто вживані на вищі позиції. З цієї причини було розроблено різні модифікації та альтернативи. Одна з поширених змін полягає в тому, що символи вище певної позиції можуть бути переміщені лише до певного порогу. Інший підхід — використання алгоритму, який підраховує локальну частоту кожного символу та використовує ці значення для визначення порядку символів у будь-який момент. Багато з цих перетворень все одно резервують нульовий символ для повторюваних символів, оскільки вони найчастіше зустрічаються в даних після перетворення Барроуза — Вілера.

Зв'язаний список «переміщення на початок»

Основна сторінка: Термін «переміщення на початок» (Move To Front, MTF) також використовується в дещо іншому контексті — як тип динамічного зв’язаного списку. У списку «переміщення на початок» кожен елемент переміщується на початок у момент звернення до нього. Це гарантує, що з часом доступ до елементів, які використовуються частіше, стає легшим.

Посилання

Зовнішні посилання

"Move to front" by Arturo San Emeterio Campos