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

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

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

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

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

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

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

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

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

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

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

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

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