estrutura de dados compactado - Compressed data structure

O termo estrutura de dados comprimido surge nas ciências da computação subcampos de algoritmos , estruturas de dados e ciência da computação teórica . Ele refere-se a uma estrutura de dados, cujas operações são aproximadamente tão rápido quanto os de uma estrutura de dados convencional para o problema, mas cujo tamanho pode ser substancialmente menor. O tamanho da estrutura de dados comprimido é, tipicamente, altamente dependente da entropia dos dados a serem representados.

Exemplos importantes de estruturas de dados comprimidos incluem a matriz sufixo comprimido e o índice de FM , ambos os quais podem representar um texto arbitrário de caracteres T para correspondência de padrões . Dado qualquer padrão de entrada P , eles suportam a operação de encontrar se e onde P aparece em T . O tempo de busca é proporcional à soma do comprimento do padrão P , uma função de crescimento muito lento do comprimento do texto T , eo número de partidas relatados. O espaço que ocupam é aproximadamente igual ao tamanho do texto T , em forma comprimida-entropia, tal como a obtida por Predição por correspondência parcial ou gzip . Além disso, ambas as estruturas de dados são auto-indexação, em que eles podem reconstruir o texto T de uma forma de acesso aleatório e, portanto, o texto subjacente T pode ser descartado. Em outras palavras, eles simultaneamente, proporcionar uma representação comprimida e rapidamente pesquisável de texto T . Eles representam uma melhoria espaço substancial em relação ao convencional árvore de sufixo e variedade sufixo , que ocupam muitas vezes mais espaço do que o tamanho da T . Eles também suportam busca de padrões arbitrários, ao contrário do índice invertido , que pode suportar apenas buscas baseadas em palavras. Além disso, os índices invertidos não têm o recurso de auto-indexação.

Uma noção relacionada importante é que de uma estrutura de dados sucinta , que utiliza o espaço de mais ou menos igual ao mínimo informação teórica, que é uma noção de pior caso do espaço necessário para representar os dados. Em contraste, o tamanho de uma estrutura de dados comprimido depende dos dados particulares a serem representados. Quando os dados são compressíveis, como é frequentemente o caso na prática para o texto de linguagem natural, a estrutura de dados comprimidos podem ocupar espaço muito próximo do mínimo informação teórica, e significativamente menos espaço do que a maioria dos esquemas de compressão.

Referências