Leksikografski minimalna rotacija niske

U računarstvu, leksikografski minimalna rotacija niske, to jest leksikografski najmanja kružna podniska predstavlja problem pronalaženja takve rotacije date niske da je ta rotacija leksikografski najmanja među svim rotacijama te niske. Na primer, leksikografski minimalna rotacija niske „bbaaccaadd“ bi bila „aaccaaddbb“. Moguće je da određena niska ima više rotacija koje su leksikografski minimalne, međutim za većinu primena to nije bitno zato što te rotacije moraju biti međusobno ekvivalentne. Pronalazak leksikografski minimalne rotacije niske ima primenu za normalizaciju niski. Ako niske koje se posmatraju predstavljaju izomorfne strukture kao što su na primer grafovi, ova vrsta normalizacije niski omogućava jednostavnu proveru jednakosti. Da bi se izbeglo korišćene modularne aritmetike pri računanju indeksa u nisci, često se koristi trik da se niska nadoveže na samu sebe.

Algoritmi

Naivni algoritam

Kod naivnog algoritma iterira se kroz sve uzastopne rotacije niske, pri čemu se pamti i ažurira leksikografski najmanja rotacija na koju se do sada naišlo. Za nisku dužine n, vremenska složenost ovog algoritma u najgorem slučaju iznosi O(n²).

Butov algoritam

Efikasan algoritam koji rešava ovaj problem je izneo But (1980). Algoritam koristi modifikovanu funkciju za pretprocesiranje niske iz KMP algoritma. Funkcija neuspeha se za nisku računa na uobičajen način, međutim niska se rotira tokom izračunavanja pa se za neke indekse niske računanja vrše više odjednom. Kada su svi indeksi funkcije neuspeha uspešno izračunati i kada nema potrebe za ponovnom rotacijom niske, poznat je indeks gde počinje leksikografski najmanja rotacija niske i taj indeks se jednostavno vraća. Korektnost algoritma nije sasvim lako razumeti, ali se sam algoritam jednostavno implementira.

def LCS(S):
    n = len(S)
    S += S      # Nadovezivanje niski da bi se izbegla modularna aritmetika
    f = [-1 for c in S]     # Funkcija neuspeha
    k = 0       # Indeks početka leksikografski najmanje rotacije pronađene do sada
    for j in range(1, 2*n):
        i = f[j-k-1]
        while i != -1 and S[j] != S[k+i+1]:
            if S[j] < S[k+i+1]:
                k = j-i-1
            i = f[i]
        if i == -1 and S[j] != S[k+i+1]:
            if S[j] < S[k+i+1]:
                k = j
            f[j-k] = -1
        else:
            f[j-k] = i+1
    return k

Zanimljivo je da se uklanjanjem svih linija koda koje modifikuju vrednost promenljive k dobija originalna pretprocesirajuća funkcija koja se koristi u Knut-Moris-Prat algoritmu, zato što će promenljiva k (koja predstavlja rotaciju) ostati nula. Vremenska složenost Butovog algoritma je O(n), pri čemu je n dužina niske. Algoritam će izvršiti najviše 3n poređenja u najgorem slučaju, i koristi O(n) dodatnog memorijskog prostora za čuvanje tabele funkcije neuspeha.

Šajlokov algoritam brze kanonizacije

Šajlok (1981) je predložio algoritam koji ima bolje performanse od Butovog algoritma. On je primetio da ako postoji q leksikografski minimalnih ekvivalentnih rotacija niske dužine n, tada se originalna niska mora sastojati od q jednakih podniski dužine d=n/q. Predloženi algoritam koristi samo n + d/2 poređenja i konstantno dodatne memorije.

Algoritam ima dve faze. Prva faza služi za pronalaženje i odbacivanje indeksa niske koji zasigurno nisu mesta gde leksikografski minimalna rotacija niske počinje. Druga faza predstavlja pronalaženje indeksa početka leksikografski minimalne rotacije niske među preostalim indeksima.

Duvalov algoritam Lindon faktorizacije

Duval (1983) je takođe predložio efikasan algoritam koji se bazira na faktorizaciji niske u svoje komponente Lindonove reči, i izvršava se u linearnom vremenu i koristi konstantno dodatne memorije.

Varijante

Šajlok (1979) je preložio efikasan algoritam za poređenje dve kružne niske na jednakost bez potrebe za njihovom normalizacijom. Ovaj algoritam je našao primenu u brzom generisanju određenih hemijskih struktura bez njihovog ponavljanja.

Vidi još

• Lindonova reč
• Knut-Moris-Prat algoritam