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

Не путать с Z-кривой или Z-порядком .

Четыре итерации кривой Z-порядка.

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

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

Значения координат

Вычисление координат кривой Z-порядка ( x , y ) из чередующихся битов z -значения 2479.

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

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

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

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

x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101x[i−j] = ((x[i] & 0b01010101) − x[j]) & 0b01010101  if i ≥ j

Это свойство можно использовать для смещения значения Z, например, в двух измерениях координат сверху (уменьшение y), нижнего (увеличение y), левого (уменьшение x) и правого (увеличение x) от текущего значения 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-значения w и z :

sum    = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)

Эффективное построение квадро- и окт-деревьев

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

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

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

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

def cmp_zorder(lhs, rhs) -> bool:    """Compare z-ordering."""    # Assume lhs and rhs array-like objects of indices.    assert len(lhs) == len(rhs)    # Will contain the most significant dimension.    msd = 0    # Loop over the other dimensions.    for dim in range(1, len(lhs)):        # Check if the current dimension is more significant        # by comparing the most significant bits.        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-порядок хорошо сохраняет локальность, для эффективного поиска диапазона необходим алгоритм для расчета из точки, встречающейся в структуре данных, следующего возможного значения Z, которое находится в многомерном диапазоне поиска:

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

Подробное объяснение алгоритма расчета LITMAX/BIGMIN вместе с исходным кодом Pascal (3D, легко адаптируемым к nD) и подсказки о том, как обрабатывать данные с плавающей запятой и, возможно, отрицательные данные, предоставлены Tropf в 2021 году : Здесь чередование битов не сделано явно; структура данных содержит только указатели на исходные (несортированные) записи базы данных. Благодаря общей функции сравнения записей (больше-меньше-равно в смысле z-значения) можно избежать осложнений, связанных с длиной битовых последовательностей, превышающей длину компьютерного слова, и код можно легко адаптировать к любому количеству измерений и любой записи. длина ключевого слова.

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

Выбор «Свободный» упрощает внедрение метода в существующие базы данных. Это отличается, например, от R-деревьев , где необходимы особые соображения.

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

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

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

В качестве альтернативы была предложена кривая Гильберта , поскольку она лучше сохраняет порядок. и, по сути, использовался в оптимизированном индексе S2-геометрии.

Приложения

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

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

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

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

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

Наложение текстур

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

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

телом проблема с

Алгоритм Барнса – Хата требует построения октодерева. Хранение данных в виде дерева на основе указателей требует множества последовательных разыменований указателей для перебора окто-дерева в порядке глубины (дорого на машине с распределенной памятью). Вместо этого, если данные сохраняются в хеш-таблице , используя хеширование октодерева, кривая Z-порядка естественным образом повторяет октодерево в порядке глубины.

См. также

• Геохэш
• Гильбертово R-дерево
• Линейная алгебра
• Хеширование с сохранением локальности
• Матричное представление
• Теорема Нетто
• PH-дерево
• Пространственный индекс

Внешние ссылки

• STANN: библиотека для приблизительного поиска ближайших соседей с использованием кривой Z-порядка.
• Методы программирования чередования битов , Шон Эрон Андерсон, Стэнфордский университет