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

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