contrib/fuzzystrmatch/daitch_mokotoff.c

   1 /*
   2  * Daitch-Mokotoff Soundex
   3  *
   4  * Copyright (c) 2023, PostgreSQL Global Development Group
   5  *
   6  * This module was originally sponsored by Finance Norway /
   7  * Trafikkforsikringsforeningen, and implemented by Dag Lem <dag@nimrod.no>
   8  *
   9  * The implementation of the Daitch-Mokotoff Soundex System aims at correctness
  10  * and high performance, and can be summarized as follows:
  11  *
  12  * - The processing of each phoneme is initiated by an O(1) table lookup.
  13  * - For phonemes containing more than one character, a coding tree is traversed
  14  *   to process the complete phoneme.
  15  * - The (alternate) soundex codes are produced digit by digit in-place in
  16  *   another tree structure.
  17  *
  18  * References:
  19  *
  20  * https://www.avotaynu.com/soundex.htm
  21  * https://www.jewishgen.org/InfoFiles/Soundex.html
  22  * https://familypedia.fandom.com/wiki/Daitch-Mokotoff_Soundex
  23  * https://stevemorse.org/census/soundex.html (dmlat.php, dmsoundex.php)
  24  * https://github.com/apache/commons-codec/ (dmrules.txt, DaitchMokotoffSoundex.java)
  25  * https://metacpan.org/pod/Text::Phonetic (DaitchMokotoff.pm)
  26  *
  27  * A few notes on other implementations:
  28  *
  29  * - All other known implementations have the same unofficial rules for "UE",
  30  *   these are also adapted by this implementation (0, 1, NC).
  31  * - The only other known implementation which is capable of generating all
  32  *   correct soundex codes in all cases is the JOS Soundex Calculator at
  33  *   https://www.jewishgen.org/jos/jossound.htm
  34  * - "J" is considered (only) a vowel in dmlat.php
  35  * - The official rules for "RS" are commented out in dmlat.php
  36  * - Identical code digits for adjacent letters are not collapsed correctly in
  37  *   dmsoundex.php when double digit codes are involved. E.g. "BESST" yields
  38  *   744300 instead of 743000 as for "BEST".
  39  * - "J" is considered (only) a consonant in DaitchMokotoffSoundex.java
  40  * - "Y" is not considered a vowel in DaitchMokotoffSoundex.java
  41 */
  42
  43 #include "postgres.h"
  44
  45 #include "catalog/pg_type.h"
  46 #include "mb/pg_wchar.h"
  47 #include "utils/array.h"
  48 #include "utils/builtins.h"
  49 #include "utils/memutils.h"
  50
  51
  52 /*
  53  * The soundex coding chart table is adapted from
  54  * https://www.jewishgen.org/InfoFiles/Soundex.html
  55  * See daitch_mokotoff_header.pl for details.
  56 */
  57
  58 /* Generated coding chart table */
  59 #include "daitch_mokotoff.h"
  60
  61 #define DM_CODE_DIGITS 6
  62
  63 /* Node in soundex code tree */
  64 typedef struct dm_node
  65 {
  66         int                     soundex_length; /* Length of generated soundex code */
  67         char            soundex[DM_CODE_DIGITS];        /* Soundex code */
  68         int                     is_leaf;                /* Candidate for complete soundex code */
  69         int                     last_update;    /* Letter number for last update of node */
  70         char            code_digit;             /* Last code digit, 0 - 9 */
  71
  72         /*
  73          * One or two alternate code digits leading to this node. If there are two
  74          * digits, one of them is always an 'X'. Repeated code digits and 'X' lead
  75          * back to the same node.
  76          */
  77         char            prev_code_digits[2];
  78         /* One or two alternate code digits moving forward. */
  79         char            next_code_digits[2];
  80         /* ORed together code index(es) used to reach current node. */
  81         int                     prev_code_index;
  82         int                     next_code_index;
  83         /* Possible nodes branching out from this node - digits 0-9. */
  84         struct dm_node *children[10];
  85         /* Next node in linked list. Alternating index for each iteration. */
  86         struct dm_node *next[2];
  87 } dm_node;
  88
  89 /* Template for new node in soundex code tree. */
  90 static const dm_node start_node = {
  91         .soundex_length = 0,
  92         .soundex = "000000",            /* Six digits */
  93         .is_leaf = 0,
  94         .last_update = 0,
  95         .code_digit = '\0',
  96         .prev_code_digits = {'\0', '\0'},
  97         .next_code_digits = {'\0', '\0'},
  98         .prev_code_index = 0,
  99         .next_code_index = 0,
 100         .children = {NULL},
 101         .next = {NULL}
 102 };
 103
 104 /* Dummy soundex codes at end of input. */
 105 static const dm_codes end_codes[2] =
 106 {
 107         {
 108                 "X", "X", "X"
 109         }
 110 };
 111
 112 /* Mapping from ISO8859-1 to upper-case ASCII, covering the range 0x60..0xFF. */
 113 static const char iso8859_1_to_ascii_upper[] =
 114 "`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~                                  !                             ?AAAAAAECEEEEIIIIDNOOOOO*OUUUUYDSAAAAAAECEEEEIIIIDNOOOOO/OUUUUYDY";
 115
 116 /* Internal C implementation */
 117 static bool daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex);
 118
 119
 120 PG_FUNCTION_INFO_V1(daitch_mokotoff);
 121
 122 Datum
 123 daitch_mokotoff(PG_FUNCTION_ARGS)
 124 {
 125         text       *arg = PG_GETARG_TEXT_PP(0);
 126         Datum           retval;
 127         char       *string;
 128         ArrayBuildState *soundex;
 129         MemoryContext old_ctx,
 130                                 tmp_ctx;
 131
 132         /* Work in a temporary context to simplify cleanup. */
 133         tmp_ctx = AllocSetContextCreate(CurrentMemoryContext,
 134                                                                         "daitch_mokotoff temporary context",
 135                                                                         ALLOCSET_DEFAULT_SIZES);
 136         old_ctx = MemoryContextSwitchTo(tmp_ctx);
 137
 138         /* We must convert the string to UTF-8 if it isn't already. */
 139         string = pg_server_to_any(text_to_cstring(arg), VARSIZE_ANY_EXHDR(arg),
 140                                                           PG_UTF8);
 141
 142         /* The result is built in this ArrayBuildState. */
 143         soundex = initArrayResult(TEXTOID, tmp_ctx, false);
 144
 145         if (!daitch_mokotoff_coding(string, soundex))
 146         {
 147                 /* No encodable characters in input */
 148                 MemoryContextSwitchTo(old_ctx);
 149                 MemoryContextDelete(tmp_ctx);
 150                 PG_RETURN_NULL();
 151         }
 152
 153         retval = makeArrayResult(soundex, old_ctx);
 154
 155         MemoryContextSwitchTo(old_ctx);
 156         MemoryContextDelete(tmp_ctx);
 157
 158         PG_RETURN_DATUM(retval);
 159 }
 160
 161
 162 /* Initialize soundex code tree node for next code digit. */
 163 static void
 164 initialize_node(dm_node *node, int last_update)
 165 {
 166         if (node->last_update < last_update)
 167         {
 168                 node->prev_code_digits[0] = node->next_code_digits[0];
 169                 node->prev_code_digits[1] = node->next_code_digits[1];
 170                 node->next_code_digits[0] = '\0';
 171                 node->next_code_digits[1] = '\0';
 172                 node->prev_code_index = node->next_code_index;
 173                 node->next_code_index = 0;
 174                 node->is_leaf = 0;
 175                 node->last_update = last_update;
 176         }
 177 }
 178
 179
 180 /* Update soundex code tree node with next code digit. */
 181 static void
 182 add_next_code_digit(dm_node *node, int code_index, char code_digit)
 183 {
 184         /* OR in index 1 or 2. */
 185         node->next_code_index |= code_index;
 186
 187         if (!node->next_code_digits[0])
 188                 node->next_code_digits[0] = code_digit;
 189         else if (node->next_code_digits[0] != code_digit)
 190                 node->next_code_digits[1] = code_digit;
 191 }
 192
 193
 194 /* Mark soundex code tree node as leaf. */
 195 static void
 196 set_leaf(dm_node *first_node[2], dm_node *last_node[2],
 197                  dm_node *node, int ix_node)
 198 {
 199         if (!node->is_leaf)
 200         {
 201                 node->is_leaf = 1;
 202
 203                 if (first_node[ix_node] == NULL)
 204                         first_node[ix_node] = node;
 205                 else
 206                         last_node[ix_node]->next[ix_node] = node;
 207
 208                 last_node[ix_node] = node;
 209                 node->next[ix_node] = NULL;
 210         }
 211 }
 212
 213
 214 /* Find next node corresponding to code digit, or create a new node. */
 215 static dm_node *
 216 find_or_create_child_node(dm_node *parent, char code_digit,
 217                                                   ArrayBuildState *soundex)
 218 {
 219         int                     i = code_digit - '0';
 220         dm_node   **nodes = parent->children;
 221         dm_node    *node = nodes[i];
 222
 223         if (node)
 224         {
 225                 /* Found existing child node. Skip completed nodes. */
 226                 return node->soundex_length < DM_CODE_DIGITS ? node : NULL;
 227         }
 228
 229         /* Create new child node. */
 230         node = palloc_object(dm_node);
 231         nodes[i] = node;
 232
 233         *node = start_node;
 234         memcpy(node->soundex, parent->soundex, sizeof(parent->soundex));
 235         node->soundex_length = parent->soundex_length;
 236         node->soundex[node->soundex_length++] = code_digit;
 237         node->code_digit = code_digit;
 238         node->next_code_index = node->prev_code_index;
 239
 240         if (node->soundex_length < DM_CODE_DIGITS)
 241         {
 242                 return node;
 243         }
 244         else
 245         {
 246                 /* Append completed soundex code to output array. */
 247                 text       *out = cstring_to_text_with_len(node->soundex,
 248                                                                                                    DM_CODE_DIGITS);
 249
 250                 accumArrayResult(soundex,
 251                                                  PointerGetDatum(out),
 252                                                  false,
 253                                                  TEXTOID,
 254                                                  CurrentMemoryContext);
 255                 return NULL;
 256         }
 257 }
 258
 259
 260 /* Update node for next code digit(s). */
 261 static void
 262 update_node(dm_node *first_node[2], dm_node *last_node[2],
 263                         dm_node *node, int ix_node,
 264                         int letter_no, int prev_code_index, int next_code_index,
 265                         const char *next_code_digits, int digit_no,
 266                         ArrayBuildState *soundex)
 267 {
 268         int                     i;
 269         char            next_code_digit = next_code_digits[digit_no];
 270         int                     num_dirty_nodes = 0;
 271         dm_node    *dirty_nodes[2];
 272
 273         initialize_node(node, letter_no);
 274
 275         if (node->prev_code_index && !(node->prev_code_index & prev_code_index))
 276         {
 277                 /*
 278                  * If the sound (vowel / consonant) of this letter encoding doesn't
 279                  * correspond to the coding index of the previous letter, we skip this
 280                  * letter encoding. Note that currently, only "J" can be either a
 281                  * vowel or a consonant.
 282                  */
 283                 return;
 284         }
 285
 286         if (next_code_digit == 'X' ||
 287                 (digit_no == 0 &&
 288                  (node->prev_code_digits[0] == next_code_digit ||
 289                   node->prev_code_digits[1] == next_code_digit)))
 290         {
 291                 /* The code digit is the same as one of the previous (i.e. not added). */
 292                 dirty_nodes[num_dirty_nodes++] = node;
 293         }
 294
 295         if (next_code_digit != 'X' &&
 296                 (digit_no > 0 ||
 297                  node->prev_code_digits[0] != next_code_digit ||
 298                  node->prev_code_digits[1]))
 299         {
 300                 /* The code digit is different from one of the previous (i.e. added). */
 301                 node = find_or_create_child_node(node, next_code_digit, soundex);
 302                 if (node)
 303                 {
 304                         initialize_node(node, letter_no);
 305                         dirty_nodes[num_dirty_nodes++] = node;
 306                 }
 307         }
 308
 309         for (i = 0; i < num_dirty_nodes; i++)
 310         {
 311                 /* Add code digit leading to the current node. */
 312                 add_next_code_digit(dirty_nodes[i], next_code_index, next_code_digit);
 313
 314                 if (next_code_digits[++digit_no])
 315                 {
 316                         update_node(first_node, last_node, dirty_nodes[i], ix_node,
 317                                                 letter_no, prev_code_index, next_code_index,
 318                                                 next_code_digits, digit_no,
 319                                                 soundex);
 320                 }
 321                 else
 322                 {
 323                         /* Add incomplete leaf node to linked list. */
 324                         set_leaf(first_node, last_node, dirty_nodes[i], ix_node);
 325                 }
 326         }
 327 }
 328
 329
 330 /* Update soundex tree leaf nodes. */
 331 static void
 332 update_leaves(dm_node *first_node[2], int *ix_node, int letter_no,
 333                           const dm_codes *codes, const dm_codes *next_codes,
 334                           ArrayBuildState *soundex)
 335 {
 336         int                     i,
 337                                 j,
 338                                 code_index;
 339         dm_node    *node,
 340                            *last_node[2];
 341         const dm_code *code,
 342                            *next_code;
 343         int                     ix_node_next = (*ix_node + 1) & 1;      /* Alternating index: 0, 1 */
 344
 345         /* Initialize for new linked list of leaves. */
 346         first_node[ix_node_next] = NULL;
 347         last_node[ix_node_next] = NULL;
 348
 349         /* Process all nodes. */
 350         for (node = first_node[*ix_node]; node; node = node->next[*ix_node])
 351         {
 352                 /* One or two alternate code sequences. */
 353                 for (i = 0; i < 2 && (code = codes[i]) && code[0][0]; i++)
 354                 {
 355                         /* Coding for previous letter - before vowel: 1, all other: 2 */
 356                         int                     prev_code_index = (code[0][0] > '1') + 1;
 357
 358                         /* One or two alternate next code sequences. */
 359                         for (j = 0; j < 2 && (next_code = next_codes[j]) && next_code[0][0]; j++)
 360                         {
 361                                 /* Determine which code to use. */
 362                                 if (letter_no == 0)
 363                                 {
 364                                         /* This is the first letter. */
 365                                         code_index = 0;
 366                                 }
 367                                 else if (next_code[0][0] <= '1')
 368                                 {
 369                                         /* The next letter is a vowel. */
 370                                         code_index = 1;
 371                                 }
 372                                 else
 373                                 {
 374                                         /* All other cases. */
 375                                         code_index = 2;
 376                                 }
 377
 378                                 /* One or two sequential code digits. */
 379                                 update_node(first_node, last_node, node, ix_node_next,
 380                                                         letter_no, prev_code_index, code_index,
 381                                                         code[code_index], 0,
 382                                                         soundex);
 383                         }
 384                 }
 385         }
 386
 387         *ix_node = ix_node_next;
 388 }
 389
 390
 391 /*
 392  * Return next character, converted from UTF-8 to uppercase ASCII.
 393  * *ix is the current string index and is incremented by the character length.
 394  */
 395 static char
 396 read_char(const unsigned char *str, int *ix)
 397 {
 398         /* Substitute character for skipped code points. */
 399         const char      na = '\x1a';
 400         pg_wchar        c;
 401
 402         /* Decode UTF-8 character to ISO 10646 code point. */
 403         str += *ix;
 404         c = utf8_to_unicode(str);
 405
 406         /* Advance *ix, but (for safety) not if we've reached end of string. */
 407         if (c)
 408                 *ix += pg_utf_mblen(str);
 409
 410         /* Convert. */
 411         if (c >= (unsigned char) '[' && c <= (unsigned char) ']')
 412         {
 413                 /* ASCII characters [, \, and ] are reserved for conversions below. */
 414                 return na;
 415         }
 416         else if (c < 0x60)
 417         {
 418                 /* Other non-lowercase ASCII characters can be used as-is. */
 419                 return (char) c;
 420         }
 421         else if (c < 0x100)
 422         {
 423                 /* ISO-8859-1 code point; convert to upper-case ASCII via table. */
 424                 return iso8859_1_to_ascii_upper[c - 0x60];
 425         }
 426         else
 427         {
 428                 /* Conversion of non-ASCII characters in the coding chart. */
 429                 switch (c)
 430                 {
 431                         case 0x0104:            /* LATIN CAPITAL LETTER A WITH OGONEK */
 432                         case 0x0105:            /* LATIN SMALL LETTER A WITH OGONEK */
 433                                 return '[';
 434                         case 0x0118:            /* LATIN CAPITAL LETTER E WITH OGONEK */
 435                         case 0x0119:            /* LATIN SMALL LETTER E WITH OGONEK */
 436                                 return '\\';
 437                         case 0x0162:            /* LATIN CAPITAL LETTER T WITH CEDILLA */
 438                         case 0x0163:            /* LATIN SMALL LETTER T WITH CEDILLA */
 439                         case 0x021A:            /* LATIN CAPITAL LETTER T WITH COMMA BELOW */
 440                         case 0x021B:            /* LATIN SMALL LETTER T WITH COMMA BELOW */
 441                                 return ']';
 442                         default:
 443                                 return na;
 444                 }
 445         }
 446 }
 447
 448
 449 /* Read next ASCII character, skipping any characters not in [A-\]]. */
 450 static char
 451 read_valid_char(const char *str, int *ix)
 452 {
 453         char            c;
 454
 455         while ((c = read_char((const unsigned char *) str, ix)) != '\0')
 456         {
 457                 if (c >= 'A' && c <= ']')
 458                         break;
 459         }
 460
 461         return c;
 462 }
 463
 464
 465 /* Return sound coding for "letter" (letter sequence) */
 466 static const dm_codes *
 467 read_letter(const char *str, int *ix)
 468 {
 469         char            c,
 470                                 cmp;
 471         int                     i,
 472                                 j;
 473         const dm_letter *letters;
 474         const dm_codes *codes;
 475
 476         /* First letter in sequence. */
 477         if ((c = read_valid_char(str, ix)) == '\0')
 478                 return NULL;
 479
 480         letters = &letter_[c - 'A'];
 481         codes = letters->codes;
 482         i = *ix;
 483
 484         /* Any subsequent letters in sequence. */
 485         while ((letters = letters->letters) && (c = read_valid_char(str, &i)))
 486         {
 487                 for (j = 0; (cmp = letters[j].letter); j++)
 488                 {
 489                         if (cmp == c)
 490                         {
 491                                 /* Letter found. */
 492                                 letters = &letters[j];
 493                                 if (letters->codes)
 494                                 {
 495                                         /* Coding for letter sequence found. */
 496                                         codes = letters->codes;
 497                                         *ix = i;
 498                                 }
 499                                 break;
 500                         }
 501                 }
 502                 if (!cmp)
 503                 {
 504                         /* The sequence of letters has no coding. */
 505                         break;
 506                 }
 507         }
 508
 509         return codes;
 510 }
 511
 512
 513 /*
 514  * Generate all Daitch-Mokotoff soundex codes for word,
 515  * adding them to the "soundex" ArrayBuildState.
 516  * Returns false if string has no encodable characters, else true.
 517  */
 518 static bool
 519 daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex)
 520 {
 521         int                     i = 0;
 522         int                     letter_no = 0;
 523         int                     ix_node = 0;
 524         const dm_codes *codes,
 525                            *next_codes;
 526         dm_node    *first_node[2],
 527                            *node;
 528
 529         /* First letter. */
 530         if (!(codes = read_letter(word, &i)))
 531         {
 532                 /* No encodable character in input. */
 533                 return false;
 534         }
 535
 536         /* Starting point. */
 537         first_node[ix_node] = palloc_object(dm_node);
 538         *first_node[ix_node] = start_node;
 539
 540         /*
 541          * Loop until either the word input is exhausted, or all generated soundex
 542          * codes are completed to six digits.
 543          */
 544         while (codes && first_node[ix_node])
 545         {
 546                 next_codes = read_letter(word, &i);
 547
 548                 /* Update leaf nodes. */
 549                 update_leaves(first_node, &ix_node, letter_no,
 550                                           codes, next_codes ? next_codes : end_codes,
 551                                           soundex);
 552
 553                 codes = next_codes;
 554                 letter_no++;
 555         }
 556
 557         /* Append all remaining (incomplete) soundex codes to output array. */
 558         for (node = first_node[ix_node]; node; node = node->next[ix_node])
 559         {
 560                 text       *out = cstring_to_text_with_len(node->soundex,
 561                                                                                                    DM_CODE_DIGITS);
 562
 563                 accumArrayResult(soundex,
 564                                                  PointerGetDatum(out),
 565                                                  false,
 566                                                  TEXTOID,
 567                                                  CurrentMemoryContext);
 568         }
 569
 570         return true;
 571 }