Um problema em aberto na compressão de dados
Imagem de capa: flickr
Por Vinicius Tikara Venturi Date
Atualmente, há a presença de um grande fluxo de dados por toda parte, desde o sequenciamento de genomas na bioinformática (Zachary Stephens, 2015), até o armazenamento de repositórios de programas, como no GitHub. Em sua maior parte, esse tipo de informação é altamente repetitiva. Dessa característica surge um problema:
Dada uma compressão desses dados, como verificar que tal compressão foi boa?
Em primeiro lugar, precisamos definir como representar dados. Eles podem ser representados com o uso de strings, que são cadeias de caracteres. Desta forma, a compressão busca explorar padrões em strings para diminuir seu espaço armazenado. Afinal de contas, se conseguimos utilizar menos espaço podemos armazenar mais dados e, consequentemente, processar mais dados.
A princípio, para abordar o problema de compressão podemos partir para a teoria da informação, com a Entropia da Informação (Claude Shannon, 1948), que define um limite inferior para a compressão de dados sem perdas (lossless).
Da entropia da informação surge a abordagem de compressão estatística, que são métodos de compressão que tentam atingir o limite inferior declarado por Shannon. Entretanto, esse tipo de compressão falha ao trabalhar com dados repetitivos: como a entropia não consegue capturar e aproveitar as recorrências de um texto, ela não é adequada para medir a sua repetitividade. Desta forma, precisamos partir para outros tipos de abordagens.
Um desses outros caminhos para tentar capturar a repetitividade é a Complexidade de Kolmogorov (Andrei Kolmogorov, 1965), que descreve strings em termos de uma linguagem universal. Por exemplo, a string “aaabbbccc” pode ser descrita como “3a3b3c”. Apesar de ser o melhor resultado teórico que temos, essa abordagem possui um problema: nenhum algoritmo consegue computá-la (Gregory Chaitin, 1995), pois se fosse computável conseguiríamos resolver o Problema da Parada — um problema não computável clássico da Teoria da Computação (Alan Turing, 1936).
Portanto, a próxima alternativa é tentar encontrar uma métrica que se aproxime da Complexidade de Kolmogorov, surge outra abordagem de compressão: os compressores baseados em dicionários. Esses compressores mantêm uma lista de palavras e substituem essas palavras por tokens (símbolos menores que as palavras originais) no texto a ser comprimido. Os utilitários gzip e 7zip utilizam esse tipo de compressor.
As métricas de repetitividade decorrem desses compressores, porém, elas surgem a posteriori: foram enunciadas a partir de uma característica observada de cada compressor, i.e., foram criadas de forma ad-hoc. A Tabela 1 explicita algumas delas.
| Tipo de Compressão | Métrica |
| Lempel-Ziv | z frases produzidas |
| Esquemas macro bidirecionais | b frases da menor avaliação |
| Compressão baseada em gramática | Tamanho g da menor gramática |
| Transformada de Burrows-Wheeler | r sequências maximais da mesma letra |
| Sistemas de Colagem | c <= grl , onde grl é o tamanho da menor gramática run-length |
| Grafo de Palavras Direcionado Acíclico Compacto (CDAWG) | O tamanho e do menor grafo |
Tabela 1: Exemplo de compressores baseados em dicionários e suas métricas
É dessa dependência das métricas com seus respectivos compressores que surgem os string attractors (Kempa e Prezza, 2018), que, além de abordar o problema de capturar a repetitividade, tentam ser uma estrutura universal.
Um string attractor de uma string S é um conjunto de posições que possui a seguinte propriedade: todas substrings de S — intervalos contíguos de S — cruzam alguma posição do attractor. Por exemplo, a string “abcaca” tem como string attractor o conjunto de posições 2, 3 e 4. Note que o conjunto de posições 1, 2, 3 e 4 também é um string attractor, entretanto a posição 1 não é necessária.
O ponto chave do string attractor são as equivalências entre sua métrica – gamma – e as métricas de compressores já estabelecidos. Desta forma, os string attractors são uma “âncora” no estudo dos compressores: conseguimos obter o valor de gamma a partir de compressores baseados em dicionários e vice-versa.
A Imagem 1 explicita as métricas da Tabela 1 e suas equivalências com a métrica gamma.
Imagem 1: A métrica gamma e alguma de suas equivalências com outras métricas; a seta de uma métrica A para uma métrica B indica que existe uma transformação de A para B
A métrica gamma é definida como o tamanho do menor string attractor de uma dada string. Encontrar o menor string attractor está na classe de problemas NP–completo: não existe algoritmo polinomial conhecido para computar gamma — por polinomial entendemos eficiente.
Por conta dessa característica, a métrica delta é proposta (Anders Roy Christiansen, 2020). Essa métrica é definida como um limitante inferior de gamma e, ao mesmo tempo, pertence à classe de problemas P, isto é, existe algoritmo polinomial para obtê-la.
Por ser uma métrica recente, não sabemos de fato se ela captura a repetitividade. Estudos do seu comportamento combinatório, de seu cálculo em espaço limitado (Giulia Bernardini, 2023) e até mesmo sua viabilidade como métrica são desafios que precisam ser abordados antes de avançarmos no problema de medir a repetitividade em strings.
Com esse avanço no estudo da métrica delta, pesquisadores conseguem mudar seu foco para a aplicação desta métrica em algoritmos, como em estruturas que possam ser operadas em sua forma comprimida (Dominik Kempa 2023). Portanto, caso seja adequada, a métrica delta poderá auxiliar em perguntas mais sofisticadas sobre dados repetitivos e, consequentemente, na eficiência de armazenamento de dados desse tipo.
Referências
BERNARDINI, Giulia et al. Substring Complexity in Sublinear Space. In: 34th International Symposium on Algorithms and Computation (ISAAC 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2023.
CHAITIN, Gregory J.; ARSLANOV, Asat; CALUDE, Cristian. Program-size complexity computes the halting problem. Department of Computer Science, The University of Auckland, New Zealand, 1995.
CHRISTIANSEN, Anders Roy et al. Optimal-time dictionary-compressed indexes. ACM Transactions on Algorithms (TALG), v. 17, n. 1, p. 1-39, 2020.
KEMPA, Dominik; KOCIUMAKA, Tomasz. Collapsing the hierarchy of compressed data structures: Suffix arrays in optimal compressed space. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2023. p. 1877-1886.
KEMPA, Dominik; PREZZA, Nicola. At the roots of dictionary compression: string attractors. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018. p. 827-840.
KOLMOGOROV, Andrei N. Three approaches to the quantitative definition of information’. Problems of information transmission, v. 1, n. 1, p. 1-7, 1965.
SHANNON, Claude Elwood. A mathematical theory of communication. The Bell system technical journal, v. 27, n. 3, p. 379-423, 1948.
STEPHENS, Zachary D. et al. Big data: astronomical or genomical?. PLoS biology, v. 13, n. 7, p. e1002195, 2015.
TURING, Alan Mathison et al. On computable numbers, with an application to the Entscheidungsproblem. J. of Math, v. 58, n. 345-363, p. 5, 1936.
Autoria
Vinicius Tikara Venturi Date: Sou estudante do programa de pós-graduação em informática da UFPR. Sou graduado pela UFPR em Ciência da Computação (2023) e tenho interesse em Teoria da Computação. Minha área de estudo são strings, com foco no estudo da compressão de dados altamente repetitivos. Qualquer dúvida, crítica ou fato curioso me mande um oi: tikaradate@gmail.com
Como citar esta matéria:
DATE, Vinicius Tikara Venturi. Um problema em aberto na compressão de dados. SBC Horizontes. ISSN 2175-9235. 04 nov. 2024. Disponível em: <url>. Acesso em: dd mês aaaa.
