последовательность де Брейна - de Bruijn sequence

Последовательность де Брейна для размера алфавита k = 2 и длины подстроки n = 2 . Как правило, существует множество последовательностей для конкретных n и k, но в этом примере они уникальны, вплоть до циклического воспроизведения.

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

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

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

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

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

История

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

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

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

Примеры

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

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

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

Последовательности де Брейна может быть построена путем принятия гамильтонов путь А. Н. п - мерный де Брейна графа над K символов (или , что эквивалентно, в эйлеровом цикл из ап ( п  - 1) -мерном де Брейна график).

Альтернативная конструкция включает объединение в лексикографическом порядке всех слов Линдона , длина которых делит n .

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

Последовательности Де Брёйна также могут быть построены с использованием регистров сдвига или с помощью конечных полей .

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

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

Цель: построить последовательность B (2, 4) де Брейна длины 2 ⁴ = 16, используя эйлеров ( n  - 1 = 4 - 1 = 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 ...

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

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

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

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

Например, чтобы построить наименьшую последовательность B (2,4) де Брюйна длиной 2 ⁴ = 16, повторите алфавит (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 вычисляет последовательность де Брёйна при заданных k и n на основе алгоритма из книги Фрэнка Риски « Комбинаторная генерация» .

from typing import Iterable, Union, Any
def de_bruijn(k: Union[Iterable[Any], int], n: int) -> str:
    """de Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    # Two kinds of alphabet input: an integer expands
    # to a list of integers as the alphabet..
    if isinstance(k, int):
        alphabet = list(map(str, range(k)))
    else:
        # While any sort of list becomes used as it is
        alphabet = k
        k = len(k)

    a = [0] * k * n
    sequence = []

    def db(t, p):
        if t > n:
            if n % p == 0:
                sequence.extend(a[1 : p + 1])
        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 "".join(alphabet[i] for i in sequence)


print(de_bruijn(2, 3))
print(de_bruijn("abcd", 2))

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

00010111
aabacadbbcbdccdd

Обратите внимание, что эти последовательности считаются «циклическими». Например, первая последовательность содержит 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» (для удобства чтения пробелы добавлены).

Последовательность может быть использована для сокращения атаки полным перебором на замок с PIN- кодом, который не имеет клавиши «ввод» и принимает последние n введенных цифр. Например, цифровой дверной замок с 4-значным кодом (каждая цифра имеет 10 возможных значений от 0 до 9) будет иметь решения B  (10, 4) с длиной10 000 . Следовательно, только не более10 000 + 3 =Для открытия замка необходимо 10 003 (так как растворы циклические) нажатия. Для проверки всех кодов по отдельности потребуется 4 раза10 000 =40 000 прессов.

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

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

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

unsigned int v;   
int r;           
static 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
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

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

Пример возврата индекса наиболее значимого набора битов из 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 b )
{
    static const uint32_t deBruijnMagic = 0x06EB14F9;
    static 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,
    };
    return deBruijnTable[(keepHighestBit(b) * deBruijnMagic) >> 27];
}

Упрощенный принцип работы цифрового пера Anoto.
Камера определяет матрицу точек размером 6 × 6, каждая из которых смещена от синей сетки (не напечатана) в 4 направлениях.
Комбинации относительных смещений 6-битной последовательности де Брейна между столбцами и между строками дают ее абсолютное положение на цифровой бумаге.

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

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

Тор де Брёйна

STL- модель тора де Брейна (16,32; 3,3) ₂ с единицами в качестве панелей и нулями в качестве отверстий в сетке - при согласованной ориентации каждая матрица 3 × 3 появляется ровно один раз

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

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

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

Вычисление положения конкретного уникального кортежа или матрицы в последовательности или торе де Брейна известно как проблема декодирования де Брейна. Эффективные алгоритмы декодирования существуют для специальных рекурсивно построенных последовательностей и распространяются на двумерный случай. Декодирование Де Брейна представляет интерес, например, в случаях, когда большие последовательности или торы используются для позиционного кодирования. ${\ displaystyle \ color {синий} O (n \ log n)}$

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

• График де Брёйна
• Тор де Брёйна
• Нормальный номер
• Регистр сдвига с линейной обратной связью
• n -последовательность
• ЛУЧШАЯ теорема

Примечания

использованная литература

• ван Аарденне-Эренфест, Таня ; де Брёйн, Николаас Говерт (1951). «Схемы и деревья в ориентированных линейных графах» (PDF) . Саймон Стевин . 28 : 203–217. Руководство по ремонту  0047311 .
• Aguirre, GK; Маттар, MG; Магис-Вайнберг, Л. (2011). «Циклы де Брейна для нейронного декодирования» . NeuroImage . 56 (3): 1293–1300. DOI : 10.1016 / j.neuroimage.2011.02.005 . PMC  3104402 . PMID  21315160 .
• Андерсон, Шон Эрон (1997–2009). "Bit Twiddling Hacks" . Стэнфордский университет . Проверено 12 февраля 2009 .
• Берстель, Жан ; Перрен, Доминик (2007). «Истоки комбинаторики слов» (PDF) . Европейский журнал комбинаторики . 28 (3): 996–1022. DOI : 10.1016 / j.ejc.2005.07.019 . Руководство по ремонту  2300777 .
• Браун, CP (1869). Санскритская просодия и объяснения числовых символов . п. 28.
• де Брёйн, Николаас Говерт (1946). «Комбинаторная задача» (PDF) . Proc. Koninklijke Nederlandse Akademie V. Wetenschappen . 49 : 758–764. MR  0018142 , Indagationes Mathematicae 8 : 461–467.CS1 maint: postscript ( ссылка )
• де Брюйн, Николаас Говерт (1975). «Подтверждение приоритета К. Флай Сент-Мари по подсчету круговых расположений из 2 ⁿ нулей и единиц, которые показывают каждое слово из n букв ровно один раз» (PDF) . Отчет TH 75-WSK-06. Технологический университет Эйндховена. Цитировать журнал требует |journal=( помощь )
• Буш, Филипп (2009). "Вычисление конечных нулей HOWTO" . Проверено 29 января 2015 .
• Flye Sainte-Marie, Камилла (1894). «Решение вопроса № 48». L'Intermédiaire des Mathématiciens . 1 : 107–110.
• Гореский, Марк ; Клаппер, Эндрю (2012). «8.2.5 Генерация регистра сдвига последовательностей де Брейна». Алгебраические последовательности регистров сдвига . Издательство Кембриджского университета . С. 174–175. ISBN 978-1-10701499-2.
• Холл, Рэйчел В. (2008). «Математика для поэтов и барабанщиков» (PDF) . Математические горизонты . 15 (3): 10–11. DOI : 10.1080 / 10724117.2008.11974752 . S2CID  3637061 . Архивировано из оригинального (PDF) 12 февраля 2012 года . Проверено 22 октября 2008 .
• Хиггинс, Питер (ноябрь 2012 г.). «Преобразования Барроуза-Уиллера и слова де Брюйна» (PDF) . Проверено 11 февраля 2017 .
• Херлберт, Гленн; Исаак, Гарт (1993). «К проблеме тора де Брейна» . Журнал комбинаторной теории . Series A. 64 (1): 50–62. DOI : 10.1016 / 0097-3165 (93) 90087-O . Руководство по ремонту  1239511 .
• Как, Субхаш (2000). «Yamātārājabhānasalagāṃ - интересная комбинаторная сутра» (PDF) . Индийский журнал истории науки . 35 (2): 123–127. Архивировано из оригинального (PDF) 29.10.2014.
• Кляйн, Андреас (2013). Потоковые шифры . Springer. п. 59. ISBN 978-1-44715079-4.
• Кнут, Дональд Эрвин (2006). Искусство программирования, Часть 4: Создание всех деревьев - История комбинаторного поколения . Аддисон-Уэсли . п. 50. ISBN 978-0-321-33570-8.
• Фредриксен, Гарольд; Майорана, Джеймс (1978). «Ожерелья из бисера k цветов и k -ары последовательностей де Брейна» . Дискретная математика . 23 (3): 207–210. DOI : 10.1016 / 0012-365X (78) 90002-X . Руководство по ремонту  0523071 .
• Мартин, Монро Х. (1934). «Проблема в договоренностях» (PDF) . Бюллетень Американского математического общества . 40 (12): 859–864. DOI : 10.1090 / S0002-9904-1934-05988-3 . Руководство по ремонту  1562989 .
• Осипов, Владимир (2016). «Вейвлет-анализ символьных последовательностей и двукратных последовательностей де Брейна». Журнал статистической физики . 164 (1): 142–165. arXiv : 1601.02097 . Bibcode : 2016JSP ... 164..142O . DOI : 10.1007 / s10955-016-1537-5 . ISSN  1572-9613 . S2CID  16535836 .
• Поппер, Карл (2002) [1934]. Логика научного открытия . Рутледж. п. 294. ISBN 978-0-415-27843-0.
• Ральстон, Энтони (1982). «Последовательности де Брейна - модельный пример взаимодействия дискретной математики и информатики». Математический журнал . 55 (3): 131–143. DOI : 10.2307 / 2690079 . JSTOR  2690079 . Руководство по ремонту  0653429 .
• Штейн, Шерман К. (1963). «Яматараджабханасалагам». Созданная человеком Вселенная: Введение в дух математики . С. 110–118.Перепечатано в Wardhaugh, Benjamin, ed. (2012), «Богатство чисел: антология за 500 лет популярной математической литературы» , Princeton University Press , стр. 139–144.
• Тулиани, Джонатан (2001). «Последовательности де Брейна с эффективными алгоритмами декодирования» . Дискретная математика . 226 (1–3): 313–336. DOI : 10.1016 / S0012-365X (00) 00117-5 . Руководство по ремонту  1802599 .
• ван Линт, JH ; Уилсон, Ричард Майкл (2001). Курс комбинаторики . Издательство Кембриджского университета . п. 71. ISBN 978-0-52100601-9.

внешние ссылки

• Вайсштейн, Эрик В. «Последовательность де Брейна» . MathWorld .
• Последовательность OEIS A166315 (лексикографически наименьшие двоичные последовательности де Брейна)
• Последовательность де Брюйна
• Генератор CGI
• Генератор апплетов
• Генератор и декодер Javascript . Реализация алгоритма Дж. Тулиани.
• Кодовый замок двери
• Минимальные массивы, содержащие все комбинации символов подмассивов: последовательности Де Брейна и торы.