Допустим, у меня есть набор S, с элементами, которые являются N-кортежами, то есть (xi1, xi2, ... , xin).Алгоритм быстрого несовершенного совпадения против нескольких целей
Указанные элементы x = (x1, x2, ..., xn) и y = (y1, y2, ..., yn), matches(x,y,M) тогда и только тогда, когда по крайней мере M элементы x и y равны.
Теперь дан набор S, matchSet(x,S,M) возвращает элементы S которые matches(x,y,M) верно.
Предполагая, что S имеет данные такие, что matchSet будет в среднем матче только 0 или 1 элементов (это будет иногда соответствовать больше, но редко), есть ли способ, чтобы написать matchSet и структура S так, чтобы это время запуска является суб линейной к размеру S, и это пространство разумно (т. е. не помещать 2^L индексы на S, где L - длина элементов)?
В качестве альтернативы, быстрый запуск matchManySet(S', S, M) также будет приемлемым, который проходит matchSet для каждого элемента S', а также тех пор, пока он занимает значительно меньше времени, чем размер S раза размера S'.
Вы отвергнут с индексами 2^L, но как насчет L^2 индексов? Когда вы говорите, что элементы «редко» соответствуют более чем одному элементу, как редко мы говорим? В частности: если вы выполняете поиск L^2 - один для поиска элементов с (y1, y2) = (x1, x2), один для нахождения элементов с (y1, y3) = (x1, x3) и т. Д. - будет которые дают вам общее сублинейное время? – ruakh
Нет, они редко соответствуют более чем одной вещи в наборе. Поэтому, если я пытаюсь совместить 5 из 10, они почти всегда будут только соответствовать 5, но может быть много матчей 2 и 3, например – Clinton