Palavra fatoração em de tempo

12

Dadas duas cadeias , escrevemos para sua concatenação. Dada uma cadeia e número inteiro , escreve-se para a concatenação de cópias de . Agora, dada uma string, podemos usar essa notação para 'compactá-la', ou seja, pode ser escrito como . Vamos chamar o peso de uma compactação do número de caracteres que aparecem nela; portanto, o peso de é dois, e o peso de (uma compactação de ) é três (separadoS1,S2S1S2Sk1(S)k=SSSkSAABAAB((A)2B)2((A)2B2)(AB)2AABABAA s são contados separadamente).

Agora considere o problema de calcular a compressão 'mais leve' de uma determinada sequência com . Depois de pensar um pouco, existe uma abordagem de programação dinâmica óbvia que é executada em ou dependendo da abordagem exata.S|S|=nO(n3logn)O(n3)

No entanto, disseram-me que esse problema pode ser resolvido em , embora não seja possível encontrar nenhuma fonte sobre como fazer isso. Especificamente, esse problema foi apresentado em um concurso de programação recente (problema K aqui , últimas duas páginas). Durante a análise, foi apresentado um algoritmo , e no final foi mencionado o limite pseudo-quadrático ( aqui na marca de quatro minutos). Infelizmente, o apresentador apenas se referiu a 'um lema complicado de combinatória de palavras', então agora eu vim aqui para pedir a solução :-)O(n2logn)O(n3logn)

Timon Knigge
fonte
Apenas uma propriedade aleatória: se, para uma sequência , temos S = X a = Y b , também deve ser S = Z | S | / gcd ( | X | , | Y | ) [Corrigi um erro aqui], com Z tendo o comprimento gcd ( | X | , | Y | ) (que não pode ser maior que X ou YSS=Xa=YbS=Z|S|/gcd(|X|,|Y|)Zgcd(|X|,|Y|)XY) Não tenho certeza de como isso é útil. Se você já descobriu que e sabe que S contém pelo menos 2 caracteres distintos, e agora está procurando um Y menor que S = Y b , então você só precisa tentar os prefixos Y de X com comprimento que divide | X | . S=XaSYS=YbYX|X|
Jrandom_hacker
O problema é que, mesmo depois de reduzir todo o possível , você ainda precisa agregar a resposta por um DP cúbico em subsegmentos (por exemplo, D P [ l , r ] = min k D P [ l , k ] + D P [ k + 1 , r ] ), por isso ainda há algum trabalho extra a ser feito depois disso ...XaDP[l,r]=minkDP[l,k]+DP[k+1,r]
Timon Knigge
Eu vejo o que você quer dizer. Acho que você precisa de algum tipo de relação de dominância que elimine alguns valores de da necessidade de serem testados - mas não consegui pensar em nenhum. Em particular, considerei o seguinte: Suponha que S [ 1 .. i ] tenha uma fatoração ótima S [ 1 .. i ] = X Y k com k > 1 ; é possível que exista uma solução ótima na qual S seja fatorado como X Y j Z com j < k ? Infelizmente a resposta é sim: parakS[1..i]S[1..i]=XYkk>1SXYjZj<k , S [ 1..4 ] possui fatoração ótima ( A B ) 2 , mas a fatoração ideal única para S é A B ( A B C ) 2 . S=ABABCABCS[1..4](AB)2SAB(ABC)2
Jrandom_hacker

Respostas:

1

Se não estou lhe entendendo mal, acho que a fatoração de custo mínimo pode ser calculada no tempo de O(n2) seguinte maneira.

Para cada índice i, iremos calcular um grupo de valores (pi,ri) para =1,2, , como se segue. Seja pi11 o número inteiro menor, de modo que exista um número inteiro r2 satisfazendo

S[irpi1+1,ipi1]=S[i(r1)pi1+1,i].
For this particular pi1, let ri1 be the largest r with this property. If no such pi exists, set Li=0 so we know there are zero (pi,ri) values for this index.

Let pi2 be the smallest integer strictly bigger than (ri11)pi1 satisfying, likewise,

S[iri2pi2+1,ipi2]=S[i(ri21)pi2+1,i]
for some ri22. Like before, take ri2 to be the maximal one having fixed pi2. In general pi is the smallest such number strictly bigger than (ri11)pi1. If no such pi exists, then Li=1.

Note that for each index i, we have Li=O(log(i+1)) due to pi values increasing geometrically with . (if pi+1 exists, it's not just strictly bigger than (ri1)pi but bigger than that by at least pi/2. This establishes the geometric increase.)

Suppose now all (pi,ri) values are given to us. The minimum cost is given by the recurrence

dp(i,j)=min{dp(i,j1)+1,min(dp(i,jrjpj)+dp(jrjpj+1,jpj))}
with the understanding that for i>j we set dp(i,j)=+. The table can be filled in O(n2+njLj) time.

We already observed above that jLj=O(jlog(j+1))=Θ(nlogn) by bounding the sum term by term. But actually if we look at the whole sum, we can prove something sharper.

Consider the suffix tree T(S) of the reverse of S (i.e., the prefix tree of S). We will charge each contribution to the sum iLi to an edge of T(S) so that each edge will be charged at most once. Charge each pij to the edge emanating from nca(v(i),v(ipij)) and going towards v(ipij). Here v(i) is the leaf of the prefix tree corresponding to S[1..i] and nca denotes the nearest common ancestor.

This shows that O(iLi)=O(n). The values (pij,rij) can be calculated in time O(n+iLi) by a traversal of the suffix tree but I will leave the details to a later edit if anyone is interested.

Let me know if this makes sense.

Mert Sağlam
fonte
-1

There is your initial string S of length n. Here is the pseudo-code of the method.

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

I intentionally gave little details on "end brackets" as it needs lot of steps to stack and unstack which would let the core method unclear. The idea is to test an eventual further contraction inside the first one. for exemple ABCBCABCBC => (ABCBC)² => (A(BC)²)².

So the main point is to look for large periods first. Note that S[i] is the ith term of S skipping any "(", ")" or power.

  • i-loop is O(n)
  • j-loop is O(n)
  • r+k-loops is O(log(n)) as it stops at first difference

This is globally O(n²log(n)).

Optidad
fonte
It's not clear to me that the r and k loops are O(log n) -- even separately. What ensures that a difference is found after at most O(log n) iterations?
j_random_hacker
Do I understand correctly that you are compressing greedily? Because that is incorrect, consider e.g. ABABCCCABCCC which you should factorize as AB(ABC^3)^2.
Timon Knigge
Yeah you are totally right about that, I've to think about this.
Optidad