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

При обработке запросов алгоритм обновления списков несет накладные расходы. Если запрос является операцией доступа или удаления, то накладные расходы равны <math>i</math>, где <math>i</math> – позиция запрашиваемого элемента в списке. Если запрос является вставкой, то расходы равны <math>n + 1</math>, где <math>n</math> – количество элементов в списке перед вставкой. В процессе обработки последовательности запросов алгоритм обновления списков может перестроить список. Сразу после доступа или вставки запрошенный элемент может быть перемещен без дополнительных расходов на любую позицию, расположенную ближе к началу списка. Такие обмены называются ''бесплатными''. При помощи бесплатных обменов алгоритм может снизить стоимость последующих запросов. В любой момент времени два соседних элемента в списке могут быть обменены с затратами 1. Такие обмены называются ''платными''. Цель состоит в том, чтобы обработать последовательность запросов так, чтобы суммарная стоимость была как можно ниже.

Особый интерес представляют алгоритмы обновления списков, работающие в режиме ''онлайн'', т. е. каждый запрос обрабатывается без знания о будущих запросах. Производительность онлайн-алгоритмов обычно оценивается при помощи ''сравнительного анализа''. Здесь онлайновая стратегия сравнивается с оптимальным оффлайновым алгоритмом, который заранее знает всю последовательность запросов и может обработать ее с минимальными затратами. Пусть имеется последовательность запросов <math>\sigma</math>. Обозначим за <math>A(\sigma)</math> затраты, понесенные онлайн-алгоритмом <math>A</math> при обработке последовательности <math>\sigma</math>, а за <math>OPT(\sigma)</math> – затраты, понесенные оптимальным офлайн-алгоритмом OPT. Онлайн-алгоритм <math>A</math> называется <math>c</math>-конкурентным, если существует константа <math>\alpha</math> такая, что для списков любых размеров и всех последовательностей запросов <math>\sigma</math> выполняется соотношение <math>A(\sigma) \le c \cdot OPT(\sigma) + \alpha</math>. Коэффициент <math>c</math> также называется ''коэффициентом конкурентоспособности''. Конкурентоспособность должна быть одинаковой для ''списков любых размеров''.

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

Сначала рассмотрим алгоритмы 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.