Re: daitch_mokotoff module - Mailing list pgsql-hackers
| From | Dag Lem |
|---|---|
| Subject | Re: daitch_mokotoff module |
| Date | |
| Msg-id | ygelf0mizon.fsf@sid.nimrod.no Whole thread Raw |
| In response to | Re: daitch_mokotoff module (Tomas Vondra <tomas.vondra@enterprisedb.com>) |
| List | pgsql-hackers |
Tomas Vondra <tomas.vondra@enterprisedb.com> writes:
[...]
>
> Thanks, looks interesting. A couple generic comments, based on a quick
> code review.
Thank you for the constructive review!
>
> 1) Can the extension be marked as trusted, just like fuzzystrmatch?
I have now moved the daitch_mokotoff function into the fuzzystrmatch
module, as suggested by Andrew Dunstan.
>
> 2) The docs really need an explanation of what the extension is for,
> not just a link to fuzzystrmatch. Also, a couple examples would be
> helpful, I guess - similarly to fuzzystrmatch. The last line in the
> docs is annoyingly long.
Please see the updated documentation for the fuzzystrmatch module.
>
> 3) What's daitch_mokotov_header.pl for? I mean, it generates the
> header, but when do we need to run it?
It only has to be run if the soundex rules are changed. I have now
made the dependencies explicit in the fuzzystrmatch Makefile.
>
> 4) It seems to require perl-open, which is a module we did not need
> until now. Not sure how well supported it is, but maybe we can use a
> more standard module?
I believe Perl I/O layers have been part of Perl core for two decades
now :-)
>
> 5) Do we need to keep DM_MAIN? It seems to be meant for some kind of
> testing, but our regression tests certainly don't need it (or the
> palloc mockup). I suggest to get rid of it.
Done. BTW this was modeled after dmetaphone.c
>
> 6) I really don't understand some of the comments in
> daitch_mokotov.sql, like for example:
>
> -- testEncodeBasic
> -- Tests covered above are omitted.
>
> Also, comments with names of Java methods seem pretty confusing. It'd
> be better to actually explain what rules are the tests checking.
The tests were copied from various web sites and implementations. I have
cut down on the number of tests and made the comments more to the point.
>
> 7) There are almost no comments in the .c file (ignoring the comment
> on top). Short functions like initialize_node are probably fine
> without one, but e.g. update_node would deserve one.
More comments are added to both the .h and the .c file.
>
> 8) Some of the lines are pretty long (e.g. the update_node signature
> is almost 170 chars). That should be wrapped. Maybe try running
> pgindent on the code, that'll show which parts need better formatting
> (so as not to get broken later).
Fixed. I did run pgindent earlier, however it didn't catch those long
lines.
>
> 9) I'm sure there's better way to get the number of valid chars than this:
>
> for (i = 0, ilen = 0; (c = read_char(&str[i], &ilen)) && (c < 'A' ||
> c > ']'); i += ilen)
> {
> }
>
> Say, a while loop or something?
The code gets to the next encodable character, skipping any other
characters. I have now added a comment which should hopefully make this
clearer, and broken up the for loop for readability.
Please find attached the revised patch.
Best regards
Dag Lem
diff --git a/contrib/fuzzystrmatch/Makefile b/contrib/fuzzystrmatch/Makefile
index 0704894f88..826e529e3e 100644
--- a/contrib/fuzzystrmatch/Makefile
+++ b/contrib/fuzzystrmatch/Makefile
@@ -3,11 +3,12 @@
MODULE_big = fuzzystrmatch
OBJS = \
$(WIN32RES) \
+ daitch_mokotoff.o \
dmetaphone.o \
fuzzystrmatch.o
EXTENSION = fuzzystrmatch
-DATA = fuzzystrmatch--1.1.sql fuzzystrmatch--1.0--1.1.sql
+DATA = fuzzystrmatch--1.2.sql fuzzystrmatch--1.1--1.2.sql fuzzystrmatch--1.0--1.1.sql
PGFILEDESC = "fuzzystrmatch - similarities and distance between strings"
REGRESS = fuzzystrmatch
@@ -22,3 +23,8 @@ top_builddir = ../..
include $(top_builddir)/src/Makefile.global
include $(top_srcdir)/contrib/contrib-global.mk
endif
+
+daitch_mokotoff.o: daitch_mokotoff.h
+
+daitch_mokotoff.h: daitch_mokotoff_header.pl
+ perl $< > $@
diff --git a/contrib/fuzzystrmatch/daitch_mokotoff.c b/contrib/fuzzystrmatch/daitch_mokotoff.c
new file mode 100644
index 0000000000..302e9a6d86
--- /dev/null
+++ b/contrib/fuzzystrmatch/daitch_mokotoff.c
@@ -0,0 +1,516 @@
+/*
+ * Daitch-Mokotoff Soundex
+ *
+ * Copyright (c) 2021 Finance Norway
+ * Author: Dag Lem <dag@nimrod.no>
+ *
+ * This implementation of the Daitch-Mokotoff Soundex System aims at high
+ * performance.
+ *
+ * - The processing of each phoneme is initiated by an O(1) table lookup.
+ * - For phonemes containing more than one character, a coding tree is traversed
+ * to process the complete phoneme.
+ * - The (alternate) soundex codes are produced digit by digit in-place in
+ * another tree structure.
+ *
+ * References:
+ *
+ * https://www.avotaynu.com/soundex.htm
+ * https://www.jewishgen.org/InfoFiles/Soundex.html
+ * https://familypedia.fandom.com/wiki/Daitch-Mokotoff_Soundex
+ * https://stevemorse.org/census/soundex.html (dmlat.php, dmsoundex.php)
+ * https://github.com/apache/commons-codec/ (dmrules.txt, DaitchMokotoffSoundex.java)
+ * https://metacpan.org/pod/Text::Phonetic (DaitchMokotoff.pm)
+ *
+ * A few notes on other implementations:
+ *
+ * - "J" is considered a vowel in dmlat.php
+ * - The official rules for "RS" are commented out in dmlat.php
+ * - Identical code digits for adjacent letters are not collapsed correctly in
+ * dmsoundex.php when double digit codes are involved. E.g. "BESST" yields
+ * 744300 instead of 743000 as for "BEST".
+ * - "Y" is not considered a vowel in DaitchMokotoffSoundex.java
+ * - Both dmlat.php and dmrules.txt have the same unofficial rules for "UE".
+ * - Coding of MN/NM + M/N differs between dmsoundex.php and DaitchMokotoffSoundex.java
+ * - No other known implementation yields the correct set of codes for e.g.
+ * "CJC" (550000 540000 545000 450000 400000 440000).
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose, without fee, and without a written agreement
+ * is hereby granted, provided that the above copyright notice and this
+ * paragraph and the following two paragraphs appear in all copies.
+ *
+ * IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
+ * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
+ * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS TO
+ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+*/
+
+#include "daitch_mokotoff.h"
+
+#include "postgres.h"
+#include "utils/builtins.h"
+#include "mb/pg_wchar.h"
+
+#include <ctype.h>
+#include <string.h>
+
+
+/* Internal C implementation */
+static char *_daitch_mokotoff(char *word, char *soundex, size_t n);
+
+
+PG_FUNCTION_INFO_V1(daitch_mokotoff);
+Datum
+daitch_mokotoff(PG_FUNCTION_ARGS)
+{
+ text *arg = PG_GETARG_TEXT_PP(0);
+ char *string,
+ *tmp_soundex;
+ text *soundex;
+
+ /*
+ * The maximum theoretical soundex size is several KB, however in practice
+ * anything but contrived synthetic inputs will yield a soundex size of
+ * less than 100 bytes. We thus allocate and free a temporary work buffer,
+ * and return only the actual soundex result.
+ */
+ string = pg_server_to_any(text_to_cstring(arg), VARSIZE_ANY_EXHDR(arg), PG_UTF8);
+ tmp_soundex = palloc(DM_MAX_SOUNDEX_CHARS);
+
+ _daitch_mokotoff(string, tmp_soundex, DM_MAX_SOUNDEX_CHARS);
+
+ soundex = cstring_to_text(pg_any_to_server(tmp_soundex, strlen(tmp_soundex), PG_UTF8));
+ pfree(tmp_soundex);
+
+ PG_RETURN_TEXT_P(soundex);
+}
+
+
+typedef dm_node dm_nodes[DM_MAX_NODES];
+typedef dm_node * dm_leaves[DM_MAX_LEAVES];
+
+
+/* Template for new node in soundex code tree */
+static const dm_node start_node = {
+ .soundex_length = 0,
+ .soundex = "000000 ", /* Six digits + joining space */
+ .is_leaf = 0,
+ .last_update = 0,
+ .code_digit = '\0',
+ .prev_code_digits = {'\0', '\0'},
+ .next_code_digits = {'\0', '\0'},
+ .next_nodes = {NULL}
+};
+
+
+/* Initialize soundex code tree node for next code digit */
+static void
+initialize_node(dm_node * node, int last_update)
+{
+ if (node->last_update < last_update)
+ {
+ node->prev_code_digits[0] = node->next_code_digits[0];
+ node->prev_code_digits[1] = node->next_code_digits[1];
+ node->next_code_digits[0] = '\0';
+ node->next_code_digits[1] = '\0';
+ node->is_leaf = 0;
+ node->last_update = last_update;
+ }
+}
+
+
+/* Update soundex code tree node with next code digit */
+static void
+add_next_code_digit(dm_node * node, char code_digit)
+{
+ if (!node->next_code_digits[0])
+ {
+ node->next_code_digits[0] = code_digit;
+ }
+ else if (node->next_code_digits[0] != code_digit)
+ {
+ node->next_code_digits[1] = code_digit;
+ }
+}
+
+
+/* Mark soundex code tree node as leaf (soundex code completed) */
+static void
+set_leaf(dm_leaves leaves_next, int *num_leaves_next, dm_node * node)
+{
+ if (!node->is_leaf)
+ {
+ node->is_leaf = 1;
+ leaves_next[(*num_leaves_next)++] = node;
+ }
+}
+
+
+/* Find next node corresponding to code digit, or create a new node */
+static dm_node * find_or_create_node(dm_nodes nodes, int *num_nodes,
+ dm_node * node, char code_digit)
+{
+ dm_node **next_nodes;
+ dm_node *next_node;
+
+ for (next_nodes = node->next_nodes; (next_node = *next_nodes); next_nodes++)
+ {
+ if (next_node->code_digit == code_digit)
+ {
+ return next_node;
+ }
+ }
+
+ next_node = &nodes[(*num_nodes)++];
+ *next_nodes = next_node;
+
+ *next_node = start_node;
+ memcpy(next_node->soundex, node->soundex, sizeof(next_node->soundex));
+ next_node->soundex_length = node->soundex_length;
+ next_node->soundex[next_node->soundex_length++] = code_digit;
+ next_node->code_digit = code_digit;
+
+ return next_node;
+}
+
+
+/* Update node for next code digit(s) */
+static int
+update_node(dm_nodes nodes, dm_node * node, int *num_nodes,
+ dm_leaves leaves_next, int *num_leaves_next,
+ int char_number, char next_code_digit, char next_code_digit_2)
+{
+ int i;
+ int num_dirty_nodes = 0;
+ dm_node *dirty_nodes[2];
+
+ initialize_node(node, char_number);
+
+ if (node->soundex_length == DM_MAX_CODE_DIGITS)
+ {
+ /* Keep completed soundex code. */
+ set_leaf(leaves_next, num_leaves_next, node);
+ return 0;
+ }
+
+ if (next_code_digit == 'X' ||
+ node->prev_code_digits[0] == next_code_digit ||
+ node->prev_code_digits[1] == next_code_digit)
+ {
+ /* The code digit is the same as one of the previous (i.e. not added). */
+ dirty_nodes[num_dirty_nodes++] = node;
+ }
+
+ if (next_code_digit != 'X' &&
+ (node->prev_code_digits[0] != next_code_digit ||
+ node->prev_code_digits[1]))
+ {
+ /* The code digit is different from one of the previous (i.e. added). */
+ node = find_or_create_node(nodes, num_nodes, node, next_code_digit);
+ initialize_node(node, char_number);
+ dirty_nodes[num_dirty_nodes++] = node;
+ }
+
+ for (i = 0; i < num_dirty_nodes; i++)
+ {
+ /* Add code digit leading to the current node. */
+ add_next_code_digit(dirty_nodes[i], next_code_digit);
+
+ if (next_code_digit_2)
+ {
+ update_node(nodes, dirty_nodes[i], num_nodes,
+ leaves_next, num_leaves_next,
+ char_number, next_code_digit_2, '\0');
+ }
+ else
+ {
+ set_leaf(leaves_next, num_leaves_next, dirty_nodes[i]);
+ }
+ }
+
+ return 1;
+}
+
+
+/* Mark completed soundex node leaves. Return 1 when all nodes are completed */
+static int
+update_leaves(dm_nodes nodes, int *num_nodes,
+ dm_leaves leaves[2], int *ix_leaves, int *num_leaves,
+ int char_number, dm_codes codes)
+{
+ int i,
+ j;
+ char *code;
+ int num_leaves_next = 0;
+ int ix_leaves_next = (*ix_leaves + 1) % 2;
+ int finished = 1;
+
+ for (i = 0; i < *num_leaves; i++)
+ {
+ dm_node *node = leaves[*ix_leaves][i];
+
+ /* One or two alternate code sequences. */
+ for (j = 0; j < 2 && (code = codes[j]) && code[0]; j++)
+ {
+ /* One or two sequential code digits. */
+ if (update_node(nodes, node, num_nodes,
+ leaves[ix_leaves_next], &num_leaves_next,
+ char_number, code[0], code[1]))
+ {
+ finished = 0;
+ }
+ }
+ }
+
+ *ix_leaves = ix_leaves_next;
+ *num_leaves = num_leaves_next;
+
+ return finished;
+}
+
+
+/* Mapping from ISO8859-1 to ASCII */
+static const char tr_accents_iso8859_1[] =
+/*
+"ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ"
+*/
+"AAAAAAECEEEEIIIIDNOOOOO*OUUUUYDsaaaaaaeceeeeiiiidnooooo/ouuuuydy";
+
+static char
+unaccent_iso8859_1(unsigned char c)
+{
+ return c >= 192 ? tr_accents_iso8859_1[c - 192] : c;
+}
+
+
+/* Convert an UTF-8 character to ISO-8859-1.
+ * Unconvertable characters are returned as '?'.
+ * NB! Beware of the domain specific conversion of Ą, Ę, and Ţ/Ț.
+ */
+static char
+utf8_to_iso8859_1(char *str, int *len)
+{
+ const char unknown = '?';
+ unsigned char c;
+ unsigned int code_point;
+
+ *len = 1;
+ c = (unsigned char) str[0];
+ if (c < 0x80)
+ {
+ /* ASCII code point. */
+ return c;
+ }
+ else if (c < 0xE0)
+ {
+ /* Two-byte character. */
+ if (!str[1])
+ {
+ /* The UTF-8 character is cut short (invalid code point). */
+ return unknown;
+ }
+ *len = 2;
+ code_point = ((c & 0x1F) << 6) | (str[1] & 0x3F);
+ if (code_point < 0x100)
+ {
+ /* ISO-8859-1 code point. */
+ return code_point;
+ }
+ else if (code_point == 0x0104 || code_point == 0x0105)
+ {
+ /* Ą/ą */
+ return '[';
+ }
+ else if (code_point == 0x0118 || code_point == 0x0119)
+ {
+ /* Ę/ę */
+ return '\\';
+ }
+ else if (code_point == 0x0162 || code_point == 0x0163 ||
+ code_point == 0x021A || code_point == 0x021B)
+ {
+ /* Ţ/ţ or Ț/ț */
+ return ']';
+ }
+ else
+ {
+ return unknown;
+ }
+ }
+ else if (c < 0xF0)
+ {
+ /* Three-byte character. */
+ if (!str[2])
+ {
+ /* The UTF-8 character is cut short (invalid code point). */
+ *len = 2;
+ }
+ else
+ {
+ *len = 3;
+ }
+ return unknown;
+ }
+ else
+ {
+ /* Four-byte character. */
+ if (!str[3])
+ {
+ /* The UTF-8 character is cut short (invalid code point). */
+ *len = 3;
+ }
+ else
+ {
+ *len = 4;
+ }
+ return unknown;
+ }
+}
+
+
+/* Return next character, converted from UTF-8 to uppercase ASCII */
+static char
+read_char(char *str, int *len)
+{
+ return toupper(unaccent_iso8859_1(utf8_to_iso8859_1(str, len)));
+}
+
+
+/* Return next character in the character set [A..\]], skipping any other characters */
+static char
+read_valid_char(char *str, int *len)
+{
+ int c;
+ int i,
+ ilen;
+
+ for (i = 0, ilen = 0;
+ (c = read_char(&str[i], &ilen)) && (c < 'A' || c > ']');
+ i += ilen)
+ {
+ }
+
+ *len = i + ilen;
+ return c;
+}
+
+
+/* Generate all Daitch-Mokotoff soundex codes for word, separated by space */
+static char *
+_daitch_mokotoff(char *word, char *soundex, size_t n)
+{
+ int c,
+ cmp;
+ int i,
+ ilen,
+ i_ok,
+ j,
+ jlen,
+ k;
+ int first_letter = 1;
+ int ix_leaves = 0;
+ int num_nodes = 0,
+ num_leaves = 0;
+ dm_letter *letter,
+ *letters;
+ dm_codes *codes_ok,
+ codes;
+
+ dm_node *nodes = palloc(sizeof(dm_nodes));
+ dm_leaves *leaves = palloc(2 * sizeof(dm_leaves));
+
+ /* Starting point. */
+ nodes[num_nodes++] = start_node;
+ leaves[ix_leaves][num_leaves++] = &nodes[0];
+
+ for (i = 0; (c = read_valid_char(&word[i], &ilen)); i += ilen)
+ {
+ /* First letter in sequence. */
+ letter = &letter_[c - 'A'];
+ codes_ok = letter->codes;
+ i_ok = i;
+
+ /* Subsequent letters. */
+ for (j = i + ilen;
+ (letters = letter->letters) && (c = read_valid_char(&word[j], &jlen));
+ j += jlen)
+ {
+ for (k = 0; (cmp = letters[k].letter); k++)
+ {
+ if (cmp == c)
+ {
+ /* Coding for letter found. */
+ break;
+ }
+ }
+ if (!cmp)
+ {
+ /* The sequence of letters has no coding. */
+ break;
+ }
+
+ letter = &letters[k];
+ if (letter->codes)
+ {
+ codes_ok = letter->codes;
+ i_ok = j;
+ ilen = jlen;
+ }
+ }
+
+ /* Determine which code to use. */
+ if (first_letter)
+ {
+ /* This is the first letter. */
+ j = 0;
+ first_letter = 0;
+ }
+ else if ((c = read_valid_char(&word[i_ok + ilen], &jlen)) && strchr(DM_VOWELS, c))
+ {
+ /* The next letter is a vowel. */
+ j = 1;
+ }
+ else
+ {
+ /* All other cases. */
+ j = 2;
+ }
+ memcpy(codes, codes_ok[j], sizeof(codes));
+
+ /* Update leaves. */
+ if (update_leaves(nodes, &num_nodes,
+ leaves, &ix_leaves, &num_leaves,
+ i, codes))
+ {
+ /* All soundex codes are completed to six digits. */
+ break;
+ }
+
+ /* Prepare for next letter sequence. */
+ i = i_ok;
+ }
+
+ /* Concatenate all generated soundex codes. */
+ for (i = 0, j = 0;
+ i < num_leaves && j + DM_MAX_CODE_DIGITS + 1 <= n;
+ i++, j += DM_MAX_CODE_DIGITS + 1)
+ {
+ memcpy(&soundex[j], leaves[ix_leaves][i]->soundex, DM_MAX_CODE_DIGITS + 1);
+ }
+
+ /* Terminate string. */
+ soundex[j - (j != 0)] = '\0';
+
+ pfree(leaves);
+ pfree(nodes);
+
+ return soundex;
+}
diff --git a/contrib/fuzzystrmatch/daitch_mokotoff.h b/contrib/fuzzystrmatch/daitch_mokotoff.h
new file mode 100644
index 0000000000..071760495c
--- /dev/null
+++ b/contrib/fuzzystrmatch/daitch_mokotoff.h
@@ -0,0 +1,1115 @@
+/*
+ * Types and lookup tables for Daitch-Mokotoff Soundex
+ *
+ * Copyright (c) 2021 Finance Norway
+ * Author: Dag Lem <dag@nimrod.no>
+ *
+ * This file is generated by daitch_mokotoff_header.pl
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose, without fee, and without a written agreement
+ * is hereby granted, provided that the above copyright notice and this
+ * paragraph and the following two paragraphs appear in all copies.
+ *
+ * IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
+ * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
+ * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS TO
+ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+ */
+
+#include <stdlib.h>
+
+#define DM_MAX_CODE_DIGITS 6
+#define DM_MAX_ALTERNATE_CODES 5
+#define DM_MAX_NODES 1564
+#define DM_MAX_LEAVES 1250
+#define DM_MAX_SOUNDEX_CHARS (DM_MAX_NODES*(DM_MAX_CODE_DIGITS + 1))
+#define DM_VOWELS "AEIOUY"
+
+typedef char dm_code[2 + 1]; /* One or two sequential code digits + NUL */
+typedef dm_code dm_codes[2]; /* One or two alternate code sequences */
+
+/* Letter in input sequence */
+struct dm_letter
+{
+ char letter; /* Present letter in sequence */
+ struct dm_letter *letters; /* List of possible successive letters */
+ dm_codes *codes; /* Code sequence(s) for complete sequence */
+};
+
+/* Node in soundex code tree */
+struct dm_node
+{
+ int soundex_length; /* Length of generated soundex code */
+ char soundex[DM_MAX_CODE_DIGITS + 1]; /* Soundex code */
+ int is_leaf; /* Completed soundex codes are leaves */
+ int last_update; /* Character index for last update of node */
+ char code_digit; /* Current code digit */
+
+ /*
+ * One or two alternate code digits leading to this node - repeated code
+ * digits and 'X' lead back to the same node.
+ */
+ char prev_code_digits[2];
+ char next_code_digits[2];
+ /* Branching nodes */
+ struct dm_node *next_nodes[DM_MAX_ALTERNATE_CODES + 1];
+};
+
+typedef struct dm_letter dm_letter;
+typedef struct dm_node dm_node;
+
+/* Codes for letter sequence at start of name, before a vowel, and any other. */
+static dm_codes codes_0_1_X[] =
+{
+ {
+ "0"
+ },
+ {
+ "1"
+ },
+ {
+ "X"
+ }
+};
+static dm_codes codes_0_7_X[] =
+{
+ {
+ "0"
+ },
+ {
+ "7"
+ },
+ {
+ "X"
+ }
+};
+static dm_codes codes_0_X_X[] =
+{
+ {
+ "0"
+ },
+ {
+ "X"
+ },
+ {
+ "X"
+ }
+};
+static dm_codes codes_1_1_X[] =
+{
+ {
+ "1"
+ },
+ {
+ "1"
+ },
+ {
+ "X"
+ }
+};
+static dm_codes codes_1_X_X[] =
+{
+ {
+ "1"
+ },
+ {
+ "X"
+ },
+ {
+ "X"
+ }
+};
+static dm_codes codes_1or4_Xor4_Xor4[] =
+{
+ {
+ "1", "4"
+ },
+ {
+ "X", "4"
+ },
+ {
+ "X", "4"
+ }
+};
+static dm_codes codes_2_43_43[] =
+{
+ {
+ "2"
+ },
+ {
+ "43"
+ },
+ {
+ "43"
+ }
+};
+static dm_codes codes_2_4_4[] =
+{
+ {
+ "2"
+ },
+ {
+ "4"
+ },
+ {
+ "4"
+ }
+};
+static dm_codes codes_3_3_3[] =
+{
+ {
+ "3"
+ },
+ {
+ "3"
+ },
+ {
+ "3"
+ }
+};
+static dm_codes codes_3or4_3or4_3or4[] =
+{
+ {
+ "3", "4"
+ },
+ {
+ "3", "4"
+ },
+ {
+ "3", "4"
+ }
+};
+static dm_codes codes_4_4_4[] =
+{
+ {
+ "4"
+ },
+ {
+ "4"
+ },
+ {
+ "4"
+ }
+};
+static dm_codes codes_5_54_54[] =
+{
+ {
+ "5"
+ },
+ {
+ "54"
+ },
+ {
+ "54"
+ }
+};
+static dm_codes codes_5_5_5[] =
+{
+ {
+ "5"
+ },
+ {
+ "5"
+ },
+ {
+ "5"
+ }
+};
+static dm_codes codes_5_5_X[] =
+{
+ {
+ "5"
+ },
+ {
+ "5"
+ },
+ {
+ "X"
+ }
+};
+static dm_codes codes_5or45_5or45_5or45[] =
+{
+ {
+ "5", "45"
+ },
+ {
+ "5", "45"
+ },
+ {
+ "5", "45"
+ }
+};
+static dm_codes codes_5or4_5or4_5or4[] =
+{
+ {
+ "5", "4"
+ },
+ {
+ "5", "4"
+ },
+ {
+ "5", "4"
+ }
+};
+static dm_codes codes_66_66_66[] =
+{
+ {
+ "66"
+ },
+ {
+ "66"
+ },
+ {
+ "66"
+ }
+};
+static dm_codes codes_6_6_6[] =
+{
+ {
+ "6"
+ },
+ {
+ "6"
+ },
+ {
+ "6"
+ }
+};
+static dm_codes codes_7_7_7[] =
+{
+ {
+ "7"
+ },
+ {
+ "7"
+ },
+ {
+ "7"
+ }
+};
+static dm_codes codes_8_8_8[] =
+{
+ {
+ "8"
+ },
+ {
+ "8"
+ },
+ {
+ "8"
+ }
+};
+static dm_codes codes_94or4_94or4_94or4[] =
+{
+ {
+ "94", "4"
+ },
+ {
+ "94", "4"
+ },
+ {
+ "94", "4"
+ }
+};
+static dm_codes codes_9_9_9[] =
+{
+ {
+ "9"
+ },
+ {
+ "9"
+ },
+ {
+ "9"
+ }
+};
+static dm_codes codes_X_X_6orX[] =
+{
+ {
+ "X"
+ },
+ {
+ "X"
+ },
+ {
+ "6", "X"
+ }
+};
+
+/* Coding for alternative following letters in sequence. */
+static dm_letter letter_A[] =
+{
+ {
+ 'I', NULL, codes_0_1_X
+ },
+ {
+ 'J', NULL, codes_0_1_X
+ },
+ {
+ 'U', NULL, codes_0_7_X
+ },
+ {
+ 'Y', NULL, codes_0_1_X
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_CH[] =
+{
+ {
+ 'S', NULL, codes_5_54_54
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_CS[] =
+{
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_CZ[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_C[] =
+{
+ {
+ 'H', letter_CH, codes_5or4_5or4_5or4
+ },
+ {
+ 'K', NULL, codes_5or45_5or45_5or45
+ },
+ {
+ 'S', letter_CS, codes_4_4_4
+ },
+ {
+ 'Z', letter_CZ, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_DR[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_DS[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_DZ[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_D[] =
+{
+ {
+ 'R', letter_DR, NULL
+ },
+ {
+ 'S', letter_DS, codes_4_4_4
+ },
+ {
+ 'T', NULL, codes_3_3_3
+ },
+ {
+ 'Z', letter_DZ, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_E[] =
+{
+ {
+ 'I', NULL, codes_0_1_X
+ },
+ {
+ 'J', NULL, codes_0_1_X
+ },
+ {
+ 'U', NULL, codes_1_1_X
+ },
+ {
+ 'Y', NULL, codes_0_1_X
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_F[] =
+{
+ {
+ 'B', NULL, codes_7_7_7
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_I[] =
+{
+ {
+ 'A', NULL, codes_1_X_X
+ },
+ {
+ 'E', NULL, codes_1_X_X
+ },
+ {
+ 'O', NULL, codes_1_X_X
+ },
+ {
+ 'U', NULL, codes_1_X_X
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_K[] =
+{
+ {
+ 'H', NULL, codes_5_5_5
+ },
+ {
+ 'S', NULL, codes_5_54_54
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_M[] =
+{
+ {
+ 'N', NULL, codes_66_66_66
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_N[] =
+{
+ {
+ 'M', NULL, codes_66_66_66
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_O[] =
+{
+ {
+ 'I', NULL, codes_0_1_X
+ },
+ {
+ 'J', NULL, codes_0_1_X
+ },
+ {
+ 'Y', NULL, codes_0_1_X
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_P[] =
+{
+ {
+ 'F', NULL, codes_7_7_7
+ },
+ {
+ 'H', NULL, codes_7_7_7
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_R[] =
+{
+ {
+ 'S', NULL, codes_94or4_94or4_94or4
+ },
+ {
+ 'Z', NULL, codes_94or4_94or4_94or4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SCHTC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SCHTSC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SCHTS[] =
+{
+ {
+ 'C', letter_SCHTSC, NULL
+ },
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SCHT[] =
+{
+ {
+ 'C', letter_SCHTC, NULL
+ },
+ {
+ 'S', letter_SCHTS, NULL
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SCH[] =
+{
+ {
+ 'D', NULL, codes_2_43_43
+ },
+ {
+ 'T', letter_SCHT, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SC[] =
+{
+ {
+ 'H', letter_SCH, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SHC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SHTC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SHTS[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SHT[] =
+{
+ {
+ 'C', letter_SHTC, NULL
+ },
+ {
+ 'S', letter_SHTS, NULL
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SH[] =
+{
+ {
+ 'C', letter_SHC, NULL
+ },
+ {
+ 'D', NULL, codes_2_43_43
+ },
+ {
+ 'T', letter_SHT, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_STC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_STR[] =
+{
+ {
+ 'S', NULL, codes_2_4_4
+ },
+ {
+ 'Z', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_STSC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_STS[] =
+{
+ {
+ 'C', letter_STSC, NULL
+ },
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ST[] =
+{
+ {
+ 'C', letter_STC, NULL
+ },
+ {
+ 'R', letter_STR, NULL
+ },
+ {
+ 'S', letter_STS, NULL
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SZC[] =
+{
+ {
+ 'S', NULL, codes_2_4_4
+ },
+ {
+ 'Z', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_SZ[] =
+{
+ {
+ 'C', letter_SZC, NULL
+ },
+ {
+ 'D', NULL, codes_2_43_43
+ },
+ {
+ 'T', NULL, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_S[] =
+{
+ {
+ 'C', letter_SC, codes_2_4_4
+ },
+ {
+ 'D', NULL, codes_2_43_43
+ },
+ {
+ 'H', letter_SH, codes_4_4_4
+ },
+ {
+ 'T', letter_ST, codes_2_43_43
+ },
+ {
+ 'Z', letter_SZ, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TR[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TSC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TS[] =
+{
+ {
+ 'C', letter_TSC, NULL
+ },
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TTC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TTSC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TTS[] =
+{
+ {
+ 'C', letter_TTSC, NULL
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TT[] =
+{
+ {
+ 'C', letter_TTC, NULL
+ },
+ {
+ 'S', letter_TTS, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_TZ[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_T[] =
+{
+ {
+ 'C', letter_TC, codes_4_4_4
+ },
+ {
+ 'H', NULL, codes_3_3_3
+ },
+ {
+ 'R', letter_TR, NULL
+ },
+ {
+ 'S', letter_TS, codes_4_4_4
+ },
+ {
+ 'T', letter_TT, NULL
+ },
+ {
+ 'Z', letter_TZ, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_U[] =
+{
+ {
+ 'E', NULL, codes_0_X_X
+ },
+ {
+ 'I', NULL, codes_0_1_X
+ },
+ {
+ 'J', NULL, codes_0_1_X
+ },
+ {
+ 'Y', NULL, codes_0_1_X
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ZDZ[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ZD[] =
+{
+ {
+ 'Z', letter_ZDZ, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ZHDZ[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ZHD[] =
+{
+ {
+ 'Z', letter_ZHDZ, NULL
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ZH[] =
+{
+ {
+ 'D', letter_ZHD, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ZSC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_ZS[] =
+{
+ {
+ 'C', letter_ZSC, NULL
+ },
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_Z[] =
+{
+ {
+ 'D', letter_ZD, codes_2_43_43
+ },
+ {
+ 'H', letter_ZH, codes_4_4_4
+ },
+ {
+ 'S', letter_ZS, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static dm_letter letter_[] =
+{
+ {
+ 'A', letter_A, codes_0_X_X
+ },
+ {
+ 'B', NULL, codes_7_7_7
+ },
+ {
+ 'C', letter_C, codes_5or4_5or4_5or4
+ },
+ {
+ 'D', letter_D, codes_3_3_3
+ },
+ {
+ 'E', letter_E, codes_0_X_X
+ },
+ {
+ 'F', letter_F, codes_7_7_7
+ },
+ {
+ 'G', NULL, codes_5_5_5
+ },
+ {
+ 'H', NULL, codes_5_5_X
+ },
+ {
+ 'I', letter_I, codes_0_X_X
+ },
+ {
+ 'J', NULL, codes_1or4_Xor4_Xor4
+ },
+ {
+ 'K', letter_K, codes_5_5_5
+ },
+ {
+ 'L', NULL, codes_8_8_8
+ },
+ {
+ 'M', letter_M, codes_6_6_6
+ },
+ {
+ 'N', letter_N, codes_6_6_6
+ },
+ {
+ 'O', letter_O, codes_0_X_X
+ },
+ {
+ 'P', letter_P, codes_7_7_7
+ },
+ {
+ 'Q', NULL, codes_5_5_5
+ },
+ {
+ 'R', letter_R, codes_9_9_9
+ },
+ {
+ 'S', letter_S, codes_4_4_4
+ },
+ {
+ 'T', letter_T, codes_3_3_3
+ },
+ {
+ 'U', letter_U, codes_0_X_X
+ },
+ {
+ 'V', NULL, codes_7_7_7
+ },
+ {
+ 'W', NULL, codes_7_7_7
+ },
+ {
+ 'X', NULL, codes_5_54_54
+ },
+ {
+ 'Y', NULL, codes_1_X_X
+ },
+ {
+ 'Z', letter_Z, codes_4_4_4
+ },
+ {
+ 'a', NULL, codes_X_X_6orX
+ },
+ {
+ 'e', NULL, codes_X_X_6orX
+ },
+ {
+ 't', NULL, codes_3or4_3or4_3or4
+ },
+ {
+ '\0'
+ }
+};
diff --git a/contrib/fuzzystrmatch/daitch_mokotoff_header.pl b/contrib/fuzzystrmatch/daitch_mokotoff_header.pl
new file mode 100755
index 0000000000..30cf9d3909
--- /dev/null
+++ b/contrib/fuzzystrmatch/daitch_mokotoff_header.pl
@@ -0,0 +1,281 @@
+#!/bin/perl
+#
+# Generation of types and lookup tables for Daitch-Mokotoff soundex.
+#
+# Copyright (c) 2021 Finance Norway
+# Author: Dag Lem <dag@nimrod.no>
+#
+# Permission to use, copy, modify, and distribute this software and its
+# documentation for any purpose, without fee, and without a written agreement
+# is hereby granted, provided that the above copyright notice and this
+# paragraph and the following two paragraphs appear in all copies.
+#
+# IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
+# DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
+# LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
+# DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+#
+# THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
+# INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+# AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+# ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS TO
+# PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+#
+
+use strict;
+use warnings;
+use utf8;
+use open IO => ':utf8', ':std';
+use Data::Dumper;
+
+# Parse code table and generate tree for letter transitions.
+my %codes;
+my %alternates;
+my $table = [{}, [["","",""]]];
+while (<DATA>) {
+ chomp;
+ my ($letters, $codes) = split(/\s+/);
+ my @codes = map { [ split(/\|/) ] } split(/,/, $codes);
+
+ # Find alternate code transitions for calculation of storage.
+ # The first character can never yield more than two alternate codes, and is not considered here.
+ for my $c (@codes[1..2]) {
+ if (@$c > 1) {
+ for my $i (0..1) {
+ my ($a, $b) = (substr($c->[$i], -1, 1), substr($c->[($i + 1)%2], 0, 1));
+ $alternates{$a}{$b} = 1 if $a ne $b;
+ }
+ }
+ }
+ my $key = "codes_" . join("_", map { join("or", @$_) } @codes);
+ my $val = join(",\n", map { "\t{\n\t\t" . join(", ", map { "\"$_\"" } @$_) . "\n\t}" } @codes);
+ $codes{$key} = $val;
+
+ for my $letter (split(/,/, $letters)) {
+ my $ref = $table->[0];
+ # Link each character to the next in the letter combination.
+ my @c = split(//, $letter);
+ my $last_c = pop(@c);
+ for my $c (@c) {
+ $ref->{$c} //= [ {}, undef ];
+ $ref->{$c}[0] //= {};
+ $ref = $ref->{$c}[0];
+ }
+ # The sound code for the letter combination is stored at the last character.
+ $ref->{$last_c}[1] = $key;
+ }
+}
+close(DATA);
+
+# Find the maximum number of alternate codes in one position.
+my $alt_x = $alternates{"X"};
+while (my ($k, $v) = each %alternates) {
+ if (defined delete $v->{"X"}) {
+ for my $x (keys %$alt_x) {
+ $v->{$x} = 1;
+ }
+ }
+}
+my $max_alt = (reverse sort (2, map { scalar keys %$_ } values %alternates))[0];
+
+# The maximum number of nodes and leaves in the soundex tree.
+# These are safe estimates, but in practice somewhat higher than the actual maximums.
+# Note that the first character can never yield more than two alternate codes,
+# hence the calculations are performed as sums of two subtrees.
+my $digits = 6;
+# Number of nodes (sum of geometric progression).
+my $max_nodes = 2 + 2*(1 - $max_alt**($digits - 1))/(1 - $max_alt);
+# Number of leaves (exponential of base number).
+my $max_leaves = 2*$max_alt**($digits - 2);
+
+print <<EOF;
+/*
+ * Types and lookup tables for Daitch-Mokotoff Soundex
+ *
+ * Copyright (c) 2021 Finance Norway
+ * Author: Dag Lem <dag\@nimrod.no>
+ *
+ * This file is generated by daitch_mokotoff_header.pl
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose, without fee, and without a written agreement
+ * is hereby granted, provided that the above copyright notice and this
+ * paragraph and the following two paragraphs appear in all copies.
+ *
+ * IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
+ * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING
+ * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
+ * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS TO
+ * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
+ */
+
+#include <stdlib.h>
+
+#define DM_MAX_CODE_DIGITS $digits
+#define DM_MAX_ALTERNATE_CODES $max_alt
+#define DM_MAX_NODES $max_nodes
+#define DM_MAX_LEAVES $max_leaves
+#define DM_MAX_SOUNDEX_CHARS (DM_MAX_NODES*(DM_MAX_CODE_DIGITS + 1))
+#define DM_VOWELS "AEIOUY"
+
+typedef char dm_code[2 + 1]; /* One or two sequential code digits + NUL */
+typedef dm_code dm_codes[2]; /* One or two alternate code sequences */
+
+/* Letter in input sequence */
+struct dm_letter
+{
+ char letter; /* Present letter in sequence */
+ struct dm_letter *letters; /* List of possible successive letters */
+ dm_codes *codes; /* Code sequence(s) for complete sequence */
+};
+
+/* Node in soundex code tree */
+struct dm_node
+{
+ int soundex_length; /* Length of generated soundex code */
+ char soundex[DM_MAX_CODE_DIGITS + 1]; /* Soundex code */
+ int is_leaf; /* Completed soundex codes are leaves */
+ int last_update; /* Character index for last update of node */
+ char code_digit; /* Current code digit */
+
+ /*
+ * One or two alternate code digits leading to this node - repeated code
+ * digits and 'X' lead back to the same node.
+ */
+ char prev_code_digits[2];
+ char next_code_digits[2];
+ /* Branching nodes */
+ struct dm_node *next_nodes[DM_MAX_ALTERNATE_CODES + 1];
+};
+
+typedef struct dm_letter dm_letter;
+typedef struct dm_node dm_node;
+
+/* Codes for letter sequence at start of name, before a vowel, and any other. */
+EOF
+
+for my $key (sort keys %codes) {
+ print "static dm_codes $key\[\] =\n{\n" . $codes{$key} . "\n};\n";
+}
+
+print <<EOF;
+
+/* Coding for alternative following letters in sequence. */
+EOF
+
+sub hash2code {
+ my ($ref, $letter) = @_;
+
+ my @letters = ();
+
+ my $h = $ref->[0];
+ for my $key (sort keys %$h) {
+ $ref = $h->{$key};
+ my $children = "NULL";
+ if (defined $ref->[0]) {
+ $children = "letter_$letter$key";
+ hash2code($ref, "$letter$key");
+ }
+ my $codes = $ref->[1] // "NULL";
+ push(@letters, "\t{\n\t\t'$key', $children, $codes\n\t}");
+ }
+
+ print "static dm_letter letter_$letter\[\] =\n{\n";
+ for (@letters) {
+ print "$_,\n";
+ }
+ print "\t{\n\t\t'\\0'\n\t}\n";
+ print "};\n";
+}
+
+hash2code($table, '');
+
+
+# Table adapted from https://www.jewishgen.org/InfoFiles/Soundex.html
+#
+# X = NC (not coded)
+#
+# Note that the following letters are coded with substitute letters
+#
+# Ą => a (use '[' for table lookup)
+# Ę => e (use '\\' for table lookup)
+# Ţ => t (use ']' for table lookup)
+#
+
+__DATA__
+AI,AJ,AY 0,1,X
+AU 0,7,X
+a X,X,6|X
+A 0,X,X
+B 7,7,7
+CHS 5,54,54
+CH 5|4,5|4,5|4
+CK 5|45,5|45,5|45
+CZ,CS,CSZ,CZS 4,4,4
+C 5|4,5|4,5|4
+DRZ,DRS 4,4,4
+DS,DSH,DSZ 4,4,4
+DZ,DZH,DZS 4,4,4
+D,DT 3,3,3
+EI,EJ,EY 0,1,X
+EU 1,1,X
+e X,X,6|X
+E 0,X,X
+FB 7,7,7
+F 7,7,7
+G 5,5,5
+H 5,5,X
+IA,IE,IO,IU 1,X,X
+I 0,X,X
+J 1|4,X|4,X|4
+KS 5,54,54
+KH 5,5,5
+K 5,5,5
+L 8,8,8
+MN 66,66,66
+M 6,6,6
+NM 66,66,66
+N 6,6,6
+OI,OJ,OY 0,1,X
+O 0,X,X
+P,PF,PH 7,7,7
+Q 5,5,5
+RZ,RS 94|4,94|4,94|4
+R 9,9,9
+SCHTSCH,SCHTSH,SCHTCH 2,4,4
+SCH 4,4,4
+SHTCH,SHCH,SHTSH 2,4,4
+SHT,SCHT,SCHD 2,43,43
+SH 4,4,4
+STCH,STSCH,SC 2,4,4
+STRZ,STRS,STSH 2,4,4
+ST 2,43,43
+SZCZ,SZCS 2,4,4
+SZT,SHD,SZD,SD 2,43,43
+SZ 4,4,4
+S 4,4,4
+TCH,TTCH,TTSCH 4,4,4
+TH 3,3,3
+TRZ,TRS 4,4,4
+TSCH,TSH 4,4,4
+TS,TTS,TTSZ,TC 4,4,4
+TZ,TTZ,TZS,TSZ 4,4,4
+t 3|4,3|4,3|4
+T 3,3,3
+UI,UJ,UY 0,1,X
+U,UE 0,X,X
+V 7,7,7
+W 7,7,7
+X 5,54,54
+Y 1,X,X
+ZDZ,ZDZH,ZHDZH 2,4,4
+ZD,ZHD 2,43,43
+ZH,ZS,ZSCH,ZSH 4,4,4
+Z 4,4,4
diff --git a/contrib/fuzzystrmatch/expected/fuzzystrmatch.out b/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
index 493c95cdfa..1f7708fff0 100644
--- a/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
+++ b/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
@@ -65,3 +65,194 @@ SELECT dmetaphone_alt('gumbo');
KMP
(1 row)
+-- Wovels
+SELECT daitch_mokotoff('Augsburg');
+ daitch_mokotoff
+-----------------
+ 054795
+(1 row)
+
+SELECT daitch_mokotoff('Breuer');
+ daitch_mokotoff
+-----------------
+ 791900
+(1 row)
+
+SELECT daitch_mokotoff('Freud');
+ daitch_mokotoff
+-----------------
+ 793000
+(1 row)
+
+-- The letter "H"
+SELECT daitch_mokotoff('Halberstadt');
+ daitch_mokotoff
+-----------------
+ 587943 587433
+(1 row)
+
+SELECT daitch_mokotoff('Mannheim');
+ daitch_mokotoff
+-----------------
+ 665600
+(1 row)
+
+-- Adjacent sounds
+SELECT daitch_mokotoff('Chernowitz');
+ daitch_mokotoff
+-----------------
+ 596740 496740
+(1 row)
+
+-- Adjacent letters with identical adjacent code digits
+SELECT daitch_mokotoff('Cherkassy');
+ daitch_mokotoff
+-----------------
+ 595400 495400
+(1 row)
+
+SELECT daitch_mokotoff('Kleinman');
+ daitch_mokotoff
+-----------------
+ 586660
+(1 row)
+
+SELECT daitch_mokotoff('Besst');
+ daitch_mokotoff
+-----------------
+ 743000
+(1 row)
+
+-- More than one word
+SELECT daitch_mokotoff('Nowy Targ');
+ daitch_mokotoff
+-----------------
+ 673950
+(1 row)
+
+-- Padded with "0"
+SELECT daitch_mokotoff('Berlin');
+ daitch_mokotoff
+-----------------
+ 798600
+(1 row)
+
+-- Other examples from https://www.avotaynu.com/soundex.htm
+SELECT daitch_mokotoff('Ceniow');
+ daitch_mokotoff
+-----------------
+ 567000 467000
+(1 row)
+
+SELECT daitch_mokotoff('Tsenyuv');
+ daitch_mokotoff
+-----------------
+ 467000
+(1 row)
+
+SELECT daitch_mokotoff('Holubica');
+ daitch_mokotoff
+-----------------
+ 587500 587400
+(1 row)
+
+SELECT daitch_mokotoff('Golubitsa');
+ daitch_mokotoff
+-----------------
+ 587400
+(1 row)
+
+SELECT daitch_mokotoff('Przemysl');
+ daitch_mokotoff
+-----------------
+ 794648 746480
+(1 row)
+
+SELECT daitch_mokotoff('Pshemeshil');
+ daitch_mokotoff
+-----------------
+ 746480
+(1 row)
+
+SELECT daitch_mokotoff('Rosochowaciec');
+ daitch_mokotoff
+---------------------------------------------------------
+ 945755 945754 945745 945744 944755 944754 944745 944744
+(1 row)
+
+SELECT daitch_mokotoff('Rosokhovatsets');
+ daitch_mokotoff
+-----------------
+ 945744
+(1 row)
+
+-- Accents
+SELECT daitch_mokotoff('Müller');
+ daitch_mokotoff
+-----------------
+ 689000
+(1 row)
+
+SELECT daitch_mokotoff('Schäfer');
+ daitch_mokotoff
+-----------------
+ 479000
+(1 row)
+
+SELECT daitch_mokotoff('Straßburg');
+ daitch_mokotoff
+-----------------
+ 294795
+(1 row)
+
+SELECT daitch_mokotoff('Éregon');
+ daitch_mokotoff
+-----------------
+ 095600
+(1 row)
+
+-- Ignored characters
+SELECT daitch_mokotoff('''OBrien');
+ daitch_mokotoff
+-----------------
+ 079600
+(1 row)
+
+SELECT daitch_mokotoff('O''Brien');
+ daitch_mokotoff
+-----------------
+ 079600
+(1 row)
+
+-- Special characters added at https://www.jewishgen.org/InfoFiles/Soundex.html
+SELECT daitch_mokotoff('gąszczu');
+ daitch_mokotoff
+-----------------
+ 564000 540000
+(1 row)
+
+SELECT daitch_mokotoff('brzęczy');
+ daitch_mokotoff
+-----------------------------
+ 794640 794400 746400 744000
+(1 row)
+
+SELECT daitch_mokotoff('ţamas');
+ daitch_mokotoff
+-----------------
+ 364000 464000
+(1 row)
+
+SELECT daitch_mokotoff('țamas');
+ daitch_mokotoff
+-----------------
+ 364000 464000
+(1 row)
+
+-- Contrived case which is not handled correctly by other implementations.
+SELECT daitch_mokotoff('CJC');
+ daitch_mokotoff
+-------------------------------------------
+ 550000 540000 545000 450000 400000 440000
+(1 row)
+
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch--1.1--1.2.sql b/contrib/fuzzystrmatch/fuzzystrmatch--1.1--1.2.sql
new file mode 100644
index 0000000000..b9d7b229a3
--- /dev/null
+++ b/contrib/fuzzystrmatch/fuzzystrmatch--1.1--1.2.sql
@@ -0,0 +1,8 @@
+/* contrib/fuzzystrmatch/fuzzystrmatch--1.1--1.2.sql */
+
+-- complain if script is sourced in psql, rather than via ALTER EXTENSION
+\echo Use "ALTER EXTENSION fuzzystrmatch UPDATE TO '1.2'" to load this file. \quit
+
+CREATE FUNCTION daitch_mokotoff(text) RETURNS text
+AS 'MODULE_PATHNAME', 'daitch_mokotoff'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql b/contrib/fuzzystrmatch/fuzzystrmatch--1.2.sql
similarity index 92%
rename from contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql
rename to contrib/fuzzystrmatch/fuzzystrmatch--1.2.sql
index 41de9d949b..2a8a100699 100644
--- a/contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql
+++ b/contrib/fuzzystrmatch/fuzzystrmatch--1.2.sql
@@ -42,3 +42,7 @@ LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
CREATE FUNCTION dmetaphone_alt (text) RETURNS text
AS 'MODULE_PATHNAME', 'dmetaphone_alt'
LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION daitch_mokotoff(text) RETURNS text
+AS 'MODULE_PATHNAME', 'daitch_mokotoff'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.control b/contrib/fuzzystrmatch/fuzzystrmatch.control
index 3cd6660bf9..8b6e9fd993 100644
--- a/contrib/fuzzystrmatch/fuzzystrmatch.control
+++ b/contrib/fuzzystrmatch/fuzzystrmatch.control
@@ -1,6 +1,6 @@
# fuzzystrmatch extension
comment = 'determine similarities and distance between strings'
-default_version = '1.1'
+default_version = '1.2'
module_pathname = '$libdir/fuzzystrmatch'
relocatable = true
trusted = true
diff --git a/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql b/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
index f05dc28ffb..85ac755ddd 100644
--- a/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
+++ b/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
@@ -19,3 +19,55 @@ SELECT metaphone('GUMBO', 4);
SELECT dmetaphone('gumbo');
SELECT dmetaphone_alt('gumbo');
+
+-- Wovels
+SELECT daitch_mokotoff('Augsburg');
+SELECT daitch_mokotoff('Breuer');
+SELECT daitch_mokotoff('Freud');
+
+-- The letter "H"
+SELECT daitch_mokotoff('Halberstadt');
+SELECT daitch_mokotoff('Mannheim');
+
+-- Adjacent sounds
+SELECT daitch_mokotoff('Chernowitz');
+
+-- Adjacent letters with identical adjacent code digits
+SELECT daitch_mokotoff('Cherkassy');
+SELECT daitch_mokotoff('Kleinman');
+SELECT daitch_mokotoff('Besst');
+
+-- More than one word
+SELECT daitch_mokotoff('Nowy Targ');
+
+-- Padded with "0"
+SELECT daitch_mokotoff('Berlin');
+
+-- Other examples from https://www.avotaynu.com/soundex.htm
+SELECT daitch_mokotoff('Ceniow');
+SELECT daitch_mokotoff('Tsenyuv');
+SELECT daitch_mokotoff('Holubica');
+SELECT daitch_mokotoff('Golubitsa');
+SELECT daitch_mokotoff('Przemysl');
+SELECT daitch_mokotoff('Pshemeshil');
+SELECT daitch_mokotoff('Rosochowaciec');
+SELECT daitch_mokotoff('Rosokhovatsets');
+
+-- Accents
+SELECT daitch_mokotoff('Müller');
+SELECT daitch_mokotoff('Schäfer');
+SELECT daitch_mokotoff('Straßburg');
+SELECT daitch_mokotoff('Éregon');
+
+-- Ignored characters
+SELECT daitch_mokotoff('''OBrien');
+SELECT daitch_mokotoff('O''Brien');
+
+-- Special characters added at https://www.jewishgen.org/InfoFiles/Soundex.html
+SELECT daitch_mokotoff('gąszczu');
+SELECT daitch_mokotoff('brzęczy');
+SELECT daitch_mokotoff('ţamas');
+SELECT daitch_mokotoff('țamas');
+
+-- Contrived case which is not handled correctly by other implementations.
+SELECT daitch_mokotoff('CJC');
diff --git a/doc/src/sgml/fuzzystrmatch.sgml b/doc/src/sgml/fuzzystrmatch.sgml
index 382e54be91..a5dbd535f4 100644
--- a/doc/src/sgml/fuzzystrmatch.sgml
+++ b/doc/src/sgml/fuzzystrmatch.sgml
@@ -241,4 +241,98 @@ test=# SELECT dmetaphone('gumbo');
</screen>
</sect2>
+ <sect2>
+ <title>Daitch-Mokotoff Soundex</title>
+
+ <para>
+ Compared to the American Soundex System implemented in the
+ <function>soundex</function> function, the major improvements of the
+ Daitch-Mokotoff Soundex System are:
+
+ <itemizedlist spacing="compact" mark="bullet">
+ <listitem>
+ <para>
+ Information is coded to the first six meaningful letters rather than
+ four.
+ </para>
+ </listitem>
+ <listitem>
+ <para>
+ The initial letter is coded rather than kept as is.
+ </para>
+ </listitem>
+ <listitem>
+ <para>
+ Where two consecutive letters have a single sound, they are coded as a
+ single number.
+ </para>
+ </listitem>
+ <listitem>
+ <para>
+ When a letter or combination of letters may have two different sounds,
+ it is double coded under the two different codes.
+ </para>
+ </listitem>
+ <listitem>
+ <para>
+ A letter or combination of letters maps into ten possible codes rather
+ than seven.
+ </para>
+ </listitem>
+ </itemizedlist>
+ </para>
+
+ <indexterm>
+ <primary>daitch_mokotoff</primary>
+ </indexterm>
+
+ <para>
+ The following function generates Daitch-Mokotoff soundex codes for matching
+ of similar-sounding input:
+ </para>
+
+<synopsis>
+daitch_mokotoff(text source) returns text
+</synopsis>
+
+ <para>
+ Since a Daitch-Mokotoff soundex code consists of only 6 digits,
+ <literal>source</literal> should be preferably a single word or name.
+ Any alternative soundex codes are separated by space, which makes the returned
+ text suited for use in Full Text Search, see <xref linkend="textsearch"/> and
+ <xref linkend="functions-textsearch"/>.
+ </para>
+
+ <para>
+ Example:
+ </para>
+
+<programlisting>
+CREATE OR REPLACE FUNCTION soundex_name(v_name text) RETURNS text AS $$
+ SELECT string_agg(daitch_mokotoff(n), ' ')
+ FROM regexp_split_to_table(v_name, '\s+') AS n
+$$ LANGUAGE sql STRICT IMMUTABLE PARALLEL SAFE;
+
+CREATE OR REPLACE FUNCTION soundex_tsvector(v_name text) RETURNS tsvector AS $$
+ SELECT to_tsvector('simple', soundex_name(v_name))
+$$ LANGUAGE sql STRICT IMMUTABLE PARALLEL SAFE;
+
+CREATE OR REPLACE FUNCTION soundex_tsquery(v_name text) RETURNS tsquery AS $$
+ SELECT to_tsquery('simple', quote_literal(soundex_name(v_name)))
+$$ LANGUAGE sql STRICT IMMUTABLE PARALLEL SAFE;
+
+-- Note that searches could be more efficient with the tsvector in a separate column
+-- (no computation on table row recheck).
+CREATE TABLE s (nm text);
+CREATE INDEX ix_s_txt ON s USING gin (soundex_tsvector(nm)) WITH (fastupdate = off);
+
+INSERT INTO s VALUES ('john');
+INSERT INTO s VALUES ('joan');
+INSERT INTO s VALUES ('wobbly');
+INSERT INTO s VALUES ('jack');
+
+SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john');
+</programlisting>
+ </sect2>
+
</sect1>
pgsql-hackers by date: