Estrutura de dados sucinta

Em ciência da computação, uma estrutura de dados sucinta é uma estrutura de dados que usa uma quantidade de espaço que é "próxima" ao mínimo espaço teórico de informação, mas que, ao contrário de outras representações comprimidas, permite operações de consulta eficientes. O conceito foi originalmente introduzido por Jacobson para codificar , árvores não rotuladas e grafos planares. Ao contrário dos algoritmos de compressão sem perda de dados em geral, estruturas de dados sucintas sem que seja necessária a descompressão. Um conceito relacionado é o de , na qual o tamanho da estrutura de dados depende dos dados em particular que estão sendo representados. Suponha que é número ótimo teórico de informação de bits necessários para armazenar um certo conjunto de dados. Uma representação desses dados é chamada: * implícita, se necessita bits de espaço, * sucinta se necessita bits de espaço, e * compacta se necessita bits de espaço. Por exemplo, uma estrutura de dados que usa bits de armazenamento é compacta, bits é sucinta, bits também é sucinta, e bits é implícita. Estruturas implícitas são, portanto, geralmente reduzidas para armazenar informações usando alguns permutações dos dados de entrada; o exemplo mais conhecido exemplo é a heap.