11.6 距離標籤 Distance Labellings

最短距離資料結構 Distance Oracles 有一個非常極端的形式，那就是距離標籤：透過預處理，給予圖上的每一個點 v 一個二元字串 L(v)，作為標籤 (labels)。這個標籤可以儲存任何的訊息。但是，當我們想要知道某兩個點 u 和 v 之間的最短距離的時候，只能依靠 L(u) 和 L(v) 這兩個標籤的資訊，就必須要推算出最短距離。

昨天說明的 Agarwal-Godfrey Distance Oracle 滿足上述 (Approximate) Distance Labeling 的條件：對於每個節點，我們只要在標籤寫下與之有關的所有距離即可。查詢的時候由於已經從標籤上得知 dist(u, ℓ(u))、 dist(v, ℓ(u))、 dist(u, ℓ(v))、 dist(v, ℓ(v)) 這幾個數值，可以直接算出近似距離。

這個距離標籤有什麼好處呢？最直接的好處就是，經過預處理以後，我們不需要記住整張圖、甚至在查詢的時候也只需要存取兩張標籤，對於常見資料庫的存取負擔是極小的。

以色列魏茨曼科學研究學院的教授 David Peleg 在 1999 年提出了 Distance Labelling 的概念。
在 Peleg 提出的論文 中利用了樹覆蓋的概念，來得出 O(log n)-近似距離標籤。我們今天會先介紹大方向，然後明天繼續把細節補完：

對於每一個點 v，我們將它的「距離 L 以內」的 BFS 樹刻劃出來。選取 L=1, 2, 4, 8, ...，我們就會得到 log n 棵樹。總共有 n log n 棵，每一層 L 有 n 棵 BFS 樹。對於每一層距離 L，同一個點可能出現在多棵 BFS 樹裡面。如果我們可以把這些樹稍加合併，使得每一個點只出現在至多 O(log n) 棵樹上，而且同時不犧牲太多距離 (原本對於某一層 L，樹上任意兩點的距離不超過 2L，但是合併一些樹以後，樹上任何兩點的距離可能會超過 2L)。在我們的例子中，這個距離會被犧牲 log n倍。

這麼一來，我們能對每一個節點定義他的距離標籤，這個標籤大小是 O(log^3 n)-bits 的：
有 log n 個不同的 L 數值
每一個不同的 L，我們記錄下這個點出現所在的 "被合併過的BFS樹" 的編號，對於一個固定的 L，最多有 O(log n) 個不同的編號，因為出現在至多 O(log n) 棵樹上。
每一棵樹的編號是一個 O(log n)-bits 的整數，因為合併前至多只有 n log n 棵樹，因此合併後也只有這麼多，我們可以將他們重新編號。

要怎麼估計 u 和 v 的最短距離呢？很簡單，把它們的距離標籤拿出來看看：對於每一層 L，檢查他們所出現的那些樹的編號。如果 u 和 v 出現在同一棵樹上，代表他們距離不超過 (log n)L。如果 u 和 v 沒有出現在同一棵樹，那麼代表他們的最短距離一定超過 L。

剩下什麼細節呢？剩下把 BFS 樹合併的方法。方法單純，而且與氣球的概念非常類似。這個我們明天繼續~