De Bruijnシーケンス
A上のすべての可能な長さ- N列 （すなわち、 連続したサブシーケンスのように）一度だけのサブストリングとして発生コンビナトリアル数学で、、サイズKのアルファベットA上の次数nのデBruijnグラフの配列が、環状配列です。このようなシーケンスはB （ k 、 n ）で示され、長さk nを持ちます。これは、 A上の長さnの個別のサブストリングの数でもあります。したがって、de Bruijnシーケンスは最適に短いです。 （k！）kn−1kn {\ displaystyle {\ dfrac {\ left（k！\ right）^ {k ^ {n-1}}} {k ^ {n}}}}の異なるde BruijnシーケンスB （ k 、 n ）。
シーケンスの名前は、オランダの数学者ニコラース・ゴベール・ド・ブルーインにちなんで付けられました。彼によると、1894年にカミーユ・フライ・サント・マリーによって、2つの要素を持つアルファベットの場合、上記の特性とともに各順序のde Bruijnシーケンスの存在が最初に証明されましたが、より大きなアルファベットへの一般化は元々 Tatyana van Aardenne-Ehrenfestと彼自身。
ほとんどのアプリケーションでは、 A = {0,1}。
歴史
de Bruijnシーケンスの最も初期の既知の例は、サンスクリット語の韻律に由来します。ここでは、ピンガラの作品以来、可能性のある長い音節と短い音節の各3音節パターンに名前が付けられています。 m 'は長い、長い、長い。これらの名前を覚えるために、ニーモニックyamātārājabhānasalagāmが使用されます。この名前では、それぞれの3音節パターンがその名前で始まります。オン、短い-短い-長いパターンを持つ「salagām」まで。このニーモニックは、バイナリ3タプルのde Bruijnシーケンスに相当し、古代のものではありませんが、少なくとも1869年にチャールズフィリップブラウンがサンスクリットの韻律について書いた本であり、「Pāṇiniによって書かれた古代の行」と見なされます。
1894年に、 A。deRivièreは、フランスの問題ジャーナルL'IntermédiairedesMathématiciensの問題で、すべてを含むゼロとサイズ2n {\ displaystyle 2 ^ {n}}の円形配置の存在に関する問題を提起しました。長さn {\ displaystyle n}の2n {\ displaystyle 2 ^ {n}}バイナリシーケンス。この問題は、同じ年にカミーユフライサントマリーによって22n-1-n {\ displaystyle 2 ^ {2 ^ {n-1} -n}}個の明確な解決策とともに（肯定的に）解決されました。 。これはほとんど忘れられており、Martin（1934）は、それらを構築するアルゴリズムにより、2の代わりに一般的なアルファベットサイズのそのようなサイクルの存在を証明しました。最後に、1944年にKees Posthumusがバイナリシーケンスのカウント22n-1-n {\ displaystyle 2 ^ {2 ^ {n-1} -n}}を推測したとき、de Bruijnは1946年に推測を証明しました。 -既知。
カールポッパーは、科学的発見の論理 （1934）でこれらのオブジェクトを独立して説明し、「最短のランダムなシーケンス」と呼びます。
例
- A = {0、1}をとると、2つの異なるB （2、3）があります：00010111と11101000、一方は他方の反転または否定です。
- 同じアルファベットの2048の可能性のあるB （2、5）のうち2つは、00000100011001010011101011011111と00000101001000111110111001101011です。
建設
de Bruijnシーケンスは、 kシンボルにわたるn次元のde Bruijnグラフのハミルトニアンパス（または、（ n − 1）次元のde Bruijnグラフのオイラーサイクル）を使用して構築できます。
別の構成では、長さがnで除算されるすべてのリンドン語を辞書式順序で連結します。
逆バロウズ-ウィーラー変換を使用して、辞書式順序で必要なリンドン語を生成できます。
De Bruijnシーケンスは、シフトレジスタを使用して、または有限体を介して構築することもできます。
de Bruijnグラフを使用した例
目標：Eulerian（ n − 1 = 4 − 1 = 3）3-D de Bruijnグラフサイクルを使用して、長さ24 = 16のB （2、4）de Bruijnシーケンスを構築します。
この3次元de Bruijnグラフの各エッジは、4桁のシーケンスに対応します。エッジが残す頂点にラベルを付ける3桁の後に、エッジにラベルを付けるものが続きます。 000から1とラベル付けされたエッジを横断すると、001に到達し、それによってde Bruijnシーケンス内のサブシーケンス0001の存在を示します。各エッジを1回だけトラバースするには、16の4桁シーケンスのそれぞれを1回だけ使用します。
たとえば、これらの頂点を通る次のオイラーパスをたどるとします。
000、000、001、011、111、111、110、101、011,110、100、001、010、101、010、100、000。これらは、長さkの出力シーケンスです。
0 0 0 0 _ 0 0 0 1 1 _ _ 0 0 1 1これは、次のde Bruijnシーケンスに対応します。
0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 18つの頂点は、次のようにシーケンスに表示されます。
{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のホイーラー変換は、文字列とその回転で構成される等価クラスのマルチセットを生成します。これらの文字列の等価クラスにはそれぞれ一意の最小要素としてリンドン語が含まれているため、逆バロウズ-ウィーラー変換を考慮してリンドン語のセットを生成できます。逆krowrows—ウィーラー変換をサイズkのアルファベットからなる単語wに対してkn-1回繰り返し実行すると（所望のde Bruijnシーケンスと同じ長さの単語が生成されるように）、結果は、長さがnで除算されるすべてのリンドン語のセットになります。これらのリンドン語を辞書式順序で配列すると、de BruijnシーケンスB（k、n）が生成され、これが辞書式順序での最初のde Bruijnシーケンスになります。次の方法を使用して、 標準の順列を使用して、逆バロウズ-ウィーラー変換を実行できます。
- 文字列wの文字を並べ替え、新しい文字列w 'を生成します
- wの文字列「位置ワットの文字列以上を、そしてW内の各文字の位置をマップする」順序を維持しながら、 ワットでその位置に。このプロセスは、標準順列を定義します。
- この順列をサイクル表記で記述します。最初に各サイクルの最小の位置を指定し、サイクルを昇順でソートします。
- 各サイクルで、各番号をその位置の文字列w 'の対応する文字に置き換えます。
- 各サイクルはリンドン語になり、辞書式順序で配置されているため、括弧を削除すると最初のde Bruijnシーケンスが生成されます。
たとえば、長さ24 = 16の最小のB（2,4）de Bruijnシーケンスを構築するには、アルファベット（ab）を8回繰り返してw = ababababababababを生成します。 wの文字をソートし、 w '= aaaaaaaabbbbbbbbを生成します。位置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に分かれるリンドン語であるため、括弧を削除するとB（2,4）= aaaabaabbababbbbになります。
アルゴリズム
次のPythonコードは、Frank RuskeyのCombinatorial Generationのアルゴリズムに基づいて、 kおよびnが与えられたde Bruijnシーケンスを計算します。
印刷する
00010111 aabacadbbcbdccddこれらのシーケンスは、サイクル内で「ラップアラウンド」すると理解されていることに注意してください。たとえば、最初のシーケンスにはこの方法で110と100が含まれます。
用途
このシーケンスは、「入力」キーを持たず、入力された最後のn桁を受け入れるPINのようなコードロックに対するブルートフォース攻撃を短縮するために使用できます。たとえば、4桁のコードのデジタルドアロックには、長さが10000のB （10、4）ソリューションがあります。したがって、最大10000 + 3 = 10003（ソリューションは周期的であるため）ロック。すべてのコードを個別に試すには、4×10000 = 40000を押す必要があります。
円形オブジェクト（ロボットの車輪など）の周りに書かれたde Bruijnシーケンスのシンボルを使用して、固定点に面したn個の連続したシンボルを調べることにより、その角度を特定できます。この角度エンコードの問題は、「回転ドラムの問題」として知られています。グレーコードは、同様の回転位置エンコードメカニズムとして使用できます。
De Bruijnサイクルは、神経系に対する刺激秩序の効果を調べる神経科学および心理学実験で一般的に使用され、機能的磁気共鳴画像法で使用するために特別に作成できます。
de Bruijnシーケンスは、ビット単位演算を使用して、ワード内の最下位セットビット（「右端1」）または最上位セットビット（「左端1」）のインデックスをすばやく見つけるために使用できます。 32ビットの符号なし整数から最下位ビットのインデックスを返す例を、ビット操作と乗算を使用して以下に示します。
vのLSBのインデックスはrに格納され、 vにビットが設定されていない場合、演算は0を返します。式の定数0x077CB531Uは、 B （2、5）シーケンス0000 0111 0111 1100 1011 0101 0011 0001（スペース明確にするために追加）。
f-fold de Bruijnシーケンス
Bruijnグラフ系列デF倍n進」長FKNのシーケンス{\ displaystyle FK ^は、{N}}長さのすべての可能な部分配列を含有するN正確Fように、概念のn進化de Bruijn配列の延長であります回。たとえば、n = 2 {\ displaystyle n = 2}の場合、巡回シーケンス11100010および11101000は2分割バイナリde Bruijnシーケンスです。二重のde Bruijnシーケンスの数、n = 1 {\ displaystyle n = 1}のNn {\ displaystyle N_ {n}}はN1 = 2 {\ displaystyle N_ {1} = 2}であり、他の既知の数はN2 = 5 {\ displaystyle N_ {2} = 5}、N3 = 72 {\ displaystyle N_ {3} = 72}、N4 = 43768 {\ displaystyle N_ {4} = 43768}。
デブルーイントーラス
de Bruijnトーラスは、すべてのk -ary m行n列の行列が正確に1回発生するという特性を持つトロイダル配列です。
このようなパターンは、回転エンコードについて上記で説明したのと同様の方法で、2次元の位置エンコードに使用できます。位置は、センサーに直接隣接するm行n列の行列を調べ、de Bruijnトーラス上の位置を計算することにより決定できます。
De Bruijnデコーディング
de Bruijnシーケンスまたはトーラス内の特定の一意のタプルまたは行列の位置を計算することは、de Bruijn Decoding Problemとして知られています。効率的なO（n log n）復号化アルゴリズムは、特別な再帰的に構築されたシーケンスに対して存在し、2次元の場合に拡張されます。 De Bruijnデコードは、たとえば、大きなシーケンスまたはトーラスが位置エンコードに使用される場合に重要です。
