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

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

Определение 1 (статическая задача о принадлежности). В статической задаче о принадлежности дается подмножество S из не более чем n ключей из совокупности U = f1; 2... ; mg. Необходимо организовать хранение S таким образом, чтобы на запросы вида «Входит ли u в S?» можно было отвечать, сделав несколько обращений к памяти.

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

Определение 2 (модель клеточного зонда). Схема клеточного зонда (s, w, t) для решения задачи о статической структуре данных f: D x Q ! A состоит из двух компонентов: схемы хранения и схемы выполнения запросов. Схема хранения хранит данные d 2 D в виде таблицы T[d] из s клеток, каждая из которых содержит слово размером w бит. Схема хранения является детерминированной. Если задан запрос q 2 Q, схема выполнения запроса вычисляет f(d, q), выполняя не более t зондирований T[d], причем каждое зондирование читает по одной клетке за раз, а сами операции зондирования могут быть адаптивными. В детерминированной схеме клеточного зонда схема выполнения запросов является детерминированной. В рандомизированной схеме клеточного зонда схема выполнения запросов рандомизирована и может ошибаться с небольшой вероятностью.

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