Онлайн-алгоритм обновления списков

Ключевые слова и синонимы

Самоорганизующиеся списки (Self organizing lists)

Постановка задачи

Обновление списков представляет собой классическую онлайновую задачу и, наряду с задачей о подкачке, является первой проблемой, которая была изучена с точки зрения конкурентоспособности. Задача обновления списков заключается в поддержании словаря в виде несортированного линейного списка. Рассмотрим множество элементов, представленное в виде линейного цепного списка. Системе предъявляется последовательность запросов a, где каждый запрос представляет собой одну из следующих операций. Это может быть (1) доступ к элементу списка, (2) вставка нового элемента в список или (3) удаление элемента. Чтобы выполнить доступ к элементу, алгоритм обновления списков начинает с первых элементов списка и линейно перебирает элементы, пока не будет найден нужный. Для вставки нового элемента алгоритм сначала сканирует весь список, чтобы убедиться, что этого элемента еще нет, а затем вставляет его в конец списка. Для удаления элемента алгоритм сканирует список в поисках элемента, а затем удаляет его.

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

Особый интерес представляют алгоритмы обновления списков, работающие в режиме онлайн, т. е. каждый запрос обрабатывается без знания о будущих запросах. Производительность онлайн-алгоритмов обычно оценивается при помощи сравнительного анализа. Здесь онлайновая стратегия сравнивается с оптимальным оффлайновым алгоритмом, который заранее знает всю последовательность запросов и может обработать ее с минимальными затратами. Пусть имеется последовательность запросов a. Обозначим за A(a) затраты, понесенные онлайн-алгоритмом A при обработке последовательности a, а за OPT(a) – затраты, понесенные оптимальным офлайн-алгоритмом OPT. Онлайн-алгоритм A называется c-конкурентным, если существует константа a такая, что для списков любых размеров и всех последовательностей запросов o,A{a) < c-OPT(a)+a. Коэффициент c также называется коэффициентом конкурентоспособности. Конкурентоспособность должна быть одинаковой для списков любых размеров.

Основные результаты

Существует три известных детерминированных онлайн-алгоритма для задачи обновления списков.

Алгоритм «Перемещение к началу» (Move-To-Front): перемещает запрашиваемый элемент в начало списка.

Алгоритм «Транспозиция» (Transpose): меняет запрашиваемый элемент на непосредственно предшествующий ему элемент списка.

Алгоритм «Подсчет частоты» (Frequency-Count): ведет счетчик частоты для каждого элемента в списке. Каждый раз, когда элемент запрашивается, его счетчик увеличивается на 1. Список поддерживается таким образом, чтобы элементы всегда располагались в порядке невозрастания частоты.

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

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

Теорема 1 [16]. Алгоритм Move-To-Front является 2-конкурентным.

Алгоритмы Transpose и Frequency-Count не являются c-конкурентными для любого константного c.

Карп и Рагхаван [13] разработали нижнюю границу конкурентоспособности, которая может быть достигнута детерминированными онлайн-алгоритмами. Из этой нижней границы следует, что Move-To-Front имеет оптимальный коэффициент конкурентоспособности.

Теорема 2 [13]. Пусть A – детерминированный онлайн-алгоритм для задачи обновления списков. Если A c-конкурентен, то с > 2.

Интересным вопросом является рандомизация в задаче обновления списков. При наличии адаптивных соперников ни один рандомизированный онлайн-алгоритм обновления списков не может быть лучше чем 2-конкурентный, см. [6, 14]. Поэтому основное внимание уделяется алгоритмам в присутствии рассеянных соперников. Было предложено множество рандомизированных алгоритмов обновления списков [1, 2, 12, 14]. В следующих параграфах описываются два наиболее важных. Райнголд и др. [ ] предложили очень простой алгоритм, названный Bit.

Алгоритм «Бит» (Bit): каждый элемент списка хранит бит, который дополняется при каждом обращении к элементу. Если в результате доступа к элементу значение бита меняется на 1, то запрашиваемый элемент перемещается в начало списка. В противном случае список остается неизменным. Биты элементов инициализируются независимо и равномерно случайным образом.

Теорема 3 [14]. Алгоритм Bit является 1,75-конкурентным относительно любого рассеянного соперника.

Райнголд и др. [ ] обобщили алгоритм Bit и доказали верхнюю границу p3 fa 1,73 относительно рассеянных соперников. Лучший рандомизированный алгоритм из известных на данный момент представляет собой комбинацию алгоритма Bit и детерминированного 2-конкурентного онлайнового алгоритма Timestamp, предложенного в [1].

Алгоритм «Временные метки» (Timestamp): вставляет запрашиваемый элемент, например x, перед первым элементом в списке, который предшествует x и который был запрошен не более одного раза с момента последнего запроса x. Если такого элемента нет или если x не был запрошен до сих пор, то позиция x остается без изменений.

В качестве примера рассмотрим список из шести элементов, расположенных в порядке L: x1!x2!x3!x4!x5! x6. Предположим, что алгоритм Timestamp должен обработать второй запрос к x5 в последовательности запросов a = x5 ; x2 ; x2 ; x3 ; x1 ; x1 ; x5. Элементы x3 и x4 были запрошены не более одного раза с момента последнего запроса к x5, в то время как x1 и x2 были запрошены дважды. Таким образом, алгоритм Timestamp вставит x5 сразу перед x3 в списке. Комбинация алгоритмов Bit и Timestamp была предложена в работе [3].

Алгоритм «Комбинация» (Combination): с вероятностью | алгоритм обрабатывает последовательность запросов, используя Bit, и с вероятностью ^ обрабатывает последовательность запросов, используя Timestamp.

Combination достигает наилучшего коэффициента конкурентоспособности из всех известных на данный момент.

Теорема 4 [2]. Алгоритм Combination является 1,6-конкурентным относительно любого рассеянного соперника.

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

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

Используя методы теории обучения, Блам и др. [9] предложили рандомизированный онлайн-алгоритм, который при любом e > 0 является (1,6 + e)-конкурентным и в то же время (1+e)-конкурентным относительно оффлайнового алгоритма, ограниченного обработкой последовательности запросов со статическим списком.

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

Райнголд и др. [ ] исследовали расширенную модель затрат, названную P-моделью, для задачи обновления списков. В модели Pd нет бесплатных обменов, а каждый платный обмен стоит d. Рейнгольд и коллеги проанализировали детерминированные и рандомизированные стратегии в этой модели.

Многие из концепций, показанных для самоорганизующихся линейных списков, могут быть распространены на бинарные деревья поиска. Наиболее популярной версией самоорганизующихся бинарных деревьев поиска являются косые деревья, представленные Слейтором и Тарьяном; см. [17].

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

Эта граница является строгой. Ривест [ ] определил распределения, на которых Transpose работает лучше, чем Move-To-Front.

Применение

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

В задаче сжатия данных дается строка S, которая должна быть сжата, то есть представлена с использованием меньшего количества бит. Строка S состоит из символов, где каждый символ является элементом алфавита S = fx1... ; xng. Идея схем сжатия данных с использованием линейных списков заключается в том, чтобы преобразовать строку S символов в строку I целых чисел. Кодер поддерживает линейный список символов, содержащихся в S, и считывает символы из строки S. Всякий раз, когда символ xi должен быть сжат, кодер ищет текущую позицию xi в линейном списке, выводит эту позицию и обновляет список с помощью правила обновления списков. Если символы, подлежащие сжатию, переместить ближе к началу списка, то часто встречающиеся символы можно закодировать небольшими целыми числами. Декодер, который получает строку I и должен восстановить исходную строку S, также ведет линейный список символов. Для каждого целого числа j, которое он считывает из I, он ищет символ, который в данный момент хранится в позиции ј. Затем декодер обновляет список, используя то же правило обновления списков, что и кодер. В качестве правила обновления списков можно использовать любой (детерминированный) онлайн-алгоритм. Очевидно, что при реальном хранении или передаче строки I каждое целое число в строке должно быть закодировано с помощью префиксного кода переменной длины.

Барроуз и Уилер [ ] разработали очень эффективный алгоритм сжатия данных с помощью самоорганизующихся списков. Сначала алгоритм применяет обратимое преобразование к строке S. Цель этого преобразования[[1]] – сгруппировать экземпляры символа xi, встречающиеся в S. Затем полученная строка S0 кодируется с помощью алгоритма Move-To-Front. Более точно, преобразованная строка S0 вычисляется следующим образом. Пусть m – длина S. Сначала алгоритм вычисляет m поворотов (циклических сдвигов) S и лексикографически сортирует их. Затем он извлекает последний символ из этих поворотов. k-й символом S0 является последний символ k-го отсортированного поворота. Алгоритм также вычисляет индекс J исходной строки S в отсортированном списке поворотов. Барроуз и Уилер предложили эффективный алгоритм восстановления исходной строки S, имея только S0 и J. В соответствующей статье [10] дается очень подробное описание алгоритма и сообщается о результатах экспериментов. На корпусе Calgary Compression Corpus [ ] этот алгоритм превосходит UNIX-утилиты compress и gzip, причем улучшение составляет 13% и 6%, соответственно.

Открытые вопросы

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

Экспериментальные результаты

Ранние экспериментальные исследования алгоритмов Move-To-Front, Transpose и Frequency Count были проведены Ривестом [15], а также Бентли и Макгиох [7]. Более позднее и обширное экспериментальное исследование представили Бахрах и коллеги [ ]. Они реализовали и протестировали большое количество онлайновых алгоритмов обновления списков на последовательностях запросов, сгенерированных вероятностными распределениями и цепями Маркова, а также на последовательностях, извлеченных из корпуса Calgary Corpus. Было показано, что локальность ссылок существенно влияет на абсолютную и относительную производительность алгоритмов. Бахрах и др. также проанализировали различные алгоритмы как стратегии сжатия данных.

Литература

1. Albers, S.: Improved randomized on-line algorithms for the list update problem. SIAM J. Comput. 27,670-681 (1998)

2. Albers, S., von Stengel, B., Werchner, R.: A combined BIT and TIMESTAMP algorithm for the list update problem. Inf. Proc. Lett. 56,135-139(1995)

3. Ambuhl, C.: Offline list update is NP-hard. In: Proc. 8th Annual European Symposium on Algorithms, pp. 42-51. LNCS,vol. 1879. Springer (2001)

4. Ambuhl, C, Gartner, B., von Stengel, B.: Towards new lower bounds for the list update problem. Theor. Comput. Sci 68, 3-16(2001)

5. Bachrach, B., El-Yaniv, R., Reinstadtler, M.: On the competitive theory and practice of online list accessing algorithms. Algorithmica 32, 201-245 (2002)

6. Ben-David, S., Borodin, A., Karp, R.M.,Tardos, G., Wigderson, A.: On the power of randomization in on-line algorithms. Algorithmica 11, 2-14 (1994)

7. Benteley, J.L., McGeoch, C.C.: Amortized analyses of self-organizing sequential search heuristics. Commun. ACM 28, 404-411 (1985)

8. Bentley, J.L., Sleator, D.S., Tarjan, R.E., Wei, V.K.: A locally adaptive data compression scheme. Commun. ACM 29, 320-330 (1986)

9. Blum, A., Chawla, S., Kalai, A.: Static optimality and dynamic search-optimality in lists and trees. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1 -8 (2002)

10. Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. DEC SRC Research Report 124, (1994)

11. Chung, F.R.K., Hajela, D.J., Seymour, P.D.: Self-organizing sequential search and Hilbert's inequality. In: Proc. 17th Annual Symposium on the Theory of Computing pp 217-223 (1985)

12. Irani, S.: Two results on the list update problem. Inf. Proc. Lett. 38,301-306(1991)

13. Karp, R. Raghavan, P.: From a personal communication cited in [14]

14. Reingold, N., Westbrook, J., Sleator, D.D.: Randomized competitive algorithms for the list update problem. Algorithmica 11,15-32(1994)

15. Rivest, R.: On self-organizing sequential search heuristics. Commun. ACM 19,63-67 (1976)

16. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28, 202-208 (1985)

17. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32,652-686 (1985)

18. Witten, I.H., Bell, T.: The Calgary/Canterbury text compression corpus. Anonymous ftp from ftp://ftp.cpsc.ucalgary.ca:/pub/text.compression/corpus/text.compression.corpus.tar.Z