PostgreSQL Source Code  git master
daitch_mokotoff.c
Go to the documentation of this file.
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  */
78  /* One or two alternate code digits moving forward. */
80  /* ORed together code index(es) used to reach current node. */
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];
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 
121 
122 Datum
124 {
125  text *arg = PG_GETARG_TEXT_PP(0);
126  Datum retval;
127  char *string;
130  tmp_ctx;
131 
132  /* Work in a temporary context to simplify cleanup. */
134  "daitch_mokotoff temporary context",
136  old_ctx = MemoryContextSwitchTo(tmp_ctx);
137 
138  /* We must convert the string to UTF-8 if it isn't already. */
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 */
149  MemoryContextDelete(tmp_ctx);
150  PG_RETURN_NULL();
151  }
152 
153  retval = makeArrayResult(soundex, old_ctx);
154 
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
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 *
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. */
249 
251  PointerGetDatum(out),
252  false,
253  TEXTOID,
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,
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,
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
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  {
562 
564  PointerGetDatum(out),
565  false,
566  TEXTOID,
568  }
569 
570  return true;
571 }
ArrayBuildState * accumArrayResult(ArrayBuildState *astate, Datum dvalue, bool disnull, Oid element_type, MemoryContext rcontext)
Definition: arrayfuncs.c:5331
ArrayBuildState * initArrayResult(Oid element_type, MemoryContext rcontext, bool subcontext)
Definition: arrayfuncs.c:5274
Datum makeArrayResult(ArrayBuildState *astate, MemoryContext rcontext)
Definition: arrayfuncs.c:5401
static bool daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex)
PG_FUNCTION_INFO_V1(daitch_mokotoff)
static const char iso8859_1_to_ascii_upper[]
static void update_node(dm_node *first_node[2], dm_node *last_node[2], dm_node *node, int ix_node, int letter_no, int prev_code_index, int next_code_index, const char *next_code_digits, int digit_no, ArrayBuildState *soundex)
struct dm_node dm_node
static dm_node * find_or_create_child_node(dm_node *parent, char code_digit, ArrayBuildState *soundex)
static const dm_node start_node
Datum daitch_mokotoff(PG_FUNCTION_ARGS)
static const dm_codes end_codes[2]
static char read_char(const unsigned char *str, int *ix)
static void update_leaves(dm_node *first_node[2], int *ix_node, int letter_no, const dm_codes *codes, const dm_codes *next_codes, ArrayBuildState *soundex)
#define DM_CODE_DIGITS
static const dm_codes * read_letter(const char *str, int *ix)
static void add_next_code_digit(dm_node *node, int code_index, char code_digit)
static char read_valid_char(const char *str, int *ix)
static void set_leaf(dm_node *first_node[2], dm_node *last_node[2], dm_node *node, int ix_node)
static void initialize_node(dm_node *node, int last_update)
#define palloc_object(type)
Definition: fe_memutils.h:62
#define PG_GETARG_TEXT_PP(n)
Definition: fmgr.h:309
#define PG_RETURN_NULL()
Definition: fmgr.h:345
#define PG_RETURN_DATUM(x)
Definition: fmgr.h:353
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
Datum soundex(PG_FUNCTION_ARGS)
int j
Definition: isn.c:74
int i
Definition: isn.c:73
static pg_wchar utf8_to_unicode(const unsigned char *c)
Definition: mbprint.c:53
unsigned int pg_wchar
Definition: mbprint.c:31
char * pg_server_to_any(const char *s, int len, int encoding)
Definition: mbutils.c:749
MemoryContext CurrentMemoryContext
Definition: mcxt.c:131
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:442
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:153
void * arg
#define pg_utf_mblen
Definition: pg_wchar.h:633
@ PG_UTF8
Definition: pg_wchar.h:232
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
uintptr_t Datum
Definition: postgres.h:64
char * c
char string[11]
Definition: preproc-type.c:52
RT_SCOPE RT_RADIX_TREE *MemoryContext old_ctx
Definition: radixtree.h:1786
MemoryContextSwitchTo(old_ctx)
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:743
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1474
char prev_code_digits[2]
int soundex_length
int last_update
struct dm_node * children[10]
struct dm_node * next[2]
int prev_code_index
char next_code_digits[2]
char soundex[DM_CODE_DIGITS]
int next_code_index
char code_digit
Definition: c.h:674
#define VARSIZE_ANY_EXHDR(PTR)
Definition: varatt.h:317
char * text_to_cstring(const text *t)
Definition: varlena.c:217
text * cstring_to_text_with_len(const char *s, int len)
Definition: varlena.c:196