Онлайн-алгоритм обновления списков: различия между версиями

Линейные списки представляют собой одну из возможностей представления множества элементов. Конечно, существуют и другие структуры данных, такие как сбалансированные деревья поиска или хэш-таблицы, которые, в зависимости от конкретного приложения, могут хранить множество более эффективным способом. В целом линейные списки полезны, когда множество невелико и состоит всего из нескольких десятков элементов. Наиболее важным способом применения алгоритмов обновления списков являются локально адаптивные схемы сжатия данных. Барроуз и Уилер [10] разработали схему сжатия данных с помощью линейных списков, которая обеспечивает лучшее сжатие, чем алгоритмы на основе подхода Лемпеля-Зива. Перед описанием этого алгоритма в следующем параграфе сначала приводится очень простая и легко реализуемая схема сжатия данных, предложенная Бентли и др. [8].

В задаче сжатия данных дается строка <math>S</math>, которая должна быть сжата, то есть представлена с использованием меньшего количества бит. Строка <math>S</math> состоит из символов, где каждый символ является элементом алфавита <math>\Sigma = \{ x_1, ..., x_n \}</math>. Идея схем сжатия данных с использованием линейных списков заключается в том, чтобы преобразовать строку <math>S</math> символов в строку <math>I</math> целых чисел. Кодер поддерживает линейный список символов, содержащихся в <math>\Sigma</math>, и считывает символы из строки <math>S</math>. Всякий раз, когда символ <math>x_i</math> должен быть сжат, кодер ищет текущую позицию <math>x_i</math> в линейном списке, выводит эту позицию и обновляет список с помощью правила обновления списков. Если символы, подлежащие сжатию, переместить ближе к началу списка, то часто встречающиеся символы можно закодировать небольшими целыми числами. Декодер, который получает строку <math>I</math> и должен восстановить исходную строку <math>S</math>, также ведет линейный список символов. Для каждого целого числа <math>j</math>, которое он считывает из <math>I</math>, он ищет символ, который в данный момент хранится в позиции <math>j</math>. Затем декодер обновляет список, используя то же правило обновления списков, что и кодер. В качестве правила обновления списков можно использовать любой (детерминированный) онлайн-алгоритм. Очевидно, что при реальном хранении или передаче строки <math>I</math> каждое целое число в строке должно быть закодировано с помощью префиксного кода переменной длины.

Барроуз и Уилер [10] разработали очень эффективный алгоритм сжатия данных с помощью самоорганизующихся списков. Сначала алгоритм применяет обратимое преобразование к строке <math>S</math>. Цель этого преобразования[https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%91%D0%B0%D1%80%D1%80%D0%BE%D1%83%D0%B7%D0%B0_%E2%80%94_%D0%A3%D0%B8%D0%BB%D0%B5%D1%80%D0%B0] – сгруппировать экземпляры символа <math>x_i</math>, встречающиеся в <math>S</math>. Затем полученная строка <math>S'</math> кодируется с помощью алгоритма Move-To-Front. Более точно, преобразованная строка <math>S'</math> вычисляется следующим образом. Пусть <math>m</math> – длина <math>S</math>. Сначала алгоритм вычисляет <math>m</math> поворотов (циклических сдвигов) <math>S</math> и лексикографически сортирует их. Затем он извлекает последний символ из этих поворотов. <math>k</math>-м символом <math>S'</math> является последний символ <math>k</math>-го отсортированного поворота. Алгоритм также вычисляет индекс <math>J</math> исходной строки <math>S</math> в отсортированном списке поворотов. Барроуз и Уилер предложили эффективный алгоритм восстановления исходной строки <math>S</math>, имея только <math>S'</math> и <math>J</math>. В соответствующей статье [10] дается очень подробное описание алгоритма и сообщается о результатах экспериментов. На корпусе Calgary Compression Corpus [18] этот алгоритм превосходит UNIX-утилиты compress и gzip, причем улучшение составляет 13% и 6%, соответственно.

Наиболее важной проблемой является определение строгих верхних и нижних границ коэффициента конкурентоспособности, который может быть достигнут рандомизированными алгоритмами обновления списков в режиме онлайн относительно рассеянных соперников. Неясно, какова истинная конкурентоспособность. Предполагается, что она меньше 1,6. Однако, как следует из Теоремы 5, коэффициент эффективности должен быть выше 1,5.