A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Space-Saving Approximation Algorithm for Grammar-Based Compression Um algoritmo de aproximação que economiza espaço para compactação baseada em gramática

Hiroshi SAKAMOTO, Shirou MARUYAMA, Takuya KIDA, Shinichi SHIMOZONO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

É apresentado um algoritmo de aproximação com uso eficiente de espaço para o problema de compressão baseado em gramática, que solicita que uma determinada string encontre a menor gramática livre de contexto que deriva a string. Para o comprimento de entrada n e um tamanho ideal de CFG g, o algoritmo consome apenas O(g log g) espaço e O(n log*n) tempo para alcançar O((registro*n)registro n) relação de aproximação para a compressão ideal, onde log*n é o número máximo de logaritmos que satisfazem log log log n > 1. Esta relação é, portanto, considerada quase O(registro n), que é a melhor relação de aproximação atualmente. Enquanto g depende da string, sabe-se que g=Ω(log n) e para cordas de k-alfabeto de letras [12].

Publicação
IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.158-165
Data de publicação
2009/02/01
Publicitada
ISSN online
1745-1361
DOI
10.1587/transinf.E92.D.158
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science)
Categoria

autores

Palavra-chave