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

Статическая задача о принадлежности хорошо изучена в модели клеточного зонда, где каждая клетка способна вместить один элемент совокупности. То есть 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] было очень мало известно о сложности этой задачи в модели битового зонда.