git.sur5r.net Git - openldap/blob - servers/slapd/phonetic.c

   1 /* phonetic.c - routines to do phonetic matching */
   2
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include <ctype.h>
   6 #include <sys/time.h>
   7 #include <sys/types.h>
   8 #include <sys/socket.h>
   9 #include "portable.h"
  10 #include "slap.h"
  11
  12 #if !defined(METAPHONE) && !defined(SOUNDEX)
  13 #define METAPHONE
  14 #endif
  15
  16 #define iswordbreak(x)  (!isascii(x) || isspace((unsigned char) (x)) || \
  17                          ispunct((unsigned char) (x)) || \
  18                          isdigit((unsigned char) (x)) || x == '\0')
  19
  20 char *
  21 first_word( char *s )
  22 {
  23         if ( s == NULL ) {
  24                 return( NULL );
  25         }
  26
  27         while ( iswordbreak( *s ) ) {
  28                 if ( *s == '\0' ) {
  29                         return( NULL );
  30                 } else {
  31                         s++;
  32                 }
  33         }
  34
  35         return( s );
  36 }
  37
  38 char *
  39 next_word( char *s )
  40 {
  41         if ( s == NULL ) {
  42                 return( NULL );
  43         }
  44
  45         while ( ! iswordbreak( *s ) ) {
  46                 s++;
  47         }
  48
  49         while ( iswordbreak( *s ) ) {
  50                 if ( *s == '\0' ) {
  51                         return( NULL );
  52                 } else {
  53                         s++;
  54                 }
  55         }
  56
  57         return( s );
  58 }
  59
  60 char *
  61 word_dup( char *w )
  62 {
  63         char    *s, *ret;
  64         char    save;
  65
  66         for ( s = w; !iswordbreak( *s ); s++ )
  67                 ;       /* NULL */
  68         save = *s;
  69         *s = '\0';
  70         ret = strdup( w );
  71         *s = save;
  72
  73         return( ret );
  74 }
  75
  76 #ifndef MAXPHONEMELEN
  77 #define MAXPHONEMELEN   4
  78 #endif
  79
  80 #if defined(SOUNDEX)
  81
  82 /* lifted from isode-8.0 */
  83 char *
  84 phonetic( char *s )
  85 {
  86         char    code, adjacent, ch;
  87         char    *p;
  88         char    **c;
  89         int     i, cmax;
  90         char    phoneme[MAXPHONEMELEN + 1];
  91
  92         p = s;
  93         if (  p == NULL || *p == '\0' ) {
  94                 return( NULL );
  95         }
  96
  97         adjacent = '0';
  98         phoneme[0] = TOUPPER(*p);
  99
 100         phoneme[1]  = '\0';
 101         for ( i = 0; i < 99 && (! iswordbreak(*p)); p++ ) {
 102                 ch = TOUPPER (*p);
 103
 104                 code = '0';
 105
 106                 switch (ch) {
 107                 case 'B':
 108                 case 'F':
 109                 case 'P':
 110                 case 'V':
 111                         code = (adjacent != '1') ? '1' : '0';
 112                         break;
 113                 case 'S':
 114                 case 'C':
 115                 case 'G':
 116                 case 'J':
 117                 case 'K':
 118                 case 'Q':
 119                 case 'X':
 120                 case 'Z':
 121                         code = (adjacent != '2') ? '2' : '0';
 122                         break;
 123                 case 'D':
 124                 case 'T':
 125                         code = (adjacent != '3') ? '3' : '0';
 126                         break;
 127                 case 'L':
 128                         code = (adjacent != '4') ? '4' : '0';
 129                         break;
 130                 case 'M':
 131                 case 'N':
 132                         code = (adjacent != '5') ? '5' : '0';
 133                         break;
 134                 case 'R':
 135                         code = (adjacent != '6') ? '6' : '0';
 136                         break;
 137                 default:
 138                         adjacent = '0';
 139                 }
 140
 141                 if ( i == 0 ) {
 142                         adjacent = code;
 143                         i++;
 144                 } else if ( code != '0' ) {
 145                         if ( i == MAXPHONEMELEN )
 146                                 break;
 147                         adjacent = phoneme[i] = code;
 148                         i++;
 149                 }
 150         }
 151
 152         if ( i > 0 )
 153                 phoneme[i] = '\0';
 154
 155         return( strdup( phoneme ) );
 156 }
 157
 158 #else
 159 #if defined(METAPHONE)
 160
 161 /*
 162  * Metaphone copied from C Gazette, June/July 1991, pp 56-57,
 163  * author Gary A. Parker, with changes by Bernard Tiffany of the
 164  * University of Michigan, and more changes by Tim Howes of the
 165  * University of Michigan.
 166  */
 167
 168 /* Character coding array */
 169 static char     vsvfn[26] = {
 170            1, 16, 4, 16, 9, 2, 4, 16, 9, 2, 0, 2, 2,
 171         /* A   B  C   D  E  F  G   H  I  J  K  L  M  */
 172            2, 1, 4, 0, 2, 4, 4, 1, 0, 0, 0, 8, 0};
 173         /* N  O  P  Q  R  S  T  U  V  W  X  Y  Z  */
 174
 175 /* Macros to access character coding array */
 176 #define vowel(x)        ((x) != '\0' && vsvfn[(x) - 'A'] & 1)   /* AEIOU */
 177 #define same(x)         ((x) != '\0' && vsvfn[(x) - 'A'] & 2)   /* FJLMNR */
 178 #define varson(x)       ((x) != '\0' && vsvfn[(x) - 'A'] & 4)   /* CGPST */
 179 #define frontv(x)       ((x) != '\0' && vsvfn[(x) - 'A'] & 8)   /* EIY */
 180 #define noghf(x)        ((x) != '\0' && vsvfn[(x) - 'A'] & 16)  /* BDH */
 181
 182 char *
 183 phonetic( char *Word )
 184 {
 185         char           *n, *n_start, *n_end;    /* pointers to string */
 186         char           *metaph, *metaph_end;    /* pointers to metaph */
 187         char            ntrans[40];     /* word with uppercase letters */
 188         char            newm[8];/* new metaph for comparison */
 189         int             KSflag; /* state flag for X -> KS */
 190         char            buf[MAXPHONEMELEN + 2];
 191         char            *Metaph;
 192
 193         /*
 194          * Copy Word to internal buffer, dropping non-alphabetic characters
 195          * and converting to upper case
 196          */
 197
 198         for (n = ntrans + 4, n_end = ntrans + 35; !iswordbreak( *Word ) &&
 199             n < n_end; Word++) {
 200                 if (isalpha(*Word))
 201                         *n++ = TOUPPER(*Word);
 202         }
 203         Metaph = buf;
 204         *Metaph = '\0';
 205         if (n == ntrans + 4) {
 206                 return( strdup( buf ) );                /* Return if null */
 207         }
 208         n_end = n;              /* Set n_end to end of string */
 209
 210         /* ntrans[0] will always be == 0 */
 211         ntrans[0] = '\0';
 212         ntrans[1] = '\0';
 213         ntrans[2] = '\0';
 214         ntrans[3] = '\0';
 215         *n++ = 0;
 216         *n++ = 0;
 217         *n++ = 0;
 218         *n = 0;                 /* Pad with nulls */
 219         n = ntrans + 4;         /* Assign pointer to start */
 220
 221         /* Check for PN, KN, GN, AE, WR, WH, and X at start */
 222         switch (*n) {
 223         case 'P':
 224         case 'K':
 225         case 'G':
 226                 /* 'PN', 'KN', 'GN' becomes 'N' */
 227                 if (*(n + 1) == 'N')
 228                         *n++ = 0;
 229                 break;
 230         case 'A':
 231                 /* 'AE' becomes 'E' */
 232                 if (*(n + 1) == 'E')
 233                         *n++ = 0;
 234                 break;
 235         case 'W':
 236                 /* 'WR' becomes 'R', and 'WH' to 'H' */
 237                 if (*(n + 1) == 'R')
 238                         *n++ = 0;
 239                 else if (*(n + 1) == 'H') {
 240                         *(n + 1) = *n;
 241                         *n++ = 0;
 242                 }
 243                 break;
 244         case 'X':
 245                 /* 'X' becomes 'S' */
 246                 *n = 'S';
 247                 break;
 248         }
 249
 250         /*
 251          * Now, loop step through string, stopping at end of string or when
 252          * the computed 'metaph' is MAXPHONEMELEN characters long
 253          */
 254
 255         KSflag = 0;             /* state flag for KS translation */
 256         for (metaph_end = Metaph + MAXPHONEMELEN, n_start = n;
 257              n <= n_end && Metaph < metaph_end; n++) {
 258                 if (KSflag) {
 259                         KSflag = 0;
 260                         *Metaph++ = 'S';
 261                 } else {
 262                         /* Drop duplicates except for CC */
 263                         if (*(n - 1) == *n && *n != 'C')
 264                                 continue;
 265                         /* Check for F J L M N R or first letter vowel */
 266                         if (same(*n) || (n == n_start && vowel(*n)))
 267                                 *Metaph++ = *n;
 268                         else
 269                                 switch (*n) {
 270                                 case 'B':
 271
 272                                         /*
 273                                          * B unless in -MB
 274                                          */
 275                                         if (n == (n_end - 1) && *(n - 1) != 'M')
 276                                                 *Metaph++ = *n;
 277                                         break;
 278                                 case 'C':
 279
 280                                         /*
 281                                          * X if in -CIA-, -CH- else S if in
 282                                          * -CI-, -CE-, -CY- else dropped if
 283                                          * in -SCI-, -SCE-, -SCY- else K
 284                                          */
 285                                         if (*(n - 1) != 'S' || !frontv(*(n + 1))) {
 286                                                 if (*(n + 1) == 'I' && *(n + 2) == 'A')
 287                                                         *Metaph++ = 'X';
 288                                                 else if (frontv(*(n + 1)))
 289                                                         *Metaph++ = 'S';
 290                                                 else if (*(n + 1) == 'H')
 291                                                         *Metaph++ = ((n == n_start && !vowel(*(n + 2)))
 292                                                          || *(n - 1) == 'S')
 293                                                             ? (char) 'K' : (char) 'X';
 294                                                 else
 295                                                         *Metaph++ = 'K';
 296                                         }
 297                                         break;
 298                                 case 'D':
 299
 300                                         /*
 301                                          * J if in DGE or DGI or DGY else T
 302                                          */
 303                                         *Metaph++ = (*(n + 1) == 'G' && frontv(*(n + 2)))
 304                                             ? (char) 'J' : (char) 'T';
 305                                         break;
 306                                 case 'G':
 307
 308                                         /*
 309                                          * F if in -GH and not B--GH, D--GH,
 310                                          * -H--GH, -H---GH else dropped if
 311                                          * -GNED, -GN, -DGE-, -DGI-, -DGY-
 312                                          * else J if in -GE-, -GI-, -GY- and
 313                                          * not GG else K
 314                                          */
 315                                         if ((*(n + 1) != 'J' || vowel(*(n + 2))) &&
 316                                             (*(n + 1) != 'N' || ((n + 1) < n_end &&
 317                                                                  (*(n + 2) != 'E' || *(n + 3) != 'D'))) &&
 318                                             (*(n - 1) != 'D' || !frontv(*(n + 1))))
 319                                                 *Metaph++ = (frontv(*(n + 1)) &&
 320                                                              *(n + 2) != 'G') ? (char) 'G' : (char) 'K';
 321                                         else if (*(n + 1) == 'H' && !noghf(*(n - 3)) &&
 322                                                  *(n - 4) != 'H')
 323                                                 *Metaph++ = 'F';
 324                                         break;
 325                                 case 'H':
 326
 327                                         /*
 328                                          * H if before a vowel and not after
 329                                          * C, G, P, S, T else dropped
 330                                          */
 331                                         if (!varson(*(n - 1)) && (!vowel(*(n - 1)) ||
 332                                                            vowel(*(n + 1))))
 333                                                 *Metaph++ = 'H';
 334                                         break;
 335                                 case 'K':
 336
 337                                         /*
 338                                          * dropped if after C else K
 339                                          */
 340                                         if (*(n - 1) != 'C')
 341                                                 *Metaph++ = 'K';
 342                                         break;
 343                                 case 'P':
 344
 345                                         /*
 346                                          * F if before H, else P
 347                                          */
 348                                         *Metaph++ = *(n + 1) == 'H' ?
 349                                             (char) 'F' : (char) 'P';
 350                                         break;
 351                                 case 'Q':
 352
 353                                         /*
 354                                          * K
 355                                          */
 356                                         *Metaph++ = 'K';
 357                                         break;
 358                                 case 'S':
 359
 360                                         /*
 361                                          * X in -SH-, -SIO- or -SIA- else S
 362                                          */
 363                                         *Metaph++ = (*(n + 1) == 'H' ||
 364                                                      (*(n + 1) == 'I' && (*(n + 2) == 'O' ||
 365                                                           *(n + 2) == 'A')))
 366                                             ? (char) 'X' : (char) 'S';
 367                                         break;
 368                                 case 'T':
 369
 370                                         /*
 371                                          * X in -TIA- or -TIO- else 0 (zero)
 372                                          * before H else dropped if in -TCH-
 373                                          * else T
 374                                          */
 375                                         if (*(n + 1) == 'I' && (*(n + 2) == 'O' ||
 376                                                            *(n + 2) == 'A'))
 377                                                 *Metaph++ = 'X';
 378                                         else if (*(n + 1) == 'H')
 379                                                 *Metaph++ = '0';
 380                                         else if (*(n + 1) != 'C' || *(n + 2) != 'H')
 381                                                 *Metaph++ = 'T';
 382                                         break;
 383                                 case 'V':
 384
 385                                         /*
 386                                          * F
 387                                          */
 388                                         *Metaph++ = 'F';
 389                                         break;
 390                                 case 'W':
 391
 392                                         /*
 393                                          * W after a vowel, else dropped
 394                                          */
 395                                 case 'Y':
 396
 397                                         /*
 398                                          * Y unless followed by a vowel
 399                                          */
 400                                         if (vowel(*(n + 1)))
 401                                                 *Metaph++ = *n;
 402                                         break;
 403                                 case 'X':
 404
 405                                         /*
 406                                          * KS
 407                                          */
 408                                         if (n == n_start)
 409                                                 *Metaph++ = 'S';
 410                                         else {
 411                                                 *Metaph++ = 'K';        /* Insert K, then S */
 412                                                 KSflag = 1;
 413                                         }
 414                                         break;
 415                                 case 'Z':
 416
 417                                         /*
 418                                          * S
 419                                          */
 420                                         *Metaph++ = 'S';
 421                                         break;
 422                                 }
 423                 }
 424         }
 425
 426         *Metaph = 0;            /* Null terminate */
 427         return( strdup( buf ) );
 428 }
 429
 430 #endif /* metaphone */
 431 #endif /* soundex */