Compreendendo a compactação / codificação em tempo linear

8

Estou lendo o artigo NJ Larsson, A. Moffat: Compactação baseada em dicionário offline , que descreve um algoritmo de compactação que, se bem entendi, é bastante semelhante à codificação de pares de bytes .

Dada uma string de comprimento , estou tentando entender como se pode compactá-la no tempo linear, , com esse método de compactação. Como exatamente isso é feito? Eu li o jornal, mas ainda não entendo como eles atingem o tempo linear, então talvez eu entenda isso explicado de uma maneira diferente.SnO(n)

Minha primeira confusão surge na primeira etapa do algoritmo, onde encontramos o par mais comum, por exemplo, no abcababcabcpar mais comum abseria substituído por um novo símbolo, digamos XcXXcXc. Não entendo como podemos encontrar o par mais comum com rapidez suficiente. Minha abordagem ingênua seria olhar primeiro para o primeiro par abe depois contar o número de ocorrências, depois olhar para o próximo par bce contar o número de ocorrências etc. No entanto, isso já daria apenas para encontrando o par mais comum uma vez .O(n2)

A seguir, mesmo que eu entenda como encontrar o par mais comum no tempo . Meu próximo problema é que, não precisamos encontrar o par mais comum até vezes? E, portanto, isso daria um tempo total de ?O(n)O(n)O(n2)

Eff
fonte
Você deve fazer uma pergunta mais específica. Reiterar um artigo em palavras diferentes parece amplo para este site. Onde os autores o perdem?
precisa saber é o seguinte
@adrianN Eu escrevi um pouco mais sobre o que especificamente estou confuso.
Eff
O artigo assumiu que ele usaria a tabela de hash e a contaria como , que nesse caso pode ser substituído pelo wlog pela árvore de sufixos como . Acabei de ler o texto, sua pergunta ainda é muito exigente, mas realmente não vejo por que você gastaria apenas para um item. O(n)O(n)O(n2)
Mal
@Evil Então, você está dizendo que se poderia construir uma árvore de sufixos de in time (BTW, eu ainda não entendo quando é possível construir uma árvore de sufixos em tempo linear e quando é necessário ). Em seguida, encontramos a substring mais frequente na árvore de sufixos no tempo . Corrigir? SΘ(n)O(nlogn)Θ(n)
Eff
Eu? Não. Mas Ukkonen disse algumas palavras sobre isso. para alfabeto de tamanho constante e em geral. Em seguida, podemos ordenar por frequências em ou até explorar pequenos números naturais para contar a classificação. Não tenho certeza se algo 1 ~ n é , desculpe por não responder a essa parte. O(n)O(nlogn)O(nlogn)Θ(n)
Mal

Respostas:

1

Verifiquei o código, reli o artigo e parece que o algoritmo não está executando em da maneira que você descreveu. As chamadas recursivas para encontrar pares funcionam emO(n)
O(nlogn)dividido por constante se você quiser empacotá-lo até o fim. De fato, a estrutura abaixo mantém ponteiros para a primeira ocorrência de pares, divide a fila de pares por ocorrências para torná-la eficiente, mas ainda linear. Por outro lado, analisando o código escrito por Ph.D. aluno do autor, descobri vários truques - o comprimento dos pares (o nome original) é dado como parâmetro (o padrão é 2) e a recorrência é limitada pelo parâmetro, que pode descartar chamadas adicionais (o padrão é de cerca de 5 níveis), com capacidade de fazer apenas um passe ou empurrar até o fim. O código padrão é executado em , mas não produz uma compactação ideal. Há também opções para preferir memória, hora ou ser neutro.O(n)

O documento e o código mostram o uso da tabela de hash, que é executada apenas no tempo constante esperado, mas a função fornecida funciona muito bem com caracteres. Além disso, o código limita o comprimento da entrada por código constante constante.

Mudar a hashtable para a árvore de sufixos e reescrever a parte da recorrência em pares parciais de contabilidade pode gerar melhores resultados - não tenho certeza se isso é possível torná-lo , essa provavelmente seria uma pergunta diferente.O(n)

Também existe um truque usado para impedir que o espaço vazio seja percorrido - o início do bloco vazio aponta para o primeiro caractere não vazio, mas isso apenas acelera o deslocamento, ainda com tempo linear. A parte responsável por esse comportamento é substituir pares pelo novo personagem a cada iteração - manter apenas regras de reescrita e operar com elas seria mais rápido, mas ainda assim o acesso para verificar se novos pares foram introduzidos exigiria a verificação de regras de reescrita nos novos - no caso, construímos uma árvore binária completa com pares nas folhas, de forma que, após substituir o par por um novo caractere e concatenar com o pai, obtivemos novos pares nas folhas até a raiz - existem bate-papo então pares, então ,nn2n4n8 , ... Você vê o padrão, existem pares, mas de acordo com algoritmo descrição deste produtividade do feijoeiro Ter tempo apenas passagens de entrada.n162nO(nlogn+n)

Mal
fonte