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

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