Дополненная карта - Augmented map

В Информатика, то дополненная карта^[1] является абстрактный тип данных (ADT) на основе заказанного карты, который связывает каждую упорядоченную карту с увеличенная ценность. Для заказанной карты ${ displaystyle m}$ с типом ключа ${ displaystyle K}$, функция сравнения ${ displaystyle <_ {K}}$ на ${ displaystyle K}$ и тип значения ${ displaystyle V}$, увеличенное значение определяется на основе двух функций: база функция ${ displaystyle g: K times V mapsto A}$ и комбинировать функция ${ displaystyle f: A times A mapsto A}$, где ${ displaystyle A}$ это тип увеличиваемого значения. Базовая функция ${ displaystyle g}$ преобразует одну запись в ${ displaystyle m}$ на увеличенное значение, а функция объединения ${ displaystyle f}$ объединяет несколько дополнительных значений. Функция комбинирования ${ displaystyle f}$ требуется быть ассоциативный и иметь идентичность ${ displaystyle I}$ (т.е. ${ displaystyle A, f, I}$ образует моноид ). Расширяем определение ассоциативной функции ${ displaystyle f}$ следующим образом:

${ Displaystyle е ( emptyset) = I}$${ Displaystyle f (а) = а}$${ displaystyle f (a_ {1}, a_ {2},  dots, a_ {n}) = f (f (a_ {1}, a_ {2},  dots, a_ {n-1}), a_ {n})}$

Затем увеличенное значение упорядоченной карты ${ displaystyle m = {(k_ {1}, v_ {1}), (k_ {2}, v_ {2}), dots (k_ {n}, v_ {n}) }}$ определяется следующим образом:

${ Displaystyle А (м) = е (г (к_ {1}, v_ {1}), г (k_ {2}, v_ {2}),  точки, г (k_ {n}, v_ {n}) ))}$

Соответственно, расширенную карту можно формально определить как семикортежную ${ Displaystyle mathbb {AM} (K, <_ {K}, V, A, g, f, I)}$. Например, расширенная карта с целыми ключами и значениями, на которой расширенное значение определяется как сумма всех значений в карте, определяется как:

${ Displaystyle M_ {1} =  mathbb {AM} ( mathbb {Z}, <_ { mathbb {Z}},  mathbb {Z},  mathbb {Z}, (к, v)  mapsto v , + _ { mathbb {Z}}, 0)}$

Как абстрактный тип данных расширенная карта часто используется для моделирования проблем и служит абстракцией с полезным интерфейсом. Он разработан для поддержки быстрых сумм диапазонов, что означает быстрое возвращение увеличенного значения всех записей в определенном ключевом диапазоне.

Интерфейс

Помимо интерфейса для стандартной упорядоченной карты, расширенная карта также должна поддерживать функции для сумм диапазонов. Особенно:

• aug_left${ Displaystyle (м, к)}$: возвращает увеличенное значение всех записей в ${ displaystyle m}$ с ключами не более ${ displaystyle k}$.
• aug_right${ Displaystyle (м, к)}$: возвращает увеличенное значение всех записей в ${ displaystyle m}$ с ключами не менее ${ displaystyle k}$.
• aug_left${ Displaystyle (м, к_ {1}, к_ {2})}$: возвращает увеличенное значение всех записей в ${ displaystyle m}$ с ключами в диапазоне ${ Displaystyle [к_ {1}, к_ {2}]}$.
• aug_val${ Displaystyle (м)}$: возвращает увеличенное значение всех записей в ${ displaystyle m}$.

Некоторые функции, хотя и не определены на основе расширенных значений, могут использовать расширенные значения для ускорения своих алгоритмов. Обычно они требуют определенного представления расширенных карт и определенных условий для входных параметров.

• aug_filter${ Displaystyle (м, ч)}$: возвращает все записи в ${ displaystyle m}$ удовлетворяющий показателю ${ displaystyle h: A mapsto { text {bool}}}$. Это применимо только когда ${ Displaystyle ч (а) ви ч (б) Leftrightarrow ч (е (а, Ь))}$. В этом случае функция aug_filter эквивалентна filter${ displaystyle m, h '}$, где ${ displaystyle h ': K times V mapsto { text {bool}}}$ и ${ Displaystyle ч (г (к, v)) Leftrightarrow h '(к, v)}$. Когда расширенная карта реализуется с использованием расширенных деревьев, эта функция может быть реализована асимптотически более эффективно, чем наивная реализация.
• aug_project${ displaystyle (g ', f', m, k_ {1}, k_ {2})}$: возвращает ${ displaystyle g '(август _range (м, k_ {1}, k_ {2}))}$. Вот ${ displaystyle g ': A mapsto B}$, ${ displaystyle f ': B times B mapsto B}$. Это требует ${ displaystyle (B, f ', g' (I))}$ быть моноид и ${ displaystyle f '(g' (a), g '(b)) = g' (f (a, b))}$. Эта функция полезна, когда расширенные значения

сами являются картами или другими большими структурами данных. Это позволяет проецировать расширенные значения на другой тип с помощью ${ displaystyle g '}$ (например, проецируйте расширенные значения со сложной структурой на такие значения, как их размеры), а затем суммируйте их по ${ displaystyle f '}$, и намного эффективнее, когда это применимо.

Реализация

Дополненные деревья

Расширенная карта может эффективно поддерживаться расширенными деревьями, где каждый узел дерева дополняется расширенным значением всех записей в его поддереве. Из-за ассоциативность функции комбайна ${ displaystyle f}$, увеличенное значение определенного дерева является фиксированным и не зависит от формы дерева, независимо от поворотов. В этом случае, комбинируя частичные суммы в узлах дерева, любая сумма диапазона может быть возвращена в ${ Displaystyle О ( журнал п)}$ время на увеличенной карте размера ${ displaystyle n}$, предполагая, что оба ${ displaystyle f}$ и ${ displaystyle g}$ имеют постоянную стоимость. Для aug_filter древовидная структура использует то преимущество, что если увеличенное значение поддерева не удовлетворяет индикатору ${ displaystyle h}$, все дерево отбрасывается. В этом случае стоимость aug_filter составляет ${ Displaystyle О (к журнал (1 + { гидроразрыва {п} {к}})}$ где ${ displaystyle k}$ - размер вывода. Для aug_project, когда все поддерево попадает в диапазон ${ Displaystyle [к_ {1}, к_ {2}]}$, его увеличенное значение может быть напрямую объединено с результатом, вместо того, чтобы требовать обхода дерева.

Префиксные структуры

Другая реализация - использовать префиксные структуры,^[2] в котором хранится увеличенное значение всех префиксов карты. Для определенной выше расширенной карты ${ displaystyle M_ {1}}$, структура префикса представляет собой массив, в котором хранится сумма префиксов значений, отсортированных по их ключам. Структуры префикса особенно полезны для aug_left, но могут быть неэффективными для реализации других функций в интерфейсе расширенной карты. Это может быть полезно в некоторых геометрических алгоритмах.

Пример приложения

1D колющий запрос

Одномерный колющий запрос принимает в качестве входных данных набор интервалов на одномерной числовой строке. Запрос спрашивает, покрыта ли данная точка каким-либо входным интервалом или всеми интервалами, покрывающими эту точку. Для этой проблемы может быть определена расширенная карта, где ключи - это левые конечные точки всех интервалов, значения - соответствующие правые конечные точки, а увеличенное значение - максимальное значение всех правых конечных точек на карте. Более формально:

${ Displaystyle M_ {интервал} = ( mathbb {R}, <_ { mathbb {R}},  mathbb {R},  mathbb {R}, (k, v)  mapsto v, { text { max}} _ { mathbb {R}}, -  infty)}$

Чтобы сообщить, покрывает ли какой-либо интервал заданную точку ${ displaystyle p}$, алгоритм запроса просто определяет, если aug_left${ displaystyle (p)> p}$. Это потому, что aug_left просматривает все интервалы, начинающиеся до ${ displaystyle p}$, и если максимальная правая конечная точка среди них превышает ${ displaystyle p}$, тогда ${ displaystyle p}$ При реализации с расширенными деревьями расширенная карта ${ displaystyle M _ { text {interval}}}$ это точно дерево интервалов. Построение такой расширенной древовидной структуры стоит трудозатрат. ${ Displaystyle О (п журнал п)}$, ${ Displaystyle О ( журнал п)}$ параллельная глубина и ${ Displaystyle О (п)}$ Космос. Каждый колющий запрос можно выполнить вовремя ${ Displaystyle О ( журнал п)}$.

2D-запрос диапазона

Запрос 2D-диапазона принимает в качестве входных данных набор точек в двух измерениях. Запрос запрашивает все точки (или число) в определенном прямоугольнике, края которого параллельны оси. Для этой проблемы может быть определена расширенная карта, которая представляет собой двухуровневую вложенную структуру карты. На внешней карте хранятся все точки и отсортированы их по x-координатам. Расширенное значение внешней карты - это внутренняя расширенная структура карты, которая хранит тот же набор точек, что и внешняя карта, но сортирует их по их y-координатам. Увеличение внутренних деревьев накапливает количество точек, то есть увеличиваемое значение внутренней карты - это ее размер. Соответственно, функция объединения внешней карты состоит в объединении двух внутренних расширенных карт. Более формально:

${ Displaystyle M_ {внутренний} = (Y, <_ {Y}, X,  mathbb {Z}, (k, v)  mapsto 1, + _ { mathbb {Z}}, 0)}$${ displaystyle M_ {external} = (X, <_ {X}, Y, M _ { text {inner}}, (k, v)  mapsto M _ { text {inner}}. singleton (v, k) , M _ { text {inner}}. { Text {union}}, M _ { text {inner}}. { Text {empty}})}$

Здесь для простоты предположим, что все координаты уникальны. ${ displaystyle X}$ и ${ displaystyle Y}$ - это типы координат x и y. Чтобы ответить на запрос диапазона в прямоугольнике ${ displaystyle (x_ {1}, x_ {2}, y_ {1}, y_ {2})}$, алгоритм запроса извлекает увеличенное значение внешней карты в диапазоне ключей ${ Displaystyle [х_ {1}, х_ {2}]}$, которая представляет собой внутреннюю карту всех желаемых точек, отсортированных по y-координатам. Следовательно, алгоритм берет другой aug_range на этой внутренней карте и получает результат. Для подсчета запросов алгоритм может использовать функцию aug_project.

${ displaystyle query (m, x_ {1}, x_ {2}, y_ {1}, y_ {2}) = M _ { text {outer}}. { text {aug}}  _ { text { проект}} (g ', + _ { mathbb {Z}}, m, x_ {1}, x_ {2})}$${ displaystyle { text {where}} g ': M _ { text {inner}}  mapsto  mathbb {Z}, g' (m ') = M _ { text {inner}}. { text {aug }}  _ { text {диапазон}} (м, г_ {1}, г_ {2})}$

Если и внутренняя, и внешняя карты реализованы расширенными деревьями, тогда вся двухуровневая структура карты становится дерево диапазона структура. Если внутренняя карта поддерживается расширенной древовидной структурой, а внешнее дерево поддерживается как префиксная структура, тогда алгоритм становится алгоритм Sweepline.

Другие примеры

Другие примеры^[1][2] включать сегментные запросы, поиск по инвертированному индексу, прямоугольные запросы и т. д.

Поддержка Libaray

Параллельная реализация интерфейса расширенной карты предоставляется в библиотеке. PAM.

Заметки

использованная литература