Lexikograficky minimální rotace řetězce

Lexikograficky minimální rotace řetězce je v matematické informatice problém nalezení takového místa v řetězci, od něhož začíná řetězec, který bude v lexikografickém uspořádání první ze všech řetězců získaných z původního řetězce. Například pro řetězec bbaaccaadd je lexikograficky minimální rotace aaccaaddbb. Jeden řetězec může mít několik lexikograficky minimálních rotací, ale ve většině použití na tom nezáleží, protože rotace musí být ekvivalentní. Hledání lexikograficky minimální rotace je užitečný způsob normalizace řetězců. Pokud řetězce reprezentují potenciálně izomorfní struktury, jako grafy, tato metoda normalizace umožňuje jednoduché testování rovnosti. Při práci s cyklickými řetězci je obvyklým implementačním trikem použít zřetězení dvou instancí řetězce místo provádění modulární aritmetiky na indexy řetězce.

Algoritmy

Naivní algoritmus

Naivní algoritmus pro hledání lexikograficky minimální rotace řetězce prochází všechny rotace a udržuje si informaci o dosud nalezené lexikograficky minimální rotaci. Pokud má řetězec délku n, má tento algoritmus v nejhorším případě časovou složitost O(n²).

Boothův algoritmus

Efektivní algoritmus navrhl v roce 1980 Kellogg S. Booth. Algoritmus používá upravenou funkci pro předzpracování z Knuthova-Morrisova-Prattova algoritmu pro vyhledávání řetězců. Funkce selhání pro řetězec se počítá jako obvykle, ale během výpočtu je řetězec rotován, takže některé indexy se musí počítat více než jednou, protože řetězec je zacyklen. Po vypočítání všech indexů funkce selhání bez rotování řetězce, je známo, že je nalezena lexikograficky minimální rotace, a její počáteční index je vrácen. Porozumět korektnosti algoritmu je poněkud obtížné, ale jeho implementace je snadná.

def least_rotation(s: str) -> int:
    """Boothův algoritmus pro lexikograficky minimální rotaci řetězce."""
    n = len(s)
    f = [-1] * (2 * n)
    k = 0
    for j in range(1, 2 * n):
        i = f[j - k - 1]
        while i != -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j - i - 1
            i = f[i]
        if i == -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

Zajímavé je, že odstraněním všech řádků kódu, které mění hodnotu k, dostaneme původní funkci pro předzpracování z Knuthova-Morrisova-Prattova algoritmu pro vyhledávání řetězců, protože k (reprezentující rotaci) bude zůstávat na nule. Časová složitost Boothova algoritmu je $O(n)$, kde n je délka řetězce. Algoritmus provádí v nejhorším případě nejvýše $3n$ porovnání, a pro udržování tabulky funkce selhání vyžaduje pomocnou paměť délky n.

Shiloachův rychlý kanonizační algoritmus

V roce 1981 navrhl Yossi Shiloach výkonnostní vylepšení Boothova algoritmu. Pozoroval, že pokud existuje q ekvivalentních lexikograficky minimálních rotací řetězce délky n, pak se řetězec musí skládat z q stejných podřetězců délky d=n/q. Vylepšený algoritmus vyžaduje v nejhorším případě pouze n + d/2 porovnání a konstantní prostor.

Algoritmus má dvě fáze. První fáze je rychlé síto, které vylučuje indexy, jež zjevně nejsou počáteční lokací lexikograficky minimální rotace. Ve druhé fázi se pak hledá počáteční index lexikograficky minimální rotace ze zbylých indexů.

Duvalův Lyndonův faktorizační algoritmus

Jean Pierre Duval navrhl v roce 1983 efektivní algoritmus obsahující faktorizaci řetězce na Lyndonova slova, z nichž se skládá. Algoritmus běží v lineární čase s konstantními nároky na paměť.

Varianty

Yossi Shiloach navrhl v roce 1979 algoritmus pro efektivně porovnání dvou kruhových řetězců na rovnost bez požadavku normalizace. Dalším použitím tohoto algoritmu je rychlé generování určitých chemických struktur bez opakování.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Lexicographically minimal string rotation na anglické Wikipedii.

Související články

• Lyndonovo slovo
• Knuthův–Morrisův–Prattův algoritmus