Приближенные словари

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

Статическая задача о принадлежности; приближенная задача о принадлежности

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

Задача и модель

Задача о статической структуре данных состоит из набора данных D, набора запросов Q, набора ответов A и функции [math]\displaystyle{ f: D \times Q \to A }[/math]. Целью является хранение данных в сжатом виде, чтобы на любой запрос можно было ответить с помощью всего нескольких обращений к структуре данных. Статическая задача о принадлежности представляет собой хорошо изученный раздел в проектировании структур данных [1, 4, 7, 8, 12, 13, 16].

Определение 1 (статическая задача о принадлежности). В статической задаче о принадлежности дается подмножество S из не более чем n ключей из совокупности [math]\displaystyle{ U = \{ 1, 2, ..., m \} }[/math]. Необходимо организовать хранение S таким образом, чтобы на запросы вида «Принадлежит ли u к S?» можно было отвечать, сделав несколько обращений к памяти.

Естественной моделью общего вида для изучения любой задачи о структуре данных является модель клеточного зонда, предложенная Яо [16].

Определение 2 (модель клеточного зонда). Схема клеточного зонда (s, w, t) для решения задачи о статической структуре данных [math]\displaystyle{ U = \{ 1, 2, ..., m \} }[/math] состоит из двух компонентов: схемы хранения и схемы выполнения запросов. Схема хранения хранит данные [math]\displaystyle{ d \in D }[/math] в виде таблицы T[d] из s клеток, каждая из которых содержит слово размером w бит. Схема хранения является детерминированной. Если задан запрос [math]\displaystyle{ q \in Q }[/math], схема выполнения запроса вычисляет f(d, q), выполняя не более t зондирований T[d], причем каждое зондирование читает по одной клетке за раз, а сами операции зондирования могут быть адаптивными. В детерминированной схеме клеточного зонда схема выполнения запросов является детерминированной. В рандомизированной схеме клеточного зонда схема выполнения запросов рандомизирована и может ошибаться с небольшой вероятностью.

Бурман и коллеги [2] изучают сложность статической задачи о принадлежности в модели битового зонда. Это вариация модели клеточного зонда, в которой каждая клетка содержит всего один бит. Иными словами, размер слова w равен 1. Таким образом, в этой модели алгоритму запроса предоставляется побитовый доступ к структуре данных. Изучение задачи о принадлежности в модели битового зонда было начато Минским и Папертом в книге «Перцептроны» [1] [12]. Однако их интересовали верхние границы в среднем случае', тогда как далее рассматриваются границы для задачи о принадлежности в наихудшем случае.

Заметим, что если от схемы требуется хранить множества размером не более n, то она должна использовать не менее [math]\displaystyle{ \lceil log \; \sum_{i \le n} \tbinom{m}{i} \rceil }[/math] бит. Если [math]\displaystyle{ n \le m^{1 - \Omega(1)} }[/math], это означает, что схема должна хранить [math]\displaystyle{ \Omega(n \; log \; m) }[/math] бит (и, следовательно, использовать [math]\displaystyle{ \Omega(n) }[/math] ячеек). Целью работы [2] является получение схемы, которая отвечает на запросы с помощью постоянного числа битовых зондов и при этом использует таблицу размером [math]\displaystyle{ \O(n \; log \; m) }[/math] бит.

Родственные работы

Статическая задача о принадлежности хорошо изучена в модели клеточного зонда, где каждая клетка способна вместить один элемент совокупности. То есть w = O (log m). В своей фундаментальной работе Фредман и др. [8] предложили схему для решения статической задачи о принадлежности в модели клеточного зонда с размером слова O(log m), которая использует постоянное количество зондов и таблицу размера O(n). Далее эта схема будет называться схемой FKS. Таким образом, с точностью до постоянных коэффициентов схема FKS использует оптимальные объем памяти и количество клеточных зондов. Фактически, Фиат и др. [7], Бродник и Манро [1] и Паг [13] получили схемы, которые используют объем памяти (в битах) в пределах небольшого аддитивного члена [math]\displaystyle{ \lceil log \; \sum_{i \le n} \tbinom{m}{i} \rceil }[/math] и отвечают на запросы, считывая не более чем постоянное число клеток. Несмотря на все эти фундаментальные результаты для задачи о принадлежности в модели клеточного зонда, до выхода работы [2] было очень мало известно о сложности этой задачи в модели битового зонда.

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

Бурман и коллеги исследовали сложность статической задачи о принадлежности в модели битового зонда. Они изучали следующие схемы:

• Рандомизированные схемы с двусторонней ошибкой, которым разрешено ошибаться как в положительных, так и в отрицательных случаях (то есть эти схемы могут с малой вероятностью сказать «Нет», когда запрашиваемый элемент u содержится в множестве S, и «Да», когда это не так);

• Рандомизированные схемы с односторонней ошибкой, в которых ошибки ограничены только отрицательными случаями (то есть эти схемы никогда не дают ответа «Нет», когда запрашиваемых элемент u содержится в множестве S);

• Детерминированные схемы, в которых ошибки не допускаются. Основные приемы, используемые в [ ], основаны на двухцветных раскрасках систем специальных множеств, связанных с «r-cover-free семейством множеств» //семейство множеств, в котором ни одно из множеств не содержится в объединении r (или меньше) других множеств из этого же семейства//, рассмотренным в [3,5,9]. Более подробную информацию можно найти в работе [2].

Рандомизированные схемы с двусторонней ошибкой

Основной результат работы [2] показывает, что существуют рандомизированные схемы, использующие только один битовый зонд и объем памяти, близкий к теоретико-информационной нижней границе [math]\displaystyle{ \Omega(n \; log \; m) }[/math] бит.

Теорема 1. Для любого [math]\displaystyle{ 0 \lt \epsilon \le \frac{1}{4} }[/math] существует схема хранения подмножеств S размером не более n с элементами из совокупности размера m с использованием [math]\displaystyle{ O(\frac{n}{\epsilon^2} \; log \; m) }[/math] бит, так что на любой запрос о принадлежности «Принадлежит ли u к S?» можно ответить с вероятностью ошибки не более [math]\displaystyle{ \epsilon }[/math] с помощью рандомизированного алгоритма, который зондирует память только в одном месте, определяемом броском монеты и элементом запроса u.

Заметим, что рандомизация допускается только в алгоритме запроса. По-прежнему считается, что для каждого множества S существует ровно одна связанная с ним структура данных T(S). Можно показать, что детерминированные схемы, отвечающие на запросы с помощью одного битового зонда, нуждаются в m битах памяти (см. замечания после теоремы 4). Теорема 1 показывает, что если разрешить рандомизацию, то это ограничение (при постоянном [math]\displaystyle{ \epsilon }[/math]) можно сократить до O(n log m) бит. Этот объем памяти не более чем на постоянный множитель отличается от теоретико-информационной границы для достаточно малых n. При этом рандомизированная схема отвечает на запросы с помощью одного битового зонда.

К сожалению, приведенная выше конструкция не позволяет иметь псевдопостоянную вероятность ошибки и одновременно с этим использовать оптимальный объем памяти. Можно ли еще улучшить результат Теоремы 1 и сконструировать такую схему? В работе [2] показано, что это невозможно: если сделать ошибку [math]\displaystyle{ \epsilon }[/math] псевдопостоянной, то схема будет вынуждена использовать памяти больше n log m.

Теорема 2. Предположим, что [math]\displaystyle{ \frac{n}{m^{1/3}} \le \epsilon \le \frac{1}{4} }[/math]. Тогда любой рандомизированной схеме с двухсторонней ошибкой [math]\displaystyle{ \epsilon }[/math], отвечающей на запросы с помощью одного битового зонда, требуется объем памяти [math]\displaystyle{ \Omega \big( \frac{n}{\epsilon \; log(1/\epsilon)} \; log \; m \big) }[/math].

Рандомизированные схемы с односторонней ошибкой

Можно ли сэкономить память, если предполагается, что схема выполнения запросов будет допускать только односторонние ошибки? Следующий результат показывает, что это возможно, если ошибка допускается только на отрицательных экземплярах.

Теорема 3. Для любого Для любого [math]\displaystyle{ 0 \lt \epsilon \le \frac{1}{4} }[/math] существует схема хранения подмножеств S размером не более n с элементами из совокупности размера m с использованием [math]\displaystyle{ O( \tbinom{n}{\epsilon}^2 \; log \; m) }[/math] бит, так что на любой запрос о принадлежности «Принадлежит ли u к S?» можно ответить с вероятностью ошибки не более e с помощью рандомизированного алгоритма, который делает единственный битовый запрос к структуре данных. Более того, если [math]\displaystyle{ u \in S }[/math], то вероятность ошибки равна 0.

Хотя эта схема и не обеспечивает оптимальное использование памяти, она все же требует ее значительно меньше, чем битовый вектор. Однако зависимость от n квадратичная, в отличие от схемы с двусторонней ошибкой, где она была линейной. В работе [2] показано, что эта схема практически оптимальна: для любой схемы с односторонней ошибкой обязательно существует квадратичная зависимость от ^.

Теорема 4. Предположим, что [math]\displaystyle{ \frac{n}{m^{1/3}} \le \epsilon \le \frac{1}{4} }[/math]. Рассмотрим статическую задачу о принадлежности для множества S размера не более n из совокупности размера m. Тогда любая схема с односторонней ошибкой [math]\displaystyle{ \epsilon }[/math], отвечающая на запросы с использованием не более одного битового зонда, должна использовать [math]\displaystyle{ \Omega \big( \frac{n^2}{\epsilon^2 \; log(n/\epsilon)} \; log \; m \big) }[/math] бит памяти.

Замечание. Можно также рассмотреть однозондовые схемы с односторонней ошибкой, которые допускают ошибки только в положительных экземплярах. Это означает, что для элементов запроса, не входящих в множество S, ошибки не допускаются.

В этом случае, как показано в [2], рандомизация не помогает: подобная схема должна использовать m бит памяти.

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

Теорема 5. Предположим, что [math]\displaystyle{ 0 \lt \delta \lt 1 }[/math]. Существует рандомизированная схема с односторонней ошибкой [math]\displaystyle{ n^{- \delta} }[/math], которая решает статическую задачу о принадлежности, используя [math]\displaystyle{ O(n^{1 + \delta} \; log \; m) }[/math] бит памяти и [math]\displaystyle{ O( \frac{1}{\delta}) }[/math] битовых зондов.

Детерминированные схемы

Бурман и коллеги показали, что детерминированные схемы, в отличие от рандомизированных, демонстрируют компромиссное соотношение времени и памяти.

Теорема 6. Предположим, что детерминированная схема хранит подмножества размера n из совокупности размера m, используя биты памяти, и отвечает на запросы о принадлежности с помощью t битовых зондов с запросами к памяти. Тогда [math]\displaystyle{ \tbinom{m}{n} \le max_{i \le nt} \tbinom{2s}{i} }[/math].

У этого компромиссного результата есть интересное следствие. Вспомним, что схема хэширования FKS представляет собой структуру данных для хранения множеств размером не более n из совокупности размера m с использованием O(n log m) бит, так что на запросы о принадлежности можно отвечать с использованием O(log m) битовых зондов. В качестве следствия компромиссного результата в работе [2] показано, что схема FKS применяет оптимальное количество битовых зондов с постоянным коэффициентом для данного объема памяти.

Следствие 1. Пусть [math]\displaystyle{ \epsilon \gt 0, c \ge 1 }[/math] – любые константы. Существует константа [math]\displaystyle{ \delta \gt 0 }[/math], такая, что верно следующее утверждение. Пусть [math]\displaystyle{ n \le m^{1 - \epsilon} }[/math], и пусть задана схема хранения множеств размером не более n из совокупности размера m в виде структур данных размером не более [math]\displaystyle{ cn \; log \; m }[/math] бит. Тогда любой детерминированный алгоритм, отвечающий на запросы о принадлежности, используя эту структуру, должен в наихудшем случае использовать не менее [math]\displaystyle{ \delta \; log \; m }[/math] битовых зондов.

Из Теоремы 6 также следует, что любая детерминированная схема, отвечающая на запросы с использованием t битовых зондов, в наихудшем случае должна занимать не менее [math]\displaystyle{ ntm^{\Omega(1/t)} }[/math] бит памяти. Последний результат доказывает существование схем, почти соответствующих нижней границе.

Теорема 7.

1. Существует неадаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием [math]\displaystyle{ O(ntm^{\frac{2}{t + 1}}) }[/math] бит памяти и отвечает на запросы с использованием 2t + 1 битовых зондов. Это неявная схема.

2. Существует явная адаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием [math]\displaystyle{ O(m^{1/t} n \; log \; m) }[/math] бит памяти и отвечает на запросы с использованием O(log n + loglog m) + t битовых зондов.

Применение

Результаты, полученные в [ ], имеют интересные связи с вопросами теории кодирования и коммуникационной сложности. В рамках теории кодирования результаты работы [2] можно рассматривать как построение локально декодируемых исходных кодов, аналогичных локально декодируемым канальным кодам из [10]. Теоремы 1-4 также можно рассматривать как жесткие границы для следующей задачи коммуникационной сложности, приведенной в [ ]: Алиса получает u 2 f1... ; mg, Боб получает SC jl;:::; mg размера не более n, и Алиса посылает одно сообщение Бобу, после чего Боб объявляет, выполняется ли u 2 S. Более подробную информацию см. в [ ].

Литература

1. Brodnik, A., Munro, J.I.: Membership in constant time and minimum space. In: Lecture Notes in Computer Science, vol. 855, pp. 72-81, Springer, Berlin (1994). Final version: Membership in Constant Time and Almost-Minimum Space. SIAM J. Comput. 28(5), 1627-1640 (1999)

2. Buhrman, H., Miltersen, P.B., Radhakrishnan, J., Venkatesh, S.: Are bitvectors optimal? SIAM J. Comput. 31(6), 1723-1744 (2002)

3. Dyachkov, A.G., Rykov, V.V.: Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii 18(3), 7-13 (1982)

4. Elias, P., Flower, R.A.: The complexity of some simple retrieval problems. J. Assoc. Comput. Mach. 22, 367-379 (1975)

5. Erdos, P., Frankl, P., FCiredi, Z.: Families of finite sets in which no set is covered by the union of r others. Isr. J. Math. 51, 79-89 (1985)

6. Fiat, A., Naor, M.: Implicit O(1) probe search. SIAM J. Comput. 22,1-10(1993)

7. Fiat, A., Naor, M., Schmidt, J.P., Siegel, A.: Non-oblivious hashing. J. Assoc. Comput. Mach. 31,764-782 (1992)

8. Fredman, M.L., Komlos, J., Szemeredi, E.: Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach. 31(3),538-544(1984)

9. FCiredi, Z.: On r-cover-free families. J. Comb. Theory, Series A 73,172-173(1996)

10. Katz, J., Trevisan, L.:On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of STOC'00, pp. 80-86

11. Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. J. Comput. Syst.Sci. 57, 37^9 (1998)

12. Minsky, M., Papert, S.: Perceptrons. MIT Press, Cambridge (1969)

13. Pagh, R.: Low redundancy in static dictionaries with O(1) lookup time. In: Proceedings of ICALP '99. LNCS, vol. 1644, pp. 595-604. Springer, Berlin (1999)

14. Ruszinko, M. On the upper bound of the size of r-cover-free families. J. Comb. Theory, Ser. A 66, 302-310(1984)

15. Ta-Shma, A.: Explicit one-probe storing schemes using universal extractors. Inf. Proc. Lett. 83(5), 267-274 (2002)

16. Yao, A.C.C.: Should tables be sorted? J. Assoc. Comput. Mach. 28(3),615-628(1981)