wordz listing 1 The string matching program #include /* standard input/output library */ #include /* handy character manipulation routines */ #ifdef tolower # undef tolower /* we want our own 'tolower' routine */ #endif #define tolower(c) (isupper(c) ? c - 'A' + 'a' : c) #define min(a,b) ((a) < (b) ? (a) : (b)) #define WORD_LENGTH 40 #define THRESHOLD 0.500 /* threshold for PF474 algorithm */ #define SOUNDEX_LENGTH 4 /* total Soundex string length */ #ifndef TRUE # define TRUE 1 # define FALSE 0 #endif /** for the Soundex algorithm: 'x' means 'delete this letter' **/ #define index_of(ch) (ch - 'A') #define IGNORE 'x' static char soundex_mappings[] = { "x123x12xx22455x12623x1x2x2" }; char *remove_duplicate_letters(), *translate_case(); char *soundex_translation_of(), *reverse(); double pf474_algorithm(); main() { char word[WORD_LENGTH], pattern[WORD_LENGTH], no_dups_pattern[WORD_LENGTH]; double pf474_value; printf("Enter the pattern to match against: "); gets(pattern, WORD_LENGTH); strcpy(no_dups_pattern, remove_duplicate_letters(pattern)); while (1) { printf("\nEnter word or \"quit\" to quit : "); gets(word, WORD_LENGTH); if (strcmp(translate_case(word), "quit") == 0) exit(0); if (strcmp(word, pattern) == 0) { printf("matched through translation of case.\n"); continue; } if (strcmp(remove_duplicate_letters(word), no_dups_pattern) == 0) { printf("matched through removal of duplicate letters.\n"); continue; } if (check_transpositions(word, pattern)) { printf("matched through transposition of letters.\n"); continue; } Š if (allow_a_missing_character(word, pattern)) { printf("matched through allowance of a missing character.\n"); continue; } if (allow_an_incorrect_character(word, pattern)) { printf("matched through allowing an incorrect character.\n"); continue; } if (soundex(word, pattern)) { printf("matched through using the Soundex algorithm.\n"); continue; } if ((pf474_value = pf474_algorithm(word, pattern)) > THRESHOLD) { printf("Matched (value = %g) through using the PF474 algorithm.\n", pf474_value); continue; } printf("couldn't match word given to pattern \"%s\"\n", pattern); } } char *translate_case(word) char *word; { /** destructively translate the word to all lowercase, returning both the altered word and a pointer to the altered word **/ register int index; for (index = 0; index < strlen(word); index++) word[index] = tolower(word[index]); return ( (char *) word); } char *remove_duplicate_letters(word) char *word; { /** This routine removes all multiply occuring letters in the given word and returns a 'sanitized' version of the word. For example, given the word "missionary" it would return "misionary". **/ register int index, bindex = 0; static char buffer[WORD_LENGTH]; buffer[bindex] = word[0]; for (index=1; index < strlen(word); index++) if (word[index] != word[index-1]) buffer[bindex++] = word[index]; buffer[bindex] = 0; return((char *) buffer); } int check_transpositions(word, pattern) char *word, *pattern; { /** transposes character pairs in word to see if any match the given pattern. Returns TRUE if so, FALSE if not. **/ register int index; Š char spare_character; for (index=1; index < strlen(word); index++) { spare_character = word[index]; word[index] = word[index-1]; word[index-1] = spare_character; if (strcmp(word, pattern) == 0) return(TRUE); word[index-1] = word[index]; word[index] = spare_character; } return(FALSE); } int allow_a_missing_character(word, pattern) char *word, *pattern; { /** This routine returns TRUE if word is the same as pattern, just missing a single letter. **/ register int index, windex = 0; if (strlen(word) + 1 != strlen(pattern)) return(FALSE); /* can't possibly match */ for (index=0, windex=0; index < strlen(pattern); index++) if (word[windex] == pattern[index]) windex++; else if (windex < index) return(FALSE); /* no match, already skipped a letter */ if (pattern[index] == word[windex]) return(TRUE); else return(FALSE); } int allow_an_incorrect_character(word, pattern) char *word, *pattern; { /** This routine returns TRUE if word is the same as pattern, just with a single incorrect letter **/ register int index, windex, already_seen_bad_letter = FALSE; if (strlen(word) != strlen(pattern)) return(FALSE); /* can't possibly match */ for (index=0, windex=0; index < strlen(pattern); index++) { if (word[windex] == pattern[index]) windex++; else if (already_seen_bad_letter) return(FALSE); /* already seen one wrong letter */ else { already_seen_bad_letter++; windex++; /* skip past the bad letter */ } } return(TRUE); } int soundex(word, pattern) Šchar *word, *pattern; { /** Implements the Soundex algorithm - this simple part simply gets the two words 'Soundex'ized then returns nonzero if the two match based on this technique. **/ char word2[WORD_LENGTH], pattern2[WORD_LENGTH]; strcpy(word2, soundex_translation_of(word)); strcpy(pattern2, soundex_translation_of(pattern)); return( (strcmp(word2, pattern2) == 0) ); } char * soundex_translation_of(buffer) char *buffer; { /** This routine implements the Soundex algorithm as presented in the accompanying article. **/ static char result[WORD_LENGTH]; register int i, j, ch, newch; /* Initialize string so we don't have to worry about not filling it all in when we're in the loop below... **/ result[0] = toupper(buffer[0]); result[1] = result[2] = result[3] = '0'; result[4] = '\0'; for (i=1, j=1; i < strlen(buffer) && j < SOUNDEX_LENGTH; i++) { ch = toupper(buffer[i]); if ((newch = soundex_mappings[index_of(ch)]) != IGNORE) /* it's a character we should be translating... */ if (result[j-1] != newch) /* it's not a dup of the previous */ if (! (j == 1 && ch == result[0])) /* it's not char #1 */ result[j++] = newch; } return( (char *) result); } double pf474_algorithm(word, pattern) char *word, *pattern; { /** This is the top-level PF474 pattern matching routine. It simply implements the actual equation we're using... */ if (strlen(word) == 0 && strlen(pattern) == 0) return(1.0); /* avoid divide-by-zero errors! */ return((double) (proximity_value(word, pattern) / (proximity_value(word, word)+proximity_value(pattern, pattern)))); } int proximity_value(word, pattern) char *word, *pattern; { /** This actually implements the algorithm used in the PF474 pattern matching chip from Proximity technologies, returning the number of matches encountered. **/ int matches = 0, iteration, index, len, count = 1; Š /* Shortcut - are the two the same? if so, we can compute the value much easier... */ if (strcmp(word, pattern) == 0) { for (count = 0; count <= strlen(word); count++) matches += (2*count); return(matches); } /* I guess not, well then.... */ /* first off, 'len' is always going to be the minimum of the lengths of the two strings (can't compare NULLs to characters!).. */ len = min(strlen(word), strlen(pattern)) + 1; /* Now the first real step is to go forward gradually looking at larger and larger slices of the string, adding up all paired characters */ count = 1; do { for (iteration = 1; iteration < len; iteration++) for (index = 0; index < iteration; index++) if (tolower(word[index]) == tolower(pattern[index])) matches++; strcpy(word, reverse(word)); strcpy(pattern, reverse(pattern)); } while (count++ < 2); return(0.0); } char *reverse(word) char *word; { /** reverse the word and return it... **/ static char buffer[WORD_LENGTH]; register int i, j = 0; for (i=strlen(word)-1; i > -1; i--) buffer[j++] = word[i]; buffer[j] = '\0'; return ( (char *) buffer); } /ª Thió prograí implementó thå variouó algorithmó discusseä iî thå accompanying article. Please refer to the article for further informatioî oî anù oæ thå particulaò techniqueó useä herein® (C) Copyright 1986, Dave Taylor */