De Bruijn sequence

本文是寫程式產生 De Bruijn sequence 的副產品,因此純為筆記性質,科普文可參考: 数学魔术:难倒数学家的表演

De Bruijn sequence B(k, n) 是一種 sequence,由 k 種不同符號組成,且其所有長度為 n 之連續子序列恰為 k 種符號組成長度為 n 的所有排列。 例如:00010111 即為一 B(2, 3) 序列,因其連續子序列(尾端循環至開頭) 000, 001, 010, 101, 011, 111, 110, 100 恰為所有由 {0, 1} 組成且長度 3 的序列。

若由 k 種符號組成之所有長度為 n 之序列表為有向圖中的頂點,則圖中有 k^n 個頂點, 若頂點 m 去掉第一個符號並在尾端添加一符號可得頂點 n,則有一有向邊由 m 指向 n,此即 De Bruijn graph。 例如:k = 2, n = 3 的圖中,頂點 010 有兩條對外的邊,分別指向 101 及 100。

在 De Bruijn graph 中之 Hamiltonian path 即為 De Bruijn sequence,下方左圖中紅色有向邊即為一組 Hamiltonian path, 圖中可見對應之 De Bruijn sequence 為 10111000,且此組 Hamiltonian path 等價於長度 2 的 De Bruijn graph 中的一組 Eulerian cycle, 下方右圖邊上標記的即為對應之順序。

k = 2, n = 3 k = 2, n = 2

k = 3(使用符號 0, 1, 2)的狀況同樣可畫出 De Bruijn graph,左圖中標記的 Hamiltonian path 為 102112200,右方同樣是等價的 Eulerian cycle。

k = 3, n = 2 k = 3, n = 1

應用:

假定有一個非零正數 x 以二進位表示,要找出最後一個 1 的位置,範例:
0100101000100000 <- 第 6 個位置為 1,所以輸出 5(計算 0-base 的位置,也可以想像成是算最後有幾個 0)
在這邊先假設n為機器上表示一個整數所使用的位元數,以 n = 32 來示範。
首先可以把題目簡化,假定x中只有一個 bit 為 1,如果 x 中有兩個以上的 bit 為 1,
可以利用 x &= (~x + 1) 來把最後一個 1 分離。(x &= -x 也可以,如果是二的補數表示法)
當分離出來之後,就有很多種計算法了,這邊就不考慮用組合語言的解法。
[...略...]
第六種是利用 de Bruijn sequence。
其實這方法跟第五種方法很像,也是設計一個 perfect hash function。
只是這方法免除了取餘數的運算,同時也只需要大小為 32 的 table。
hash function 是 (x * 0x077CB531) >> 27 其中的 0x077CB531 就是 de Bruijn sequence。
這方法對於 n 是二的次方數的機器都可以使用,至於 n 不是二的次方數的機器應該不多。
這方法的原理從兩個方面來看,第一個是x本身一定是二的次方數,
所以任何一個數字乘以 x,就相當於左移的運算。
而 de Bruijn sequence 的特殊之處,就是在於此序列中的任意連續五位元都是相異的。
五個位元總共有三十二種可能性,而至少要有三十二個位元才有可能包含所有三十二種可能性
(序列要想成頭尾相接的)
舉例:00010111就包含了 000, 001, 010, 101, 011, 111, 110, 100 這八種三位元的所有組合。
所以當 de Bruijn sequence 乘以 x 又右移27個位元的時候,就相當於是把 sequence 中的一組五位元子序列取出,
這保證不同的x一定會有不同的子序列,所以是一個很好的 hash 函數。
(32 位元的 de Bruijn sequence 有很多個,但是這方法要用的時候必須挑 00000 開頭的)
關於第六種方法的詳細研究可以參考下面這網址,
裡面還有說當一個數字有兩個 bit 為 1 的時候,怎樣可以快速找出來
http://supertech.csail.mit.edu/papers/debruijn.pdf
-- FRAXIS, [心得] Bit index和de Bruijn sequence

參考資料:

作者:En-Ran Zhou
建立:2014/02/10 修改 2014/02/11