Usuário(a):Jflima1/Testes
![]() | Esta é uma página de testes de Jflima1, uma subpágina da principal. Serve como um local de testes e espaço de desenvolvimento, desta feita não é um artigo enciclopédico. Para uma página de testes sua, crie uma aqui. Como editar: Tutorial • Guia de edição • Livro de estilo • Referência rápida Como criar uma página: Guia passo a passo • Como criar • Verificabilidade • Critérios de notoriedade |
Em ciência da computação, uma estrutura de dados sucinta é uma estrutura de dados que usa uma quantidade de espaço que está "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[1] para codificar vetores de bits, á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 estrutura de dados comprimida, 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.
Dicionários sucintos
[editar | editar código-fonte]Dicionários indexáveis sucintos, também chamados dicionários rank/select, formam a base de uma série de técnicas de representação sucinta, incluindo árvores binárias, árvores -árias e multiconjuntos.[2] O problema básico é o armazenamento de um subconjunto de um universo normalmente representado como uma matriz de bits onde se, e somente se, . Um dicionário indexável suporta os métodos usuais em dicionários (consultas e inserções/deleções no caso dinâmico), bem como as seguintes operações:
para .
Em outras palavras, devolve o número de elementos igual a até a posição enquanto devolve a posição da -ésima ocorrência de .
Há uma representação simples[3] que utiliza bits de armazenamento (a matriz de bits original e uma estrutura auxiliar ) e suporta operações rank e select em tempo constante. Nessa representação é usada uma ideia similar à range-minimum queries; há um número constante de recursões antes que seja alcançado um subproblema de tamanho limitado. O array de bits é particionado em grandes blocos de tamanho bits e pequenos blocos de tamanho bits. Para cada grande bloco, o rank de seu primeiro bit é armazenado em uma tabela separada ; cada uma destas entradas custa bits para um total de bits de armazenamento. Dentro de um grande bloco, outro diretório armazena o rank de cada um dos pequenos blocos nele contidos. A diferença, neste caso, é são necessários somente bits para cada entrada, visto que somente as diferenças desde o rank do primeiro bit no bloco grande precisam ser armazenadas. Portanto, esta table ocupa um total de bits. Uma tabela de pesquisa pode, então, ser usada para armazenar a resposta para qualquer consulta de rank possível em uma cadeia de bits de tamanho for ; isto requer bits de espaço de armazenamento. Assim, visto que cada uma dessas tabelas ocupa espaço , esta estrutura de dados suporta consultas de rank em tempo e espaço bits.
Para responder a uma consulta para em tempo constante, um algoritmo de tempo constante calcula:
Na prática, a tabela de pesquisa pode ser substituída pode operações bit a bit e tabelas menores para efetuar a busca do número de bits definidos nos blocos pequenos. Isto é frequentemente benéfico, visto que estruturas de dados sucintas encontram seus usos em grandes conjuntos de dados, caso no qual os cache misses tornam-se mais frequentes e aumentam as chances de uma tabela de pesquisa ser removida das caches mais próximas da CPU.[4] Consultas select podem ser facilmente suportadas efetuando-se uma busca binária na mesma estrutura auxiliar usada para o rank; entretanto, o custo de tempo dessa operação é no pior caso. Uma estrutura mais complicada usando bits de armazenamento adicional pode ser usada para suportar select em tempo constante.[5] Na prática, muitas dessas soluções têm constantes ocultas na notação , as quais dominam antes que qualquer vantagem assintótica torne-se aparente; implementações utilizando operações de palavra completa e blocos alinhados a palavras normalmente apresentam melhor desempenho prático.[6]
Dicionários de entropia comprimida
[editar | editar código-fonte]A abordagem de espaço pode ser melhorada notando-se que existem distinct -subconjuntos distintos de (ou strings binárias de tamanho com exatamente 1’s), e, portanto, é um mínimo teórico de informação no número de bits necessários para armazenar . Existe um dicionário sucinto (estático) que alcança este limite, nomeadamente usando espaço .[7] Esta estrutura pode ser estendida para suportar consultas rank and select e ocupa espaço .[8] Este limite pode ser reduzido para uma compensação espaço/tempo reduzindo o espaço de armazenamento do dicionário para com consultas de custo de tempo.[9]
Exemplos
[editar | editar código-fonte]Uma string de terminação nula (string em C) ocupa espaço Z + 1, e é, portanto, implícita. Uma string arbitrária, coom tamanho arbitrário (string em Pascal) ocupa espaço Z + log(Z), e é, portanto, sucinta. Se existe um tamanho máximo – o que é o caso na prática, dado que 232 = 4 GiB de dados é uma string muito longa, e 264 = 16 EiB de dados é maior que qualquer string na prática – então, uma string com tamanho é também implícita, ocupando espaço Z + k, onde k é o número de dados para representar o tamanho máximo (e.g., bytes em uma palavra).
Quando uma sequência com itens de tamanho variável (tal como strings) precisa ser codificada, existem diversas possibilidades. Uma abordagem direta é armazenar um tamanho e um item em cada registro – estas podem então serem posicionadas uma após a outra. Isto permite encontrar de maneira eficiente o próximo elemento, mas não encontrar o kth elemento. Uma alternativa é organizar os itens em ordem com um delimitador (e.g., uma string com terminação nula). Neste caso, é utilizado um delimitador em lugar de um tamanho, e é substancialmente mais lenta, uma vez que a sequência inteira deve ser lida em busca dos delimitadores. Ambas os casos são eficientes em espaço. Uma alternativa é a separação de maneira independente: os elementos podem simplesmente serem colocados um após o outro, sem delimitadores. Os limites de um item podem ser armazenados como uma sequência de tamanho, ou melhor, deslocamentos dentro dessa sequência. Alternativamente, uma outra string binária consistindo de 1s nas posições em que um item começa e 0s nas demais posições é codificada conjuntamente. Dada esta cadeia, a função pode rapidamente determinar onde cada item começa, dado o seu índice.[10] Isto é compacto, mas não sucinto, uma vez que ocupa espaço 2Z, que é O(Z).
Um outro exemplo é a representação de uma árvore binária: uma árvore binária arbitrária com nós pode ser representada em bits, suportando ainda operações em qualquer dos nós, o que inclui encontrar o seu pai, sues filhos da esquerda e da direita e devolver sua subárvore, cada qual em tempo constante. O número de árvores binárias distintas com nós é . Para um , isto é aproximadamente ; assim, é necessário ao menos bits para a codificação. Uma árvore binária sucinta, portanto, ocupa bits por nó.
Ver também
[editar | editar código-fonte]- Minimal perfect hash function
Referências
- ↑ Jacobson, G. J (1988). Succinct static data structures (Ph.D.). Pittsburgh, PA: Carnegie Mellon University
- ↑ Sadakane, K.; R. Grossi (2006). «Squeezing succinct data structures into entropy bounds» (PDF). Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. pp. 1230–1239. ISBN 0-89871-605-5
- ↑ Jacobson, G. (1989). «Space-efficient static trees and graphs» (PDF)
- ↑ González, R.; S. Grabowski; V. Mäkinen; G. Navarro (2005). «Practical implementation of rank and select queries» (PDF). Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). pp. 27–38
- ↑ Clark, D. (1998). «Compact pat trees» (PDF)
- ↑ Vigna, S. (2008). «Broadword implementation of rank/select queries» (PDF). Experimental Algorithms. Lecture Notes in Computer Science. 5038: 154–168. ISBN 978-3-540-68548-7. doi:10.1007/978-3-540-68552-4_12
- ↑ Brodnik, A.; J. I Munro (1999). «Membership in constant time and almost-minimum space» (PDF). SIAM J. Comput. 28 (5): 1627–1640. doi:10.1137/S0097539795294165
- ↑ Raman, R.; V. Raman; S. S Rao (2002). «Succinct indexable dictionaries with applications to encoding k-ary trees and multisets» (PDF). Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 233–242. ISBN 0-89871-513-X
- ↑ Pătraşcu, M. (2008). «Succincter» (PDF). Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on. pp. 305–313
- ↑ Belazzougui, Djamal. «Hash, displace, and compress» (PDF)