b'\n_START_ARTICLE_\nEstrutura de dados sucinta\n_START_SECTION_\nDicion\xc3\xa1rios de entropia comprimida\n_START_PARAGRAPH_\nA abordagem de espa\xc3\xa7o\xc2\xa0 pode ser melhorada notando-se que existem\xc2\xa0 distinct -subconjuntos distintos de  (ou strings bin\xc3\xa1rias de tamanho\xc2\xa0 com exatamente\xc2\xa0 1\xe2\x80\x99s), e, portanto,\xc2\xa0 \xc3\xa9 um m\xc3\xadnimo te\xc3\xb3rico de informa\xc3\xa7\xc3\xa3o no n\xc3\xbamero de bits necess\xc3\xa1rios para armazenar\xc2\xa0. Existe um dicion\xc3\xa1rio sucinto (est\xc3\xa1tico) que alcan\xc3\xa7a este limite, nomeadamente usando espa\xc3\xa7o\xc2\xa0. Esta estrutura pode ser estendida para suportar consultas\xc2\xa0rank and select e ocupa espa\xc3\xa7o\xc2\xa0. Este limite pode ser reduzido para uma compensa\xc3\xa7\xc3\xa3o espa\xc3\xa7o/tempo reduzindo o espa\xc3\xa7o de armazenamento do dicion\xc3\xa1rio para\xc2\xa0 com consultas de custo\xc2\xa0 de tempo.\n_START_SECTION_\nExemplos\n_START_PARAGRAPH_\nUma\xc2\xa0string de termina\xc3\xa7\xc3\xa3o nula\xc2\xa0(string em C) ocupa espa\xc3\xa7o\xc2\xa0Z + 1, e \xc3\xa9, portanto, impl\xc3\xadcita. Uma string arbitr\xc3\xa1ria, coom tamanho arbitr\xc3\xa1rio (string em Pascal) ocupa espa\xc3\xa7o\xc2\xa0Z + log(Z), e \xc3\xa9, portanto, sucinta. Se existe um tamanho m\xc3\xa1ximo \xe2\x80\x93 o que \xc3\xa9 o caso na pr\xc3\xa1tica, dado que 2\xc2\xb3\xc2\xb2 = 4 GiB de dados \xc3\xa9 uma string muito longa, e 2\xe2\x81\xb6\xe2\x81\xb4 = 16 EiB de dados \xc3\xa9 maior que qualquer string na pr\xc3\xa1tica \xe2\x80\x93 ent\xc3\xa3o, uma string com tamanho \xc3\xa9 tamb\xc3\xa9m impl\xc3\xadcita, ocupando espa\xc3\xa7o\xc2\xa0Z + k, onde\xc2\xa0k \xc3\xa9 o n\xc3\xbamero de dados para representar o tamanho m\xc3\xa1ximo (e.g., bytes em uma palavra)._NEWLINE_Quando uma sequ\xc3\xaancia com itens de tamanho vari\xc3\xa1vel (tal como strings) precisa ser codificada, existem diversas possibilidades. Uma abordagem direta \xc3\xa9 armazenar um tamanho e um item em cada registro \xe2\x80\x93 estas podem ent\xc3\xa3o serem posicionadas uma ap\xc3\xb3s a outra. Isto permite encontrar de maneira eficiente o pr\xc3\xb3ximo elemento, mas n\xc3\xa3o encontrar o kth elemento. Uma alternativa \xc3\xa9 organizar os itens em ordem com um delimitador\xc2\xa0(e.g., uma string com termina\xc3\xa7\xc3\xa3o nula). Neste caso, \xc3\xa9 utilizado um delimitador em lugar de um tamanho, e \xc3\xa9 substancialmente mais lenta, uma vez que a sequ\xc3\xaancia inteira deve ser lida em busca dos delimitadores. Ambas os casos s\xc3\xa3o eficientes em espa\xc3\xa7o. Uma alternativa \xc3\xa9 a separa\xc3\xa7\xc3\xa3o de maneira independente: os elementos podem simplesmente serem colocados um ap\xc3\xb3s o outro, sem delimitadores. Os limites de um item podem ser armazenados como uma sequ\xc3\xaancia de tamanho, ou melhor, deslocamentos dentro dessa sequ\xc3\xaancia. Alternativamente, uma outra string bin\xc3\xa1ria consistindo de 1s nas posi\xc3\xa7\xc3\xb5es em que um item come\xc3\xa7a e 0s nas demais posi\xc3\xa7\xc3\xb5es \xc3\xa9 codificada conjuntamente. Dada esta cadeia, a fun\xc3\xa7\xc3\xa3o\xc2\xa0 pode rapidamente determinar onde cada item come\xc3\xa7a, dado o seu \xc3\xadndice.\xc2\xa0Isto \xc3\xa9 compacto, mas n\xc3\xa3o sucinto, uma vez que ocupa espa\xc3\xa7o 2Z, que \xc3\xa9 O(Z)._NEWLINE_Um outro exemplo \xc3\xa9 a representa\xc3\xa7\xc3\xa3o de uma \xc3\xa1rvore bin\xc3\xa1ria: uma \xc3\xa1rvore bin\xc3\xa1ria arbitr\xc3\xa1ria com  n\xc3\xb3s pode ser representada em\xc2\xa0 bits, suportando ainda opera\xc3\xa7\xc3\xb5es em qualquer dos n\xc3\xb3s, o que inclui encontrar o seu pai, sues filhos da esquerda e da direita e devolver sua sub\xc3\xa1rvore, cada qual em tempo constante. O n\xc3\xbamero de \xc3\xa1rvores bin\xc3\xa1rias distintas com\xc2\xa0 n\xc3\xb3s \xc3\xa9\xc2\xa0. Para um\xc2\xa0, isto \xc3\xa9 aproximadamente\xc2\xa0; assim, \xc3\xa9 necess\xc3\xa1rio ao menos\xc2\xa0 bits para a codifica\xc3\xa7\xc3\xa3o. Uma \xc3\xa1rvore bin\xc3\xa1ria sucinta, portanto, ocupa\xc2\xa0 bits por n\xc3\xb3.'