Sigla de 3 letras da cidade no namespace do estado

[ppKrauss]

Abreviações de 3 letras dos nomes de cidade foram consagradas pelo uso em aeroportos. São também bem difundidas as abreviações ISO de 3 letras de nomes de países. Abreviar nomes de cidades brasileiras não deveria ser problema, mas atualmente não existe nem um "algoritmo oficial" das abreviações de nome em 3 letras.

Poderíamos usar uma tabela de abreviaturas já fixada por um órgão do governo, e de fato existe ou existiu, é a tabela da ANATEL. Ela todavia não chega a ser muito superior que a convenção da issue #6 , o código compacto (4 caracteres) do identificador IBGE, e não é uma convenção "por estado", é para todo o Brasil... A presente proposta se justifica pela impossibilidade teórica de conseguir bons resultados com uma proporção tão grande se comparada ao número de combinações possíveis com as 3 letras (ver nota tecnica abaixo).

Classificando o algoritmo

É como uma função hash u=H(x), onde x é uma string de entrada (um nome), e o "digest" resultante na saída, u, é uma string de tamanho fixo, com 3 letras. Mas certamente não é um hash criptográfico, é muito mais um "hash de semelhança" (entradas parecidas podem resultar em hashes iguais).

Em funções hash especializadas podemos também restringir o domínio, portanto classificando também o tipo de entrada: são topônimos da língua portuguesa. Um conjunto T de topônimos, com a restrição de que seu tamanho |T| não exceda em 5% o número de elementos do contra-domínio de H, ou seja, o número de combinações possíveis com 3 letras, que é 26^3=17576.

Por fim, a característica que diferencia ou torna ainda mais especializada essa função H, quando comparada com hashes usuais. Como são previstas colisões, essa função deve também suprir estratégias para lidar com as colisões: a função muda o algoritmo em função de parâmetros q de qualidade e i de "i-ésima tentativa" dentro de certa qualidade, H(x,q,i). O uso do parâmetro q seria então vinculado ao contexto de colisão:

• use H(x,0) para resultados de "primeira classe" (máxima qualidade) enquanto não houverem colisões;

• depois da primeira colisão, testar H(x,1,i), um resultado de "segunda classe";

• depois tentar H(x,2,i) o resultado de pior qualidade.

Examplos:

• H("Hello",0) é "HEL", H("Hello",2,i) é "HLL" ou "HLO", e H("Hello",3,i) é "LLO" ou "LLH".

• quando x="Hello My Friend", H(x,0) é "HMF", H(x,1) é "HLF" ou "HFR", e H(x,2) é "MFR" ou "MFD".

Agrupamento e sequência

Com mais de 1% do ...

Outros critérios de qualidade

A qualidade da sigla deve ser avaliada em termos de:

• simplicidade e popularidade da regra: se perguntamos para 100 pessoas "como você abreviaria o nome x para 3 letras?", esta vai ser a resposta mais frequente. Mas como vimos existem pelo menos dois tipos de nome, os simples e os compostos.

• semelhança: siglas de três letras serão consideradas 40% parecidas se apenas a primeira letra for igual e 70% parecidas se além da primeira uma das demais letras for também igual. Quando apenas as duas últimas forem iguais será considerada semelhança de 50%.
  É esperado que a média de um índice de semelhança aplicado aos pares de nomes com 70% de semelhança nas suas siglas seja preservada.

• diferenciação preservando a popularidade: fazer uso inteligente de regras de diferenciação do português. Por exemplo, plural/singular se diferenciam pelo "s" no final (ver Varginha ); os dígrafos com som de uma letra só, "RR", "SS", "CH", ... podem ser reduzidos, garantidos maior taxa de diferenciação sem perda de agrupamento dos semelhantes.

NOTA TÉCNICA - CRITÉRIO DE ABUSO

A chance de colisão deve ser intendida como probabilidade P de dois nomes calharem de ficar com a mesma abreviação de 3 letras.

Recapitulando o que temos para poder estimar P: a sigla de 3 letras faz o papel de um digest de hash, e neste sentido vale a relação clássica de chance de colisão... Como temos 26^3=17576 combinações com 3 letras, esse é o tamanho c do contra-domínio de H.

Para efeitos de análise teórica das chances de colisão podemos aproximar grosseiramente 17576 para a potencia de 2 mais próxima, que é 16383, ou seja, 14 bits. Se o conjunto de entrada T tem 50 elementos, a chance de colisão em uma hash com c de 14 bits, será da ordem de 7,2%. Com 100 elementos já salta para 26%, com 500 para 99,90% (saturação).

O estado mais pobre em número de municípios é o MS, com 79, que fica na primeira faixa (17% de chance). O recordista é MG, com 99,999% de chance.

Como no processo de atribuição de siglas, a cada colisão oferecemos uma opção diferente de sigla, e essas opções vão se deteriorando em termos de qualidade... Podemos supor que lá pela quarta ou quinta tentativa já não há mais qualidade. Assim um bom chute de chance de preservação da qualidade é P/5 (chance não colidir ou na primeira, ou na segunda, ou .. na quinta tentativa). Voltando aos valores estimados acima teremos ~1% para MS e ~10% para MG.

Outro parâmetro simples é o número médio o de opções de abreviação por nome: MG tem o=17576/853=20, SP tem o=17576/645=27, ..., MS tem o=17576/79=222. Com mais opções haverão maiores chances de eleger uma de melhor qualidade. O então, para traduzir em termos percentuais precisamos imaginar qual o número mínimo de opções aleatórias de 3 letras. Conhecemos o resultado da Anatel que consideramos ruim, que foi de apenas 3,2 opções (o=17576/5500 ~ 3,2). Chutamos que dez opções seja o mínimo, o_min=10.

Critério de "qualidade máxima esperada", por abuso ou não do número de itens a abreviar com 3 letras:

• Sem chance de qualidade: o<10
• Garantia de boa qualidade: P<1% e o>50

---

Referências

• Cidades brasileiras com aeroportos: aparentemente todas elas deveriam ter abreviações IATA, mas não encontrei uma listagem sistemática do Brasil (não confundir com aeroportos)... Alguns exemplos mas não sei se são oficiais: ANS Anápolis-GO, PTM Patos de Minas-MG, PTS Patos-PB, URA Uberaba-MG, UDI Uberlândia-MG... e os mais exóticos, BSB Brasília-DF, GYN Goiânia-GO, ...

• Abreviações Anatel: só em PDF e parece ser (Date HTTP header) de 2013.

• Abreviações do CDHU/SP: não possuem 3 letras, mas são todas palavras simples e reduzidas, simplificando bastante o trabalho do algoritmo. Ajudaria como "referência oficial" se não houver outra de ponto de partida... Só está disponível em PDF e parece ser de 2005.

• Dados das cidades, por estado, etc. Wikidata. Como fazer queries SparQL pode ser chato, algumas tabelas como a de São Paulo já se encontram prontas, e um dataset homologado também pode ser utilizado.

---

Cálculo de semelhança de nomes: pode-se reduzir o nome aplicando o metaphone (reduzindo a 4 caracteres) à primeira e última palavra, e as demais preservando apenas iniciais; em seguida aplicando um índice como Levenshtein.