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

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