Крива Гільберта та криві, що заповнюють простір — локальність, індексація, стиснення

1. Парадокс Пеано: лінія, що заповнює квадрат

У 1890 р. італійський математик Джузеппе Пеано побудував дещо, що, здавалося, суперечило здоровому глузду: неперервну криву — єдиний, нерозривний одновимірний шлях — яка проходить через кожну без винятку точку двовимірного квадрата. До Пеано математики вважали, що крива, будучи по суті одновимірною, просто не може мати «достатньо точок», щоб покрити цілу 2D-площу. Георг Кантор вже показав, що множина точок на прямій і множина точок у квадраті мають однакову потужність (обидві незліченно нескінченні, у бієкції одна з одною) — але конструкція Пеано пішла далі, показавши, що цю відповідність можна зробити неперервною: можна прокреслити відображення пером, не відриваючи його, і зрештою зафарбувати кожну точку квадрата.

Цей клас кривих називається кривими, що заповнюють простір. Вони неперервні (без стрибків), але, як відомо, ніде не диференційовні — не мають чітко визначеного напрямку дотичної в жодній точці, бо вони нескінченно часто змінюють напрямок на кожному масштабі, подібно до фрактальної кривої розмірності рівно 2.

Девід Гільберт уточнив конструкцію Пеано у 1891 р. у чистіше, візуально інтуїтивніше рекурсивне правило, і саме версія Гільберта — а не оригінальний зигзаг Пеано — використовується майже повсюдно в обчисленнях сьогодні, завдяки одній вирішальній додатковій властивості конструкції Гільберта: локальності.

2. Рекурсивна конструкція Гільберта

Крива Гільберта будується рекурсивно. Почніть з простого U-подібного шляху, що відвідує чотири квадранти квадрата по порядку. Щоб отримати наступний рівень деталізації, замініть кожен з чотирьох квадрантів меншою, відповідно повернутою й/або віддзеркаленою копією тієї самої U-подібної форми, обраною так, щоб точка виходу одної підкривої точно збігалася з точкою входу наступної. Повторюйте цю підстановку нескінченно, і в межі крива відвідує кожну точку квадрата.

Повороти на кожному рекурсивному рівні — саме те, що робить криву Гільберта особливою: вони гарантують, що там, де завершується шлях однієї підквадрата, шлях наступного підквадрата підхоплюється прямо поруч у фізичному просторі, а не лише в абстрактному 1D-впорядкуванні. Застосована рекурсивно, ця гарантія стає глобальною: послідовні індекси вздовж усієї кривої завжди фізично суміжні клітинки, на кожному масштабі, усюди в сітці — властивість, якої жодна простіша рекурсивна схема не досягає так добре.

// Перетворення 1D-відстані Гільберта d у координати сітки (x, y), порядок n
// (Класичний бітовий алгоритм; n = кількість бітів на вісь)
function hilbertD2XY(n, d) {
  let [x, y] = [0, 0];
  let t = d;
  for (let s = 1; s < n; s *= 2) {
    const rx = 1 & (t / 2 | 0);
    const ry = 1 & (t ^ rx);
    // Повертаємо квадрант так, щоб вхід/вихід вирівнявся з батьківською кривою
    if (ry === 0) {
      if (rx === 1) { x = s - 1 - x; y = s - 1 - y; }
      [x, y] = [y, x];  // обмін (віддзеркалення по діагоналі)
    }
    x += s * rx;
    y += s * ry;
    t = Math.floor(t / 4);
  }
  return [x, y];
}

3. Гільберт проти Мортона (Z-порядок)

Простіша, швидша у обчисленні альтернатива — порядок Мортона, також званий Z-кривою: перемежувати біти координат x і y безпосередньо, щоб отримати єдиний індекс. Вона поділяє з кривою Гільберта ідею рекурсивних квадрантів, але пропускає крок повороту — що робить її драматично простішою й швидшою для обчислення, ціною реальних втрат якості локальності.

// Кодування Мортона (Z-порядок): перемежування бітів x і y
function mortonEncode(x, y) {
  function spread(v) {
    v &= 0x0000ffff;
    v = (v | (v << 8)) & 0x00ff00ff;
    v = (v | (v << 4)) & 0x0f0f0f0f;
    v = (v | (v << 2)) & 0x33333333;
    v = (v | (v << 1)) & 0x55555555;
    return v;
  }
  return spread(x) | (spread(y) << 1);
}

Слабкість Z-кривої видна вже в її назві: прокреслюючи послідовні індекси Мортона, малюється Z-подібна форма, і щоразу, коли крива переходить з одного квадранта в наступний, вона може стрибнути через усю сітку — бо старші біти коду Мортона можуть перемкнутися, тоді як молодші скидаються, породжуючи великий стрибок у фізичному просторі при зміні індексу лише на 1. Повороти кривої Гільберта існують саме для того, щоб усунути ці стрибки, роблячи її локальність доказово оптимальною, ціною приблизно у 2–4 рази більшої обчислювальної вартості порівняно з кодуванням/декодуванням Мортона.

4. Чому це важливо: бази даних, кеші, стиснення

Індексація просторових баз даних. PostGIS, географічні інформаційні системи й бази даних часових рядів із локацією відображають 2D- чи 3D-координати в єдиний індекс Гільберта і зберігають рядки, відсортовані за цим індексом, у звичайному B-дереві. Оскільки крива Гільберта настільки добре зберігає локальність, суцільний діапазон індексів Гільберта відповідає компактному географічному регіону, перетворюючи дорогі багатовимірні діапазонні запити на швидкі одновимірні сканування діапазону B-дерева.

Локальність кешу CPU й GPU. Обхід 2D-текстури, висотного поля чи сітки в растровому (порядковому) порядку спричиняє некеш-дружні патерни доступу щоразу, коли ви переходите на новий рядок. Зберігання тих самих даних у порядку кривої Гільберта натомість означає, що будь-яка невелика локальна околиця пікселів чи клітинок сітки — це також невеликий суцільний блок адрес пам'яті, що драматично покращує показники влучень у кеш для алгоритмів на кшталт генерації mip-мап, стрімінгу текстур плитками й ядер розмиття/згортки зображень.

Розподілені системи й балансування навантаження. Системи, що шардують дані на багатьох машинах за географічним чи просторовим ключем (маршрутизація доставки, географічне шардування, розподілені хеш-таблиці з вимогами локальності), використовують індекси Гільберта, щоб близькі реальні локації потрапляли на той самий чи сусідній шард, мінімізуючи дорогі міжшардові запити.

Стиснення зображень і відео. Деякі алгоритми стиснення зображень і дизерингу обходять пікселі в порядку кривої Гільберта, а не в растровому порядку саме тому, що це тримає візуально схожі (просторово близькі) пікселі поруч у результуючому 1D-потоці даних, що допомагає ентропійним кодерам і алгоритмам квантування кольору ефективніше використовувати локальну кореляцію, ніж це зробив би растровий обхід.

Процедурна генерація й потокові світи. Ігри з відкритим світом, що стрімлять фрагменти рельєфу в пам'ять і назад під час руху гравця, часто використовують впорядкування за Гільбертом чи Мортоном для індексів фрагментів, щоб просторово близькі фрагменти були близькими й у черзі пріоритету стрімінгу, і в розкладці на диску — зменшуючи витрати на позиціонування й покращуючи точність попереднього завантаження.

Пов'язані статті