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 (oddzielny $S_1, S_2$ $S_1S_2$ $S$ $k\geq 1$ $(S)^k = SS\cdots S$ $k$ $S$ $AABAAB$ $((A)^2 B)^2$ $((A)^2 B^2)$ $(AB)^2 A$ $ABABA$ $A$ 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|=n$ $O(n^3 \log n)$ $O(n^3)$

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(n^2 \log n)$ $O(n^3 \log n)$

dynamic-programming word-combinatorics

— 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.

S

$S$

S = X^{a} = Y^{b}

$S=X^a=Y^b$

S = Z^{| S | / gcd (| X |, | Y |)}

$S=Z^{|S|/\gcd(|X|, |Y|)}$

Z

$Z$

gcd (| X |, | Y |)

$\gcd(|X|, |Y|)$

X

$X$

Y

$Y$

S = X^{a}

$S=X^a$

S

$S$

Y

$Y$

S = Y^{b}

$S=Y^b$

Y

$Y$

X

$X$

| X |

$|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 ...

X^{a}

$X^a$

D P [l, r] = min_{k} D P [l, k] + D P [k + 1, r]

$DP[l, r] = \min_k DP[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 .

k

$k$

S [1.. i]

$S[1..i]$

S [1.. i] = X Y^{k}

$S[1..i] = XY^k$

k > 1

$k>1$

S

$S$

X Y^{j} Z

$XY^jZ$

j < k

$j<k$

S = A B A B C A B C

$S=ABABCABC$

S [1..4]

$S[1..4]$

(A B)^{2}

$(AB)^2$

S

$S$

A B (A B C)^{2}

$AB(ABC)^2$

— j_random_hacker

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(n^2)$

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 . $(p_i^\ell, r_i^\ell)$ $\ell=1,2,\ldots$ $p_i^1\ge 1$ $r\ge 2$

S [i - r p_{i}^{1} + 1, i - p_{i}^{1}] = S [i - (r - 1) p_{i}^{1} + 1, i] .

$S[i-rp_i^1+1, i-p_i^1] = S[i-(r-1)p_i^1+1, i].$

p_{i}^{1}

$p_i^1$

r_{i}^{1}

$r_i^1$

r

$r$

p_{i}

$p_i$

L_{i} = 0

$L_i=0$

(p_{i}^{ℓ}, r_{i}^{ℓ})

$(p_i^\ell,r_i^\ell)$

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 . $p_i^2$ $(r_i^1-1)p_i^1$

S [i - r_{i}^{2} p_{i}^{2} + 1, i - p_{i}^{2}] = S [i - (r_{i}^{2} - 1) p_{i}^{2} + 1, i]

$S[i-r_i^2p_i^2+1, i-p_i^2] = S[i-(r_i^2-1)p_i^2+1, i]$

r_{i}^{2} \geq 2

$r_i^2\ge 2$

r_{i}^{2}

$r_i^2$

p_{i}^{2}

$p_i^2$

p_{i}^{ℓ}

$p_i^\ell$

(r_{i}^{ℓ - 1} - 1) p_{i}^{ℓ - 1}

$(r_i^{\ell-1}-1)p_i^{\ell-1}$

p_{i}^{ℓ}

$p_i^\ell$

L_{i} = ℓ - 1

$L_i=\ell-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. ) $L_i=O(\log (i+1))$ $p_i^\ell$ $\ell$ $p_i^{\ell+1}$ $(r_i^\ell-1)p_i^\ell$ $p_i^\ell/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 . $(p_i^\ell,r_i^\ell)$
$d p (i, j) = min {d p (i, j - 1) + 1, min_{ℓ} (d p (i, j - r_{j}^{ℓ} p_{j}^{ℓ}) + d p (j - r_{j}^{ℓ} p_{j}^{ℓ} + 1, j - p_{j}^{ℓ}))}$ $\mathrm{dp}(i,j) = \min\left\{\mathrm{dp}(i, j-1) + 1, \min_\ell \left(\mathrm{dp}\left(i,j - r_j^\ell p_j^\ell\right) + \mathrm{dp}(j-r_j^\ell p_j^\ell+1,j-p_j^\ell)\right)\right\}$ $i>j$ $\mathrm{dp}(i,j) = +\infty$ $O(n^2 + n\sum_j L_j)$

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. $\sum_j L_j = O(\sum_j \log (j+1)) = \Theta(n\log n)$

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(\overleftarrow{S})$ $S$ $\sum_i L_i$ $T(\overleftarrow{S})$ $p_i^j$ $\mathrm{nca}(v(i), v(i-p_i^j))$ $v(i-p_i^j)$ $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(\sum_i L_i)=O(n)$ $(p_i^j,r_i^j)$ $O(n+\sum_i L_i)$

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