Кривая Z-порядка

редактировать
Четыре итерации кривой Z-порядка. Итерации кривой Z-порядка расширены до трех измерений.

В математическом анализе и информатике, функции, которые имеют Z-порядок, кривую Лебега, Кривая заполнения пространства Мортона, Порядок Мортона или код Мортона отображает многомерные данные в одно измерение, сохраняя при этом локальность точек данных. Он назван в честь того, кто первым применил порядок к упорядочиванию файлов в 1966 году. Z-значение точки в многомерности просто вычисляется путем чередования двоичных представлений ее значений координат. После сортировки данных в этом порядке можно использовать любую одномерную структуру данных, такую ​​как деревья двоичного поиска, B-деревья, списки пропуска или ( с усеченными младшими значащими битами) хеш-таблицы. Результирующий порядок можно эквивалентно описать как порядок, который можно было бы получить при обходе в глубину квадродерева.

Содержание
  • 1 Значения координат
  • 2 Эффективное построение квадродеревьев
  • 3 Использование с одним- размерные структуры данных для поиска по диапазону
  • 4 Связанные структуры
  • 5 Приложения
    • 5.1 Линейная алгебра
    • 5.2 Отображение текстур
  • 6 См. также
  • 7 Ссылки
  • 8 Внешние ссылки
Координата values ​​

На рисунке ниже показаны Z-значения для двумерного случая с целочисленными координатами 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (показаны как в десятичном, так и в двоичном формате). Чередование значений двоичных координат дает двоичные z-значения, как показано. Соединение z-значений в их числовом порядке дает рекурсивную Z-образную кривую. Двумерные Z-значения также называются квадратичными.

Z-curve.svg

Z-значения x описываются как двоичные числа из последовательности Мозера – де Брейна, имеющие ненулевые биты только в их четных позициях:

x = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}

Сумма и разность двух x вычисляются с помощью побитовых операций :

x [i + j] = ((x [i] | 0b10101010) + x [j]) 0b01010101 x [ij] = ((x [i] 0b01010101) - x [j]) 0b01010101 if i>= j

Это свойство можно использовать для смещение Z-значения, например, в двух измерениях координаты вверху (уменьшение y), внизу (увеличение y), влево (уменьшение x) и вправо (увеличение x) от текущего Z-значения z:

top = (((z 0b10101010) - 1) 0b10101010) | (z 0b01010101) bottom = (((z | 0b01010101) + 1) 0b10101010) | (z 0b01010101) left = (((z 0b01010101) - 1) 0b01010101) | (z 0b10101010) right = (((z | 0b10101010) + 1) 0b01010101) | (z 0b10101010)

И вообще, чтобы добавить два двумерных Z-значения:

sum = ((z | 0b10101010) + (w 0b01010101) 0b01010101) | ((z | 0b01010101) + (w 0b10101010) 0b10101010)
Эффективное построение квадродеревьев

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

Входные точки обычно масштабируются в каждом измерении, чтобы быть положительными целыми числами, либо в виде представления с фиксированной точкой в ​​диапазоне единиц [0, 1], либо в соответствии с размером машинного слова. Оба представления эквивалентны и позволяют находить ненулевой бит высшего порядка за постоянное время. Каждый квадрат в дереве квадрантов имеет длину стороны, равную степени двойки, и координаты углов, кратные длине стороны. Для любых двух точек производный квадрат для этих двух точек является наименьшим квадратом, покрывающим обе точки. Перемежение битов из компонентов x и y каждой точки называется перемешиванием x и y и может быть расширено до более высоких измерений.

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

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

def cmp_zorder (lhs, rhs) ->bool: "" "Сравнить z-ordering." "" # Предположим, что объекты индексов, подобные массивам lhs и rhs. assert len ​​(lhs) == len (rhs) # Будет содержать наиболее значимое измерение. msd = 0 # Перебираем другие измерения. for dim in range (1, len (lhs)): # Проверить, является ли текущее измерение более значимым # путем сравнения самых значимых битов. if less_msb (lhs [msd] ^ rhs [msd], lhs [dim] ^ rhs [dim]): msd = dim return lhs [msd] < rhs[msd]

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

def less_msb (x: int, y: int) ->bool: return x < y and x < (x ^ y)

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

Когда точки расположены в отсортированном порядке, два свойства упрощают построение квадродерева: во-первых, точки, содержащиеся в квадрате квадродерево образуют непрерывный интервал в отсортированном порядке. Во-вторых, если более чем один дочерний элемент квадрата содержит входную точку, квадрат является производным квадратом для двух смежных точек в отсортированном порядке.

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

Вместо построения дерева квадрантов на основе указателя точки могут поддерживаться в отсортированном порядке в структуре данных, такой как двоичное дерево поиска. Это позволяет добавлять и удалять точки за время O (log n). Два квадродерева можно объединить, объединив два отсортированных набора точек и удалив дубликаты. Местоположение точки может быть выполнено путем поиска точек, предшествующих и следующих за точкой запроса в отсортированном порядке. Если дерево квадрантов сжато, найденный узел-предшественник может быть произвольным листом внутри сжатого интересующего узла. В этом случае необходимо найти предшественника наименее общего предка точки запроса и найденного листа.

Использование с одномерными структурами данных для поиска по диапазону

Хотя с сохранением локальности Что ж, для эффективного поиска по диапазону необходим алгоритм для вычисления следующего Z-значения, которое находится в многомерном диапазоне поиска:

поиск BIGMIN в кривой Z-порядка.svg

В этом примере запрашиваемый диапазон (x = 2,..., 3, y = 2,..., 6) обозначен пунктирным прямоугольником. Его максимальное Z-значение (MAX) составляет 45. В этом примере значение F = 19 встречается при поиске структуры данных в направлении увеличения Z-значения, поэтому нам придется искать в интервале между F и MAX (заштрихованная область). Чтобы ускорить поиск, нужно вычислить следующее Z-значение, которое находится в диапазоне поиска, названное BIGMIN (36 в примере), и искать только в интервале между BIGMIN и MAX (значения, выделенные жирным шрифтом), таким образом пропуская большую часть заштрихованных площадь. Поиск в убывающем направлении аналогичен LITMAX, который является самым высоким Z-значением в диапазоне запроса ниже F. Проблема BIGMIN была впервые сформулирована, и ее решение показано в Tropf и Herzog. Это решение также используется в UB-деревьях («GetNextZ-адрес»). Поскольку подход не зависит от выбранной одномерной структуры данных, по-прежнему существует свободный выбор структурирования данных, поэтому для работы с динамическими данными можно использовать хорошо известные методы, такие как сбалансированные деревья (в отличие, например, от R -деревья, где необходимы особые соображения). Точно так же эта независимость упрощает включение метода в существующие базы данных.

Применение метода иерархически (в соответствии с имеющейся структурой данных), необязательно как в направлении увеличения, так и уменьшения, дает высокоэффективный поиск по многомерному диапазону, который важен как для коммерческих, так и для технических приложений, например как процедура, лежащая в основе поиска ближайшего соседа. Z-порядок - один из немногих методов многомерного доступа, который нашел свое применение в коммерческих системах баз данных (Oracle database 1995, Transbase 2000).

Еще в 1966 году Г.М. Мортон предложил Z-порядок для упорядочивания файлов статической двухмерной географической базы данных. Единицы площадных данных содержатся в одном или нескольких квадратичных кадрах, представленных их размерами и Z-значениями нижнего правого угла, размеры которых соответствуют иерархии Z-порядка в угловой позиции. С большой вероятностью переход к соседнему кадру выполняется за один или несколько относительно небольших шагов сканирования.

Связанные структуры

В качестве альтернативы была предложена кривая Гильберта, поскольку она лучше сохраняет порядок и фактически использовалась в оптимизированном индекс, S2-геометрия. До S2 этого избегали, потому что вычисления несколько сложнее, что приводило к значительным накладным расходам процессора. Исходный код BIGMIN для Z-кривой и кривой Гильберта был описан в патенте Х. Тропфа.

Для недавнего обзора многомерной обработки данных, включая, например, поиск ближайшего соседа, см. учебник Ханана Самета.

Приложения
Таблица сложения для x + 2 y {\ displaystyle x + 2y}{\ displaystyle x + 2y} где x {\ displaystyle x}x и y {\ displaystyle y}y оба принадлежат последовательности Мозера – де Брейна, и кривая Z-порядка, которая соединяет суммы в числовом порядке

Линейная алгебра

Алгоритм Штрассена для умножения матриц основан на разделении матриц на четыре блока, а затем рекурсивном разделении каждого из этих блоков в четыре меньших блока, пока блоки не станут одиночными элементами (или, что более практично: до достижения матриц настолько малых, что тривиальный алгоритм последовательности Мозера – де Брейна будет быстрее). Расположение элементов матрицы в Z-порядке улучшает локальность и дает дополнительное преимущество (по сравнению с упорядочением по строкам или столбцам), заключающееся в том, что подпрограмме умножения двух блоков не требуется знать общий размер матрицы, а нужно знать только ее размер. размер блоков и их расположение в памяти. Эффективное использование умножения Штрассена с Z-порядком было продемонстрировано, см. Статью Валсалама и Скьеллума 2002 г.

Buluç et al. представляют структуру данных разреженной матрицы, которая Z-упорядочивает свои ненулевые элементы, чтобы включить параллельное умножение матрицы на вектор.

Отображение текстуры

Некоторые GPU хранят карты текстуры в Z-порядке, чтобы увеличить пространственную локальность ссылки во время растеризации с отображением текстуры. Это позволяет строкам кэша представлять прямоугольные плитки, увеличивая вероятность того, что соседние обращения находятся в кэше. В более крупном масштабе это также снижает вероятность дорогостоящих, так называемых, «разрывов страниц» (т.е. стоимость изменения строк ) в SDRAM / DDRAM. Это важно, поскольку 3D-рендеринг включает произвольные преобразования (поворот, масштабирование, перспективу и искажение анимированными поверхностями).

Эти форматы часто называют «сдвинутыми» текстурами или «скрученными текстурами». Также могут использоваться другие плиточные форматы.

См. Также
Ссылки
Внешние ссылки
Последняя правка сделана 2021-06-23 05:06:22
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте