Usuário(a):Jflima1/Testes

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 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 $Z$ é 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 $Z+O(1)$ bits de espaço,
• sucinta se necessita $Z+o(Z)$ bits de espaço, e
• compacta se necessita $O(Z)$ bits de espaço.

Por exemplo, uma estrutura de dados que usa $2Z$ bits de armazenamento é compacta, $Z+{\sqrt {Z}}$ bits é sucinta, $Z+\lg Z$ bits também é sucinta, e $Z+3$ 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

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 $k$-árias e multiconjuntos. O problema básico é o armazenamento de um subconjunto $S$ de um universo $U=[0\dots n)=\{0,1,\dots ,n-1\}$ normalmente representado como uma matriz de bits $B[0\dots n)$ onde $B[i]=1$ se, e somente se, $i\in S$. 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:

• $\mathbf {rank} _{q}(x)=|\{k\in [0\dots x]:B[k]=q\}|$
• $\mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}$

para $q\in \{0,1\}$.

Em outras palavras, $\mathbf {rank} _{q}(x)$ devolve o número de elementos igual a $q$ até a posição $x$ enquanto $\mathbf {select} _{q}(x)$ devolve a posição da $x$-ésima ocorrência de $q$.

Há uma representação simples que utiliza $n+o(n)$ bits de armazenamento (a matriz de bits original e uma estrutura auxiliar $o(n)$) 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 $B$ é particionado em grandes blocos de tamanho $l=\lg ^{2}n$ bits e pequenos blocos de tamanho $s=\lg n/2$ bits. Para cada grande bloco, o rank de seu primeiro bit é armazenado em uma tabela separada $R_{l}[0\dots n/l)$; cada uma destas entradas custa $\lg n$ bits para um total de $(n/l)\lg n=n/\lg n$ bits de armazenamento. Dentro de um grande bloco, outro diretório $R_{s}[0\dots l/s)$ armazena o rank de cada um dos $l/s=2\lg n$ pequenos blocos nele contidos. A diferença, neste caso, é são necessários somente $\lg l=\lg \lg ^{2}n=2\lg \lg n$ 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 $(n/s)\lg l=4n\lg \lg n/\lg n$ bits. Uma tabela de pesquisa $R_{p}$ pode, então, ser usada para armazenar a resposta para qualquer consulta de rank possível em uma cadeia de bits de tamanho $s$ for $i\in [0,s)$; isto requer $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ bits de espaço de armazenamento. Assim, visto que cada uma dessas tabelas ocupa espaço $o(n)$, esta estrutura de dados suporta consultas de rank em tempo $O(1)$ e espaço $n+o(n)$ bits.

Para responder a uma consulta para $\mathbf {rank} _{1}(x)$ em tempo constante, um algoritmo de tempo constante calcula:

• $\mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]$

Na prática, a tabela de pesquisa $R_{p}$ 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. 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 é $O(\lg n)$ no pior caso. Uma estrutura mais complicada usando $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ bits de armazenamento adicional pode ser usada para suportar select em tempo constante. Na prática, muitas dessas soluções têm constantes ocultas na notação $O(\cdot )$, 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.

Dicionários de entropia comprimida

A abordagem de espaço $n+o(n)$ pode ser melhorada notando-se que existem $\textstyle {\binom {n}{m}}$ distinct $m$-subconjuntos distintos de $[n)$ (ou strings binárias de tamanho $n$ com exatamente $m$ 1’s), e, portanto, $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ é um mínimo teórico de informação no número de bits necessários para armazenar $B$. Existe um dicionário sucinto (estático) que alcança este limite, nomeadamente usando espaço ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$. Esta estrutura pode ser estendida para suportar consultas rank and select e ocupa espaço ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$. Este limite pode ser reduzido para uma compensação espaço/tempo reduzindo o espaço de armazenamento do dicionário para ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ com consultas de custo $O(t)$ de tempo.

Exemplos

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 2³² = 4 GiB de dados é uma string muito longa, e 2⁶⁴ = 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 $select$ pode rapidamente determinar onde cada item começa, dado o seu índice. 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$ nós pode ser representada em $2n+o(n)$ 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$ nós é ${\tbinom {2n}{n}}$$/(n+1)$. Para um $n$, isto é aproximadamente $4^{n}$; assim, é necessário ao menos $\log _{2}(4^{n})=2n$ bits para a codificação. Uma árvore binária sucinta, portanto, ocupa $2$ bits por nó.

Ver também

• Minimal perfect hash function