В компьютерной науке , в лексикографический минимальном вращении строки или лексикографический наималейшей круговой подстроке является задачей нахождения вращения струны , обладающей самой низка лексикографического порядка всех таких вращений. Например, лексикографически минимальное вращение «bbaaccaadd» будет «aaccaaddbb». Строка может иметь несколько лексикографически минимальных поворотов, но для большинства приложений это не имеет значения, поскольку повороты должны быть эквивалентными. Нахождение лексикографически минимального вращения полезно как способ нормализации строк. Если строки представляют собой потенциально изоморфные структуры, такие как графы, нормализация таким образом позволяет выполнить простую проверку равенства. [1] Распространенный трюк реализации при работе с циклическими строками состоит в том, чтобы объединить строку с самой собой, вместо того, чтобы выполнять модульную арифметику над индексами строки.
Алгоритмы
Наивный алгоритм
Наивный алгоритм нахождения лексикографически минимального вращения строки состоит в том, чтобы перебирать последовательные вращения, отслеживая наиболее лексикографически минимальное вращение, которое встречается. Если строка имеет длину n , этот алгоритм работает в худшем случае за время O ( n 2 ) .
Алгоритм Бута
Эффективный алгоритм был предложен Бутом (1980). [2] Алгоритм использует модифицированную функцию предварительной обработки из алгоритма поиска строки Кнута-Морриса-Пратта . Функция отказа для строки вычисляется как обычно, но строка поворачивается во время вычисления, поэтому некоторые индексы должны вычисляться более одного раза по мере их зацикливания. После того, как все индексы функции отказа были успешно вычислены без повторного вращения строки, известно, что минимальное лексикографическое вращение найдено, и возвращается его начальный индекс. Правильность алгоритма понять довольно сложно, но реализовать его несложно.
def minimum_rotation ( S : str ) -> int : "" "Алгоритм Бута." "" S + = S # Объединить строку с собой, чтобы избежать модульной арифметики f = [ - 1 ] * len ( S ) # Функция отказа k = 0 # Наименьшее вращение строки, найденное до сих пор для j в диапазоне ( 1 , len ( S )): sj = S [ j ] i = f [ j - k - 1 ] while i ! = - 1 and sj ! = S [ k + i + 1 ]: если sj < S [ k + i + 1 ]: k = j - i - 1 i = f [ i ], если sj ! = S [ k + i + 1 ]: # if sj! = S [k + i + 1], то i == -1, если sj < S [ k ]: # k + i + 1 = k k = j f [ j - k ] = - 1 иначе : f [ j - k ] = i + 1 вернуть k
Интересно то, что удаление всех строк кода, которые изменяют значение k, приводит к исходной функции предварительной обработки Кнута-Морриса-Пратта, поскольку k (представляющий вращение) останется нулевым. Алгоритм Бута работает ввремя, где n - длина строки. Алгоритм выполняет не болеесравнения в худшем случае и требует вспомогательной памяти длины n для хранения таблицы функций отказа.
Алгоритм быстрой канонизации Шилоаха
Shiloach (1981) [3] предложил алгоритм, улучшающий результат Бута с точки зрения производительности. Было замечено, что если существует q эквивалентных лексикографически минимальных поворотов строки длины n , то строка должна состоять из q равных подстрок длины d = n / q . Алгоритм требует только n + d / 2 сравнений и постоянного пространства в худшем случае.
Алгоритм разделен на два этапа. Первая фаза - это быстрое сито, исключающее индексы, которые, очевидно, не являются начальными местоположениями для лексикографически минимального вращения. Затем на втором этапе определяется лексикографически минимальный индекс начала вращения из оставшихся индексов.
Алгоритм факторизации Дюваля Линдона
Дюваль (1983) [4] предложил эффективный алгоритм, включающий факторизацию строки в составляющие ее слова Линдона , который работает за линейное время с постоянными требованиями к памяти.
Варианты
Shiloach (1979) [5] предложил алгоритм для эффективного сравнения двух круговых строк на равенство без требования нормализации. Дополнительным применением алгоритма является быстрое создание определенных химических структур без повторов.
Смотрите также
Рекомендации
- ^ Келлог С. Бут; Колборн, Чарльз Дж. (1980). «Алгоритмы линейного автоморфизма времени для деревьев, интервальных графов и плоских графов» . SIAM Journal on Computing . Общество промышленной и прикладной математики. 10 (1): 203–225. DOI : 10.1137 / 0210015 . ISSN 0097-5397 .
- ^ Келлог С. Бут (1980). «Лексикографически наименее круговые подстроки». Письма об обработке информации . Эльзевир. 10 (4–5): 240–242. DOI : 10.1016 / 0020-0190 (80) 90149-0 . ISSN 0020-0190 .
- ^ Йоси Шилоач (1981). «Быстрая канонизация циркулярных струн». Журнал алгоритмов . Эльзевир. 2 (2): 107–121. DOI : 10.1016 / 0196-6774 (81) 90013-4 . ISSN 0196-6774 .
- ^ Жан-Пьер Дюваль (1983). «Факторизация слов по упорядоченному алфавиту». Журнал алгоритмов . Эльзевир. 8 (8): 363–381. DOI : 10.1016 / 0196-6774 (83) 90017-2 . ISSN 0196-6774 .
- ^ Йоси Шилоач (1979). «Быстрый алгоритм проверки эквивалентности для круговых списков». Письма об обработке информации . Эльзевир. 8 (5): 236–238. DOI : 10.1016 / 0020-0190 (79) 90114-5 . ISSN 0020-0190 .