У меня есть приложение, где Hilbert R-Tree (wikipedia) (citeseer), как представляется, является соответствующей структурой данных. В частности, он требует достаточно быстрых пространственных запросов по набору данных, который будет испытывать много обновлений.
Однако, насколько я вижу, ни одно из описаний алгоритмов для этой структуры данных даже не упоминает, как реально вычислить требуемое значение Гильберта; который представляет собой расстояние по кривой
Веселый вопрос!
Я немного поработал в поисковых системах, и хорошая новость: я нашел реализацию значения Гильберта.
Потенциально плохая новость, это в Haskell...
http://www.serpentine.com/blog/2007/01/11/two-dimensional-spatial-hashing-with-space-filling-curves/
В нем также предлагается метрика расстояния Лебега, которую вы могли бы легко вычислить.
Ниже мой код Java, адаптированный из кода C в документе "Кодирование и декодирование порядка Гильберта" Сиан Лу и Гюнтера Шрека, опубликованного в "Software: Practice and Experience Vol. 26 с. 1335-46 (1996).
Надеюсь, это поможет. Усовершенствования приветствуются!
Майкл
/**
* Find the Hilbert order (=vertex index) for the given grid cell
* coordinates.
* @param x cell column (from 0)
* @param y cell row (from 0)
* @param r resolution of Hilbert curve (grid will have Math.pow(2,r)
* rows and cols)
* @return Hilbert order
*/
public static int encode(int x, int y, int r) {
int mask = (1 << r) - 1;
int hodd = 0;
int heven = x ^ y;
int notx = ~x & mask;
int noty = ~y & mask;
int temp = notx ^ y;
int v0 = 0, v1 = 0;
for (int k = 1; k < r; k++) {
v1 = ((v1 & heven) | ((v0 ^ noty) & temp)) >> 1;
v0 = ((v0 & (v1 ^ notx)) | (~v0 & (v1 ^ noty))) >> 1;
}
hodd = (~v0 & (v1 ^ x)) | (v0 & (v1 ^ noty));
return interleaveBits(hodd, heven);
}
/**
* Interleave the bits from two input integer values
* @param odd integer holding bit values for odd bit positions
* @param even integer holding bit values for even bit positions
* @return the integer that results from interleaving the input bits
*
* @todo: I'm sure there a more elegant way of doing this !
*/
private static int interleaveBits(int odd, int even) {
int val = 0;
// Replaced this line with the improved code provided by Tuska
// int n = Math.max(Integer.highestOneBit(odd), Integer.highestOneBit(even));
int max = Math.max(odd, even);
int n = 0;
while (max > 0) {
n++;
max >>= 1;
}
for (int i = 0; i < n; i++) {
int bitMask = 1 << i;
int a = (even & bitMask) > 0 ? (1 << (2*i)) : 0;
int b = (odd & bitMask) > 0 ? (1 << (2*i+1)) : 0;
val += a + b;
}
return val;
}
См. uzaygezen.
Код и код Java выше подходят для 2D-данных. Но для более высоких измерений вам, возможно, придется посмотреть на статью Джонатана Лаудера: J.K.Lawder. Вычисление отображений между одним и n-мерными значениями с использованием кривой заполнения пространства Гильберта.
Я понял немного более эффективный способ чередования битов. Его можно найти на
Майкл
спасибо за код Java! Я тестировал его и, похоже, работал нормально, но я заметил, что функция чередования бит переполняется на уровне 7 рекурсии (по крайней мере, в моих тестах, но я использовал длинные значения), потому что значение "n" вычисляется с использованием mostOneBit ( ) -функция, которая возвращает значение, а не позицию самого высокого одного бита; поэтому цикл делает излишне много перемежений.
Я просто изменил его на следующий фрагмент, и после этого он работал нормально.
int max = Math.max(odd, even);
int n = 0;
while (max > 0) {
n++;
max >>= 1;
}
Если вам нужен пространственный индекс с быстрыми возможностями удаления/вставки, посмотрите на PH-дерево. Он частично основан на квадрантах, но быстрее и эффективнее. Внутри он использует Z-кривую, которая имеет несколько худшие пространственные свойства, чем H-кривая, но легче .
Бумага: http://www.globis.ethz.ch/script/publication/download?docid=699
Реализация Java: http://globis.ethz.ch/files/2014/11/ph-tree-2014-11-10.zip
Другим вариантом является X-дерево, которое также доступно здесь: https://code.google.com/p/xxl/
Предложение. Хорошей простой эффективной структурой данных для пространственных запросов является многомерное двоичное дерево.
В традиционном двоичном дереве есть один "дискриминант"; значение, используемое для определения того, берете ли вы левую ветвь или правую ветвь. Это можно рассматривать как одномерный случай.
В многомерном двоичном дереве у вас есть несколько дискриминаторов; последовательные уровни используют разные дискриминаторы. Например, для двумерных пространственных данных вы можете использовать координаты X и Y как дискриминанты. Последовательные уровни будут использовать X, Y, X, Y...
Для пространственных запросов (например, для поиска всех узлов внутри прямоугольника) вы выполняете поиск по глубине дерева, начинающегося с корня, и используете дискриминант на каждом уровне, чтобы избежать поиска в ветвях, которые не содержат узлов в заданный прямоугольник.
Это позволяет потенциально сократить пространство поиска пополам на каждом уровне, что делает его очень эффективным для поиска небольших областей в массиве данных. (BTW, эта структура данных также полезна для запросов с частичным совпадением, то есть запросов, которые опускают один или несколько дискриминаторов. Вы просто просматриваете обе ветки на уровнях с пропущенным дискриминантом.)
Хорошая статья по этой структуре данных: http://portal.acm.org/citation.cfm?id=361007 Эта статья содержит хорошие диаграммы и описания алгоритмов: http://en.wikipedia.org/wiki/Kd-tree