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

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