Лексикографически минимальное вращение струны - Википедия - Lexicographically minimal string rotation

В Информатика, то лексикографически минимальное вращение строки или же лексикографически наименьшая круговая подстрока проблема поиска вращение струны обладающий самым низким лексикографический порядок всех таких вращений. Например, лексикографически минимальное вращение «bbaaccaadd» будет «aaccaaddbb». Строка может иметь несколько лексикографически минимальных поворотов, но для большинства приложений это не имеет значения, поскольку повороты должны быть эквивалентными. Нахождение лексикографически минимального вращения полезно как способ нормализация струны. Если строки представляют потенциально изоморфный структуры, такие как графики, нормализация таким образом позволяет выполнять простую проверку равенства.[1]Распространенный трюк реализации при работе с круговыми строками состоит в том, чтобы объединить строку с самой собой вместо того, чтобы выполнять модульная арифметика на строковых индексах.

Алгоритмы

Наивный алгоритм

Наивный алгоритм поиска лексикографически минимального поворота строки состоит в том, чтобы перебирать последовательные вращения, отслеживая при этом наиболее лексикографически минимальный поворот строки. Если строка имеет длину п, этот алгоритм работает в О(п2) время в худшем случае.

Алгоритм Бута

Эффективный алгоритм был предложен Бутом (1980).[2]Алгоритм использует модифицированную функцию предварительной обработки из Алгоритм поиска строки Кнута-Морриса-Пратта. Функция отказа для строки вычисляется как обычно, но строка поворачивается во время вычисления, поэтому некоторые индексы должны вычисляться более одного раза по мере их зацикливания. Как только все индексы функции отказа были успешно вычислены без повторного вращения строки, известно, что минимальное лексикографическое вращение найдено, и возвращается его начальный индекс. Правильность алгоритма несколько сложно понять, но реализовать легко.

def минимум_ротации(S: ул.) -> int:    "" "Алгоритм Бута." ""    S += S  # Связываем строку с собой, чтобы избежать модульной арифметики    ж = [-1] * len(S)  # Функция отказа    k = 0  # Наименьшее вращение строки найдено до сих пор    за j в классифицировать(1, len(S)):        sj = S[j]        я = ж[j - k - 1]        пока я != -1 и sj != S[k + я + 1]:            если sj < S[k + я + 1]:                k = j - я - 1            я = ж[я]        если sj != S[k + я + 1]:  # если sj! = S [k + i + 1], то i == -1            если sj < S[k]:  # к + я + 1 = к                k = j            ж[j - k] = -1        еще:            ж[j - k] = я + 1    возвращаться k

Интересно то, что удаление всех строк кода, изменяющих значение k приводит к исходной функции предварительной обработки Кнута-Морриса-Пратта, как k (представляющий вращение) останется нулевым. Алгоритм Бута работает в время, где п - длина строки. Алгоритм выполняет не более сравнения в худшем случае и требует вспомогательной памяти длины п для хранения таблицы функций отказа.

Алгоритм быстрой канонизации Шилоаха

Шилоах (1981)[3]предложил алгоритм, улучшающий результат Бута с точки зрения производительности. Было замечено, что если есть q эквивалентные лексикографически минимальные повороты строки длины п, то строка должна состоять из q равные подстроки длины д = п / д. Алгоритм требует только п + д / 2 сравнения и постоянное пространство в худшем случае.

Алгоритм разделен на два этапа. Первая фаза - это быстрое сито, исключающее индексы, которые явно не являются начальными местоположениями для лексикографически минимального вращения. На втором этапе определяется лексикографически минимальный индекс начала вращения из оставшихся индексов.

Алгоритм факторизации Дюваля Линдона

Дюваль (1983)[4]предложил эффективный алгоритм, включающий факторизацию строки в ее компонент Слова Линдона, который работает в линейном времени с постоянными требованиями к памяти.

Варианты

Шилоах (1979)[5]предложил алгоритм для эффективного сравнения двух круговых строк на равенство без требования нормализации. Дополнительное применение алгоритма - быстрое создание определенных химических структур без повторов.

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

Рекомендации

  1. ^ Келлог С. Бут; Колборн, Чарльз Дж. (1980). "Алгоритмы линейного автоморфизма для деревьев, интервальных и плоских графов". SIAM Журнал по вычислениям. Общество промышленной и прикладной математики. 10 (1): 203–225. Дои:10.1137/0210015. ISSN  0097-5397.
  2. ^ Келлог С. Бут (1980). «Лексикографически наименее круговые подстроки». Письма об обработке информации. Эльзевир. 10 (4–5): 240–242. Дои:10.1016/0020-0190(80)90149-0. ISSN  0020-0190.
  3. ^ Йоси Шилоач (1981). «Быстрая канонизация циркулярных струн». Журнал алгоритмов. Эльзевир. 2 (2): 107–121. Дои:10.1016/0196-6774(81)90013-4. ISSN  0196-6774.
  4. ^ Жан-Пьер Дюваль (1983). «Факторизация слов по упорядоченному алфавиту». Журнал алгоритмов. Эльзевир. 8 (8): 363–381. Дои:10.1016/0196-6774(83)90017-2. ISSN  0196-6774.
  5. ^ Йоси Шилоах (1979). «Быстрый алгоритм проверки эквивалентности для круговых списков». Письма об обработке информации. Эльзевир. 8 (5): 236–238. Дои:10.1016/0020-0190(79)90114-5. ISSN  0020-0190.