LCOV - code coverage report
Current view: top level - contrib/fuzzystrmatch - daitch_mokotoff.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 155 162 95.7 %
Date: 2024-04-25 00:11:39 Functions: 12 12 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :  * Daitch-Mokotoff Soundex
       3             :  *
       4             :  * Copyright (c) 2023-2024, 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           6 : PG_FUNCTION_INFO_V1(daitch_mokotoff);
     121             : 
     122             : Datum
     123          70 : daitch_mokotoff(PG_FUNCTION_ARGS)
     124             : {
     125          70 :     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          70 :     tmp_ctx = AllocSetContextCreate(CurrentMemoryContext,
     134             :                                     "daitch_mokotoff temporary context",
     135             :                                     ALLOCSET_DEFAULT_SIZES);
     136          70 :     old_ctx = MemoryContextSwitchTo(tmp_ctx);
     137             : 
     138             :     /* We must convert the string to UTF-8 if it isn't already. */
     139          70 :     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          70 :     soundex = initArrayResult(TEXTOID, tmp_ctx, false);
     144             : 
     145          70 :     if (!daitch_mokotoff_coding(string, soundex))
     146             :     {
     147             :         /* No encodable characters in input */
     148           0 :         MemoryContextSwitchTo(old_ctx);
     149           0 :         MemoryContextDelete(tmp_ctx);
     150           0 :         PG_RETURN_NULL();
     151             :     }
     152             : 
     153          70 :     retval = makeArrayResult(soundex, old_ctx);
     154             : 
     155          70 :     MemoryContextSwitchTo(old_ctx);
     156          70 :     MemoryContextDelete(tmp_ctx);
     157             : 
     158          70 :     PG_RETURN_DATUM(retval);
     159             : }
     160             : 
     161             : 
     162             : /* Initialize soundex code tree node for next code digit. */
     163             : static void
     164        1328 : initialize_node(dm_node *node, int last_update)
     165             : {
     166        1328 :     if (node->last_update < last_update)
     167             :     {
     168         926 :         node->prev_code_digits[0] = node->next_code_digits[0];
     169         926 :         node->prev_code_digits[1] = node->next_code_digits[1];
     170         926 :         node->next_code_digits[0] = '\0';
     171         926 :         node->next_code_digits[1] = '\0';
     172         926 :         node->prev_code_index = node->next_code_index;
     173         926 :         node->next_code_index = 0;
     174         926 :         node->is_leaf = 0;
     175         926 :         node->last_update = last_update;
     176             :     }
     177        1328 : }
     178             : 
     179             : 
     180             : /* Update soundex code tree node with next code digit. */
     181             : static void
     182         802 : add_next_code_digit(dm_node *node, int code_index, char code_digit)
     183             : {
     184             :     /* OR in index 1 or 2. */
     185         802 :     node->next_code_index |= code_index;
     186             : 
     187         802 :     if (!node->next_code_digits[0])
     188         720 :         node->next_code_digits[0] = code_digit;
     189          82 :     else if (node->next_code_digits[0] != code_digit)
     190           4 :         node->next_code_digits[1] = code_digit;
     191         802 : }
     192             : 
     193             : 
     194             : /* Mark soundex code tree node as leaf. */
     195             : static void
     196         776 : set_leaf(dm_node *first_node[2], dm_node *last_node[2],
     197             :          dm_node *node, int ix_node)
     198             : {
     199         776 :     if (!node->is_leaf)
     200             :     {
     201         698 :         node->is_leaf = 1;
     202             : 
     203         698 :         if (first_node[ix_node] == NULL)
     204         436 :             first_node[ix_node] = node;
     205             :         else
     206         262 :             last_node[ix_node]->next[ix_node] = node;
     207             : 
     208         698 :         last_node[ix_node] = node;
     209         698 :         node->next[ix_node] = NULL;
     210             :     }
     211         776 : }
     212             : 
     213             : 
     214             : /* Find next node corresponding to code digit, or create a new node. */
     215             : static dm_node *
     216         512 : find_or_create_child_node(dm_node *parent, char code_digit,
     217             :                           ArrayBuildState *soundex)
     218             : {
     219         512 :     int         i = code_digit - '0';
     220         512 :     dm_node   **nodes = parent->children;
     221         512 :     dm_node    *node = nodes[i];
     222             : 
     223         512 :     if (node)
     224             :     {
     225             :         /* Found existing child node. Skip completed nodes. */
     226          42 :         return node->soundex_length < DM_CODE_DIGITS ? node : NULL;
     227             :     }
     228             : 
     229             :     /* Create new child node. */
     230         470 :     node = palloc_object(dm_node);
     231         470 :     nodes[i] = node;
     232             : 
     233         470 :     *node = start_node;
     234         470 :     memcpy(node->soundex, parent->soundex, sizeof(parent->soundex));
     235         470 :     node->soundex_length = parent->soundex_length;
     236         470 :     node->soundex[node->soundex_length++] = code_digit;
     237         470 :     node->code_digit = code_digit;
     238         470 :     node->next_code_index = node->prev_code_index;
     239             : 
     240         470 :     if (node->soundex_length < DM_CODE_DIGITS)
     241             :     {
     242         438 :         return node;
     243             :     }
     244             :     else
     245             :     {
     246             :         /* Append completed soundex code to output array. */
     247          32 :         text       *out = cstring_to_text_with_len(node->soundex,
     248             :                                                    DM_CODE_DIGITS);
     249             : 
     250          32 :         accumArrayResult(soundex,
     251             :                          PointerGetDatum(out),
     252             :                          false,
     253             :                          TEXTOID,
     254             :                          CurrentMemoryContext);
     255          32 :         return NULL;
     256             :     }
     257             : }
     258             : 
     259             : 
     260             : /* Update node for next code digit(s). */
     261             : static void
     262         848 : 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         848 :     char        next_code_digit = next_code_digits[digit_no];
     270         848 :     int         num_dirty_nodes = 0;
     271             :     dm_node    *dirty_nodes[2];
     272             : 
     273         848 :     initialize_node(node, letter_no);
     274             : 
     275         848 :     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          16 :         return;
     284             :     }
     285             : 
     286         832 :     if (next_code_digit == 'X' ||
     287         518 :         (digit_no == 0 &&
     288         518 :          (node->prev_code_digits[0] == next_code_digit ||
     289         486 :           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         322 :         dirty_nodes[num_dirty_nodes++] = node;
     293             :     }
     294             : 
     295         832 :     if (next_code_digit != 'X' &&
     296         518 :         (digit_no > 0 ||
     297         518 :          node->prev_code_digits[0] != next_code_digit ||
     298          32 :          node->prev_code_digits[1]))
     299             :     {
     300             :         /* The code digit is different from one of the previous (i.e. added). */
     301         512 :         node = find_or_create_child_node(node, next_code_digit, soundex);
     302         512 :         if (node)
     303             :         {
     304         480 :             initialize_node(node, letter_no);
     305         480 :             dirty_nodes[num_dirty_nodes++] = node;
     306             :         }
     307             :     }
     308             : 
     309        1634 :     for (i = 0; i < num_dirty_nodes; i++)
     310             :     {
     311             :         /* Add code digit leading to the current node. */
     312         802 :         add_next_code_digit(dirty_nodes[i], next_code_index, next_code_digit);
     313             : 
     314         802 :         if (next_code_digits[++digit_no])
     315             :         {
     316          26 :             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         776 :             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         446 : 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         446 :     int         ix_node_next = (*ix_node + 1) & 1;  /* Alternating index: 0, 1 */
     344             : 
     345             :     /* Initialize for new linked list of leaves. */
     346         446 :     first_node[ix_node_next] = NULL;
     347         446 :     last_node[ix_node_next] = NULL;
     348             : 
     349             :     /* Process all nodes. */
     350        1086 :     for (node = first_node[*ix_node]; node; node = node->next[*ix_node])
     351             :     {
     352             :         /* One or two alternate code sequences. */
     353        1380 :         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         740 :             int         prev_code_index = (code[0][0] > '1') + 1;
     357             : 
     358             :             /* One or two alternate next code sequences. */
     359        1562 :             for (j = 0; j < 2 && (next_code = next_codes[j]) && next_code[0][0]; j++)
     360             :             {
     361             :                 /* Determine which code to use. */
     362         822 :                 if (letter_no == 0)
     363             :                 {
     364             :                     /* This is the first letter. */
     365          96 :                     code_index = 0;
     366             :                 }
     367         726 :                 else if (next_code[0][0] <= '1')
     368             :                 {
     369             :                     /* The next letter is a vowel. */
     370         194 :                     code_index = 1;
     371             :                 }
     372             :                 else
     373             :                 {
     374             :                     /* All other cases. */
     375         532 :                     code_index = 2;
     376             :                 }
     377             : 
     378             :                 /* One or two sequential code digits. */
     379         822 :                 update_node(first_node, last_node, node, ix_node_next,
     380             :                             letter_no, prev_code_index, code_index,
     381         822 :                             code[code_index], 0,
     382             :                             soundex);
     383             :             }
     384             :         }
     385             :     }
     386             : 
     387         446 :     *ix_node = ix_node_next;
     388         446 : }
     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         906 : read_char(const unsigned char *str, int *ix)
     397             : {
     398             :     /* Substitute character for skipped code points. */
     399         906 :     const char  na = '\x1a';
     400             :     pg_wchar    c;
     401             : 
     402             :     /* Decode UTF-8 character to ISO 10646 code point. */
     403         906 :     str += *ix;
     404         906 :     c = utf8_to_unicode(str);
     405             : 
     406             :     /* Advance *ix, but (for safety) not if we've reached end of string. */
     407         906 :     if (c)
     408         788 :         *ix += pg_utf_mblen(str);
     409             : 
     410             :     /* Convert. */
     411         906 :     if (c >= (unsigned char) '[' && c <= (unsigned char) ']')
     412             :     {
     413             :         /* ASCII characters [, \, and ] are reserved for conversions below. */
     414           0 :         return na;
     415             :     }
     416         906 :     else if (c < 0x60)
     417             :     {
     418             :         /* Other non-lowercase ASCII characters can be used as-is. */
     419         308 :         return (char) c;
     420             :     }
     421         598 :     else if (c < 0x100)
     422             :     {
     423             :         /* ISO-8859-1 code point; convert to upper-case ASCII via table. */
     424         590 :         return iso8859_1_to_ascii_upper[c - 0x60];
     425             :     }
     426             :     else
     427             :     {
     428             :         /* Conversion of non-ASCII characters in the coding chart. */
     429           8 :         switch (c)
     430             :         {
     431           2 :             case 0x0104:        /* LATIN CAPITAL LETTER A WITH OGONEK */
     432             :             case 0x0105:        /* LATIN SMALL LETTER A WITH OGONEK */
     433           2 :                 return '[';
     434           2 :             case 0x0118:        /* LATIN CAPITAL LETTER E WITH OGONEK */
     435             :             case 0x0119:        /* LATIN SMALL LETTER E WITH OGONEK */
     436           2 :                 return '\\';
     437           4 :             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           4 :                 return ']';
     442           0 :             default:
     443           0 :                 return na;
     444             :         }
     445             :     }
     446             : }
     447             : 
     448             : 
     449             : /* Read next ASCII character, skipping any characters not in [A-\]]. */
     450             : static char
     451         898 : read_valid_char(const char *str, int *ix)
     452             : {
     453             :     char        c;
     454             : 
     455         906 :     while ((c = read_char((const unsigned char *) str, ix)) != '\0')
     456             :     {
     457         788 :         if (c >= 'A' && c <= ']')
     458         780 :             break;
     459             :     }
     460             : 
     461         898 :     return c;
     462             : }
     463             : 
     464             : 
     465             : /* Return sound coding for "letter" (letter sequence) */
     466             : static const dm_codes *
     467         516 : 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         516 :     if ((c = read_valid_char(str, ix)) == '\0')
     478          70 :         return NULL;
     479             : 
     480         446 :     letters = &letter_[c - 'A'];
     481         446 :     codes = letters->codes;
     482         446 :     i = *ix;
     483             : 
     484             :     /* Any subsequent letters in sequence. */
     485         530 :     while ((letters = letters->letters) && (c = read_valid_char(str, &i)))
     486             :     {
     487        1216 :         for (j = 0; (cmp = letters[j].letter); j++)
     488             :         {
     489         966 :             if (cmp == c)
     490             :             {
     491             :                 /* Letter found. */
     492          84 :                 letters = &letters[j];
     493          84 :                 if (letters->codes)
     494             :                 {
     495             :                     /* Coding for letter sequence found. */
     496          80 :                     codes = letters->codes;
     497          80 :                     *ix = i;
     498             :                 }
     499          84 :                 break;
     500             :             }
     501             :         }
     502         334 :         if (!cmp)
     503             :         {
     504             :             /* The sequence of letters has no coding. */
     505         250 :             break;
     506             :         }
     507             :     }
     508             : 
     509         446 :     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          70 : daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex)
     520             : {
     521          70 :     int         i = 0;
     522          70 :     int         letter_no = 0;
     523          70 :     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          70 :     if (!(codes = read_letter(word, &i)))
     531             :     {
     532             :         /* No encodable character in input. */
     533           0 :         return false;
     534             :     }
     535             : 
     536             :     /* Starting point. */
     537          70 :     first_node[ix_node] = palloc_object(dm_node);
     538          70 :     *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         516 :     while (codes && first_node[ix_node])
     545             :     {
     546         446 :         next_codes = read_letter(word, &i);
     547             : 
     548             :         /* Update leaf nodes. */
     549         446 :         update_leaves(first_node, &ix_node, letter_no,
     550             :                       codes, next_codes ? next_codes : end_codes,
     551             :                       soundex);
     552             : 
     553         446 :         codes = next_codes;
     554         446 :         letter_no++;
     555             :     }
     556             : 
     557             :     /* Append all remaining (incomplete) soundex codes to output array. */
     558         198 :     for (node = first_node[ix_node]; node; node = node->next[ix_node])
     559             :     {
     560         128 :         text       *out = cstring_to_text_with_len(node->soundex,
     561             :                                                    DM_CODE_DIGITS);
     562             : 
     563         128 :         accumArrayResult(soundex,
     564             :                          PointerGetDatum(out),
     565             :                          false,
     566             :                          TEXTOID,
     567             :                          CurrentMemoryContext);
     568             :     }
     569             : 
     570          70 :     return true;
     571             : }

Generated by: LCOV version 1.14