В математическом анализе и информатике функции Z -порядка , кривая Лебега , кривая заполнения пространства Мортона , [1] порядок Мортона или код Мортона отображают многомерные данные в одно измерение , сохраняя при этом локальность точек данных. Он назван во Франции в честь Анри Лебега , который изучал его в 1904 году, [2] и назван в США в честь Гая Макдональда Мортона, который впервые применил порядок для секвенирования файлов в 1966 году. [3] Z-значение точки в многомерных измерениях просто рассчитывается путем чередования двоичных представлений значений его координат. После того, как данные отсортированы в таком порядке, можно использовать любую одномерную структуру данных, такую как простые одномерные массивы , двоичные деревья поиска , B-деревья , списки пропуска или (с усеченными младшими значащими битами) хеш-таблицы . Результирующее упорядочение можно эквивалентно описать как порядок, который можно получить при обходе в глубину квадродерева или октодерева .
На рисунке ниже показаны значения 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, если i ≥ j
Это свойство можно использовать для смещения значения Z, например, в двух измерениях координат сверху (уменьшение y), нижнего (увеличение y), левого (уменьшение x) и правого (увеличение x) от текущего значения Z. я :
верх = (((z & 0b10101010) − 1) & 0b10101010) | (з и 0b01010101)внизу = (((z | 0b01010101) + 1) & 0b10101010) | (з и 0b01010101)влево = (((z & 0b01010101) − 1) & 0b01010101) | (з и 0b10101010)вправо = (((z | 0b10101010) + 1) & 0b01010101) | (з и 0b10101010)
И вообще, чтобы сложить два двумерных Z-значения w и z :
сумма = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)
Z-упорядочение можно использовать для эффективного построения квадродерева (2D) или октадерева (3D) для набора точек. [4] [5] Основная идея состоит в том, чтобы отсортировать входной набор в соответствии с Z-порядком. После сортировки точки можно либо сохранить в двоичном дереве поиска и использовать напрямую, которое называется линейным квадродеревом [6] , либо их можно использовать для построения квадродерева на основе указателей.
Входные точки обычно масштабируются в каждом измерении до целых положительных чисел либо в виде представления с фиксированной точкой в единичном диапазоне [0, 1] , либо в соответствии с размером машинного слова. Оба представления эквивалентны и позволяют найти ненулевой бит старшего порядка за постоянное время. Каждый квадрат в дереве квадрантов имеет длину стороны, равную степени двойки, и угловые координаты, кратные длине стороны. Для любых двух точек полученный квадрат для этих двух точек является наименьшим квадратом, охватывающим обе точки. Чередование битов компонентов x и y каждой точки называется перетасовкой x и y и может быть расширено до более высоких измерений . [4]
Точки можно сортировать в соответствии с их перемешиванием без явного чередования битов. Для этого для каждого измерения исследуется старший бит исключительных координат двух точек этого измерения. Размерность, для которой старший бит является наибольшим, затем используется для сравнения двух точек, чтобы определить порядок их тасования.
Эксклюзивная операция или операция маскирует старшие биты, для которых две координаты идентичны. Поскольку при перетасовке биты перемежаются от более высокого порядка к более низкому, идентификация координаты с самым большим и наиболее значащим битом определяет первый бит в порядке перемешивания, который отличается, и эту координату можно использовать для сравнения двух точек. [7] Это показано в следующем коде Python:
def cmp_zorder ( lhs , rhs ) -> bool : """Сравнить z-упорядочение.""" # Предположим, что объекты индексов имеют вид массива слева и справа. 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 каждой точки. Оказывается, следующая операция эквивалентна и требует только исключающих операций или: [7]
def less_msb ( x : int , y : int ) -> bool : return x < y и x < ( x ^ y )Также можно сравнивать числа с плавающей запятой, используя тот же метод. Функция less_msbизменена так, чтобы сначала сравнивать показатели степени. less_msbТолько когда они равны , к мантиссам применяется стандартная функция. [8]
Когда точки расположены в отсортированном порядке, два свойства упрощают построение квадродерева. Первое заключается в том, что точки, содержащиеся в квадрате квадродерева, образуют непрерывный интервал в отсортированном порядке. Во-вторых, если более одного дочернего элемента квадрата содержат входную точку, этот квадрат является производным квадратом для двух соседних точек в отсортированном порядке.
Для каждой соседней пары точек вычисляется производный квадрат и определяется длина его стороны. Для каждого производного квадрата интервал, содержащий его, ограничен первым большим квадратом справа и слева в отсортированном порядке. [4] Каждый такой интервал соответствует квадрату в дереве квадрантов. Результатом этого является сжатое квадродерево, в котором присутствуют только узлы, содержащие входные точки или два или более дочерних элемента. При желании несжатое квадродерево можно построить путем восстановления недостающих узлов.
Вместо построения квадродерева на основе указателей точки можно хранить в отсортированном порядке в структуре данных, такой как двоичное дерево поиска. Это позволяет добавлять и удалять точки за время O (log n ) . Два квадродерева можно объединить, объединив два отсортированных набора точек и удалив дубликаты. Местоположение точки можно определить путем поиска точек, предшествующих и следующих за точкой запроса, в отсортированном порядке. Если квадродерево сжато, найденный узел-предшественник может быть произвольным листом внутри интересующего сжатого узла. В этом случае необходимо найти предшественника наименьшего общего предка точки запроса и найденного листа. [9]
Путем побитового чередования записи базы данных преобразуются в (возможно, очень длинную) последовательность битов. Последовательности бит интерпретируются как двоичные числа, а данные сортируются или индексируются по двоичным значениям с использованием любой одномерной структуры данных, как упоминалось во введении. Однако при запросе многомерного диапазона поиска в этих данных использование двоичного поиска не очень эффективно. Хотя 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 была впервые сформулирована, а ее решение показано Тропфом и Герцогом. [10]
Подробное объяснение алгоритма расчета LITMAX/BIGMIN вместе с исходным кодом Pascal (3D, легко адаптируемым к nD) и подсказки о том, как обрабатывать данные с плавающей запятой и, возможно, отрицательные данные, предоставлены Тропфом в 2021 году: Здесь чередование битов не сделано явно; структура данных содержит только указатели на исходные (несортированные) записи базы данных. Благодаря общей функции сравнения записей (больше-меньше-равно в смысле z-значения) можно избежать осложнений, связанных с длиной битовых последовательностей, превышающей длину компьютерного слова, и код можно легко адаптировать к любому количеству измерений и любой записи. длина ключевого слова.
Поскольку подход не зависит от выбранной одномерной структуры данных, по-прежнему существует свободный выбор структурирования данных, поэтому можно использовать хорошо известные методы, такие как сбалансированные деревья, для работы с динамическими данными и сохранения баланса дерева при вставке или удалении. занимает время O(log n). Метод также используется в UB-деревьях (сбалансированных) [11] под названием «GetNextZ-адрес» для BIGMIN.
Выбор «Свободный» упрощает внедрение метода в существующие базы данных. Это отличается, например, от R-деревьев , где необходимы особые соображения.
Применение метода иерархически (в соответствии с имеющейся структурой данных), при необходимости как в возрастающем, так и в убывающем направлении, дает высокоэффективный многомерный поиск диапазона, который важен как в коммерческих, так и в технических приложениях, например, в качестве процедуры, лежащей в основе поиска ближайшего соседа. Z-порядок — один из немногих методов многомерного доступа, который нашел применение в коммерческих системах баз данных. [12] Метод используется в различных технических приложениях различных областей [13] и в коммерческих системах баз данных. [14]
Еще в 1966 году Г. М. Мортон предложил Z-порядок для упорядочения файлов статической двумерной географической базы данных. Единицы площадных данных содержатся в одном или нескольких квадратных кадрах, представленных их размерами и Z-значениями в нижнем правом углу, причем размеры соответствуют иерархии Z-порядка в угловой позиции. С высокой вероятностью переход на соседний кадр осуществляется за один или несколько относительно небольших шагов сканирования. [3]
В качестве альтернативы была предложена кривая Гильберта , поскольку она лучше сохраняет порядок [5] и фактически использовалась в оптимизированном индексе S2-геометрии. [15]
Алгоритм Штрассена для умножения матриц основан на разбиении матриц на четыре блока, а затем рекурсивном разбиении каждого из этих блоков на четыре меньших блока до тех пор, пока блоки не станут отдельными элементами (или, что более практично: до тех пор, пока матрицы не будут настолько малы, что Тривиальный алгоритм последовательности Брейна быстрее). Расположение элементов матрицы в Z-порядке улучшает локальность и имеет дополнительное преимущество (по сравнению с упорядочением по строкам или столбцам), заключающееся в том, что подпрограмме для умножения двух блоков не нужно знать общий размер матрицы, а только размер блоков и их расположение в памяти. Было продемонстрировано эффективное использование умножения Штрассена с Z-порядком, см. статью Валсалама и Скьеллума 2002 года. [16]
Булуч и др. представить разреженную матричную структуру данных, которая Z-упорядочивает свои ненулевые элементы, чтобы обеспечить параллельное умножение матрицы на вектор. [17]
Матрицы в линейной алгебре также можно перемещать с помощью кривой, заполняющей пространство. [18] Обычные циклы обходят матрицу строка за строкой. Обход с помощью Z-кривой обеспечивает эффективный доступ к иерархии памяти . [19]
Некоторые графические процессоры хранят карты текстур в Z-порядке, чтобы увеличить пространственную локальность привязки во время растеризации текстурных карт . Это позволяет строкам кэша представлять прямоугольные плитки, увеличивая вероятность того, что близлежащие обращения находятся в кэше. В более широком масштабе это также снижает вероятность дорогостоящих, так называемых, «разрывов страниц» (т. е. стоимость изменения строк ) в SDRAM/DDRAM. Это важно, поскольку 3D-рендеринг включает в себя произвольные преобразования (повороты, масштабирование, перспективу и искажение анимированными поверхностями).
Эти форматы часто называют swizzled текстурами или twiddled текстурами . Также могут использоваться другие форматы плиток.
Алгоритм Барнса – Хата требует построения октодерева. Хранение данных в виде дерева на основе указателей требует множества последовательных разыменований указателей для перебора октодерева в порядке глубины (дорого на машине с распределенной памятью). Вместо этого, если данные сохраняются в хеш-таблице , используя хеширование октодерева, кривая Z-порядка естественным образом повторяет октодерево в порядке глубины. [5]