Faktoryzacji słowo w Czas

12

Biorąc pod uwagę dwa ciągi , piszemy dla ich konkatenacji. Biorąc pod uwagę ciąg i liczba całkowita , napisać dla złączonych kopii . Teraz biorąc pod uwagę ciąg, możemy użyć tego zapisu do „skompresowania” go, tzn. można zapisać jako . Nazwijmy ten ciężar kompresji liczba znaków w niej występujących, więc waga jest dwa, a waga (a kompresja od ) jest trzy (oddzielnyS1,S2S1S2Sk1(S)k=SSSkSAABAAB((A)2B)2((A)2B2)(AB)2AABABAA są liczone osobno).

Rozważmy teraz problem obliczania „najlżejszej” kompresji danego ciągu pomocą . Po pewnym namyśle istnieje oczywiste podejście do programowania dynamicznego, które działa w lub zależności od dokładnego podejścia.S|S|=nO(n3logn)O(n3)

Powiedziano mi jednak, że ten problem można rozwiązać w czasie , chociaż nie mogę znaleźć żadnych źródeł, jak to zrobić. W szczególności problem ten został podany w ostatnim konkursie programistycznym ( tutaj problem K , ostatnie dwie strony). Podczas analizy przedstawiono algorytm , a na końcu wspomniano o granicy pseudokwadratowej ( tutaj przy znaku czterominutowym). Niestety prezenter wspomniał tylko o „skomplikowanym słowie kombinatoryki”, więc teraz przyszedłem tutaj, aby poprosić o rozwiązanie :-)O(n2logn)O(n3logn)

Timon Knigge
źródło
Po prostu losowa właściwość: jeśli dla ciągu mamy , to musi to być również [ Naprawiłem tutaj błąd], przy czym ma długość (która nie może być dłuższa niż ani ). Nie jestem jednak pewien, jak przydatne jest to. Jeśli już odkryłeś, że i wiesz, że zawiera co najmniej 2 różne znaki, a teraz szukasz krótszego takiego jak , wystarczy wypróbować przedrostki o o długości który dzieli.SS=Xa=YbS=Z|S|/gcd(|X|,|Y|)Zgcd(|X|,|Y|)XYS=XaSYS=YbYX|X|
j_random_hacker
Problem polega na tym, że nawet po zmniejszeniu wszystkich możliwych , nadal musisz agregować odpowiedź sześciennym DP nad podsekcjami (tj. ), więc jest jeszcze trochę pracy do zrobienia po tym ...XaDP[l,r]=minkDP[l,k]+DP[k+1,r]
Timon Knigge
Rozumiem, co masz na myśli. Myślę, że potrzebujesz pewnego rodzaju relacji dominacji, która eliminuje niektóre wartości z konieczności testowania - ale nie byłam w stanie wymyślić żadnej z nich. W szczególności rozważyłem, co następuje: Załóżmy, że ma optymalną faktoryzację przy ; czy jest możliwe, że istnieje optymalne rozwiązanie, w którym jest rozkładane na z ? Niestety odpowiedź brzmi tak: dla , ma optymalne , ale unikalnym optymalnym rozkładem na czynniki dla jest .kS[1..i]S[1..i]=XYkk>1SXYjZj<kS=ABABCABCS[1..4](AB)2SAB(ABC)2
j_random_hacker

Odpowiedzi:

1

Jeśli cię nie rozumiem, myślę, że minimalizację faktoryzacji kosztów można obliczyć w czasie w następujący sposób.O(n2)

Dla każdego indeksu i wiązkę wartości dla w następujący sposób. Niech będzie najmniejszą liczbą całkowitą, tak że istnieje liczba całkowita spełniającaDla tego konkretnego , niech będzie największym z tą właściwością. Jeśli nie ma takiego , ustaw , abyśmy wiedzieli, że dla tego indeksu istnieją wartości zerowe .(pi,ri)=1,2,pi11r2

S[irpi1+1,ipi1]=S[i(r1)pi1+1,i].
pi1ri1rpiLi=0(pi,ri)

Niech będzie najmniejszą liczbą całkowitą ściśle większą niż spełniającą podobnie, dla niektórych . Tak jak poprzednio, weź za maksymalny z ustalonym . Ogólnie jest najmniejszą taką liczbą ściśle większą niż . Jeśli nie ma takiego , to .pi2(ri11)pi1

S[iri2pi2+1,ipi2]=S[i(ri21)pi2+1,i]
ri22ri2pi2pi(ri11)pi1piLi=1

Zauważ, że dla każdego indeksu i mamy powodu wzrostu wartości geometrycznie wraz z . (jeśli istnieje , to nie jest ono ściśle większe niż ale większe niż o co najmniej To określa wzrost geometryczny. )Li=O(log(i+1))pipi+1(ri1)pipi/2

Załóżmy, że teraz wszystkie wartości są nam dane. Minimalny koszt jest określony przez wznowienie przy założeniu, że dla ustawiamy . Tabela może być wypełniona czasem .(pi,ri)

dp(i,j)=min{dp(i,j1)+1,min(dp(i,jrjpj)+dp(jrjpj+1,jpj))}
i>jdp(i,j)=+O(n2+njLj)

Zauważyliśmy już powyżej, że poprzez ograniczenie sumy warunek do terminu. Ale tak naprawdę, jeśli spojrzymy na całą sumę, możemy udowodnić coś ostrzejszego.jLj=O(jlog(j+1))=Θ(nlogn)

Rozważ drzewo sufiksów z tyłu (tj. Drzewo prefiksów S). każdą składkę sumą do krawędzi , aby każda krawędź została obciążona maksymalnie raz. Naładuj każdy do krawędzi emanującej z i idąc w kierunku . Tutaj jest liściem drzewa prefiksów odpowiadającego a nca oznacza najbliższego wspólnego przodka.T(S)SiLiT(S)pijnca(v(i),v(ipij))v(ipij)v(i)S[1..i]

To pokazuje, że . Wartości można obliczyć w czasie przez przejście do drzewa sufiksów, ale pozostawię szczegóły do ​​późniejszej edycji, jeśli ktoś jest zainteresowany.O(iLi)=O(n)(pij,rij)O(n+iLi)

Daj mi znać, jeśli to ma sens.

Mert Sağlam
źródło
-1

Jest twój początkowy ciąg S o długości n. Oto pseudo-kod metody.

next_end_bracket = n
for i in [0:n]: # main loop

    break if i >= length(S) # due to compression
    w = (next_end_bracket - i)# width to analyse

    for j in [w/2:0:-1]: # period loop, look for largest period first
        for r in [1:n]: # number of repetition loop
            if i+j*(r+1) > w:
                break r loop

            for k in [0:j-i]:
                # compare term to term and break at first difference
                if S[i+k] != S[i+r*j+k]:
                    break r loop

        if r > 1:
            # compress
            replace S[i:i+j*(r+1)] with ( S[i:i+j] )^r
            # don't forget to record end bracket...
            # and reduce w for the i-run, carrying on the j-loop for eventual smaller periods. 
            w = j-i

Celowo podałem trochę szczegółów na temat „nawiasów końcowych”, ponieważ wymaga to wielu kroków do układania w stosy i rozpakowywania, co pozwoliłoby na wyjaśnienie podstawowej metody. Chodzi o to, aby przetestować ewentualny dalszy skurcz wewnątrz pierwszego. na przykład ABCBCABCBC => (ABCBC) ² => (A (BC) ²) ².

Dlatego głównym celem jest poszukiwanie dużych okresów w pierwszej kolejności. Zauważ, że S [i] jest i-tym określeniem S pomijającym dowolne „(”, „)” lub moc.

  • i-loop to O (n)
  • pętla j to O (n)
  • r + pętle k to O (log (n)), ponieważ zatrzymuje się przy pierwszej różnicy

Jest to globalnie O (n²log (n)).

Optidad
źródło
Nie jest dla mnie jasne, że pętle r i k mają wartość O (log n) - nawet osobno. Co zapewnia znalezienie różnicy po co najwyżej iteracjach O (log n)?
j_random_hacker
Czy rozumiem poprawnie, że chciwie kompresujesz? Ponieważ jest to niepoprawne, rozważ np. ABABCCCABCCC, które powinieneś uwzględnić jako AB (ABC ^ 3) ^ 2.
Timon Knigge,
Tak, masz całkowitą rację, muszę o tym pomyśleć.
Optidad