Loading article…
組み合わせ論において、サイズk のアルファベットA上の次数nのde Bruijn 列とは、A上の可能なすべての長さn の文字列が部分文字列(すなわち、連続部分列)としてちょうど 1 回出現する巡回列のことです。このような列はB ( k , n )と表記され、長さはk nであり、これはA上の長さnの異なる文字列の数でもあります。これらの異なる文字列は、B ( k , n )の部分文字列として取られると、それぞれ異なる位置から始まらなければなりません。なぜなら、同じ位置から始まる部分文字列は異なるものではないからです。したがって、B ( k , n ) は少なくともk n個の記号を持たなければなりません。そして、 B ( k , n )はちょうどk n個の記号を持つので、de Bruijn 列は、長さnのすべての文字列を少なくとも 1 回含むという性質に関して最適に短い列となります。
個別の de Bruijn シーケンスB ( k , n )の数は次のとおりです。
バイナリアルファベットの場合、これは正の場合、次のシーケンスにつながる: 1, 1, 2, 16, 2048, 67108864... ( OEISのシーケンスA016031 )
これらの数列は、1946 年にそれらについて書いたオランダの数学者Nicolaas Govert de Bruijnにちなんで名付けられました。 [ 1 ]後に彼が書いたように、[ 2 ]上記の性質とともに各順序の de Bruijn 数列の存在は、2 つの要素を持つアルファベットの場合に、Camille Flye Sainte-Marie ( 1894 )によって最初に証明されました。より大きなアルファベットへの一般化は、 Tatyana van Aardenne-Ehrenfestとde Bruijn ( 1951 )によるものです。これらの数列を認識するオートマトンは、de Bruijn オートマトンと呼ばれます。
多くのアプリケーションでは、A = {0,1} です。
デ・ブルイン配列の最も古い既知の例はサンスクリット語の韻律学にあり、ピンガラの研究以来、長音節と短音節の可能な3音節パターンそれぞれに名前が付けられており、例えば短音節-長音節-長音節には「y」、長音節-長音節-長音節には「m」が付けられています。これらの名前を覚えるために、yamātārājabhānasalagāmという記憶術が使われ、それぞれの3音節パターンがその名前から始まり、「yamātā」は短音節-長音節-長音節のパターン、「mātārā」は長音節-長音節-長音節のパターン、といった具合に続き、「salagām」は短音節-短音節-長音節のパターンになります。この記憶術は、バイナリ 3 タプルの de Bruijn シーケンスに相当し、その起源は不明ですが、少なくとも、チャールズ フィリップ ブラウンの 1869 年のサンスクリット語韻律に関する著書で言及され、「パーニニによって書かれた古代の詩句」とみなされているのと同時期に存在しています。[ 3 ]
1894年、A. ド・リヴィエールは、フランスの問題雑誌『L'Intermédiaire des Mathématiciens 』のある号で、サイズが のゼロとイチの円形配列の存在について問題を提起した。すべてを含む長さのバイナリシーケンス問題は（肯定的に）解決され、同年、カミーユ・フライ・サント＝マリーによって異なる解が提案された。[ 2 ]これはほとんど忘れ去られていたが、マーティン（1934）は、アルファベットのサイズを2ではなく一般化した場合のそのようなサイクルの存在を、それらを構成するアルゴリズムとともに証明した。最後に、1944年にキース・ポストゥムスが 、その数を予想したとき、バイナリシーケンスについては、デ・ブルインが1946年に予想を証明し、それによってこの問題は広く知られるようになった。[ 2 ]
カール・ポパーは、著書『科学的発見の論理』 （1934年）の中で、これらの対象を独自に記述し、「最短のランダムのような数列」と呼んでいる。[ 4 ]
デ・ブルイン数列は、 k個の記号上のn次元デ・ブルイングラフのハミルトン経路（または同等に、( n - 1)次元デ・ブルイングラフのオイラー閉路）を取ることによって構築できる。[ 5 ]
別の構成としては、長さがnを割り切るすべてのLyndon の単語を辞書順に連結する方法がある。[ 6 ]
逆バロウズ・ウィーラー変換を使用すると、必要なリンドン語を辞書順で生成できます。[ 7 ]
デ・ブルイン数列は、シフトレジスタ[ 8 ]または有限体[ 9 ]を用いて構築することもできる。
目標:オイラー ( n − 1 = 4 − 1 = 3) 3 次元 de Bruijn グラフ サイクルを使用して、長さ 2 4 = 16 のB (2, 4) de Bruijn シーケンスを構築します。
この3次元デ・ブルイングラフの各辺は、4桁の数字列に対応しています。3桁は辺が出発する頂点の番号、1桁は辺の番号です。例えば、000から1の番号の辺をたどると001に到達し、デ・ブルイン数列に部分列0001が存在することが示されます。各辺をちょうど1回たどるということは、16個の4桁の数字列をそれぞれちょうど1回ずつ使用することになります。
例えば、これらの頂点を通る以下のオイラー経路をたどると仮定します。
これらは長さkの出力シーケンスです。
これは、以下のデ・ブルイン数列に対応します。
8つの頂点は、以下の順序で出現します。
{0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ...…そして、出発点に戻ります。8つの3桁の数字列（8つの頂点に対応）はそれぞれちょうど2回出現し、16の4桁の数字列（16の辺に対応）はそれぞれちょうど1回出現します。
数学的には、単語wに対する逆Burrows-Wheeler 変換は、文字列とその回転からなる同値類の多重集合を生成します。 [ 7 ]これらの文字列の同値類はそれぞれ、一意の最小要素としてLyndon 単語を含んでいるため、逆 Burrows-Wheeler 変換は Lyndon 単語の集合を生成するものと考えることができます。サイズkのアルファベットをk n −1回繰り返した単語wに対して逆 Burrows-Wheeler 変換を実行すると(目的の de Bruijn シーケンスと同じ長さの単語が生成されるように)、結果として長さがnを割り切るすべての Lyndon 単語の集合が得られることが示せます。したがって、これらの Lyndon 単語を辞書順に並べると de Bruijn シーケンスB ( k , n ) が得られ、これが辞書順の最初の de Bruijn シーケンスになります。以下の方法を用いると、標準的な置換を用いて逆バロウズ・ウィーラー変換を実行できます。
例えば、長さ 2 4 = 16 の最小のB (2,4) デ・ブルイン数列を構成するには、アルファベット (ab) を 8 回繰り返してw =ababababababababを得ます。w の文字をソートして、 w ′ =aaaaaaabbbbbbbb を得ます。図のようにw ′ をwの上に配置し、線を引いてw ′の各要素を対応するwの要素にマッピングします。順列のサイクルを読み取れるように、図のように列に番号を付けます。
左から順に、標準順列表記のサイクルは次のようになります。(1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16)。(標準順列)
次に、各数字をその列のw ′の対応する文字に置き換えると、次のようになります。 (a)(aaab)(aabb)(ab)(abbb)(b)。
これらは、長さが 4 で割り切れるすべての Lyndon 単語を辞書順に並べたものなので、括弧を削除するとB (2,4) = aaaabaabbababbbbとなります。
以下のPythonコードは、 Kとnが与えられた場合に、 Frank RuskeyのCombinatorial Generationのアルゴリズムに基づいてde Bruijn数列を計算します。[ 10 ]
from typing import Iterable , Anydef de_bruijn ( k : Iterable [ str ] | int , n : int ) -> str : """アルファベット k と長さ n の部分列の de Bruijn シーケンス。 長さが n を割り切る Lyndon 単語の連結から生成されます。 """ # 2 種類のアルファベット入力: 整数は、アルファベットとして整数のリストに展開されます。if isinstance ( k , int ): alphabet = list ( map ( str , range ( k ))) else : # 任意のリストがそのまま使用されますalphabet = k k = len ( k )バッファ= [ 0 ] * nシーケンス= []# バッファ内のリンドン語を反復処理する再帰メソッド。def generate ( word_len , period ): if word_len >= n : if n % period == 0 : # このリンドン語は n を割り切るので、末尾に結合します。sequence . extend ( buffer [: period ])# n より長い単語は n を割り切ることができないため、 # この場合はそれ以上再帰する必要はありません。return# 現在の単語を周期的に拡張します。# 最初のエントリを 0 で初期化する場合を除き、 #拡張されたシーケンスが辞書的に最小でないか、# または周期的であるため、これだけでは新しい Lyndon 単語は生成されません。 buffer [ word_len ] = 0 if word_len == 0 else buffer [ word_len - period ] generate ( word_len + 1 , period )# 単語の末尾でアルファベットを順に処理し、古い周期性を破ります。while buffer [ word_len ] + 1 < k : buffer [ word_len ] += 1 generate ( word_len + 1 , word_len + 1 )生成（0、1 ）return "" . join ( alphabet [ i ] for i in sequence )print ( de_bruijn ( 2 , 3 )) print ( de_bruijn ( "abcd" , 2 ))印刷される
00010111 aabacadbbcbdccdd
これらの数列は、循環的に「折り返される」ように構成されていることに注意してください。例えば、最初の数列は、このように110と100を含んでいます。
デ・ブルイン・サイクルは、神経系に対する刺激順序の影響を調べる神経科学や心理学の実験で一般的に使用されており、[ 11 ]機能的磁気共鳴画像法で使用するために特別に設計することもできます。[ 12 ]
円形の物体（ロボットの車輪など）の周りに書かれたデ・ブルイン数列のシンボルは、固定点に面するn個の連続するシンボルを調べることで、その角度を識別するために使用できます。この角度符号化問題は、「回転ドラム問題」として知られています。 [ 13 ]グレイコードは、同様の回転位置符号化メカニズムとして使用でき、これはロータリーエンコーダでよく見られる方法です。
デ・ブルイン数列は、ビット演算と乗算を使用して、ワード内の最下位セットビット（「右端の1」）または最上位セットビット（「左端の1」）のインデックスを素早く見つけるために使用できます。 [ 14 ]次の例では、デ・ブルイン数列を使用して、32ビット符号なし整数内の最下位セットビットのインデックス（末尾の「0」ビットの数を数えることに相当）を決定します。
uint8_t lowestBitIndex ( uint32_t v ) { static const uint8_t BitPositionLookup [ 32 ] = // ハッシュテーブル{ 0 , 1 , 28 , 2 , 29 , 14 , 24 , 3 , 30 , 22 , 20 , 15 , 25 , 17 , 4 , 8 , 31 , 27 , 13 , 23 , 21 , 19 , 16 , 7 , 26 , 12 , 18 , 6 , 11 , 5 , 10 , 9 }; return BitPositionLookup [(( uint32_t )(( v & - v ) * 0x077CB531U )) >> 27 ]; }この関数は、 vlowestBitIndex()内の最下位ビットがセットされているインデックスを返します。v にセットされているビットがない場合はゼロを返します。式中の定数 0x077CB531U は、B (2, 5) シーケンス 0000 0111 0111 1100 1011 0101 0011 0001 (スペースは分かりやすくするために追加) です。この操作では、セットされている最下位ビット以外のすべてのビットがゼロになり、2 のべき乗である新しい値が生成されます。この 2 のべき乗は、(2 32 を法とする算術演算で) de Bruijn シーケンスと乗算され、5 つの MSB のビットシーケンスが各 2 のべき乗ごとに一意となる 32 ビットの積が生成されます。5 つの MSB は LSB の位置にシフトされ、[0, 31] の範囲のハッシュコードが生成され、これがハッシュテーブルBitPositionLookupのインデックスとして使用されます。選択されたハッシュテーブル値は、 v内の最下位セットビットのビットインデックスです。 (v & -v)
次の例は、32ビット符号なし整数において、最上位ビットがセットされている位置のインデックスを決定します。
uint32_t keepHighestBit ( uint32_t n ) { n |= ( n >> 1 ); n |= ( n >> 2 ); n |= ( n >> 4 ); n |= ( n >> 8 ); n |= ( n >> 16 ); return n - ( n >> 1 ); }uint8_t highestBitIndex ( uint32_t v ) { static const uint8_t BitPositionLookup [ 32 ] = { // ハッシュテーブル0 , 1 , 16 , 2 , 29 , 17 , 3 , 22 , 30 , 20 , 18 , 11 , 13 , 4 , 7 , 23 , 31 , 15 , 28 , 21 , 19 , 10 , 12 , 6 , 14 , 27 , 9 , 5 , 26 , 8 , 25 , 24 , }; return BitPositionLookup [( keepHighestBit ( v ) * 0x06EB14F9U ) >> 27 ]; }上記の例では、代替のデ・ブルインシーケンス（0x06EB14F9U）が使用され、それに伴い配列値の順序が変更されています。この特定のデ・ブルインシーケンスの選択は任意ですが、ハッシュテーブルの値は選択されたデ・ブルインシーケンスに一致するように順序付けられている必要があります。このkeepHighestBit()関数は、最上位ビットを除くすべてのビットをゼロにすることで、2のべき乗となる値を生成します。この値は、前の例と同様に処理されます。
デ・ブルイン数列は、「エンター」キーがなく、最後に入力されたn桁の数字を受け入れるPINコードのようなコードロックに対する総当たり攻撃を短縮するために使用できます。たとえば、 4桁のコード（各桁に0から9までの10通りの選択肢がある）を持つデジタルドアロックの場合、 B (10, 4)通りの解が存在し、その長さは 10,000 。したがって、最大でも10 000 + 3 =ロックを開けるには10 003 回（解は循環的であるため）の押下が必要ですが、すべてのコードを個別に試すと4 ×10,000 =4万台の印刷機。
多重デブルインシーケンス: サイズqのアルファベット上のすべてのk-merがちょうどm回含まれる循環または線形シーケンス。[ 16 ]例えば、バイナリアルファベット{0, 1}では、循環シーケンス(00010111)と線形シーケンス000101110はそれぞれ、2-mer 00、01、10、11のインスタンスを2つずつ含んでいます。多重度m=2、アルファベットサイズq=2、ワードサイズk=1の場合のシーケンスは2つあります: (0011)と(0101)、k=2の場合は5つです。
デ・ブルイン・トーラスとは、 k項のm × n行列が必ず一度だけ出現するという性質を持つトーラス状の配列である。
このようなパターンは、回転符号化について上述した方法と同様の方法で、2次元位置符号化に利用できる。位置は、センサに隣接するm × n行列を調べ、デ・ブルイン・トーラス上のその位置を計算することによって決定できる。
デ・ブルイン列またはトーラス内の特定の一意なタプルまたは行列の位置を計算することは、デ・ブルイン復号問題として知られています。効率的な再帰的に構築された特殊なシーケンス[ 17 ]の復号アルゴリズムが存在し、2次元の場合にも拡張されています[ 18 ] 。デ・ブルイン復号は、例えば、位置符号化に大規模なシーケンスやトーラスが使用される場合に興味深いものです。
{{cite journal}}: CS1 maint: postscript (リンク)