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

В формулировках алгоритмов обновления списка обычно предполагается, что последовательность запросов состоит только из доступов. Достаточно очевидно, как можно расширить алгоритмы, чтобы они также могли обрабатывать вставки и удаления. При вставке алгоритм сначала добавляет новый элемент в конец списка, а затем выполняет те же действия, как если бы элемент был запрошен впервые. При удалении алгоритм сначала ищет элемент, а затем просто удаляет его.

Сначала рассмотрим алгоритмы Move-To-Front, Transpose и Frequency-Count. Отметим, что Move-To-Front и Transpose – стратегии ''без памяти'', то есть им не требуется дополнительная память для принятия решения о том, куда переместить запрошенный элемент. Таким образом, с практической точки зрения они более привлекательны, чем Frequency-Count. Слейтор и Тарьян [16] проанализировали коэффициенты конкурентоспособности этих трех алгоритмов.

'''Алгоритм «Комбинация» (Combination)''': с вероятностью <math>\frac{4}{5}</math> алгоритм обрабатывает последовательность запросов, используя Bit, и с вероятностью <math>\frac{1}{5}</math> обрабатывает последовательность запросов, используя Timestamp.

Амбюл и др. [4] представили нижнюю границу для рандомизированных алгоритмов обновления списков.

'''Теорема 5 [4]. Пусть A – рандомизированный онлайн-алгоритм для задачи обновления списков. Если A <math>c</math>-конкурентен относительно любого рассеянного соперника, то с > 1,50084.'''

До сих пор в данной статье рассматривались онлайновые алгоритмы. В оффлайновом варианте задачи обновления списков вся последовательность запросов <math>\sigma</math> известна заранее. Амбюл [3] показал, что оффлайновый вариант является NP-трудным.

Что касается истории задачи об обновлении списков, то до появления сравнительного анализа алгоритмы обновления списков изучались в сценариях, где последовательности запросов формируются в соответствии с вероятностными распределениями. Асимптотические ожидаемые затраты, понесенные онлайновым алгоритмом при обработке одного запроса, сравнивались с соответствующими затратами, понесенными при оптимальном статическом упорядочивании. Существует большой объем литературы по этой теме. Чанг и др. [11] показали, что для любого распределения асимптотическая стоимость обработки алгоритма Move-To-Front не более чем в <math>\frac{\pi}{2}</math> раз превышает стоимость обработки оптимального упорядочения.

Линейные списки представляют собой одну из возможностей представления множества элементов. Конечно, существуют и другие структуры данных, такие как сбалансированные деревья поиска или хэш-таблицы, которые, в зависимости от конкретного приложения, могут хранить множество более эффективным способом. В целом линейные списки полезны, когда множество невелико и состоит всего из нескольких десятков элементов. Наиболее важным способом применения алгоритмов обновления списков являются локально адаптивные схемы сжатия данных. Барроуз и Уилер [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.