Código Natural/Requisitos e motivações

Todo código natural pode ser representado por uma cadeia de bits, mas nem por isso é uma cadeia de bits. O conjunto dos códigos naturais é munido de diversas operações e tipos alternativos de representação. A escolha das operações essenciais e tipos de representação relevantes é que estabelece o conceito de código natural.

A seguir os problemas motivadores e requisitos utilizados originalmente para se obter a definição das operações essenciais. Os requisitos são, indiretamente, soluções dos problemas.

Requisitos na representação textual

Ver definições adicionais em Código natural/Notação posicional.

Números binários são representações válidas da notação posicional numérica base2, e podem ser representados de forma mais compacta (mais amigável para o ser humano) através de bases maiores, tais como base8 (sistema octal) ou base10 (sistema decimal). Códigos, todavia, não possuem um sistema posicional adequado, não existe um padrão para se representar todos os códigos naturais, nem sequer na base4 é possível.

Requisito R1.1. Essa "representação compacta e amigável para humanos" é necessária, e portanto é o primeiro requisito.

A escolha das bases mais adequadas, todavia, também requer justificativas: descritas em Código natural/Notação posicional, e resultam em um conjunto limitado de bases, as quais se tornam requisitos:

Requisito R1.2. Oferecer representações nas bases N com

N\in \{4,8,16,32\}

; principalmente base 16.

Outro problema é a ordem: listagens de códigos representados em outras bases, precisam seguir a mesma ordem que as listagens binárias, ou seja, a ordem lexicográfica natural dos bits. Isso porque códigos naturais, independentemente da representação, precisam exibir a ordem hierárquica, de modo que "ramos da hierarquia" fiquem listados dentro de um intervalo único. Em $X_{2}$ por exemplo iniciamos pelo 0, depois 00, depois 01, depois 1, etc. O ramo dos "filhos de 0" ficam ordenados no intervalo [0,00,01] da listagem lexicográfica. Os "filhos de 1" no intervalo [1,10,11].

Requisito R1.3. A ordenação de texto orientada a diferentes idiomas, num banco de dados relacional, é conhecida como collation; portanto é necessário estabelecer a collations adequadas a cada base de representação textual do código natural.

Requisitos na representação interna

Códigos em um banco de dados podem ser identificadores ou simples atributos (ex. hashes de integridade). A aplicação mais importante é a identificação única, que, tradicionalmente, nos bancos de dados é implementada través de números naturais, ditos "seriais", tipicamente em 32 ou 64 bits.

Requisito R2.1: ser um tipo de dado de 32 ou 64 bits, com fácil conversão para números inteiros de comprimento equivalente.

Requisito R2.2: oferecer uma função "sucessor(x)", que retorna o próximo x numa listagem ordenada, da maneira análoga que um contador numérico de "+1".

Requisito R2.3: permitir as ordenações lexicográfica (prioritária) e por nível (secundária).

Através da ordenação lexicográfica é possível associar conjuntos aninhados a intervalos, e portanto realizar operações hierárquicas de alta performance fazendo uso apenas dos identificadores. Por isso R2.3 é de grande importância para "identificadores inteligentes", que preservam informação sobre a sua hierarquia.

Problemas na representação textual baseN

A tabela abaixo, listando códigos em sua ordem natural (lexicográfica da expressão bitString), ilustra problemas da Base4 e a solução Base4h, bem como a solução hbit.

(size,value)	BitString	Base4	Base4h	hbitBitstring	hbit
(1,0)	`0`	?	G	`10`	2
(2,0)	`00`	0	0	`100`	4
(3,0)	`000`	?	0G	`1000`	8
(4,0)	`0000`	00	00	`10000`	16
(5,0)	`00000`	?	00G	`100000`	32
(6,0)	`000000`	000	000	`1000000`	64
(7,0)	`0000000`	?	000G	`10000000`	128
(8,0)	`00000000`	0000	0000	`100000000`	256
(8,1)	`00000001`	0001	0001	`100000001`	257
(7,1)	`0000001`	?	000Q	`10000001`	129
(8,2)	`00000010`	0002	0002	`100000010`	258
(8,3)	`00000011`	0003	0003	`100000011`	259
(6,1)	`000001`	001	001	`1000001`	65
(7,2)	`0000010`	?	001G	`10000010`	130
(8,4)	`00000100`	0010	0010	`100000100`	260
(8,5)	`00000101`	0011	0011	`100000101`	261
...	...	...	...	...	...

A coluna "hbitBitstring" é relativa à representação das bitStrings em formato "hidden bit", definido em [KraEtAll2019]. Consiste em acrescentar o 1 na frente da bitString, para que não lhe cortem os zeros à esquerda, ao interpretá-la como número inteiro positivo (em formato decimal na coluna hbit).

A coluna "Base4" é a tentativa (frustrada) de representar as bitStrings com o algoritmo da notação posicional numérica da Base 4. A coluna "Base4h" é a inovação proposta em [KraEtAll2019], que adaptou o algoritmo para expressar códigos ao invés de números, permitindo zeros a esquerda e quantidade variável de dígitos.

Nota. Conjuntos finitos de códigos naturais sempre podem ser expressos como conjuntos de hbits, portanto através de números naturais. O conjunto de todos os Códigos Naturais todavia é infinito, e neste caso particular (com infinitos elementos), a representação hbit não é permitida pelo Teorema de Cantor. Portanto, matematicamente, size-value é um tradutor mais rigoroso para expressões em

\mathbb {N}

.

Tamanho do problema

Quantos códigos naturais de k bits deixam de ser representados na Base N?

Avaliando a seguir apenas bases com N em {4, 8, 16, 32} da RFC 4648 das aplicações da Internet e (base 4) das aplicações em geocódigos. São todas na forma $N=2^{n}$ , com n variando de 2 (4=2²) a 5 (32=2⁵). O valor de n fornece também o número de bits por dígito da base, por exemplo base N=8 temos n=3, portanto cada dígito da base 8 tem 3 bits.

Na tabela abaixo foram avaliadas experimentalmente as taxas de ocupação para diversos valores de k, resultando em uma quantidade de códigos, $n\_codes=2^{k+1}-2$ , e nas quantidades de representações válidas a cada base.

		Base and occupancy rate of n_codes
k (bits)	n_codes	base4		base8		base16		base32
1	2	0	0%	0	0%	0	0%	0	0%
2	6	4	67%	0	0%	0	0%	0	0%
3	14	4	29%	8	57%	0	0%	0	0%
4	30	20	67%	8	27%	16	53%	0	0%
5	62	20	32%	8	13%	16	26%	32	52%
6	126	84	67%	72	57%	16	13%	32	25%
7	254	84	33%	72	28%	16	6%	32	13%
8	510	340	67%	72	14%	272	53%	32	6%
9	1022	340	33%	584	57%	272	27%	32	3%
10	2046	1364	67%	584	29%	272	13%	1056	52%
11	4094	1364	33%	584	14%	272	7%	1056	26%
12	8190	5460	67%	4680	57%	4368	53%	1056	13%
13	16382	5460	33%	4680	29%	4368	27%	1056	6%
14	32766	21844	67%	4680	14%	4368	13%	1056	3%
15	65534	21844	33%	37448	57%	4368	7%	33824	52%
16	131070	87380	67%	37448	29%	69904	53%	33824	26%
Average on stable cycle:			50%		33%		25%		20%
Loss, 100% - occupancy:			50%		67%		75%		80%

Os valores percentuais foram calculados com relação a n_codes, as médias finais de occupancy com relação aos ciclos.

O comportamento da taxa de ocupação é cíclico e converge rapidamente, sendo destacado em negrito o primeiro ciclo estável de cada base. A média dentro do ciclo estável é a esperada pelo número de bits: em 2 bits (base 4) apenas os códigos de 1 bit deixam de ser representados, portanto 50%; em 3 bits (base 8) os códigos de 1 e 2 bits deixam de ser representados, portanto apenas 1/3 = 33% é representado; em 4 bits apenas 1/4=25% e em 5 bits apenas 1/5=20%.

Conclusão: nas bases de aplicação mais frequente (as bases 8 e 16), entre 67% e 75% dos códigos naturais deixam de ser representados. É uma perda muito grande, vale a penas investir numa solução.

Padronização da eventual solução

Conforme visto na definição dos códigos naturais, existe uma proposta de solução (propostas base 4h, base 8h e base 16h), mas ela permanece como proposta enquanto não foi aceita como padrão de fato para a "representação humana compacta" dos códigos naturais.

A padronização portanto é mais um problema da representação textual, o último obstáculo a ser vencido.

Problemas na representação interna e processamento

...

Problema da ordenação na representação interna

... Para ser amigável, evitando traduções, os códigos base-h devem ser representados por texto com collation especial. Supondo que a base-h seja um padrão, é natural propor um agrupamento para ela. Imagine definir uma coluna como representação base16h:...

Ver também