Algoritmo de Verhoeff

Na edição 16 da Revista PROGRAMAR em Outubro de 2008 foi publicado o artigo Algoritmos para o Cálculo de Dígito Verificador que descreveu o cálculo de dígito verificador para códigos de identificação a partir dos métodos de módulo 10 e 11. Além dos algoritmos já apresentados existem outros mecanismos para cálculo e obtenção de dígitos verificadores, podendo-se destacar o algoritmo de Verhoeff, tema deste artigo.

O algoritmo ora apresentado foi desenvolvido por Jacobus (Koos) Verhoeff, matemático holandês para sua tese de doutorado em 1969 (GARCIA, et. al., 2007, p. 47). Verhoeff escreveu um algoritmo capaz de operacionalizar sequências de dígitos decimais de qualquer tamanho, evitando desta forma a ocorrência de erros de dados (HAMMING, 1986, p.27) e de transposição de dígitos adjacentes quando efectuados por utilizadores humanos (WAGNER & PUTTER,1989), tais como:

  • Substituir um dígito por um outro dígito. Por exemplo, invés de informar os dígitos 5678 acaba-se por informar 4678, onde o dígito que deveria ser 5 foi substituído pelo dígito 4. Este tipo de erro ocorre quando se acciona no teclado uma tecla adjacente à tecla que deveria ter sido realmente accionada. Ocorre em cerca de 60% a 90% dos casos.
  • Omissões ou adições de dígitos. Este tipo de erro ocorre normalmente por falta de atenção do utilizador. Ocorre em cerca de 10% a 20% dos casos.
  • Trocar da ordem entre dois dígitos. Por exemplo, invés de informar os dígitos 5678 acaba-se por informar 6578, onde os dígitos 56 foram trocados pelos dígitos 65. Este tipo de erro ocorre quando se escreve muito rápido em um teclado. Ocorre em cerca de 10% a 20% dos casos.

Além das formas habituais de detecção de erros que podem ser equacionadas com o algoritmo de Verhoeff, é possível também descobrir algumas formas menos comuns de erros (WAGNER & PUTTER, 1989), tais como:

  • Erros gémeos contínuos. Por exemplo, invés de informar os  dígitos 1123 acaba-se por informar 7723, onde os dígitos 11 foram trocados pelos dígitos 77. Este tipo de erro pode ocorrer por distracção do utilizador na entrada da sequência de dígitos ou por ilegibilidade na escrita manual do código a ser verificado. Ocorrem em cerca de 0,5% a 1,5% dos casos.
  • Erros gémeos irregulares. Por exemplo, invés de informar os dígitos 1214 acaba-se por informa a sequência 7274, onde os dígitos 121 foram trocados pelos dígitos 727. Este tipo de erro pode ocorrer pelas mesmas razões apontadas na ocorrência de erros gémeos contínuos ou por ilegibilidade na escrita manual dos dígitos numéricos. Ocorrem em menos de 1% dos casos.
  • Transposição irregular. Por exemplo, invés de informar os dígitos 1234 acaba-se por informar a sequência 3214, onde os dígitos 123 foram transpostos de forma irregular pelos dígitos 321. Este tipo de erro pode ocorrer por distracção do utilizador. Ocorre em cerca de 0,5% a 1% dos casos.
  • Erros fonéticos. Por exemplo, invés de informar os dígitos 6-123 acaba-se por informar 3-123, onde o dígito 6 foi trocado pelo dígito 3. Este tipo de erro ocorre normalmente quando o código numérico é transmitido por voz por meio de um telefone, o interlocutor fala “seis” e o utilizador do outro lado entende “três”. Ocorre em cerca de 0,5% a 1,5% dos casos.

Os percentuais de erros apontados por Paul Putter e Neal R. Wagner basearam-se num estudo de erros com 12.000 ocorrências de erros humanos quando da utilização de códigos de identificação.

O maior questionamento encontrado a respeito do uso do algoritmo de Verhoeff é sua complexidade de implantação. Pelo fato de ser baseado em tabelas numéricas, essas tabelas necessitam ser implementadas em memória e de forma correcta. Normalmente se utiliza técnicas de uso de matrizes ou faz-se o armazenamento dos valores em uma tabela de banco de dados. Neste artigo estará sendo considerado a primeira forma de implementação.

Método Algorítmico

O método algorítmico apresentado por Verhoeff (1969) baseia-se no uso de três tabelas de valores fixos, sendo: tabela de localização do inversor, tabela do índice de inversão e tabela do dígito verificador. Há referência a essas tabelas, na Wikipédia, como: tabela de permuta, tabela de multiplicação e tabela de inversão. No entanto, essas denominações não representam seu sentido operacional, dificultando seu entendimento didáctico. Por esta razão neste artigo as referências as três tabelas obedecerá a seguinte nomenclatura:

Nomenclatura
Forma em alguns documentosForma documentada neste artigo
tabela de permutatabela de localização do inversor 
tabela de multiplicaçãotabela do índice de inversão 
tabela de inversão tabela do dígito verificado 

A primeira tabela—tabela de localização do inversor—possui os valores dos índices que são obtidos a partir do fornecimento de um código de identificação que terá o dígito verificador conferido ou mesmo gerado e que serão usados na tabela do índice de inversão.

Tabela de localização do inversor
 0123456789
00123456789
11576283094
25803796142
38916043527
49453126870
54286573901
62793806415
77046913258

Para que esta tabela seja usada é necessário inverter-se a disposição (da esquerda para a direita) dos valores constantes do código de identificação, que serão usados como coordenadas das colunas.

Assim que o código de identificação é invertido numera-se a partir de 0 (zero) até 7 (sete) da esquerda para a direita toda a sequência de código de identificação, repetindo-se a sequência de zero a sete por toda a extensão do código de identificação não importando o seu tamanho para que desta forma tenha-se os valores das coordenadas das linhas.

A segunda tabela—tabela do índice de inversão—possui os valores de inversão de retorno para auxiliar a obtenção do dígito verificador da tabela do dígito verificador. Para que esta tabela seja utilizada é necessário ter primeiramente os valores de localização da tabela de localização do inversor.

Tabela do índice de inversão
 0123456789
00123456789
11234067895
22340178956
33401289567
44012395678
55987604321
66598710432
77659821043
88765932104
99876543210

Para uso desta tabela é necessário obter as coordenadas de linha e coluna. A coordenada de coluna da tabela do índice de inversão é obtida a partir do índice de localização seleccionado na tabela de localização do inversor. Já a coordenada de linha é obtida por meio da definição do valor de verificação.

O primeiro valor de verificação é por definição 0 (zero), os demais valores são obtidos a partir da obtenção do índice de localização e do índice verificador localizados na própria tabela.

O índice verificador obtido na tabela do índice de inversão de um dos dígitos do código de identificação torna-se o próximo valor de verificação para o próximo dígito do código de identificação. O último valor obtido como índice verificador será utilizado como índice de localização do dígito verificador na tabela do dígito verificador.

A terceira tabela—tabela do dígito verificador—apresenta os valores que serão utilizados como dígitos verificadores a partir da definição do índice verificador (que é o último valor obtido como índice verificador) extraído a partir da tabela do índice de inversão.

Tabela do dígito verificador
Índice verificador0123456789
Dígito verificador0432156789

Publicado na edição 18 (PDF) da Revista PROGRAMAR.