SoundEx

[Maligno]

Quando estive trabalhando numa pesquisa de localidades do banco de dados de CEP (tenho no meu site) que vou utilizar num programa, reparei que o sistema de busca convencional, numa
base de dados relativamente grande (200.000 no Estado de SP), seria muito ineficiente. Então me lembrei do algoritmo SoundEx. Só que esse algoritmo é muito lento pra constar numa chave de índice, tanto no Firebird, que é o que uso agora, e mais ainda no Clipper. Aliás, se não me falha a memória, nos fontes que acompanham o Clipper consta um fonte (PRG) do SoundEx. Não sei se é o SoundEx convencional, ou uma versão modificada. De qualquer forma, como PRG, numa chave de índice a velocidade tornaria muito lenta a indexação. Até tinha desistido. Mas resolvi pesquisar a respeito, encontrei o algoritmo original do American SoundEx e o implementei em C, que estou agora colocando à disposição dos colegas. Agradeceria muito se puderem testar e me dar um retorno acerca dos resultados, com relação a facilidade de uso, bugs e, principalmente, velocidade de indexação.

O pacote ZIP está no meu site.
Download: http://pub.buzinello.com/xbase/clipper/libs/soundex.zip

Nele constam os arquivos:

Código: Selecionar todos

DEMO.EXE     - programa de demonstração (Clipper/DOS)
DEMO.PRG     - fonte deste programa
Soundex.C    - fonte C do algoritmo
Soundex.LIB  - biblioteca para uso no Clipper
Soundex.OBJ  - objeto que foi acondicionado na LIB
SoundexD.EXE - utilitário de linha (versão DOS)
SoundexW.EXE - utilitário de linha (versão Windows)

O algoritmo original foi rigorosamente observado. A não ser por um detalhe: como a língua portuguesa conta com acentuação, uma etapa de remoção de acentos foi acrescentada ao código. Assim, não faz diferença se tem o acento ou não, nem mesmo se o nome está em maiúsculas ou minúsculas.

A biblioteca resultante, para Clipper, contém apenas duas funções de interface: AmSoundEx(), que calcula o SoundEx de uma palavra simples e AmSoundExN(), mais apropriada para ser inserida numa chave de índice, pois calcula o SoundEx de várias palavras e retorna como resultado o SoundEx combinado de todas. Nesta última função pode-se definir quais são os caracteres espaçadores de palavras (pontos, vírgulas, etc) além do caractere espaço (default). Um argumento adicional pode ser utilizado (opcional) para informar qual o tamanho mínimo para uma palavra ser considerada (default=2). Os protótipos:


AmSoundex(<strFonte>)
AmSoundexN(<strFonte>,<strDelimitadores>[,<numTamanhoMinimo>])


PARA QUEM NÃO CONHECE SOUNDEX...
SoundEx é um algoritmo relativamente simples, cuja missão é calcular uma string que seja a representação fonética de uma palavra. A intenção é justamente facilitar os sistemas de busca, principalmente em bases muito grandes. O algoritmo original sofreu poucas alterações ao longo dos anos. A versão que codifiquei é a última publicada. No fonte C consta o link para o órgão do governo americano mantenedor do algoritmo.

Acho que alguns exemplos de cálculos (feitos pelos programas do ZIP) devem ajudar a esclarecer um pouco sobre a utilidade de algoritmos desse tipo. Notem que o formato do código do fonema é sempre o mesmo: uma letra seguida por 3 números.

Código: Selecionar todos

Palavra Simples (p)   AmSoundex(p)
-------------------   ------------
Buzinello             B254
Busimelo              B254
Caça                  C200
Cassa                 C200
Caza                  C200

Por esses exemplos é possível perceber melhor que um algoritmo desse tipo pode realmente ajudar bastante em um sistema de busca. A seguir, outros exemplos, também conforme o programa distribuído no ZIP:

Código: Selecionar todos

Palavra Composta (p)         AmSoundexN(p,"",3) <- 3 é o tamanho mínimo
--------------------------   ------------------
Paulo Buzinello              P400B254
Paulu Busimelu               P400B254
Maria tinha um carneirinho   M600T500C656
Mary tinha um carnero        M600T500C656

Fica mais fácil agora perceber como ficaria numa chave de índice. A busca, com a ajuda da biblioteca SIX, por exemplo, poderia ser feita por um nome do meio, por exemplo.

Daqui pra frente, depois do que foi exposto, fica por conta da imaginação dos colegas que se dispuserem a testar a biblioteca.

Finalizando, quero agradecer a ajuda recebida da colega AnaCatacombs, pois sem sua infinita paciência e apoio provavelmente esse trabalho não seria concluído (e nem iniciado).

[anacatacombs]

Obrigada pelos agradecimentos Maligno, mas quem realmente merece recebe-los é você.
Parabens pelo trabalho, ficou CHIC. (hahaha)

Vou ver o que faço naquela do Lenhador, talvez funcione também

[]'s

Ana

[alxsts]

Parabens aos colegas pelo trabalho!

Maligno escreveu
...nos fontes que acompanham o Clipper consta um fonte (PRG) do SoundEx...

A título de ilustração, e para quem quiser estudar ou comparar (eu ainda não conheço a linguagem C), segue o fonte da Soundex() dos exemplos que acompanham o Clipper. Na verdade a função é escrita em C.

[]'s
AlxSts

Código: Selecionar todos

/***
*
*  Soundex.c
*
*  Clipper SOUNDEX() function
*
*  Copyright (c) 1990-1993, Computer Associates International, Inc.
*  All rights reserved.
*
*/

#include "extend.api"


/* used below */
#define ISALPHA(c)  ( (c) >= 'a' && (c) <= 'z' || (c) >= 'A' && (c) <= 'Z' )
#define TOUPPER(c)  ( (c) >= 'a' && (c) <= 'z' ? (c) - 'a' + 'A' : (c) )

#define SOUNDEX_LENGTH	4


/***
*   step2()
*   Return soundex result for a single letter.
*/

static char step2(char c)

{
	switch (c)
	{
		case 'B':
		case 'F':
		case 'P':
		case 'V':
			return ('1');

		case 'C':
		case 'G':
		case 'J':
		case 'K':
		case 'Q':
		case 'S':
		case 'X':
		case 'Z':
			return ('2');

		case 'D':
		case 'T':
			return ('3');

		case 'L':
			return ('4');


		case 'M':
		case 'N':
			return ('5');

		case 'R':
			return ('6');

		case 'A':
		case 'E':
		case 'H':
		case 'I':
		case 'O':
		case 'U':
		case 'W':
		case 'Y':
			return (NIL);
	}

	/* bad param -- return something obviously wrong */
	return ('9');
}


/***
*   SoundexC()
*   Convert a string to a soundex code (C-callable).
*
*	"Soundex" algorithm is standard Odell/Russell (1918):
*
*	Produce a code of the form "letter, digit, digit, digit"
*	using these rules:
*
*	1)	Retain the first letter unchanged.
*
*	2)	For each succeeding letter, produce a result based
*		on the following table:
*
*		letter							result
*
*		B, F, P, V						digit 1
*		C, G, J, K, Q, S, X, Z			digit 2
*		D, T							digit 3
*		L								digit 4
*		M, N							digit 5
*		R								digit 6
*		A, E, H, I, O, U, W, Y			(nothing)
*
*
*	3)	If two or more adjacent letters produce the same
*		result in step 2, ignore all but the first of the
*		adjacent letters.
*
*	4)  Repeat steps 2 and 3 until three digits have been
*		produced or until the source is exhausted.
*
*	5)	If less than three digits were produced, right-fill
*		with zeros.
*
*
*	Notes:
*
*	Non-alpha characters are ignored entirely; letters which
*	are separated only by non-alpha characters are considered
*	adjacent.  If the source contains no alpha characters, a
*	value of "0000" is returned.
*
*	Case is not significant.
*
*	Letters which produce (nothing) in step 2 are still
*	significant with respect to step 3.  That is, two letters
*	which produce the same digit are not considered adjacent
*	if they are separated by a letter that produces (nothing).
*	This is in accordance with the original algorithm.
*
*	This C-callable function returns a pointer to a static
*	buffer.  The buffer is overwritten by successive calls.
*/

static char *SoundexC(char *source, short len)

{
	static char code[SOUNDEX_LENGTH+1] = "";

    short i;
    short j;
	char c;
	char result;
	char prev;


	/* make Soundex code */
	for ( i = 0, j = 0, prev = NIL;  i < len && j < SOUNDEX_LENGTH;  i++ )
    {
		c = TOUPPER(source[i]);

		if ( ISALPHA(c) )
		{
			result = step2(c);

			if (j == 0)
			{
				/* retain first letter */
				code[j++] = c;
			}
			else if ( result != NIL && result != prev )
			{
				/* store soundex code */
				code[j++] = result;
			}

			prev = result;
		}
    }


    /* right fill with zeros */
	while (j < SOUNDEX_LENGTH)
		code[j++] = '0';


	return (code);
}


/***
*   SOUNDEX()
*   Convert a string to a "Soundex" code (Clipper-callable).
*
*   cSoundexCode := SOUNDEX(cString)
*/

CLIPPER SOUNDEX(void)

{
    char *code;


    if ( PCOUNT >= 1 && ISCHAR(1) )
	{
		code = SoundexC( _parc(1), _parclen(1) );
	}
	else
	{
		code = "0000";
	}


	_retclen(code, SOUNDEX_LENGTH);
}

[Maligno]

Tem razão. Agora que vi. Há muito tempo atrás me mostraram essa função em PRG. Pensei que fosse da versão 5.2. Nem conferi. Agora fiquei curioso pra saber em qual Clipper ela foi feita em PRG. De qualquer forma, isso não muda muita coisa. O algoritmo que usaram nesta função é o Old SoundEx, já em desuso. E a função também não considera a acentuação das palavras e tampouco separa as palavras dos nomes compostos, o que faria uma chave de índice ser muito mais lenta.