From:	MERC::"uunet!CRVAX.SRI.COM!RELAY-INFO-VAX"  8-JUL-1992 03:41:02.91
To:	info-vax@kl.sri.com
CC:	
Subj:	Re: Soundex (fuzzy-name matching)?

In article <01GM2FOZ5UVK0008DC@BENTLEY.BITNET>, KSULLIVA@BENTLEY.BITNET writes...
>I am looking for any algorythms or routines that anyone might have for
>imprecise name matching. 

Here's my offer.  It's based on the premise that it can all fit into a 
longword, which makes for GREAT speed in sorting on VAX and other 32
bit architectures (since I was trying to do 30000 x 30000 matches on
a 780 with 4 Mb of memory):


#include <stdio>
#include <ctype>

#define ERROR(msg) printf("%s\n",msg),exit(1)

main()
{
/*
 * A program to look for similar keywords
 * 
 * By Joel and Ross, as a present for Bill, the little
 * programmer who forgot that 30000*30000 = 900000000
 *
 */

/* most of the program deleted */

}


unsigned long
gen_soundex(word)
char *word;
{
/*
 * This subroutine generates the Soundex of a word an returns it
 * as an unsigned integer.  This algorithm is due to someone I
 * can't remember, and has been modified to be a little more
 * reasonable for keywords (since the original algorithm was used
 * for names)
 *
 * The algorithm is described originally, thus:
 * The Soundex system reduces all strings to a four letter/digit
 * code:
 * 1) Convert the keyword to a Soundex based on the following algorithm:
 * 	a) Compress out all whitespace and non-characters/non-digits.
 *	b) First char does not change.
 *	c) Each subsequent char is converted to a digit according
 *	   to the following table:
 *	
 *	0 AEIOUHWY
 *	1 BFPV
 *	2 CGJKQSXZ
 *	3 DT
 *	4 L
 *	5 MN
 *	6 R
 *	7 0123456789
 *
 * 2) Remove zeros
 * 3) Compress runs of the same digit to a single digit.
 * 4) Truncate to 4 characters (1 char + 3 digits)
 *
 */
    char soundex[MAX_KEY_LENGTH];
    char new_soundex[MAX_KEY_LENGTH];
    int word_len,w_index,s_index;
    char *wptr;

    wptr=word;
    s_index = 0;

    do {
	if (isupper(*wptr) || isdigit(*wptr))
	    soundex[s_index++] = *wptr;
	else if (islower(*wptr))
	    soundex[s_index++]=toupper(*wptr);
    } while (*wptr++ != '\0');

    soundex[s_index]='\0';
    if (s_index == 0) return(0);

    word_len = s_index;

/* use w_index = 1 for true soundex */
    for (w_index=0; w_index<word_len; w_index++) {
	switch((int)soundex[w_index]) {
	case 'A':
	case 'E':
	case 'I':
	case 'O':
	case 'U':
	case 'H':
	case 'W':
	case 'Y':
	    soundex[w_index]=0;
	    break;
	case 'B':
	case 'F':
	case 'P':
	case 'V':
	    soundex[w_index]=1;
	    break;
	case 'C':
	case 'G':
	case 'J':
	case 'K':
	case 'Q':
	case 'S':
	case 'X':
	case 'Z':
	    soundex[w_index]=2;
	    break;
	case 'D':
	case 'T':
	    soundex[w_index]=3;
	    break;
	case 'L':
	    soundex[w_index]=4;
	    break;
	case 'M':
	case 'N':
	    soundex[w_index]=5;
	    break;
	case 'R':
	    soundex[w_index]=6;
	    break;
	default:
	    soundex[w_index]=7;
	    break;
	}
    }

/*    w_index = 1; */
/*    new_soundex[0] = soundex[0]; */
    for (w_index=0;w_index<11;w_index++) new_soundex[w_index]=0;
    w_index = 0;
/* use s_index = 1 for true soundex */
    for (s_index=0; s_index<word_len; s_index++) {
	if (soundex[s_index] != 0 &&
	    soundex[s_index] != soundex[s_index-1] )
	    new_soundex[w_index++] = soundex[s_index];
    }

    return(((int)new_soundex[0] << 27) | ((int)new_soundex[1] << 24) | 
	   ((int)new_soundex[2] << 21)  | ((int)new_soundex[3] << 18) |
	   ((int)new_soundex[4] << 15)  | ((int)new_soundex[5] << 12) |
	   ((int)new_soundex[6] << 9)  | ((int)new_soundex[7] << 6) |
	   ((int)new_soundex[8] << 3)  | (int)new_soundex[9] );
}


Joel M Snyder, 1103 E Spring Street, Tucson, AZ, 85719 
Phone: 602.882.4094 (voice) .4095 (FAX) .4093 (data)
BITNET: jms@Arizona  Internet: jms@arizona.edu  SPAN: 47541::telcom::jms
Somewhere in DOWNTOWN BURBANK a prostitute is OVERCOOKING a LAMB CHOP!!

