Последовательность де Брюйна - De Bruijn sequence

	B {10,3} с цифрами, читаемыми сверху вниз; затем слева направо; добавление "00" дает; строка для перебора 3-значного кодового замка
	001
	002
	003
	004
	005
	006
	007
	008
	009
	011
012	112
013	113
014	114
015	115
016	116
017	117
018	118
019	119
	021
022	122
	031
032	132
	041
042	142
	051
052	152
	061
062	162
	071
072	172
	081
082	182
	091
092	192

Последовательность де Брейна для размера алфавита k = 2 и длина подстроки п = 2. В общем, существует множество последовательностей для конкретного п и k но в этом примере он уникален, вплоть до кататься на велосипеде.

В комбинаторный математика, а последовательность де Брейна порядка п по размеру-k алфавит А это циклическая последовательность в котором всевозможная длина-п нить на А встречается ровно один раз как подстрока (т.е. как смежный подпоследовательность ). Такая последовательность обозначается B(k, п) и имеет длину k^п, который также является количеством различных строк длины п на А. Каждая из этих отдельных строк, если рассматривать их как подстроку B(k, п), должны начинаться с другой позиции, потому что подстроки, начинающиеся с одной и той же позиции, не различны. Следовательно, B(k, п) должны быть по меньшей мере k^п символы. И с тех пор B(k, п) имеет точно k^п символов, последовательности Де Брёйна оптимально короткие с точки зрения свойства содержать каждую строку длины п ровно один раз.

Количество различных последовательностей де Брейна B(k, п) является

{ displaystyle { dfrac { left (k! right) ^ {k ^ {n-1}}} {k ^ {n}}}.}

Последовательности названы в честь голландского математика. Николаас Говерт де Брёйн, который писал о них в 1946. Как он позже писал,^[1] существование последовательностей де Брейна для каждого порядка вместе с указанными выше свойствами было впервые доказано для случая алфавитов с двумя элементами Камиллой Флай Сент-Мари (1894 ). Обобщение на более крупные алфавиты связано с Татьяна ван Аарденне-Эренфест и де Брейн (1951 ). Автоматы для распознавания этих последовательностей обозначаются как автоматы де Брейна и топологически похожи на некоторые нейронные сети с задержкой по времени.^[2]

В большинстве приложений А = {0,1}.

История

Самый ранний известный пример последовательности де Брейна происходит от Санскритская просодия где, поскольку работа Пингала каждому возможному трехсложному сочетанию длинных и коротких слогов дается имя, например, «y» для коротких – долгих – длинных и «m» для длинных – длинных – длинных. Чтобы запомнить эти имена, мнемоническое яматараджабханасалагам используется, в котором каждый трехсложный образец начинается с его имени: у 'yamātā' есть короткий-длинный-длинный образец, у 'mātārā' есть длинный-длинный-длинный образец, и так далее, пока 'салагам', который имеет модель короткая-короткая-длинная. Эта мнемоника, эквивалентная последовательности де Брейна на двоичных 3-кортежах, имеет неизвестную древность, но по крайней мере так же стара, как Чарльз Филип Браун в книге 1869 года по санскритской просодии, в которой это упоминается и считается «древней строкой», написанной Панини ".^[3]

В 1894 г. А. де Ривьер поднял вопрос в номере французского проблемного журнала. L'Intermédiaire des Mathématiciens, наличия кругового расположения нулей и единиц размера ${ Displaystyle 2 ^ {п}}$ который содержит все ${ Displaystyle 2 ^ {п}}$ двоичные последовательности длины ${ displaystyle n}$ . Проблема была решена (утвердительно) вместе с подсчетом ${ displaystyle 2 ^ {2 ^ {n-1} -n}}$ отличные решения, созданные Камиллой Флай Сент-Мари в том же году.^[1] Об этом в значительной степени забыли, и Мартин (1934) доказал существование таких циклов для общего размера алфавита вместо 2, с алгоритмом их построения. Наконец, когда в 1944 г. Кис Постумус предположил счет ${ displaystyle 2 ^ {2 ^ {n-1} -n}}$ для двоичных последовательностей де Брюин доказал гипотезу в 1946 году, благодаря чему проблема стала широко известной.^[1]

Карл Поппер самостоятельно описывает эти объекты в своем Логика научных открытий (1934), назвав их «кратчайшими случайными последовательностями».^[4]

Примеры

Принимая А = {0, 1}, есть два различных B(2, 3): 00010111 и 11101000, причем одно является обратным или отрицательным для другого.
Два из 2048 возможных B(2, 5) в том же алфавите - это 00000100011001010011101011011111 и 00000101001000111110111001101011.

Строительство

Граф де Брейна. Каждая четырехзначная последовательность встречается ровно один раз, если пройти через каждое ребро ровно один раз и вернуться в исходную точку (эйлеров цикл). Каждая трехзначная последовательность встречается ровно один раз, если посетить каждую вершину ровно один раз (гамильтонов путь).

Последовательности де Брейна можно построить, взяв Гамильтонов путь из п-размерный граф де Брейна над k символы (или эквивалентно Эйлеров цикл из (п - 1) -мерный граф де Брейна).^[5]

Альтернативная конструкция включает объединение в лексикографическом порядке всех Слова Линдона чья длина делит п.^[6]

Обратный Преобразование Берроуза-Уиллера может использоваться для генерации требуемых слов Линдона в лексикографическом порядке.^[7]

Последовательности Де Брёйна также могут быть построены с использованием регистры сдвига^[8] или через конечные поля.^[9]

Пример использования графа де Брейна

Направленные графы двух последовательностей де Брейна B (2,3) и последовательности B (2,4). В B (2,3). каждая вершина посещается один раз, тогда как в B (2,4) каждое ребро проходит один раз.

Цель: построить B(2, 4) последовательность де Брейна длины 2⁴ = 16 с использованием эйлерова (п - 1 = 4 - 1 = 3) 3-мерный цикл графа де Брейна.

Каждое ребро в этом трехмерном графе де Брейна соответствует последовательности из четырех цифр: трех цифр, обозначающих вершину, из которой выходит ребро, за которыми следует цифра, обозначающая ребро. Если пройти по ребру, обозначенному 1 из 000, то получится 001, что указывает на присутствие подпоследовательности 0001 в последовательности де Брюйна. Чтобы пройти каждое ребро ровно один раз, нужно использовать каждую из 16 четырехзначных последовательностей ровно один раз.

Например, предположим, что мы идем по следующему эйлерову пути через эти вершины:

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

_ _ 0 0 1 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 ...   ... 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 ...

... а затем возвращаемся к исходной точке. Каждая из восьми 3-значных последовательностей (соответствующих восьми вершинам) появляется ровно дважды, а каждая из шестнадцати 4-значных последовательностей (соответствующих 16 ребрам) появляется ровно один раз.

Пример использования обратного преобразования Барроуза-Уиллера

Математически обратное преобразование Барроуза-Уиллера для слова ш генерирует мульти-набор классов эквивалентности, состоящий из строк и их поворотов.^[7] Каждый из этих классов эквивалентности строк содержит слово Линдона в качестве уникального минимального элемента, поэтому обратное преобразование Барроуза-Уиллера можно рассматривать для генерации набора слов Линдона. Можно показать, что если мы выполним обратное преобразование Барроуза-Уиллера над словом ш состоящий из алфавита размера k, повторяющегося k^п-1 раз (чтобы получилось слово той же длины, что и искомая последовательность де Брейна), то результатом будет набор всех слов Линдона, длина которых делит n. Отсюда следует, что расположение этих слов Линдона в лексикографическом порядке даст последовательность де Брейна B (k, n), и что это будет первая последовательность де Брейна в лексикографическом порядке. Следующий метод можно использовать для выполнения обратного преобразования Барроуза-Уиллера, используя его стандартная перестановка:

Сортировать символы в строке ш, давая новую строку w '
Расположите строку w ' над строкой ш, и сопоставьте положение каждой буквы в w ' на свое место в ш при сохранении порядка. Этот процесс определяет Стандартная перестановка.
Запишите эту перестановку в обозначение цикла с наименьшей позицией в каждом цикле первой, а циклы отсортированы в порядке возрастания.
Для каждого цикла замените каждое число соответствующей буквой из строки w ' в этом положении.
Каждый цикл теперь стал словом Линдона, и они расположены в лексикографическом порядке, поэтому удаление скобок дает первую последовательность де Брейна.

Например, чтобы построить наименьшую последовательность B (2,4) де Брейна длины 2⁴ = 16, повторить алфавит (ab) 8 раз, получив ш= abababababababab. Сортировать символы в ш, уступая ш'= aaaaaaaabbbbbbbb. Позиция w ' над ш как показано, и сопоставьте каждый элемент в ш'к соответствующему элементу в ш нарисовав линию. Пронумеруйте столбцы, как показано, чтобы мы могли прочитать циклы перестановки:

Начиная слева, циклы стандартной перестановки нотации следующие: (1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16). (Стандартная перестановка )

Затем, заменяя каждое число соответствующей буквой в ш'из этого столбца дает: (a) (aaab) (aabb) (ab) (abbb) (b).

Это все слова Линдона, длина которых делится на 4 в лексикографическом порядке, поэтому, если отбросить скобки, получится B (2,4) = aaaabaabbababbbb.

Алгоритм

Следующее Python код вычисляет последовательность де Брейна, учитывая k и п, основанный на алгоритме из Фрэнк Руски с Комбинаторная генерация.^[10]

def de_bruijn(k, п: int) -> ул:    "" "последовательность де Брейна для алфавита k    и подпоследовательности длины n.    """    пытаться:        # посмотрим, можно ли преобразовать k в целое число;        # если да, то сделаем наш алфавит списком        _ = int(k)        алфавит = список(карта(ул, классифицировать(k)))    Кроме (ValueError, TypeError):        алфавит = k        k = len(k)    а = [0] * k * п    последовательность = []    def db(т, п):        если т > п:            если п % п == 0:                последовательность.продлевать(а[1 : п + 1])        еще:            а[т] = а[т - п]            db(т + 1, п)            за j в классифицировать(а[т - п] + 1, k):                а[т] = j                db(т + 1, т)    db(1, 1)    возвращаться "".присоединиться(алфавит[я] за я в последовательность)Распечатать(de_bruijn(2, 3))Распечатать(de_bruijn("abcd", 2))

который печатает

00010111aabacadbbcbdccdd

Обратите внимание, что эти последовательности считаются «циклическими». Например, таким образом первая последовательность содержит 110 и 100.

Использует

Один возможный B (10, 4) последовательность. 2530 подстрок читаются сверху вниз, затем слева направо, и их цифры объединяются. Чтобы строка использовалась для подбора кодового замка, добавляются последние три цифры в скобках (000). Строка из 10003 цифр, следовательно, имеет вид «0 0001 0002 0003 0004 0005 0006 0007 0008 0009 0011… 79 7988 7989 7998 7999 8 8889 8899 89 8999 9 000» (для удобства чтения пробелы добавлены).

Последовательность может быть использована для сокращения атаки полным перебором на ШТЫРЬ -как кодовый замок, не имеющий клавиши "ввод" и принимающий последний п введенные цифры. Например, цифровой дверной замок с 4-значным кодом (каждая цифра имеет 10 вариантов от 0 до 9) будет иметь B (10, 4) решения длиной 10000. Следовательно, только не более 10000 + 3 = 10003 (поскольку решения циклические) для открытия замка необходимы нажатия. Попытка всех кодов по отдельности потребует 4 × 10000 = 40000 прессы.

Символы последовательности де Брейна, написанные вокруг круглого объекта (например, колеса робот ) может использоваться для идентификации его угол изучив п последовательные символы, обращенные к фиксированной точке. Эта проблема углового кодирования известна как «проблема вращающегося барабана».^[12] Коды Грея могут использоваться как аналогичные поворотные механизмы позиционного кодирования.

Циклы Де Брёйна широко используются в экспериментах по нейробиологии и психологии, которые исследуют влияние порядка стимулов на нервные системы,^[13] и может быть специально разработан для использования с функциональная магнитно-резонансная томография.^[14]

Последовательность де Брейна может использоваться для быстрого поиска индекса младшего значащего бита набора («крайний правый 1») или старшего значащего бита набора («крайний левый 1») в слово с помощью побитовые операции.^[15] Пример возврата индекса младшего разряда из 32-битного целого числа без знака приведен ниже с использованием битовая манипуляция и умножение.

беззнаковый int v;   int р;           статический const int MultiplyDeBruijnBitPosition[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};р = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Индекс младшего разряда в v хранится в р и если v не имеет установленных битов, операция возвращает 0. Константа 0x077CB531U в выражении является B (2, 5) последовательность 0000 0111 0111 1100 1011 0101 0011 0001 (для ясности добавлены пробелы).

Пример возврата индекса наиболее значимого набора бит из 32-битного целого числа без знака приведен ниже с использованием битовая манипуляция и умножение.

uint32_t keepHighestBit( uint32_t п ){    п |= (п >>  1);    п |= (п >>  2);    п |= (п >>  4);    п |= (п >>  8);    п |= (п >> 16);    возвращаться п - (п >> 1);}uint8_t highBitIndex( uint32_t б ){    статический const uint32_t deBruijnMagic = 0x06EB14F9;    статический const uint8_t deBruijnTable[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,    };    возвращаться deBruijnTable[(keepHighestBit(б) * deBruijnMagic) >> 27];}

f-кратные последовательности де Брейна

f-кратная n-арная последовательность де Брейна ' является расширением понятия п-арная последовательность де Брейна, такая, что последовательность длины ${ displaystyle fk ^ {n}}$ содержит все возможные подпоследовательность длины п точно ж раз. Например, для ${ displaystyle n = 2}$ циклические последовательности 11100010 и 11101000 представляют собой двойные двоичные последовательности де Брейна. Число двукратных последовательностей де Брейна, ${ displaystyle N_ {n}}$ за ${ Displaystyle п = 1}$ является ${ displaystyle N_ {1} = 2}$ , другие известные числа^[16] находятся ${ displaystyle N_ {2} = 5}$ , ${ displaystyle N_ {3} = 72}$ , и ${ displaystyle N_ {4} = 43768}$ .

Тор де Брёйна

А тор де Брейна представляет собой тороидальный массив со свойством, что каждый k-ари м-к-п матрица встречается ровно один раз.

Такой шаблон можно использовать для двумерного позиционного кодирования способом, аналогичным описанному выше для вращательного кодирования. Положение можно определить, изучив м-к-п матрица, непосредственно примыкающая к датчику, и вычисляет ее положение на торе де Брейна.

Декодирование де Брюйна

Вычисление положения конкретного уникального кортежа или матрицы в последовательности или торе де Брейна известно как проблема декодирования де Брейна. Эффективный O (п войти п) алгоритмы декодирования существуют для специальных рекурсивно построенных последовательностей^[17] и распространимся на двумерный случай.^[18] Декодирование де Брёйна представляет интерес, например, в случаях, когда для позиционного кодирования используются большие последовательности или торы.

Смотрите также

Примечания

^ ^а ^б ^c де Брюйн (1975).
^ Джайлз, К. Ли; Хорн, Билл Дж .; Линь, Цуннан (1995). «Изучение класса больших конечных автоматов с рекуррентной нейронной сетью» (PDF). Нейронные сети. 8 (9): 1359–1365.
^ Коричневый (1869); Штейн (1963); Как (2000); Кнут (2006); Холл (2008).
^ Поппер (2002).
^ Кляйн (2013).
^ В соответствии с Берстель и Перрин (2007), последовательность, сгенерированная таким образом, была впервые описана (с другим методом генерации) Мартин (1934), а связь между ним и словами Линдона была замечена Фредриксен и Майорана (1978).
^ ^а ^б Хиггинс (2012).
^ Горески и Клаппер (2012).
^ Ральстон (1982) С. 136–139.
^ "Последовательности Де Брёйна". мудрец. Получено 2016-11-03.
^ http://hakank.org/comb/debruijn.cgi?k=10&n=3
^ ван Линт и Уилсон (2001).
^ Агирре, Маттар и Магис-Вайнберг (2011).
^ «Генератор цикла Де Брёйна».
^ Андерсон (1997–2009); Буш (2009)
^ Осипов (2016).
^ Тулиани (2001).
^ Херлберт и Исаак (1993).

внешняя ссылка

[FOOTNOTEde_Bruijn1975-1] а ^б ^c де Брюйн (1975).

[2] Джайлз, К. Ли; Хорн, Билл Дж .; Линь, Цуннан (1995). «Изучение класса больших конечных автоматов с рекуррентной нейронной сетью» (PDF). Нейронные сети. 8 (9): 1359–1365.

[3] Коричневый (1869); Штейн (1963); Как (2000); Кнут (2006); Холл (2008).

[FOOTNOTEPopper2002-4] Поппер (2002).

[FOOTNOTEKlein2013-5] Кляйн (2013).

[6] В соответствии с Берстель и Перрин (2007), последовательность, сгенерированная таким образом, была впервые описана (с другим методом генерации) Мартин (1934), а связь между ним и словами Линдона была замечена Фредриксен и Майорана (1978).

[FOOTNOTEHiggins2012-7] а ^б Хиггинс (2012).

[FOOTNOTEGoreskyKlapper2012-8] Горески и Клаппер (2012).

[FOOTNOTERalston1982136–139-9] Ральстон (1982) С. 136–139.

[10] "Последовательности Де Брёйна". мудрец. Получено 2016-11-03.

[11] ttp://hakank.org/comb/debruijn.cgi?k=10&n=3

[FOOTNOTEvan_LintWilson2001-12] ван Линт и Уилсон (2001).

[FOOTNOTEAguirreMattarMagis-Weinberg2011-13] Агирре, Маттар и Магис-Вайнберг (2011).

[14] «Генератор цикла Де Брёйна».

[15] Андерсон (1997–2009); Буш (2009)

[FOOTNOTEOsipov2016-16] Осипов (2016).

[FOOTNOTETuliani2001-17] Тулиани (2001).

[FOOTNOTEHurlbertIsaak1993-18] Херлберт и Исаак (1993).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

B {10,3} с цифрами, читаемыми сверху вниз затем слева направо;^[11] добавление "00" дает строка для перебора 3-значного кодового замка
0	1	2	3	4	5	6	7	8	9
001
002
003
004
005
006
007
008
009

011
012	112
013	113
014	114
015	115
016	116
017	117
018	118
019	119

021
022	122
023	123	223
024	124	224
025	125	225
026	126	226
027	127	227
028	128	228
029	129	229

031
032	132
033	133	233
034	134	234	334
035	135	235	335
036	136	236	336
037	137	237	337
038	138	238	338
039	139	239	339

041
042	142
043	143	243
044	144	244	344
045	145	245	345	445
046	146	246	346	446
047	147	247	347	447
048	148	248	348	448
049	149	249	349	449

051
052	152
053	153	253
054	154	254	354
055	155	255	355	455
056	156	256	356	456	556
057	157	257	357	457	557
058	158	258	358	458	558
059	159	259	359	459	559

061
062	162
063	163	263
064	164	264	364
065	165	265	365	465
066	166	266	366	466	566
067	167	267	367	467	567	667
068	168	268	368	468	568	668
069	169	269	369	469	569	669

071
072	172
073	173	273
074	174	274	374
075	175	275	375	475
076	176	276	376	476	576
077	177	277	377	477	577	677
078	178	278	378	478	578	678	778
079	179	279	379	479	579	679	779

081
082	182
083	183	283
084	184	284	384
085	185	285	385	485
086	186	286	386	486	586
087	187	287	387	487	587	687
088	188	288	388	488	588	688	788
089	189	289	389	489	589	689	789	889

091
092	192
093	193	293
094	194	294	394
095	195	295	395	495
096	196	296	396	496	596
097	197	297	397	497	597	697
098	198	298	398	498	598	698	798
099	199	299	399	499	599	699	799	899	(00)