TLA Line data Source code
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 : /*
115 : "`abcdefghijklmnopqrstuvwxyz{|}~ ¡¢£¤¥¦§¨©ª«¬ ®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ"
116 : */
117 : "`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~ ! ?AAAAAAECEEEEIIIIDNOOOOO*OUUUUYDSAAAAAAECEEEEIIIIDNOOOOO/OUUUUYDY";
118 :
119 : /* Internal C implementation */
120 : static bool daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex);
121 :
122 :
123 GNC 3 : PG_FUNCTION_INFO_V1(daitch_mokotoff);
124 :
125 : Datum
126 35 : daitch_mokotoff(PG_FUNCTION_ARGS)
127 : {
128 35 : text *arg = PG_GETARG_TEXT_PP(0);
129 : Datum retval;
130 : char *string;
131 : ArrayBuildState *soundex;
132 : MemoryContext old_ctx,
133 : tmp_ctx;
134 :
135 : /* Work in a temporary context to simplify cleanup. */
136 35 : tmp_ctx = AllocSetContextCreate(CurrentMemoryContext,
137 : "daitch_mokotoff temporary context",
138 : ALLOCSET_DEFAULT_SIZES);
139 35 : old_ctx = MemoryContextSwitchTo(tmp_ctx);
140 :
141 : /* We must convert the string to UTF-8 if it isn't already. */
142 35 : string = pg_server_to_any(text_to_cstring(arg), VARSIZE_ANY_EXHDR(arg),
143 : PG_UTF8);
144 :
145 : /* The result is built in this ArrayBuildState. */
146 35 : soundex = initArrayResult(TEXTOID, tmp_ctx, false);
147 :
148 35 : if (!daitch_mokotoff_coding(string, soundex))
149 : {
150 : /* No encodable characters in input */
151 UNC 0 : MemoryContextSwitchTo(old_ctx);
152 0 : MemoryContextDelete(tmp_ctx);
153 0 : PG_RETURN_NULL();
154 : }
155 :
156 GNC 35 : retval = makeArrayResult(soundex, old_ctx);
157 :
158 35 : MemoryContextSwitchTo(old_ctx);
159 35 : MemoryContextDelete(tmp_ctx);
160 :
161 35 : PG_RETURN_DATUM(retval);
162 : }
163 :
164 :
165 : /* Initialize soundex code tree node for next code digit. */
166 : static void
167 664 : initialize_node(dm_node *node, int last_update)
168 : {
169 664 : if (node->last_update < last_update)
170 : {
171 463 : node->prev_code_digits[0] = node->next_code_digits[0];
172 463 : node->prev_code_digits[1] = node->next_code_digits[1];
173 463 : node->next_code_digits[0] = '\0';
174 463 : node->next_code_digits[1] = '\0';
175 463 : node->prev_code_index = node->next_code_index;
176 463 : node->next_code_index = 0;
177 463 : node->is_leaf = 0;
178 463 : node->last_update = last_update;
179 : }
180 664 : }
181 :
182 :
183 : /* Update soundex code tree node with next code digit. */
184 : static void
185 401 : add_next_code_digit(dm_node *node, int code_index, char code_digit)
186 : {
187 : /* OR in index 1 or 2. */
188 401 : node->next_code_index |= code_index;
189 :
190 401 : if (!node->next_code_digits[0])
191 360 : node->next_code_digits[0] = code_digit;
192 41 : else if (node->next_code_digits[0] != code_digit)
193 2 : node->next_code_digits[1] = code_digit;
194 401 : }
195 :
196 :
197 : /* Mark soundex code tree node as leaf. */
198 : static void
199 388 : set_leaf(dm_node *first_node[2], dm_node *last_node[2],
200 : dm_node *node, int ix_node)
201 : {
202 388 : if (!node->is_leaf)
203 : {
204 349 : node->is_leaf = 1;
205 :
206 349 : if (first_node[ix_node] == NULL)
207 218 : first_node[ix_node] = node;
208 : else
209 131 : last_node[ix_node]->next[ix_node] = node;
210 :
211 349 : last_node[ix_node] = node;
212 349 : node->next[ix_node] = NULL;
213 : }
214 388 : }
215 :
216 :
217 : /* Find next node corresponding to code digit, or create a new node. */
218 : static dm_node *
219 256 : find_or_create_child_node(dm_node *parent, char code_digit,
220 : ArrayBuildState *soundex)
221 : {
222 256 : int i = code_digit - '0';
223 256 : dm_node **nodes = parent->children;
224 256 : dm_node *node = nodes[i];
225 :
226 256 : if (node)
227 : {
228 : /* Found existing child node. Skip completed nodes. */
229 21 : return node->soundex_length < DM_CODE_DIGITS ? node : NULL;
230 : }
231 :
232 : /* Create new child node. */
233 235 : node = palloc_object(dm_node);
234 235 : nodes[i] = node;
235 :
236 235 : *node = start_node;
237 235 : memcpy(node->soundex, parent->soundex, sizeof(parent->soundex));
238 235 : node->soundex_length = parent->soundex_length;
239 235 : node->soundex[node->soundex_length++] = code_digit;
240 235 : node->code_digit = code_digit;
241 235 : node->next_code_index = node->prev_code_index;
242 :
243 235 : if (node->soundex_length < DM_CODE_DIGITS)
244 : {
245 219 : return node;
246 : }
247 : else
248 : {
249 : /* Append completed soundex code to output array. */
250 16 : text *out = cstring_to_text_with_len(node->soundex,
251 : DM_CODE_DIGITS);
252 :
253 16 : accumArrayResult(soundex,
254 : PointerGetDatum(out),
255 : false,
256 : TEXTOID,
257 : CurrentMemoryContext);
258 16 : return NULL;
259 : }
260 : }
261 :
262 :
263 : /* Update node for next code digit(s). */
264 : static void
265 424 : update_node(dm_node *first_node[2], dm_node *last_node[2],
266 : dm_node *node, int ix_node,
267 : int letter_no, int prev_code_index, int next_code_index,
268 : const char *next_code_digits, int digit_no,
269 : ArrayBuildState *soundex)
270 : {
271 : int i;
272 424 : char next_code_digit = next_code_digits[digit_no];
273 424 : int num_dirty_nodes = 0;
274 : dm_node *dirty_nodes[2];
275 :
276 424 : initialize_node(node, letter_no);
277 :
278 424 : if (node->prev_code_index && !(node->prev_code_index & prev_code_index))
279 : {
280 : /*
281 : * If the sound (vowel / consonant) of this letter encoding doesn't
282 : * correspond to the coding index of the previous letter, we skip this
283 : * letter encoding. Note that currently, only "J" can be either a
284 : * vowel or a consonant.
285 : */
286 8 : return;
287 : }
288 :
289 416 : if (next_code_digit == 'X' ||
290 259 : (digit_no == 0 &&
291 259 : (node->prev_code_digits[0] == next_code_digit ||
292 243 : node->prev_code_digits[1] == next_code_digit)))
293 : {
294 : /* The code digit is the same as one of the previous (i.e. not added). */
295 161 : dirty_nodes[num_dirty_nodes++] = node;
296 : }
297 :
298 416 : if (next_code_digit != 'X' &&
299 259 : (digit_no > 0 ||
300 259 : node->prev_code_digits[0] != next_code_digit ||
301 16 : node->prev_code_digits[1]))
302 : {
303 : /* The code digit is different from one of the previous (i.e. added). */
304 256 : node = find_or_create_child_node(node, next_code_digit, soundex);
305 256 : if (node)
306 : {
307 240 : initialize_node(node, letter_no);
308 240 : dirty_nodes[num_dirty_nodes++] = node;
309 : }
310 : }
311 :
312 817 : for (i = 0; i < num_dirty_nodes; i++)
313 : {
314 : /* Add code digit leading to the current node. */
315 401 : add_next_code_digit(dirty_nodes[i], next_code_index, next_code_digit);
316 :
317 401 : if (next_code_digits[++digit_no])
318 : {
319 13 : update_node(first_node, last_node, dirty_nodes[i], ix_node,
320 : letter_no, prev_code_index, next_code_index,
321 : next_code_digits, digit_no,
322 : soundex);
323 : }
324 : else
325 : {
326 : /* Add incomplete leaf node to linked list. */
327 388 : set_leaf(first_node, last_node, dirty_nodes[i], ix_node);
328 : }
329 : }
330 : }
331 :
332 :
333 : /* Update soundex tree leaf nodes. */
334 : static void
335 223 : update_leaves(dm_node *first_node[2], int *ix_node, int letter_no,
336 : const dm_codes *codes, const dm_codes *next_codes,
337 : ArrayBuildState *soundex)
338 : {
339 : int i,
340 : j,
341 : code_index;
342 : dm_node *node,
343 : *last_node[2];
344 : const dm_code *code,
345 : *next_code;
346 223 : int ix_node_next = (*ix_node + 1) & 1; /* Alternating index: 0, 1 */
347 :
348 : /* Initialize for new linked list of leaves. */
349 223 : first_node[ix_node_next] = NULL;
350 223 : last_node[ix_node_next] = NULL;
351 :
352 : /* Process all nodes. */
353 543 : for (node = first_node[*ix_node]; node; node = node->next[*ix_node])
354 : {
355 : /* One or two alternate code sequences. */
356 690 : for (i = 0; i < 2 && (code = codes[i]) && code[0][0]; i++)
357 : {
358 : /* Coding for previous letter - before vowel: 1, all other: 2 */
359 370 : int prev_code_index = (code[0][0] > '1') + 1;
360 :
361 : /* One or two alternate next code sequences. */
362 781 : for (j = 0; j < 2 && (next_code = next_codes[j]) && next_code[0][0]; j++)
363 : {
364 : /* Determine which code to use. */
365 411 : if (letter_no == 0)
366 : {
367 : /* This is the first letter. */
368 48 : code_index = 0;
369 : }
370 363 : else if (next_code[0][0] <= '1')
371 : {
372 : /* The next letter is a vowel. */
373 97 : code_index = 1;
374 : }
375 : else
376 : {
377 : /* All other cases. */
378 266 : code_index = 2;
379 : }
380 :
381 : /* One or two sequential code digits. */
382 411 : update_node(first_node, last_node, node, ix_node_next,
383 : letter_no, prev_code_index, code_index,
384 411 : code[code_index], 0,
385 : soundex);
386 : }
387 : }
388 : }
389 :
390 223 : *ix_node = ix_node_next;
391 223 : }
392 :
393 :
394 : /*
395 : * Return next character, converted from UTF-8 to uppercase ASCII.
396 : * *ix is the current string index and is incremented by the character length.
397 : */
398 : static char
399 453 : read_char(const unsigned char *str, int *ix)
400 : {
401 : /* Substitute character for skipped code points. */
402 453 : const char na = '\x1a';
403 : pg_wchar c;
404 :
405 : /* Decode UTF-8 character to ISO 10646 code point. */
406 453 : str += *ix;
407 453 : c = utf8_to_unicode(str);
408 :
409 : /* Advance *ix, but (for safety) not if we've reached end of string. */
410 453 : if (c)
411 394 : *ix += pg_utf_mblen(str);
412 :
413 : /* Convert. */
414 453 : if (c >= (unsigned char) '[' && c <= (unsigned char) ']')
415 : {
416 : /* ASCII characters [, \, and ] are reserved for Ą, Ę, and Ţ/Ț. */
417 UNC 0 : return na;
418 : }
419 GNC 453 : else if (c < 0x60)
420 : {
421 : /* Other non-lowercase ASCII characters can be used as-is. */
422 154 : return (char) c;
423 : }
424 299 : else if (c < 0x100)
425 : {
426 : /* ISO-8859-1 code point; convert to upper-case ASCII via table. */
427 295 : return iso8859_1_to_ascii_upper[c - 0x60];
428 : }
429 : else
430 : {
431 : /* Conversion of non-ASCII characters in the coding chart. */
432 4 : switch (c)
433 : {
434 1 : case 0x0104:
435 : case 0x0105:
436 : /* Ą/ą */
437 1 : return '[';
438 1 : case 0x0118:
439 : case 0x0119:
440 : /* Ę/ę */
441 1 : return '\\';
442 2 : case 0x0162:
443 : case 0x0163:
444 : case 0x021A:
445 : case 0x021B:
446 : /* Ţ/ţ or Ț/ț */
447 2 : return ']';
448 UNC 0 : default:
449 0 : return na;
450 : }
451 : }
452 : }
453 :
454 :
455 : /* Read next ASCII character, skipping any characters not in [A-\]]. */
456 : static char
457 GNC 449 : read_valid_char(const char *str, int *ix)
458 : {
459 : char c;
460 :
461 453 : while ((c = read_char((const unsigned char *) str, ix)) != '\0')
462 : {
463 394 : if (c >= 'A' && c <= ']')
464 390 : break;
465 : }
466 :
467 449 : return c;
468 : }
469 :
470 :
471 : /* Return sound coding for "letter" (letter sequence) */
472 : static const dm_codes *
473 258 : read_letter(const char *str, int *ix)
474 : {
475 : char c,
476 : cmp;
477 : int i,
478 : j;
479 : const dm_letter *letters;
480 : const dm_codes *codes;
481 :
482 : /* First letter in sequence. */
483 258 : if ((c = read_valid_char(str, ix)) == '\0')
484 35 : return NULL;
485 :
486 223 : letters = &letter_[c - 'A'];
487 223 : codes = letters->codes;
488 223 : i = *ix;
489 :
490 : /* Any subsequent letters in sequence. */
491 265 : while ((letters = letters->letters) && (c = read_valid_char(str, &i)))
492 : {
493 608 : for (j = 0; (cmp = letters[j].letter); j++)
494 : {
495 483 : if (cmp == c)
496 : {
497 : /* Letter found. */
498 42 : letters = &letters[j];
499 42 : if (letters->codes)
500 : {
501 : /* Coding for letter sequence found. */
502 40 : codes = letters->codes;
503 40 : *ix = i;
504 : }
505 42 : break;
506 : }
507 : }
508 167 : if (!cmp)
509 : {
510 : /* The sequence of letters has no coding. */
511 125 : break;
512 : }
513 : }
514 :
515 223 : return codes;
516 : }
517 :
518 :
519 : /*
520 : * Generate all Daitch-Mokotoff soundex codes for word,
521 : * adding them to the "soundex" ArrayBuildState.
522 : * Returns false if string has no encodable characters, else true.
523 : */
524 : static bool
525 35 : daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex)
526 : {
527 35 : int i = 0;
528 35 : int letter_no = 0;
529 35 : int ix_node = 0;
530 : const dm_codes *codes,
531 : *next_codes;
532 : dm_node *first_node[2],
533 : *node;
534 :
535 : /* First letter. */
536 35 : if (!(codes = read_letter(word, &i)))
537 : {
538 : /* No encodable character in input. */
539 UNC 0 : return false;
540 : }
541 :
542 : /* Starting point. */
543 GNC 35 : first_node[ix_node] = palloc_object(dm_node);
544 35 : *first_node[ix_node] = start_node;
545 :
546 : /*
547 : * Loop until either the word input is exhausted, or all generated soundex
548 : * codes are completed to six digits.
549 : */
550 258 : while (codes && first_node[ix_node])
551 : {
552 223 : next_codes = read_letter(word, &i);
553 :
554 : /* Update leaf nodes. */
555 223 : update_leaves(first_node, &ix_node, letter_no,
556 : codes, next_codes ? next_codes : end_codes,
557 : soundex);
558 :
559 223 : codes = next_codes;
560 223 : letter_no++;
561 : }
562 :
563 : /* Append all remaining (incomplete) soundex codes to output array. */
564 99 : for (node = first_node[ix_node]; node; node = node->next[ix_node])
565 : {
566 64 : text *out = cstring_to_text_with_len(node->soundex,
567 : DM_CODE_DIGITS);
568 :
569 64 : accumArrayResult(soundex,
570 : PointerGetDatum(out),
571 : false,
572 : TEXTOID,
573 : CurrentMemoryContext);
574 : }
575 :
576 35 : return true;
577 : }
|
