“De Bruijn sequence”的意思、由来-开放百科全书

In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by {{nowrap|B(k, n)}} and has length kⁿ, which is also the number of distinct substrings of length n on A; de Bruijn sequences are therefore optimally short. There are

distinct de Bruijn sequences {{nowrap|B(k, n)}}.

The sequences are named after the Dutch mathematician Nicolaas Govert de Bruijn. According to him,^[1] the existence of de Bruijn sequences for each order together with the above properties were first proved, for the case of alphabets with two elements, by Camille Flye Sainte-Marie in 1894,^[2] whereas the generalization to larger alphabets is originally due to Tatyana van Aardenne-Ehrenfest and himself.

History

The earliest known example of a de Bruijn sequence comes from Sanskrit prosody where, since the work of Pingala, each possible three-syllable pattern of long and short syllables is given a name, such as 'y' for short–long–long and 'm' for long–long–long. To remember these names, the mnemonic yamātārājabhānasalagām is used, in which each three-syllable pattern occurs starting at its name: 'yamātā' has a short–long–long pattern, 'mātārā' has a long–long–long pattern, and so on, until 'salagām' which has a short–short–long pattern. This mnemonic, equivalent to a de Bruijn sequence on binary 3-tuples, is of unknown antiquity, but is at least as old as Charles Philip Brown's 1869 book on Sanskrit prosody that mentions it and considers it "an ancient line, written by Pāṇini".^[3]^[4]^[5]^[6]^[7]

In 1894, A. de Rivière raised the question in an issue of the French problem journal L'Intermédiaire des Mathématiciens, of the existence of a circular arrangement of zeroes and ones of size

that contains all

binary sequences of length

. The problem was solved (in the affirmative), along with the count of

distinct solutions, by Camille Flye Sainte-Marie in the same year.^[1] This was largely forgotten, and {{harvtxt|Martin|1934}} proved the existence of such cycles for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 Kees Posthumus conjectured the count

for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well-known.^[1]

Examples

Construction

The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph).^[9]

An alternative construction involves concatenating together, in lexicographic order, all the Lyndon words whose length divides n.^[10]

An inverse Burrows—Wheeler transform can be used to generate the required Lyndon words in lexicographic order.^[11]

De Bruijn sequences can also be constructed using shift registers^[12] or via finite fields.^[13]

Example using de Bruijn graph

Goal: to construct a B(2, 4) de Bruijn sequence of length 2⁴ = 16 using Eulerian (n − 1 = 4 − 1 = 3) 3-D de Bruijn graph cycle.

Each edge in this 3-dimensional de Bruijn graph corresponds to a sequence of four digits: the three digits that label the vertex that the edge is leaving followed by the one that labels the edge. If one traverses the edge labeled 1 from 000, one arrives at 001, thereby indicating the presence of the subsequence 0001 in the de Bruijn sequence. To traverse each edge exactly once is to use each of the 16 four-digit sequences exactly once.

For example, suppose we follow the following Eulerian path through these vertices:

...and then we return to the starting point. Each of the eight 3-digit sequences (corresponding to the eight vertices) appears exactly twice, and each of the sixteen 4-digit sequences (corresponding to the 16 edges) appears exactly once.

Example using inverse Burrows—Wheeler transform

Mathematically, an inverse Burrows—Wheeler transform on a word w generates a multi-set of equivalence classes consisting of strings and their rotations.^[11] These equivalence classes of strings each contain a Lyndon word as a unique minimum element, so the inverse Burrows—Wheeler transform can be considered to generate a set of Lyndon words. It can be shown that if we perform the inverse Burrows—Wheeler transform on a word w consisting of the size-k alphabet repeated k^n-1 times (so that it will produce a word the same length as the desired de Bruijn sequence), then the result will be the set of all Lyndon words whose length divides n. It follows that arranging these Lyndon words in lexicographic order will yield a de Bruijn sequence B(k,n), and that this will be the first de Bruijn sequence in lexicographic order. The following method can be used to perform the inverse Burrows—Wheeler transform, using its standard permutation:

For example, to construct the smallest B(2,4) de Bruijn sequence of length 2⁴ = 16, repeat the alphabet (ab) 8 times yielding w=abababababababab. Sort the characters in w, yielding w'=aaaaaaaabbbbbbbb. Position w' above w as shown, and map each element in w' to the corresponding element in w by drawing a line. Number the columns as shown so we can read the cycles of the permutation:

Starting from the left, the cycles are: (1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16).

Then, replacing each number by the corresponding letter in w' from that column yields: (a)(aaab)(aabb)(ab)(abbb)(b).

These are all of the Lyndon words whose length divides 4, in lexicographic order, so dropping the parentheses gives B(2,4) = aaaabaabbababbbb.

Algorithm

The following Python code calculates a de Bruijn sequence, given k and n, based on an algorithm from Frank Ruskey's Combinatorial Generation.^[14]

Note that these sequences are understood to "wrap around" in a cycle. For example, the first sequence contains 110 and 100 in this fashion.

Uses

The sequence can be used to shorten a brute-force attack on a PIN-like code lock that does not have an "enter" key and accepts the last n digits entered. For example, a digital door lock with a 4-digit code would have B (10, 4) solutions, with length {{val|10000}}. Therefore, only at most {{nowrap|{{val|10000}} + 3 {{=}} {{val|10003}}}} (as the solutions are cyclic) presses are needed to open the lock. Trying all codes separately would require {{nowrap|4 × {{val|10000}} {{=}} {{val|40000}}}} presses.

The symbols of a de Bruijn sequence written around a circular object (such as a wheel of a robot) can be used to identify its angle by examining the n consecutive symbols facing a fixed point. This angle-encoding problem is known as the "rotating drum problem".^[15] Gray codes can be used as similar rotary positional encoding mechanisms.

De Bruijn cycles are of general use in neuroscience and psychology experiments that examine the effect of stimulus order upon neural systems,^[16] and can be specially crafted for use with functional magnetic resonance imaging.^[17]

A de Bruijn sequence can be used to quickly find the index of the least significant set bit ("right-most 1") or the most significant set bit ("left-most 1") in a word using bitwise operations.^[18]^[19] An example of returning the index of the least significant bit from a 32 bit unsigned integer is given below using bit manipulation and multiplication.

The index of the LSB in v is stored in r and if v has no set bits the operation returns 0. The constant, 0x077CB531U, in the expression is the B (2, 5) sequence 0000 0111 0111 1100 1011 0101 0011 0001 (spaces added for clarity).

f-fold de Bruijn sequences

f-fold n-ary de Bruijn sequence' is an extension of the notion n-ary de Bruijn sequence, such that the sequence of the length

contains every possible subsequence of the length n exactly f times. For example, for

the cyclic sequences 11100010 and 11101000 are two-fold binary de Bruijn sequences. The number of two-fold de Bruijn sequences,

for

, the other known numbers^[20] are

, and

De Bruijn torus

A de Bruijn torus is a toroidal array with the property that every k-ary m-by-n matrix occurs exactly once.

Such a pattern can be used for two-dimensional positional encoding in a fashion analogous to that described above for rotary encoding. Position can be determined by examining the m-by-n matrix directly adjacent to the sensor, and calculating its position on the de Bruijn torus.

De Bruijn decoding

Computing the position of a particular unique tuple or matrix in a de Bruijn sequence or torus is known as the de Bruijn Decoding Problem. Efficient {{nowrap|O(n log n)}} decoding algorithms exist for special, recursively constructed sequences^[21] and extend to the two dimensional case.^[22] De Bruijn decoding is of interest, e.g., in cases where large sequences or tori are used for positional encoding.

See also

Notes

1. ^¹²{{harvtxt|de Bruijn|1975}}.
2. ^{{cite journal |author-last=Flye Sainte-Marie |author-first=Camille |journal=L'Intermédiaire des Mathématiciens |pages=107–110 |title=Solution to question nr. 48 |volume=1 |date=1894}}
3. ^{{cite |author-first=C. P. |author-last=Brown |author-link=C. P. Brown |date=1869 |title=Sanskrit Prosody and Numerical Symbols Explained |url=https://archive.org/stream/sanskritprosody00browgoog#page/n44/mode/2up |page=28}}
4. ^{{cite journal |author-first=Subhash |author-last=Kak |date=2000 |title=Yamātārājabhānasalagāṃ an interesting combinatoric sūtra |url=http://202.41.82.144/rawdataupload/upload/insa/INSA_2/200059d2_123.pdf |dead-url=yes |archive-url=https://web.archive.org/web/20141029120230/http://202.41.82.144/rawdataupload/upload/insa/INSA_2/200059d2_123.pdf |archive-date=2014-10-29 |journal=Indian Journal of History of Science |volume=35 |issue=2 |pages=123–127}}
5. ^{{cite journal |author-first=Rachel W. |author-last=Hall |url=http://www.sju.edu/~rhall/mathforpoets.pdf |title=Math for poets and drummers |journal=Math Horizons |volume=15 |date=2008 |pages=10–11}}
6. ^{{Cite book |date=2006 |title=The Art of Computer Programming, Fascicle 4: Generating All Trees – History of Combinatorial Generation |author-first=Donald Ervin |author-last=Knuth |author-link=Donald Ervin Knuth |publisher=Addison–Wesley |isbn=978-0-321-33570-8 |page=50 |url=https://books.google.com/books?id=56LNfE2QGtYC&pg=PA50}}
7. ^{{citation |author-first=Sherman K. |author-last=Stein |author-link= Sherman K. Stein |contribution=Yamátárájabhánasalagám |date=1963 |title=The Man-made Universe: An Introduction to the Spirit of Mathematics |pages=110–118}}. Reprinted in Wardhaugh, Benjamin, ed. (2012), A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing, Princeton University Press, pp. 139–144.
8. ^{{cite book |date=2002 |orig-year=1934 |title=The logic of scientific discovery |author-first=Karl |author-last=Popper |author-link=Karl Popper |publisher=Routledge |isbn=978-0-415-27843-0 |page=294 |url=https://books.google.com/books?id=0a5bLBbe_dMC&pg=PA295&cd=1#v=onepage&q=1111000010011010}}
9. ^{{cite book |title=Stream Ciphers |author-first=Andreas |author-last=Klein |publisher=Springer |date=2013 |isbn=978-1-44715079-4 |page=59 |url=https://books.google.com/books?id=GYpEAAAAQBAJ&pg=PA59}}
10. ^According to {{harvtxt|Berstel|Perrin|2007}}, the sequence generated in this way was first described (with a different generation method) by {{harvtxt|Martin|1934}}, and the connection between it and Lyndon words was observed by {{harvtxt|Fredricksen|Maiorana|1978}}.
11. ^¹{{cite web |url=http://www.macs.hw.ac.uk/~markl/Higgins.pdf |title=Burrows-Wheeler transforms and de Bruijn words |author-last=Higgins |author-first=Peter |date=November 2012 |access-date=2017-02-11}}
12. ^{{cite book |title=Algebraic Shift Register Sequences |author-first1=Mark |author-last1=Goresky |author-first2=Andrew |author-last2=Klapper |publisher=Cambridge University Press |date=2012 |isbn=978-1-10701499-2 |pages=174–175 |url=https://books.google.com/books?id=sd9AqHeeHh4C&pg=PA174 |contribution=8.2.5 Shift register generation of de Bruijn sequences}}
13. ^{{cite journal |author-last=Ralston |author-first=Anthony |doi=10.2307/2690079 |issue=3 |journal=Mathematics Magazine |mr=653429 |pages=131–143 |title=de Bruijn sequences—a model example of the interaction of discrete mathematics and computer science |volume=55 |date=1982}}. (NB. See in particular "the finite field approach", pp. 136–139.)
14. ^{{cite web |title=De Bruijn sequences |url=https://git.sagemath.org/sage.git/tree/src/sage/combinat/debruijn_sequence.pyx |work=Sage |access-date=2016-11-03}}
15. ^{{cite book |title=A Course in Combinatorics |author-first1=J. H. |author-last1=van Lint |author-first2=Richard Michael |author-last2=Wilson |publisher=Cambridge University Press |date=2001 |isbn=978-0-52100601-9 |page=71 |url=https://books.google.com/books?id=5l5ps2JkyT0C&pg=PA71}}
16. ^G. K. Aguirre, M. G. Mattar, L. Magis-Weinberg. (2011) {{cite web |url=https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn |title=de Bruijn cycles for neural decoding}}. NeuroImage 56: 1293–1300
17. ^{{cite web |url=https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn_software |title=De Bruijn cycle generator}}
18. ^{{cite web |url=http://graphics.stanford.edu/~seander/bithacks.html |title=Bit Twiddling Hacks |author-last=Anderson |author-first=Sean Eron |date=1997–2009 |publisher=Stanford University |access-date=2009-02-12}}
19. ^{{cite web |url=http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.html |title=Computing Trailing Zeros HOWTO |author-last=Busch |author-first=Philip |date=2009 |access-date=2015-01-29}}
20. ^{{harvtxt|Osipov |2016}}.
21. ^{{harvtxt|Tuliani |2001}}.
22. ^{{harvtxt|Hurlbert|Isaak|1993}}.