Приближенные словари: различия между версиями

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

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

Бурман и коллеги [2] изучают сложность статической задачи о принадлежности в модели ''битового зонда''. Это вариация модели клеточного зонда, в которой каждая клетка содержит всего один бит. Иными словами, размер слова w равен 1. Таким образом, в этой модели алгоритму запроса предоставляется побитовый доступ к структуре данных. Изучение задачи о принадлежности в модели битового зонда было начато Минским и Папертом в книге «[[Перцептроны]]» [https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D1%86%D0%B5%D0%BF%D1%82%D1%80%D0%BE%D0%BD%D1%8B_(%D0%BA%D0%BD%D0%B8%D0%B3%D0%B0] [12]. Однако их интересовали верхние границы ''в среднем случае', тогда как далее рассматриваются границы для задачи о принадлежности ''в наихудшем случае''.

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

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

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

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

Основной результат работы [2] показывает, что существуют рандомизированные схемы, использующие только один битовый зонд и объем памяти, близкий к теоретико-информационной нижней границе £?(nlogm) бит.

Теорема 1. Для любого 0 < e 1 4 существует схема хранения подмножеств S размером не более n с элементами из совокупности размера m с использованием O(^2 log m) бит, так что на любой запрос о принадлежности «Верно ли, что u в S?» можно ответить с вероятностью ошибки не более e с помощью рандомизированного алгоритма, который зондирует память только в одном месте, определяемом броском монеты и элементом запроса u.

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

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

Теорема 2. Предположим, что -^ < e < j. Тогда любой рандомизированной схеме с двухсторонней ч-ошибкой, отвечающей на запросы с помощью одного битового зонда, требуется объем памяти &{€\0 "ty€\ log m).

Теорема 3. Для любого 0 < e 1 4 существует схема хранения подмножеств S размером не более n с элементами из совокупности размера m с использованием O(^2 log m) бит, так что на любой запрос о принадлежности «Верно ли, что u в S?» можно ответить с вероятностью ошибки не более e с помощью рандомизированного алгоритма, который делает единственный битовый запрос к структуре данных. Более того, если u 2 S, то вероятность ошибки равна 0.

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

Теорема 4. Предположим, что -4^ < e < 1. Рассмотрим статическую задачу о принадлежности для множества S размера не более n из совокупности размера m. Тогда любая схема с односторонней ошибкой e, отвечающая на запросы с использованием не более одного битового зонда, должна использовать Q{2n 2 log m) бит памяти.

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

Теорема 5. Предположим, что 0 < S < 1. Существует рандомизированная схема с односторонней ошибкой n, которая решает статическую задачу о принадлежности, используя O(n1+S log m) бит памяти и O(j) битовых зондов.

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

Теорема 6. Предположим, что детерминированная схема хранит подмножества размера n из совокупности размера m, используя биты памяти, и отвечает на запросы о принадлежности с помощью t битовых зондов с запросами к памяти. Тогда (™) < max,<nt (2/).

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

Следствие 1. Пусть e > 0; c > 1 – любые константы. Существует константа 8 > 0, такая, что верно следующее утверждение. Пусть n < ml~€, и пусть задана схема хранения множеств размером не более n из совокупности размера m в виде структур данных размером не более cn log m бит. Тогда любой детерминированный алгоритм, отвечающий на запросы о принадлежности, используя эту структуру, должен в наихудшем случае использовать не менее S log m битовых зондов.

Из Теоремы 6 также следует, что любая детерминированная схема, отвечающая на запросы с использованием t битовых зондов, в наихудшем случае должна занимать не менее ntm ^llt> бит памяти. Последний результат доказывает существование схем, почти соответствующих нижней границе.

Теорема 7.

1. Существует неадаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием O(ntmt+12) бит памяти и отвечает на запросы с использованием 2t + 1 битовых зондов. Это неявная схема.

2. Существует явная адаптивная схема, которая хранит множества размером не более n из совокупности размера m с использованием O(m1/t nlog m) бит памяти и отвечает на запросы с использованием 2t + 1 битовых зондов.

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