De Bruijn sequence

De Bruijn sequence
A diagram showing the De Bruijn sequence where k=2 and n=2

In combinatorial mathematics, a k-ary De Bruijn sequence B(kn) of order n, named after the Dutch mathematician Nicolaas Govert de Bruijn, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once.

Each B(kn) has length kn.

There are  k! k (n − 1)  kn  distinct De Bruijn sequences B(kn).

According to De Bruijn himself,[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, whereas the generalization to larger alphabets is originally due to Tanja van Ardenne-Ehrenfest and himself.

Contents

History

The earliest known example of the De Bruijn sequence comes in Sanskrit prosody. The mnemonic yamātārājabhānasalagā was invented by Sanskrit prosodists to memorize the names of three-letter patterns as per the naming convention for three-letter sequences of long and short letters in Pingala's Chandah Shaastra (c. 200 BC). Denoting a long letter as L and short as S, this mnemonic corresponds to the sequence SLLLSLSSSL. By allowing wrapping around, the last two letters can be dropped from the mnemonic to give the circular mnemonic yamātārājabhānasa. The corresponding sequence is SLLLSLSS which is a B(2, 3) sequence for A = {S, L}.[2][3]

Though the name De Bruijn is attached to these sequences due to his proof of K. Posthumus' conjecture in 1946, in 1975 he acknowledged that priority in this proof belonged to C. Flye Sainte-Marie, who had independently published it in 1894 after the question had been raised in print by A. de Riviere that same year. De Bruijn notes that the problem was also examined in 1934 and again independently in 1944.[1]

Karl Popper independently describes these objects in his The Logic of Scientific Discovery, calling them "shortest random-like sequences".[4]

Examples

  • Taking A = {0, 1}, there are two distinct B(2, 3): 00010111 and 11101000, one being the reverse and/or negation of the other.
  • Two of the 2048 possible B(2, 5) in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011.

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, a Eulerian cycle of a (n − 1)-dimensional De Bruijn graph), or via finite fields.

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

Example

A De Bruijn graph. Every four-digit sequence occurs exactly once if one traverses every edge exactly once and returns to one's starting point (an Eulerian cycle). Every three-digit sequence occurs exactly once if one visits every node exactly once (a Hamiltonian path).

Goal: to construct a B(2, 4) De Bruijn sequence of length 24 = 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 nodes:

000, 000, 001, 011, 111, 111, 110, 101, 011,
110, 100, 001, 010, 101, 010, 100, 000.

These are the output sequences of length k:

0 0 0 0
_ 0 0 0 1
_ _ 0 0 1 1

This corresponds to the following De Bruijn sequence:

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

The eight vertices appear in the sequence in the following way:

      {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 ...

...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.

Algorithm

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

 de_bruijn(k, n):
    """De Bruijn Sequence for alphabet size k 
    and subsequences of length n."""
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1): sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1,1)
    return sequence
 
print(de_bruijn(2, 3))

which prints

[0, 0, 0, 1, 0, 1, 1, 1]

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 10,000. Therefore, only at most 10,000 + 3 = 10,003 (as the solutions are cyclic) presses are needed to open the lock. Trying all codes separately would require 4 × 10,000 = 40,000 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. 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,[7] and can be specially crafted for use with functional magnetic resonance imaging.[8]

A De Bruijn sequence can be used to quickly find the first or last bit in a word.[9][10]

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. (It is not necessary that the array be expressed toroidally; the array can be mapped into a 2-dimensional array. Because it is toroidal it "wraps around" on all 4 sides.)

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 O(n log n) decoding algorithms exists for special, recursively constructed sequences[11] and extend to the two dimensional case.[12] De Bruijn decoding is of interest, e.g., in cases where large sequences or tori are used for positional encoding.

See also

Notes

  1. ^ a b De Bruijn (1975).
  2. ^ Rachel W. Hall. Math for poets and drummers. Math Horizons 15 (2008) 10-11.
  3. ^ Donald Ervin Knuth (2006). The Art of Computer Programming, Fascicle 4: Generating All Trees -- History of Combinatorial Generation. Addison-Wesley. p. 50. ISBN 9780321335708. http://books.google.com/?id=56LNfE2QGtYC&pg=PA50&dq=Pingala 
  4. ^ Karl Popper (2002). The logic of scientific discovery. Routledge. p. 294. ISBN 9780415278430. http://books.google.com/?id=0a5bLBbe_dMC&pg=PA295&cd=1#v=onepage&q=1111000010011010 
  5. ^ According to Berstel & Perrin (2007), the sequence generated in this way was first described (with a different generation method) by Martin (1934), and the connection between it and Lyndon words was observed by Fredricksen & Maiorana (1978).
  6. ^ "De Bruijn sequences". Sage. http://hg.sagemath.org/sage-main/file/9e29a3d84c48/sage/combinat/debruijn_sequence.pyx. Retrieved 12 November 2011. 
  7. ^ "De Bruijn cycles for neural decoding". http://cfn.upenn.edu/aguirre/wiki/public:de_bruijn. 
  8. ^ "Software for creation of "path-guided" de Bruijn cycles". http://cfn.upenn.edu/aguirre/wiki/public:de_bruijn_software. 
  9. ^ Anderson, Sean Eron (1997-2009). "Bit Twiddling Hacks". Stanford University. http://graphics.stanford.edu/~seander/bithacks.html. Retrieved 2009-02-12. 
  10. ^ Busch, Philip (2009). "Computing Trailing Zeros HOWTO". http://www.0xe3.com/text/ntz/. Retrieved 2009-05-06. 
  11. ^ Tuliani (2001).
  12. ^ Hurlbert & Isaak (1993).

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Sequence assembly — In bioinformatics, sequence assembly refers to aligning and merging fragments of a much longer DNA sequence in order to reconstruct the original sequence. This is needed as DNA sequencing technology cannot read whole genomes in one go, but rather …   Wikipedia

  • De Bruijn graph — In graph theory, an n dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length n sequences of the given symbols; the same symbol may… …   Wikipedia

  • Nicolaas Govert de Bruijn — Born 9 July 1918 (1918 07 09) (age 93) …   Wikipedia

  • De Bruijn — is a Dutch surname. It may refer to: Chantal de Bruijn Cornelis de Bruijn, Dutch artist and traveler Daniëlle de Bruijn Inge de Bruijn, Dutch swimmer Nicolaas Govert de Bruijn, Dutch mathematician Maarten de Bruijn Nick de Bruijn Pi de Bruijn In… …   Wikipedia

  • Nicolaas Govert de Bruijn — Pour les articles homonymes, voir De Bruijn. De Bruijn à Oberwolfach, dans les années 1960 Nicolaas Govert de Bruijn (né le 9 juillet 1918) est un mathématicien …   Wikipédia en Français

  • De Bruijn torus — A De Bruijn torus. Each 2 by 2 binary matrix can be found within it exactly once. In combinatorial mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn, is an array of symbols from an alphabet (often just 0 and 1) that contains… …   Wikipedia

  • De Bruijn notation — For the representation of variables with natural numbers, see De Bruijn index. In mathematical logic, the De Bruijn notation is a syntax for terms in the λ calculus invented by the Dutch mathematician Nicolaas Govert de Bruijn.[1] It can be seen… …   Wikipedia

  • De Bruijn digraph — The vertices of the de Bruijn digraph B(n,m) are all possible words of length m 1 chosen from an alphabet of size n.B(n,m) has n^{m} edges consisting of each possible word of length m from an alphabet of size n. The edge a 1a 2dots a n connects… …   Wikipedia

  • List of mathematics articles (D) — NOTOC D D distribution D module D D Agostino s K squared test D Alembert Euler condition D Alembert operator D Alembert s formula D Alembert s paradox D Alembert s principle Dagger category Dagger compact category Dagger symmetric monoidal… …   Wikipedia

  • Koorde — In Peer to peer networks, Koorde is a Distributed hash table (DHT) based on Chord (DHT) and the De Bruijn graph (De Bruijn sequence). Inheriting the simplicity of Chord, Koorde meets O(log n) hops per node (where n is the number of nodes in the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”