summaryrefslogtreecommitdiffstats
path: root/contrib/fuzzystrmatch
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 13:44:03 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-13 13:44:03 +0000
commit293913568e6a7a86fd1479e1cff8e2ecb58d6568 (patch)
treefc3b469a3ec5ab71b36ea97cc7aaddb838423a0c /contrib/fuzzystrmatch
parentInitial commit. (diff)
downloadpostgresql-16-293913568e6a7a86fd1479e1cff8e2ecb58d6568.tar.xz
postgresql-16-293913568e6a7a86fd1479e1cff8e2ecb58d6568.zip
Adding upstream version 16.2.upstream/16.2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'contrib/fuzzystrmatch')
-rw-r--r--contrib/fuzzystrmatch/.gitignore6
-rw-r--r--contrib/fuzzystrmatch/Makefile40
-rw-r--r--contrib/fuzzystrmatch/daitch_mokotoff.c571
-rw-r--r--contrib/fuzzystrmatch/daitch_mokotoff.h949
-rwxr-xr-xcontrib/fuzzystrmatch/daitch_mokotoff_header.pl219
-rw-r--r--contrib/fuzzystrmatch/dmetaphone.c1438
-rw-r--r--contrib/fuzzystrmatch/expected/fuzzystrmatch.out244
-rw-r--r--contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8.out61
-rw-r--r--contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8_1.out8
-rw-r--r--contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql15
-rw-r--r--contrib/fuzzystrmatch/fuzzystrmatch--1.1--1.2.sql8
-rw-r--r--contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql44
-rw-r--r--contrib/fuzzystrmatch/fuzzystrmatch.c794
-rw-r--r--contrib/fuzzystrmatch/fuzzystrmatch.control6
-rw-r--r--contrib/fuzzystrmatch/meson.build48
-rw-r--r--contrib/fuzzystrmatch/sql/fuzzystrmatch.sql67
-rw-r--r--contrib/fuzzystrmatch/sql/fuzzystrmatch_utf8.sql26
17 files changed, 4544 insertions, 0 deletions
diff --git a/contrib/fuzzystrmatch/.gitignore b/contrib/fuzzystrmatch/.gitignore
new file mode 100644
index 0000000..b474444
--- /dev/null
+++ b/contrib/fuzzystrmatch/.gitignore
@@ -0,0 +1,6 @@
+# Generated files
+/daitch_mokotoff.h
+# Generated subdirectories
+/log/
+/results/
+/tmp_check/
diff --git a/contrib/fuzzystrmatch/Makefile b/contrib/fuzzystrmatch/Makefile
new file mode 100644
index 0000000..e68bc0e
--- /dev/null
+++ b/contrib/fuzzystrmatch/Makefile
@@ -0,0 +1,40 @@
+# contrib/fuzzystrmatch/Makefile
+
+MODULE_big = fuzzystrmatch
+OBJS = \
+ $(WIN32RES) \
+ daitch_mokotoff.o \
+ dmetaphone.o \
+ fuzzystrmatch.o
+
+EXTENSION = fuzzystrmatch
+DATA = fuzzystrmatch--1.1.sql fuzzystrmatch--1.1--1.2.sql \
+ fuzzystrmatch--1.0--1.1.sql
+
+PGFILEDESC = "fuzzystrmatch - similarities and distance between strings"
+
+REGRESS = fuzzystrmatch fuzzystrmatch_utf8
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/fuzzystrmatch
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
+
+# Force this dependency to be known even without dependency info built:
+daitch_mokotoff.o: daitch_mokotoff.h
+
+daitch_mokotoff.h: daitch_mokotoff_header.pl
+ $(PERL) $< $@
+
+# daitch_mokotoff.h is included in tarballs, so it has to be made by
+# "distprep" and not cleaned except by "maintainer-clean".
+distprep: daitch_mokotoff.h
+
+maintainer-clean:
+ rm -f daitch_mokotoff.h
diff --git a/contrib/fuzzystrmatch/daitch_mokotoff.c b/contrib/fuzzystrmatch/daitch_mokotoff.c
new file mode 100644
index 0000000..162e32c
--- /dev/null
+++ b/contrib/fuzzystrmatch/daitch_mokotoff.c
@@ -0,0 +1,571 @@
+/*
+ * Daitch-Mokotoff Soundex
+ *
+ * Copyright (c) 2023, PostgreSQL Global Development Group
+ *
+ * This module was originally sponsored by Finance Norway /
+ * Trafikkforsikringsforeningen, and implemented by Dag Lem <dag@nimrod.no>
+ *
+ * The implementation of the Daitch-Mokotoff Soundex System aims at correctness
+ * and high performance, and can be summarized as follows:
+ *
+ * - 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:
+ *
+ * - All other known implementations have the same unofficial rules for "UE",
+ * these are also adapted by this implementation (0, 1, NC).
+ * - The only other known implementation which is capable of generating all
+ * correct soundex codes in all cases is the JOS Soundex Calculator at
+ * https://www.jewishgen.org/jos/jossound.htm
+ * - "J" is considered (only) 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".
+ * - "J" is considered (only) a consonant in DaitchMokotoffSoundex.java
+ * - "Y" is not considered a vowel in DaitchMokotoffSoundex.java
+*/
+
+#include "postgres.h"
+
+#include "catalog/pg_type.h"
+#include "mb/pg_wchar.h"
+#include "utils/array.h"
+#include "utils/builtins.h"
+#include "utils/memutils.h"
+
+
+/*
+ * The soundex coding chart table is adapted from
+ * https://www.jewishgen.org/InfoFiles/Soundex.html
+ * See daitch_mokotoff_header.pl for details.
+*/
+
+/* Generated coding chart table */
+#include "daitch_mokotoff.h"
+
+#define DM_CODE_DIGITS 6
+
+/* Node in soundex code tree */
+typedef struct dm_node
+{
+ int soundex_length; /* Length of generated soundex code */
+ char soundex[DM_CODE_DIGITS]; /* Soundex code */
+ int is_leaf; /* Candidate for complete soundex code */
+ int last_update; /* Letter number for last update of node */
+ char code_digit; /* Last code digit, 0 - 9 */
+
+ /*
+ * One or two alternate code digits leading to this node. If there are two
+ * digits, one of them is always an 'X'. Repeated code digits and 'X' lead
+ * back to the same node.
+ */
+ char prev_code_digits[2];
+ /* One or two alternate code digits moving forward. */
+ char next_code_digits[2];
+ /* ORed together code index(es) used to reach current node. */
+ int prev_code_index;
+ int next_code_index;
+ /* Possible nodes branching out from this node - digits 0-9. */
+ struct dm_node *children[10];
+ /* Next node in linked list. Alternating index for each iteration. */
+ struct dm_node *next[2];
+} dm_node;
+
+/* Template for new node in soundex code tree. */
+static const dm_node start_node = {
+ .soundex_length = 0,
+ .soundex = "000000", /* Six digits */
+ .is_leaf = 0,
+ .last_update = 0,
+ .code_digit = '\0',
+ .prev_code_digits = {'\0', '\0'},
+ .next_code_digits = {'\0', '\0'},
+ .prev_code_index = 0,
+ .next_code_index = 0,
+ .children = {NULL},
+ .next = {NULL}
+};
+
+/* Dummy soundex codes at end of input. */
+static const dm_codes end_codes[2] =
+{
+ {
+ "X", "X", "X"
+ }
+};
+
+/* Mapping from ISO8859-1 to upper-case ASCII, covering the range 0x60..0xFF. */
+static const char iso8859_1_to_ascii_upper[] =
+"`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~ ! ?AAAAAAECEEEEIIIIDNOOOOO*OUUUUYDSAAAAAAECEEEEIIIIDNOOOOO/OUUUUYDY";
+
+/* Internal C implementation */
+static bool daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex);
+
+
+PG_FUNCTION_INFO_V1(daitch_mokotoff);
+
+Datum
+daitch_mokotoff(PG_FUNCTION_ARGS)
+{
+ text *arg = PG_GETARG_TEXT_PP(0);
+ Datum retval;
+ char *string;
+ ArrayBuildState *soundex;
+ MemoryContext old_ctx,
+ tmp_ctx;
+
+ /* Work in a temporary context to simplify cleanup. */
+ tmp_ctx = AllocSetContextCreate(CurrentMemoryContext,
+ "daitch_mokotoff temporary context",
+ ALLOCSET_DEFAULT_SIZES);
+ old_ctx = MemoryContextSwitchTo(tmp_ctx);
+
+ /* We must convert the string to UTF-8 if it isn't already. */
+ string = pg_server_to_any(text_to_cstring(arg), VARSIZE_ANY_EXHDR(arg),
+ PG_UTF8);
+
+ /* The result is built in this ArrayBuildState. */
+ soundex = initArrayResult(TEXTOID, tmp_ctx, false);
+
+ if (!daitch_mokotoff_coding(string, soundex))
+ {
+ /* No encodable characters in input */
+ MemoryContextSwitchTo(old_ctx);
+ MemoryContextDelete(tmp_ctx);
+ PG_RETURN_NULL();
+ }
+
+ retval = makeArrayResult(soundex, old_ctx);
+
+ MemoryContextSwitchTo(old_ctx);
+ MemoryContextDelete(tmp_ctx);
+
+ PG_RETURN_DATUM(retval);
+}
+
+
+/* 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->prev_code_index = node->next_code_index;
+ node->next_code_index = 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, int code_index, char code_digit)
+{
+ /* OR in index 1 or 2. */
+ node->next_code_index |= code_index;
+
+ 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. */
+static void
+set_leaf(dm_node *first_node[2], dm_node *last_node[2],
+ dm_node *node, int ix_node)
+{
+ if (!node->is_leaf)
+ {
+ node->is_leaf = 1;
+
+ if (first_node[ix_node] == NULL)
+ first_node[ix_node] = node;
+ else
+ last_node[ix_node]->next[ix_node] = node;
+
+ last_node[ix_node] = node;
+ node->next[ix_node] = NULL;
+ }
+}
+
+
+/* Find next node corresponding to code digit, or create a new node. */
+static dm_node *
+find_or_create_child_node(dm_node *parent, char code_digit,
+ ArrayBuildState *soundex)
+{
+ int i = code_digit - '0';
+ dm_node **nodes = parent->children;
+ dm_node *node = nodes[i];
+
+ if (node)
+ {
+ /* Found existing child node. Skip completed nodes. */
+ return node->soundex_length < DM_CODE_DIGITS ? node : NULL;
+ }
+
+ /* Create new child node. */
+ node = palloc_object(dm_node);
+ nodes[i] = node;
+
+ *node = start_node;
+ memcpy(node->soundex, parent->soundex, sizeof(parent->soundex));
+ node->soundex_length = parent->soundex_length;
+ node->soundex[node->soundex_length++] = code_digit;
+ node->code_digit = code_digit;
+ node->next_code_index = node->prev_code_index;
+
+ if (node->soundex_length < DM_CODE_DIGITS)
+ {
+ return node;
+ }
+ else
+ {
+ /* Append completed soundex code to output array. */
+ text *out = cstring_to_text_with_len(node->soundex,
+ DM_CODE_DIGITS);
+
+ accumArrayResult(soundex,
+ PointerGetDatum(out),
+ false,
+ TEXTOID,
+ CurrentMemoryContext);
+ return NULL;
+ }
+}
+
+
+/* Update node for next code digit(s). */
+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)
+{
+ int i;
+ char next_code_digit = next_code_digits[digit_no];
+ int num_dirty_nodes = 0;
+ dm_node *dirty_nodes[2];
+
+ initialize_node(node, letter_no);
+
+ if (node->prev_code_index && !(node->prev_code_index & prev_code_index))
+ {
+ /*
+ * If the sound (vowel / consonant) of this letter encoding doesn't
+ * correspond to the coding index of the previous letter, we skip this
+ * letter encoding. Note that currently, only "J" can be either a
+ * vowel or a consonant.
+ */
+ return;
+ }
+
+ if (next_code_digit == 'X' ||
+ (digit_no == 0 &&
+ (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' &&
+ (digit_no > 0 ||
+ 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_child_node(node, next_code_digit, soundex);
+ if (node)
+ {
+ initialize_node(node, letter_no);
+ 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_index, next_code_digit);
+
+ if (next_code_digits[++digit_no])
+ {
+ update_node(first_node, last_node, dirty_nodes[i], ix_node,
+ letter_no, prev_code_index, next_code_index,
+ next_code_digits, digit_no,
+ soundex);
+ }
+ else
+ {
+ /* Add incomplete leaf node to linked list. */
+ set_leaf(first_node, last_node, dirty_nodes[i], ix_node);
+ }
+ }
+}
+
+
+/* Update soundex tree leaf nodes. */
+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)
+{
+ int i,
+ j,
+ code_index;
+ dm_node *node,
+ *last_node[2];
+ const dm_code *code,
+ *next_code;
+ int ix_node_next = (*ix_node + 1) & 1; /* Alternating index: 0, 1 */
+
+ /* Initialize for new linked list of leaves. */
+ first_node[ix_node_next] = NULL;
+ last_node[ix_node_next] = NULL;
+
+ /* Process all nodes. */
+ for (node = first_node[*ix_node]; node; node = node->next[*ix_node])
+ {
+ /* One or two alternate code sequences. */
+ for (i = 0; i < 2 && (code = codes[i]) && code[0][0]; i++)
+ {
+ /* Coding for previous letter - before vowel: 1, all other: 2 */
+ int prev_code_index = (code[0][0] > '1') + 1;
+
+ /* One or two alternate next code sequences. */
+ for (j = 0; j < 2 && (next_code = next_codes[j]) && next_code[0][0]; j++)
+ {
+ /* Determine which code to use. */
+ if (letter_no == 0)
+ {
+ /* This is the first letter. */
+ code_index = 0;
+ }
+ else if (next_code[0][0] <= '1')
+ {
+ /* The next letter is a vowel. */
+ code_index = 1;
+ }
+ else
+ {
+ /* All other cases. */
+ code_index = 2;
+ }
+
+ /* One or two sequential code digits. */
+ update_node(first_node, last_node, node, ix_node_next,
+ letter_no, prev_code_index, code_index,
+ code[code_index], 0,
+ soundex);
+ }
+ }
+ }
+
+ *ix_node = ix_node_next;
+}
+
+
+/*
+ * Return next character, converted from UTF-8 to uppercase ASCII.
+ * *ix is the current string index and is incremented by the character length.
+ */
+static char
+read_char(const unsigned char *str, int *ix)
+{
+ /* Substitute character for skipped code points. */
+ const char na = '\x1a';
+ pg_wchar c;
+
+ /* Decode UTF-8 character to ISO 10646 code point. */
+ str += *ix;
+ c = utf8_to_unicode(str);
+
+ /* Advance *ix, but (for safety) not if we've reached end of string. */
+ if (c)
+ *ix += pg_utf_mblen(str);
+
+ /* Convert. */
+ if (c >= (unsigned char) '[' && c <= (unsigned char) ']')
+ {
+ /* ASCII characters [, \, and ] are reserved for conversions below. */
+ return na;
+ }
+ else if (c < 0x60)
+ {
+ /* Other non-lowercase ASCII characters can be used as-is. */
+ return (char) c;
+ }
+ else if (c < 0x100)
+ {
+ /* ISO-8859-1 code point; convert to upper-case ASCII via table. */
+ return iso8859_1_to_ascii_upper[c - 0x60];
+ }
+ else
+ {
+ /* Conversion of non-ASCII characters in the coding chart. */
+ switch (c)
+ {
+ case 0x0104: /* LATIN CAPITAL LETTER A WITH OGONEK */
+ case 0x0105: /* LATIN SMALL LETTER A WITH OGONEK */
+ return '[';
+ case 0x0118: /* LATIN CAPITAL LETTER E WITH OGONEK */
+ case 0x0119: /* LATIN SMALL LETTER E WITH OGONEK */
+ return '\\';
+ case 0x0162: /* LATIN CAPITAL LETTER T WITH CEDILLA */
+ case 0x0163: /* LATIN SMALL LETTER T WITH CEDILLA */
+ case 0x021A: /* LATIN CAPITAL LETTER T WITH COMMA BELOW */
+ case 0x021B: /* LATIN SMALL LETTER T WITH COMMA BELOW */
+ return ']';
+ default:
+ return na;
+ }
+ }
+}
+
+
+/* Read next ASCII character, skipping any characters not in [A-\]]. */
+static char
+read_valid_char(const char *str, int *ix)
+{
+ char c;
+
+ while ((c = read_char((const unsigned char *) str, ix)) != '\0')
+ {
+ if (c >= 'A' && c <= ']')
+ break;
+ }
+
+ return c;
+}
+
+
+/* Return sound coding for "letter" (letter sequence) */
+static const dm_codes *
+read_letter(const char *str, int *ix)
+{
+ char c,
+ cmp;
+ int i,
+ j;
+ const dm_letter *letters;
+ const dm_codes *codes;
+
+ /* First letter in sequence. */
+ if ((c = read_valid_char(str, ix)) == '\0')
+ return NULL;
+
+ letters = &letter_[c - 'A'];
+ codes = letters->codes;
+ i = *ix;
+
+ /* Any subsequent letters in sequence. */
+ while ((letters = letters->letters) && (c = read_valid_char(str, &i)))
+ {
+ for (j = 0; (cmp = letters[j].letter); j++)
+ {
+ if (cmp == c)
+ {
+ /* Letter found. */
+ letters = &letters[j];
+ if (letters->codes)
+ {
+ /* Coding for letter sequence found. */
+ codes = letters->codes;
+ *ix = i;
+ }
+ break;
+ }
+ }
+ if (!cmp)
+ {
+ /* The sequence of letters has no coding. */
+ break;
+ }
+ }
+
+ return codes;
+}
+
+
+/*
+ * Generate all Daitch-Mokotoff soundex codes for word,
+ * adding them to the "soundex" ArrayBuildState.
+ * Returns false if string has no encodable characters, else true.
+ */
+static bool
+daitch_mokotoff_coding(const char *word, ArrayBuildState *soundex)
+{
+ int i = 0;
+ int letter_no = 0;
+ int ix_node = 0;
+ const dm_codes *codes,
+ *next_codes;
+ dm_node *first_node[2],
+ *node;
+
+ /* First letter. */
+ if (!(codes = read_letter(word, &i)))
+ {
+ /* No encodable character in input. */
+ return false;
+ }
+
+ /* Starting point. */
+ first_node[ix_node] = palloc_object(dm_node);
+ *first_node[ix_node] = start_node;
+
+ /*
+ * Loop until either the word input is exhausted, or all generated soundex
+ * codes are completed to six digits.
+ */
+ while (codes && first_node[ix_node])
+ {
+ next_codes = read_letter(word, &i);
+
+ /* Update leaf nodes. */
+ update_leaves(first_node, &ix_node, letter_no,
+ codes, next_codes ? next_codes : end_codes,
+ soundex);
+
+ codes = next_codes;
+ letter_no++;
+ }
+
+ /* Append all remaining (incomplete) soundex codes to output array. */
+ for (node = first_node[ix_node]; node; node = node->next[ix_node])
+ {
+ text *out = cstring_to_text_with_len(node->soundex,
+ DM_CODE_DIGITS);
+
+ accumArrayResult(soundex,
+ PointerGetDatum(out),
+ false,
+ TEXTOID,
+ CurrentMemoryContext);
+ }
+
+ return true;
+}
diff --git a/contrib/fuzzystrmatch/daitch_mokotoff.h b/contrib/fuzzystrmatch/daitch_mokotoff.h
new file mode 100644
index 0000000..8327415
--- /dev/null
+++ b/contrib/fuzzystrmatch/daitch_mokotoff.h
@@ -0,0 +1,949 @@
+/*
+ * Constants and lookup tables for Daitch-Mokotoff Soundex
+ *
+ * Copyright (c) 2023, PostgreSQL Global Development Group
+ *
+ * This file is generated by daitch_mokotoff_header.pl
+ */
+
+/* Coding chart table: Soundex codes */
+typedef char dm_code[2 + 1]; /* One or two sequential code digits + NUL */
+typedef dm_code dm_codes[3]; /* Start of name, before a vowel, any other */
+
+/* Coding chart table: Letter in input sequence */
+struct dm_letter
+{
+ char letter; /* Present letter in sequence */
+ const struct dm_letter *letters; /* List of possible successive letters */
+ const dm_codes *codes; /* Code sequence(s) for complete sequence */
+};
+
+typedef struct dm_letter dm_letter;
+
+/* Codes for letter sequence at start of name, before a vowel, and any other. */
+static const dm_codes codes_0_1_X[2] =
+{
+ {
+ "0", "1", "X"
+ }
+};
+static const dm_codes codes_0_7_X[2] =
+{
+ {
+ "0", "7", "X"
+ }
+};
+static const dm_codes codes_0_X_X[2] =
+{
+ {
+ "0", "X", "X"
+ }
+};
+static const dm_codes codes_1_1_X[2] =
+{
+ {
+ "1", "1", "X"
+ }
+};
+static const dm_codes codes_1_X_X[2] =
+{
+ {
+ "1", "X", "X"
+ }
+};
+static const dm_codes codes_1_X_X_or_4_4_4[2] =
+{
+ {
+ "1", "X", "X"
+ },
+ {
+ "4", "4", "4"
+ }
+};
+static const dm_codes codes_2_43_43[2] =
+{
+ {
+ "2", "43", "43"
+ }
+};
+static const dm_codes codes_2_4_4[2] =
+{
+ {
+ "2", "4", "4"
+ }
+};
+static const dm_codes codes_3_3_3[2] =
+{
+ {
+ "3", "3", "3"
+ }
+};
+static const dm_codes codes_3_3_3_or_4_4_4[2] =
+{
+ {
+ "3", "3", "3"
+ },
+ {
+ "4", "4", "4"
+ }
+};
+static const dm_codes codes_4_4_4[2] =
+{
+ {
+ "4", "4", "4"
+ }
+};
+static const dm_codes codes_5_54_54[2] =
+{
+ {
+ "5", "54", "54"
+ }
+};
+static const dm_codes codes_5_5_5[2] =
+{
+ {
+ "5", "5", "5"
+ }
+};
+static const dm_codes codes_5_5_5_or_45_45_45[2] =
+{
+ {
+ "5", "5", "5"
+ },
+ {
+ "45", "45", "45"
+ }
+};
+static const dm_codes codes_5_5_5_or_4_4_4[2] =
+{
+ {
+ "5", "5", "5"
+ },
+ {
+ "4", "4", "4"
+ }
+};
+static const dm_codes codes_5_5_X[2] =
+{
+ {
+ "5", "5", "X"
+ }
+};
+static const dm_codes codes_66_66_66[2] =
+{
+ {
+ "66", "66", "66"
+ }
+};
+static const dm_codes codes_6_6_6[2] =
+{
+ {
+ "6", "6", "6"
+ }
+};
+static const dm_codes codes_7_7_7[2] =
+{
+ {
+ "7", "7", "7"
+ }
+};
+static const dm_codes codes_8_8_8[2] =
+{
+ {
+ "8", "8", "8"
+ }
+};
+static const dm_codes codes_94_94_94_or_4_4_4[2] =
+{
+ {
+ "94", "94", "94"
+ },
+ {
+ "4", "4", "4"
+ }
+};
+static const dm_codes codes_9_9_9[2] =
+{
+ {
+ "9", "9", "9"
+ }
+};
+static const dm_codes codes_X_X_6_or_X_X_X[2] =
+{
+ {
+ "X", "X", "6"
+ },
+ {
+ "X", "X", "X"
+ }
+};
+
+/* Coding for alternative following letters in sequence. */
+static const 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 const dm_letter letter_CH[] =
+{
+ {
+ 'S', NULL, codes_5_54_54
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_CS[] =
+{
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_CZ[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_C[] =
+{
+ {
+ 'H', letter_CH, codes_5_5_5_or_4_4_4
+ },
+ {
+ 'K', NULL, codes_5_5_5_or_45_45_45
+ },
+ {
+ 'S', letter_CS, codes_4_4_4
+ },
+ {
+ 'Z', letter_CZ, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_DR[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_DS[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_DZ[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const 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 const 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 const dm_letter letter_F[] =
+{
+ {
+ 'B', NULL, codes_7_7_7
+ },
+ {
+ '\0'
+ }
+};
+static const 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 const dm_letter letter_K[] =
+{
+ {
+ 'H', NULL, codes_5_5_5
+ },
+ {
+ 'S', NULL, codes_5_54_54
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_M[] =
+{
+ {
+ 'N', NULL, codes_66_66_66
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_N[] =
+{
+ {
+ 'M', NULL, codes_66_66_66
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_O[] =
+{
+ {
+ 'I', NULL, codes_0_1_X
+ },
+ {
+ 'J', NULL, codes_0_1_X
+ },
+ {
+ 'Y', NULL, codes_0_1_X
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_P[] =
+{
+ {
+ 'F', NULL, codes_7_7_7
+ },
+ {
+ 'H', NULL, codes_7_7_7
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_R[] =
+{
+ {
+ 'S', NULL, codes_94_94_94_or_4_4_4
+ },
+ {
+ 'Z', NULL, codes_94_94_94_or_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SCHTC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SCHTSC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SCHTS[] =
+{
+ {
+ 'C', letter_SCHTSC, NULL
+ },
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SCHT[] =
+{
+ {
+ 'C', letter_SCHTC, NULL
+ },
+ {
+ 'S', letter_SCHTS, NULL
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SCH[] =
+{
+ {
+ 'D', NULL, codes_2_43_43
+ },
+ {
+ 'T', letter_SCHT, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SC[] =
+{
+ {
+ 'H', letter_SCH, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SHC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SHTC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SHTS[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SHT[] =
+{
+ {
+ 'C', letter_SHTC, NULL
+ },
+ {
+ 'S', letter_SHTS, NULL
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SH[] =
+{
+ {
+ 'C', letter_SHC, NULL
+ },
+ {
+ 'D', NULL, codes_2_43_43
+ },
+ {
+ 'T', letter_SHT, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_STC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_STR[] =
+{
+ {
+ 'S', NULL, codes_2_4_4
+ },
+ {
+ 'Z', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_STSC[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_STS[] =
+{
+ {
+ 'C', letter_STSC, NULL
+ },
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ST[] =
+{
+ {
+ 'C', letter_STC, NULL
+ },
+ {
+ 'R', letter_STR, NULL
+ },
+ {
+ 'S', letter_STS, NULL
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SZC[] =
+{
+ {
+ 'S', NULL, codes_2_4_4
+ },
+ {
+ 'Z', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_SZ[] =
+{
+ {
+ 'C', letter_SZC, NULL
+ },
+ {
+ 'D', NULL, codes_2_43_43
+ },
+ {
+ 'T', NULL, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static const 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 const dm_letter letter_TC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TR[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TSC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TS[] =
+{
+ {
+ 'C', letter_TSC, NULL
+ },
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TTC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TTSC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TTS[] =
+{
+ {
+ 'C', letter_TTSC, NULL
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TT[] =
+{
+ {
+ 'C', letter_TTC, NULL
+ },
+ {
+ 'S', letter_TTS, codes_4_4_4
+ },
+ {
+ 'Z', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_TZ[] =
+{
+ {
+ 'S', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const 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 const dm_letter letter_U[] =
+{
+ {
+ 'E', NULL, codes_0_1_X
+ },
+ {
+ 'I', NULL, codes_0_1_X
+ },
+ {
+ 'J', NULL, codes_0_1_X
+ },
+ {
+ 'Y', NULL, codes_0_1_X
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ZDZ[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ZD[] =
+{
+ {
+ 'Z', letter_ZDZ, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ZHDZ[] =
+{
+ {
+ 'H', NULL, codes_2_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ZHD[] =
+{
+ {
+ 'Z', letter_ZHDZ, NULL
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ZH[] =
+{
+ {
+ 'D', letter_ZHD, codes_2_43_43
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ZSC[] =
+{
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const dm_letter letter_ZS[] =
+{
+ {
+ 'C', letter_ZSC, NULL
+ },
+ {
+ 'H', NULL, codes_4_4_4
+ },
+ {
+ '\0'
+ }
+};
+static const 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 const dm_letter letter_[] =
+{
+ {
+ 'A', letter_A, codes_0_X_X
+ },
+ {
+ 'B', NULL, codes_7_7_7
+ },
+ {
+ 'C', letter_C, codes_5_5_5_or_4_4_4
+ },
+ {
+ '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_1_X_X_or_4_4_4
+ },
+ {
+ '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_6_or_X_X_X
+ },
+ {
+ 'e', NULL, codes_X_X_6_or_X_X_X
+ },
+ {
+ 't', NULL, codes_3_3_3_or_4_4_4
+ },
+ {
+ '\0'
+ }
+};
diff --git a/contrib/fuzzystrmatch/daitch_mokotoff_header.pl b/contrib/fuzzystrmatch/daitch_mokotoff_header.pl
new file mode 100755
index 0000000..51a40e7
--- /dev/null
+++ b/contrib/fuzzystrmatch/daitch_mokotoff_header.pl
@@ -0,0 +1,219 @@
+#!/usr/bin/perl
+#
+# Generation of types and lookup tables for Daitch-Mokotoff soundex.
+#
+# Copyright (c) 2023, PostgreSQL Global Development Group
+#
+# This module was originally sponsored by Finance Norway /
+# Trafikkforsikringsforeningen, and implemented by Dag Lem <dag@nimrod.no>
+#
+
+use strict;
+use warnings;
+
+die "Usage: $0 OUTPUT_FILE\n" if @ARGV != 1;
+my $output_file = $ARGV[0];
+
+# Open the output file
+open my $OUTPUT, '>', $output_file
+ or die "Could not open output file $output_file: $!\n";
+
+# Parse code table and generate tree for letter transitions.
+my %codes;
+my $table = [ {}, [ [ "", "", "" ] ] ];
+while (<DATA>)
+{
+ chomp;
+ my ($letters, $codes) = split(/\s+/);
+ my @codes = map { [ split(/,/) ] } split(/\|/, $codes);
+
+ my $key = "codes_" . join("_or_", map { join("_", @$_) } @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);
+
+print $OUTPUT <<EOF;
+/*
+ * Constants and lookup tables for Daitch-Mokotoff Soundex
+ *
+ * Copyright (c) 2023, PostgreSQL Global Development Group
+ *
+ * This file is generated by daitch_mokotoff_header.pl
+ */
+
+/* Coding chart table: Soundex codes */
+typedef char dm_code[2 + 1]; /* One or two sequential code digits + NUL */
+typedef dm_code dm_codes[3]; /* Start of name, before a vowel, any other */
+
+/* Coding chart table: Letter in input sequence */
+struct dm_letter
+{
+ char letter; /* Present letter in sequence */
+ const struct dm_letter *letters; /* List of possible successive letters */
+ const dm_codes *codes; /* Code sequence(s) for complete sequence */
+};
+
+typedef struct dm_letter dm_letter;
+
+/* Codes for letter sequence at start of name, before a vowel, and any other. */
+EOF
+
+for my $key (sort keys %codes)
+{
+ print $OUTPUT "static const dm_codes $key\[2\] =\n{\n"
+ . $codes{$key}
+ . "\n};\n";
+}
+
+print $OUTPUT <<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 $OUTPUT "static const dm_letter letter_$letter\[\] =\n{\n";
+ for (@letters)
+ {
+ print $OUTPUT "$_,\n";
+ }
+ print $OUTPUT "\t{\n\t\t'\\0'\n\t}\n";
+ print $OUTPUT "};\n";
+}
+
+hash2code($table, '');
+
+close $OUTPUT;
+
+# Table adapted from https://www.jewishgen.org/InfoFiles/Soundex.html
+#
+# The conversion from the coding chart to the table should be self
+# explanatory, but note the differences stated below.
+#
+# X = NC (not coded)
+#
+# The non-ASCII letters in the coding chart are coded with substitute
+# lowercase ASCII letters, which sort after the uppercase ASCII letters:
+#
+# Ą => a (use '[' for table lookup)
+# Ę => e (use '\\' for table lookup)
+# Ţ => t (use ']' for table lookup)
+#
+# The rule for "UE" does not correspond to the coding chart, however
+# it is used by all other known implementations, including the one at
+# https://www.jewishgen.org/jos/jossound.htm (try e.g. "bouey").
+#
+# Note that the implementation assumes that vowels are assigned code
+# 0 or 1. "J" can be either a vowel or a consonant.
+#
+
+__DATA__
+AI,AJ,AY 0,1,X
+AU 0,7,X
+a X,X,6|X,X,X
+A 0,X,X
+B 7,7,7
+CHS 5,54,54
+CH 5,5,5|4,4,4
+CK 5,5,5|45,45,45
+CZ,CS,CSZ,CZS 4,4,4
+C 5,5,5|4,4,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,X,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,X,X|4,4,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,94,94|4,4,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,3,3|4,4,4
+T 3,3,3
+UI,UJ,UY,UE 0,1,X
+U 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/dmetaphone.c b/contrib/fuzzystrmatch/dmetaphone.c
new file mode 100644
index 0000000..f8f2c2b
--- /dev/null
+++ b/contrib/fuzzystrmatch/dmetaphone.c
@@ -0,0 +1,1438 @@
+/*
+ * This is a port of the Double Metaphone algorithm for use in PostgreSQL.
+ *
+ * contrib/fuzzystrmatch/dmetaphone.c
+ *
+ * Double Metaphone computes 2 "sounds like" strings - a primary and an
+ * alternate. In most cases they are the same, but for foreign names
+ * especially they can be a bit different, depending on pronunciation.
+ *
+ * Information on using Double Metaphone can be found at
+ * http://www.codeproject.com/string/dmetaphone1.asp
+ * and the original article describing it can be found at
+ * http://drdobbs.com/184401251
+ *
+ * For PostgreSQL we provide 2 functions - one for the primary and one for
+ * the alternate. That way the functions are pure text->text mappings that
+ * are useful in functional indexes. These are 'dmetaphone' for the
+ * primary and 'dmetaphone_alt' for the alternate.
+ *
+ * Assuming that dmetaphone.so is in $libdir, the SQL to set up the
+ * functions looks like this:
+ *
+ * CREATE FUNCTION dmetaphone (text) RETURNS text
+ * LANGUAGE C IMMUTABLE STRICT
+ * AS '$libdir/dmetaphone', 'dmetaphone';
+ *
+ * CREATE FUNCTION dmetaphone_alt (text) RETURNS text
+ * LANGUAGE C IMMUTABLE STRICT
+ * AS '$libdir/dmetaphone', 'dmetaphone_alt';
+ *
+ * Note that you have to declare the functions IMMUTABLE if you want to
+ * use them in functional indexes, and you have to declare them as STRICT
+ * as they do not check for NULL input, and will segfault if given NULL input.
+ * (See below for alternative ) Declaring them as STRICT means PostgreSQL
+ * will never call them with NULL, but instead assume the result is NULL,
+ * which is what we (I) want.
+ *
+ * Alternatively, compile with -DDMETAPHONE_NOSTRICT and the functions
+ * will detect NULL input and return NULL. The you don't have to declare them
+ * as STRICT.
+ *
+ * There is a small inefficiency here - each function call actually computes
+ * both the primary and the alternate and then throws away the one it doesn't
+ * need. That's the way the perl module was written, because perl can handle
+ * a list return more easily than we can in PostgreSQL. The result has been
+ * fast enough for my needs, but it could maybe be optimized a bit to remove
+ * that behaviour.
+ *
+ */
+
+
+/***************************** COPYRIGHT NOTICES ***********************
+
+Most of this code is directly from the Text::DoubleMetaphone perl module
+version 0.05 available from https://www.cpan.org/.
+It bears this copyright notice:
+
+
+ Copyright 2000, Maurice Aubrey <maurice@hevanet.com>.
+ All rights reserved.
+
+ This code is based heavily on the C++ implementation by
+ Lawrence Philips and incorporates several bug fixes courtesy
+ of Kevin Atkinson <kevina@users.sourceforge.net>.
+
+ This module is free software; you may redistribute it and/or
+ modify it under the same terms as Perl itself.
+
+The remaining code is authored by Andrew Dunstan <amdunstan@ncshp.org> and
+<andrew@dunslane.net> and is covered this copyright:
+
+ Copyright 2003, North Carolina State Highway Patrol.
+ All rights reserved.
+
+ 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 NORTH CAROLINA STATE HIGHWAY PATROL 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 NORTH CAROLINA STATE HIGHWAY PATROL HAS BEEN
+ ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+ THE NORTH CAROLINA STATE HIGHWAY PATROL SPECIFICALLY DISCLAIMS 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 NORTH CAROLINA STATE HIGHWAY PATROL
+ HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
+ MODIFICATIONS.
+
+***********************************************************************/
+
+
+/* include these first, according to the docs */
+#ifndef DMETAPHONE_MAIN
+
+#include "postgres.h"
+
+#include "utils/builtins.h"
+
+/* turn off assertions for embedded function */
+#define NDEBUG
+
+#else /* DMETAPHONE_MAIN */
+
+/* we need these if we didn't get them from postgres.h */
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+
+#endif /* DMETAPHONE_MAIN */
+
+#include <assert.h>
+#include <ctype.h>
+
+/* prototype for the main function we got from the perl module */
+static void DoubleMetaphone(char *str, char **codes);
+
+#ifndef DMETAPHONE_MAIN
+
+/*
+ * The PostgreSQL visible dmetaphone function.
+ */
+
+PG_FUNCTION_INFO_V1(dmetaphone);
+
+Datum
+dmetaphone(PG_FUNCTION_ARGS)
+{
+ text *arg;
+ char *aptr,
+ *codes[2],
+ *code;
+
+#ifdef DMETAPHONE_NOSTRICT
+ if (PG_ARGISNULL(0))
+ PG_RETURN_NULL();
+#endif
+ arg = PG_GETARG_TEXT_PP(0);
+ aptr = text_to_cstring(arg);
+
+ DoubleMetaphone(aptr, codes);
+ code = codes[0];
+ if (!code)
+ code = "";
+
+ PG_RETURN_TEXT_P(cstring_to_text(code));
+}
+
+/*
+ * The PostgreSQL visible dmetaphone_alt function.
+ */
+
+PG_FUNCTION_INFO_V1(dmetaphone_alt);
+
+Datum
+dmetaphone_alt(PG_FUNCTION_ARGS)
+{
+ text *arg;
+ char *aptr,
+ *codes[2],
+ *code;
+
+#ifdef DMETAPHONE_NOSTRICT
+ if (PG_ARGISNULL(0))
+ PG_RETURN_NULL();
+#endif
+ arg = PG_GETARG_TEXT_PP(0);
+ aptr = text_to_cstring(arg);
+
+ DoubleMetaphone(aptr, codes);
+ code = codes[1];
+ if (!code)
+ code = "";
+
+ PG_RETURN_TEXT_P(cstring_to_text(code));
+}
+
+
+/* here is where we start the code imported from the perl module */
+
+/* all memory handling is done with these macros */
+
+#define META_MALLOC(v,n,t) \
+ (v = (t*)palloc(((n)*sizeof(t))))
+
+#define META_REALLOC(v,n,t) \
+ (v = (t*)repalloc((v),((n)*sizeof(t))))
+
+/*
+ * Don't do pfree - it seems to cause a SIGSEGV sometimes - which might have just
+ * been caused by reloading the module in development.
+ * So we rely on context cleanup - Tom Lane says pfree shouldn't be necessary
+ * in a case like this.
+ */
+
+#define META_FREE(x) ((void)true) /* pfree((x)) */
+#else /* not defined DMETAPHONE_MAIN */
+
+/* use the standard malloc library when not running in PostgreSQL */
+
+#define META_MALLOC(v,n,t) \
+ (v = (t*)malloc(((n)*sizeof(t))))
+
+#define META_REALLOC(v,n,t) \
+ (v = (t*)realloc((v),((n)*sizeof(t))))
+
+#define META_FREE(x) free((x))
+#endif /* defined DMETAPHONE_MAIN */
+
+
+
+/* this typedef was originally in the perl module's .h file */
+
+typedef struct
+{
+ char *str;
+ int length;
+ int bufsize;
+ int free_string_on_destroy;
+}
+
+metastring;
+
+/*
+ * remaining perl module funcs unchanged except for declaring them static
+ * and reformatting to PostgreSQL indentation and to fit in 80 cols.
+ *
+ */
+
+static metastring *
+NewMetaString(const char *init_str)
+{
+ metastring *s;
+ char empty_string[] = "";
+
+ META_MALLOC(s, 1, metastring);
+ assert(s != NULL);
+
+ if (init_str == NULL)
+ init_str = empty_string;
+ s->length = strlen(init_str);
+ /* preallocate a bit more for potential growth */
+ s->bufsize = s->length + 7;
+
+ META_MALLOC(s->str, s->bufsize, char);
+ assert(s->str != NULL);
+
+ memcpy(s->str, init_str, s->length + 1);
+ s->free_string_on_destroy = 1;
+
+ return s;
+}
+
+
+static void
+DestroyMetaString(metastring *s)
+{
+ if (s == NULL)
+ return;
+
+ if (s->free_string_on_destroy && (s->str != NULL))
+ META_FREE(s->str);
+
+ META_FREE(s);
+}
+
+
+static void
+IncreaseBuffer(metastring *s, int chars_needed)
+{
+ META_REALLOC(s->str, (s->bufsize + chars_needed + 10), char);
+ assert(s->str != NULL);
+ s->bufsize = s->bufsize + chars_needed + 10;
+}
+
+
+static void
+MakeUpper(metastring *s)
+{
+ char *i;
+
+ for (i = s->str; *i; i++)
+ *i = toupper((unsigned char) *i);
+}
+
+
+static int
+IsVowel(metastring *s, int pos)
+{
+ char c;
+
+ if ((pos < 0) || (pos >= s->length))
+ return 0;
+
+ c = *(s->str + pos);
+ if ((c == 'A') || (c == 'E') || (c == 'I') || (c == 'O') ||
+ (c == 'U') || (c == 'Y'))
+ return 1;
+
+ return 0;
+}
+
+
+static int
+SlavoGermanic(metastring *s)
+{
+ if ((char *) strstr(s->str, "W"))
+ return 1;
+ else if ((char *) strstr(s->str, "K"))
+ return 1;
+ else if ((char *) strstr(s->str, "CZ"))
+ return 1;
+ else if ((char *) strstr(s->str, "WITZ"))
+ return 1;
+ else
+ return 0;
+}
+
+
+static char
+GetAt(metastring *s, int pos)
+{
+ if ((pos < 0) || (pos >= s->length))
+ return '\0';
+
+ return ((char) *(s->str + pos));
+}
+
+
+static void
+SetAt(metastring *s, int pos, char c)
+{
+ if ((pos < 0) || (pos >= s->length))
+ return;
+
+ *(s->str + pos) = c;
+}
+
+
+/*
+ Caveats: the START value is 0 based
+*/
+static int
+StringAt(metastring *s, int start, int length,...)
+{
+ char *test;
+ char *pos;
+ va_list ap;
+
+ if ((start < 0) || (start >= s->length))
+ return 0;
+
+ pos = (s->str + start);
+ va_start(ap, length);
+
+ do
+ {
+ test = va_arg(ap, char *);
+ if (*test && (strncmp(pos, test, length) == 0))
+ {
+ va_end(ap);
+ return 1;
+ }
+ }
+ while (strcmp(test, "") != 0);
+
+ va_end(ap);
+
+ return 0;
+}
+
+
+static void
+MetaphAdd(metastring *s, const char *new_str)
+{
+ int add_length;
+
+ if (new_str == NULL)
+ return;
+
+ add_length = strlen(new_str);
+ if ((s->length + add_length) > (s->bufsize - 1))
+ IncreaseBuffer(s, add_length);
+
+ strcat(s->str, new_str);
+ s->length += add_length;
+}
+
+
+static void
+DoubleMetaphone(char *str, char **codes)
+{
+ int length;
+ metastring *original;
+ metastring *primary;
+ metastring *secondary;
+ int current;
+ int last;
+
+ current = 0;
+ /* we need the real length and last prior to padding */
+ length = strlen(str);
+ last = length - 1;
+ original = NewMetaString(str);
+ /* Pad original so we can index beyond end */
+ MetaphAdd(original, " ");
+
+ primary = NewMetaString("");
+ secondary = NewMetaString("");
+ primary->free_string_on_destroy = 0;
+ secondary->free_string_on_destroy = 0;
+
+ MakeUpper(original);
+
+ /* skip these when at start of word */
+ if (StringAt(original, 0, 2, "GN", "KN", "PN", "WR", "PS", ""))
+ current += 1;
+
+ /* Initial 'X' is pronounced 'Z' e.g. 'Xavier' */
+ if (GetAt(original, 0) == 'X')
+ {
+ MetaphAdd(primary, "S"); /* 'Z' maps to 'S' */
+ MetaphAdd(secondary, "S");
+ current += 1;
+ }
+
+ /* main loop */
+ while ((primary->length < 4) || (secondary->length < 4))
+ {
+ if (current >= length)
+ break;
+
+ switch (GetAt(original, current))
+ {
+ case 'A':
+ case 'E':
+ case 'I':
+ case 'O':
+ case 'U':
+ case 'Y':
+ if (current == 0)
+ {
+ /* all init vowels now map to 'A' */
+ MetaphAdd(primary, "A");
+ MetaphAdd(secondary, "A");
+ }
+ current += 1;
+ break;
+
+ case 'B':
+
+ /* "-mb", e.g", "dumb", already skipped over... */
+ MetaphAdd(primary, "P");
+ MetaphAdd(secondary, "P");
+
+ if (GetAt(original, current + 1) == 'B')
+ current += 2;
+ else
+ current += 1;
+ break;
+
+ case '\xc7': /* C with cedilla */
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ current += 1;
+ break;
+
+ case 'C':
+ /* various germanic */
+ if ((current > 1)
+ && !IsVowel(original, current - 2)
+ && StringAt(original, (current - 1), 3, "ACH", "")
+ && ((GetAt(original, current + 2) != 'I')
+ && ((GetAt(original, current + 2) != 'E')
+ || StringAt(original, (current - 2), 6, "BACHER",
+ "MACHER", ""))))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ current += 2;
+ break;
+ }
+
+ /* special case 'caesar' */
+ if ((current == 0)
+ && StringAt(original, current, 6, "CAESAR", ""))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ current += 2;
+ break;
+ }
+
+ /* italian 'chianti' */
+ if (StringAt(original, current, 4, "CHIA", ""))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ current += 2;
+ break;
+ }
+
+ if (StringAt(original, current, 2, "CH", ""))
+ {
+ /* find 'michael' */
+ if ((current > 0)
+ && StringAt(original, current, 4, "CHAE", ""))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "X");
+ current += 2;
+ break;
+ }
+
+ /* greek roots e.g. 'chemistry', 'chorus' */
+ if ((current == 0)
+ && (StringAt(original, (current + 1), 5,
+ "HARAC", "HARIS", "")
+ || StringAt(original, (current + 1), 3, "HOR",
+ "HYM", "HIA", "HEM", ""))
+ && !StringAt(original, 0, 5, "CHORE", ""))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ current += 2;
+ break;
+ }
+
+ /* germanic, greek, or otherwise 'ch' for 'kh' sound */
+ if ((StringAt(original, 0, 4, "VAN ", "VON ", "")
+ || StringAt(original, 0, 3, "SCH", ""))
+ /* 'architect but not 'arch', 'orchestra', 'orchid' */
+ || StringAt(original, (current - 2), 6, "ORCHES",
+ "ARCHIT", "ORCHID", "")
+ || StringAt(original, (current + 2), 1, "T", "S",
+ "")
+ || ((StringAt(original, (current - 1), 1,
+ "A", "O", "U", "E", "")
+ || (current == 0))
+
+ /*
+ * e.g., 'wachtler', 'wechsler', but not 'tichner'
+ */
+ && StringAt(original, (current + 2), 1, "L", "R",
+ "N", "M", "B", "H", "F", "V", "W",
+ " ", "")))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ }
+ else
+ {
+ if (current > 0)
+ {
+ if (StringAt(original, 0, 2, "MC", ""))
+ {
+ /* e.g., "McHugh" */
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ }
+ else
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "K");
+ }
+ }
+ else
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "X");
+ }
+ }
+ current += 2;
+ break;
+ }
+ /* e.g, 'czerny' */
+ if (StringAt(original, current, 2, "CZ", "")
+ && !StringAt(original, (current - 2), 4, "WICZ", ""))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "X");
+ current += 2;
+ break;
+ }
+
+ /* e.g., 'focaccia' */
+ if (StringAt(original, (current + 1), 3, "CIA", ""))
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "X");
+ current += 3;
+ break;
+ }
+
+ /* double 'C', but not if e.g. 'McClellan' */
+ if (StringAt(original, current, 2, "CC", "")
+ && !((current == 1) && (GetAt(original, 0) == 'M')))
+ {
+ /* 'bellocchio' but not 'bacchus' */
+ if (StringAt(original, (current + 2), 1, "I", "E", "H", "")
+ && !StringAt(original, (current + 2), 2, "HU", ""))
+ {
+ /* 'accident', 'accede' 'succeed' */
+ if (((current == 1)
+ && (GetAt(original, current - 1) == 'A'))
+ || StringAt(original, (current - 1), 5, "UCCEE",
+ "UCCES", ""))
+ {
+ MetaphAdd(primary, "KS");
+ MetaphAdd(secondary, "KS");
+ /* 'bacci', 'bertucci', other italian */
+ }
+ else
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "X");
+ }
+ current += 3;
+ break;
+ }
+ else
+ { /* Pierce's rule */
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ current += 2;
+ break;
+ }
+ }
+
+ if (StringAt(original, current, 2, "CK", "CG", "CQ", ""))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ current += 2;
+ break;
+ }
+
+ if (StringAt(original, current, 2, "CI", "CE", "CY", ""))
+ {
+ /* italian vs. english */
+ if (StringAt
+ (original, current, 3, "CIO", "CIE", "CIA", ""))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "X");
+ }
+ else
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ }
+ current += 2;
+ break;
+ }
+
+ /* else */
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+
+ /* name sent in 'mac caffrey', 'mac gregor */
+ if (StringAt(original, (current + 1), 2, " C", " Q", " G", ""))
+ current += 3;
+ else if (StringAt(original, (current + 1), 1, "C", "K", "Q", "")
+ && !StringAt(original, (current + 1), 2,
+ "CE", "CI", ""))
+ current += 2;
+ else
+ current += 1;
+ break;
+
+ case 'D':
+ if (StringAt(original, current, 2, "DG", ""))
+ {
+ if (StringAt(original, (current + 2), 1,
+ "I", "E", "Y", ""))
+ {
+ /* e.g. 'edge' */
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "J");
+ current += 3;
+ break;
+ }
+ else
+ {
+ /* e.g. 'edgar' */
+ MetaphAdd(primary, "TK");
+ MetaphAdd(secondary, "TK");
+ current += 2;
+ break;
+ }
+ }
+
+ if (StringAt(original, current, 2, "DT", "DD", ""))
+ {
+ MetaphAdd(primary, "T");
+ MetaphAdd(secondary, "T");
+ current += 2;
+ break;
+ }
+
+ /* else */
+ MetaphAdd(primary, "T");
+ MetaphAdd(secondary, "T");
+ current += 1;
+ break;
+
+ case 'F':
+ if (GetAt(original, current + 1) == 'F')
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "F");
+ MetaphAdd(secondary, "F");
+ break;
+
+ case 'G':
+ if (GetAt(original, current + 1) == 'H')
+ {
+ if ((current > 0) && !IsVowel(original, current - 1))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ current += 2;
+ break;
+ }
+
+ if (current < 3)
+ {
+ /* 'ghislane', ghiradelli */
+ if (current == 0)
+ {
+ if (GetAt(original, current + 2) == 'I')
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "J");
+ }
+ else
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ }
+ current += 2;
+ break;
+ }
+ }
+
+ /*
+ * Parker's rule (with some further refinements) - e.g.,
+ * 'hugh'
+ */
+ if (((current > 1)
+ && StringAt(original, (current - 2), 1,
+ "B", "H", "D", ""))
+ /* e.g., 'bough' */
+ || ((current > 2)
+ && StringAt(original, (current - 3), 1,
+ "B", "H", "D", ""))
+ /* e.g., 'broughton' */
+ || ((current > 3)
+ && StringAt(original, (current - 4), 1,
+ "B", "H", "")))
+ {
+ current += 2;
+ break;
+ }
+ else
+ {
+ /*
+ * e.g., 'laugh', 'McLaughlin', 'cough', 'gough',
+ * 'rough', 'tough'
+ */
+ if ((current > 2)
+ && (GetAt(original, current - 1) == 'U')
+ && StringAt(original, (current - 3), 1, "C",
+ "G", "L", "R", "T", ""))
+ {
+ MetaphAdd(primary, "F");
+ MetaphAdd(secondary, "F");
+ }
+ else if ((current > 0)
+ && GetAt(original, current - 1) != 'I')
+ {
+
+
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ }
+
+ current += 2;
+ break;
+ }
+ }
+
+ if (GetAt(original, current + 1) == 'N')
+ {
+ if ((current == 1) && IsVowel(original, 0)
+ && !SlavoGermanic(original))
+ {
+ MetaphAdd(primary, "KN");
+ MetaphAdd(secondary, "N");
+ }
+ else
+ /* not e.g. 'cagney' */
+ if (!StringAt(original, (current + 2), 2, "EY", "")
+ && (GetAt(original, current + 1) != 'Y')
+ && !SlavoGermanic(original))
+ {
+ MetaphAdd(primary, "N");
+ MetaphAdd(secondary, "KN");
+ }
+ else
+ {
+ MetaphAdd(primary, "KN");
+ MetaphAdd(secondary, "KN");
+ }
+ current += 2;
+ break;
+ }
+
+ /* 'tagliaro' */
+ if (StringAt(original, (current + 1), 2, "LI", "")
+ && !SlavoGermanic(original))
+ {
+ MetaphAdd(primary, "KL");
+ MetaphAdd(secondary, "L");
+ current += 2;
+ break;
+ }
+
+ /* -ges-,-gep-,-gel-, -gie- at beginning */
+ if ((current == 0)
+ && ((GetAt(original, current + 1) == 'Y')
+ || StringAt(original, (current + 1), 2, "ES", "EP",
+ "EB", "EL", "EY", "IB", "IL", "IN", "IE",
+ "EI", "ER", "")))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "J");
+ current += 2;
+ break;
+ }
+
+ /* -ger-, -gy- */
+ if ((StringAt(original, (current + 1), 2, "ER", "")
+ || (GetAt(original, current + 1) == 'Y'))
+ && !StringAt(original, 0, 6,
+ "DANGER", "RANGER", "MANGER", "")
+ && !StringAt(original, (current - 1), 1, "E", "I", "")
+ && !StringAt(original, (current - 1), 3, "RGY", "OGY", ""))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "J");
+ current += 2;
+ break;
+ }
+
+ /* italian e.g, 'biaggi' */
+ if (StringAt(original, (current + 1), 1, "E", "I", "Y", "")
+ || StringAt(original, (current - 1), 4,
+ "AGGI", "OGGI", ""))
+ {
+ /* obvious germanic */
+ if ((StringAt(original, 0, 4, "VAN ", "VON ", "")
+ || StringAt(original, 0, 3, "SCH", ""))
+ || StringAt(original, (current + 1), 2, "ET", ""))
+ {
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ }
+ else
+ {
+ /* always soft if french ending */
+ if (StringAt
+ (original, (current + 1), 4, "IER ", ""))
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "J");
+ }
+ else
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "K");
+ }
+ }
+ current += 2;
+ break;
+ }
+
+ if (GetAt(original, current + 1) == 'G')
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ break;
+
+ case 'H':
+ /* only keep if first & before vowel or btw. 2 vowels */
+ if (((current == 0) || IsVowel(original, current - 1))
+ && IsVowel(original, current + 1))
+ {
+ MetaphAdd(primary, "H");
+ MetaphAdd(secondary, "H");
+ current += 2;
+ }
+ else
+ /* also takes care of 'HH' */
+ current += 1;
+ break;
+
+ case 'J':
+ /* obvious spanish, 'jose', 'san jacinto' */
+ if (StringAt(original, current, 4, "JOSE", "")
+ || StringAt(original, 0, 4, "SAN ", ""))
+ {
+ if (((current == 0)
+ && (GetAt(original, current + 4) == ' '))
+ || StringAt(original, 0, 4, "SAN ", ""))
+ {
+ MetaphAdd(primary, "H");
+ MetaphAdd(secondary, "H");
+ }
+ else
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "H");
+ }
+ current += 1;
+ break;
+ }
+
+ if ((current == 0)
+ && !StringAt(original, current, 4, "JOSE", ""))
+ {
+ MetaphAdd(primary, "J"); /* Yankelovich/Jankelowicz */
+ MetaphAdd(secondary, "A");
+ }
+ else
+ {
+ /* spanish pron. of e.g. 'bajador' */
+ if (IsVowel(original, current - 1)
+ && !SlavoGermanic(original)
+ && ((GetAt(original, current + 1) == 'A')
+ || (GetAt(original, current + 1) == 'O')))
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "H");
+ }
+ else
+ {
+ if (current == last)
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "");
+ }
+ else
+ {
+ if (!StringAt(original, (current + 1), 1, "L", "T",
+ "K", "S", "N", "M", "B", "Z", "")
+ && !StringAt(original, (current - 1), 1,
+ "S", "K", "L", ""))
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "J");
+ }
+ }
+ }
+ }
+
+ if (GetAt(original, current + 1) == 'J') /* it could happen! */
+ current += 2;
+ else
+ current += 1;
+ break;
+
+ case 'K':
+ if (GetAt(original, current + 1) == 'K')
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ break;
+
+ case 'L':
+ if (GetAt(original, current + 1) == 'L')
+ {
+ /* spanish e.g. 'cabrillo', 'gallegos' */
+ if (((current == (length - 3))
+ && StringAt(original, (current - 1), 4, "ILLO",
+ "ILLA", "ALLE", ""))
+ || ((StringAt(original, (last - 1), 2, "AS", "OS", "")
+ || StringAt(original, last, 1, "A", "O", ""))
+ && StringAt(original, (current - 1), 4,
+ "ALLE", "")))
+ {
+ MetaphAdd(primary, "L");
+ MetaphAdd(secondary, "");
+ current += 2;
+ break;
+ }
+ current += 2;
+ }
+ else
+ current += 1;
+ MetaphAdd(primary, "L");
+ MetaphAdd(secondary, "L");
+ break;
+
+ case 'M':
+ if ((StringAt(original, (current - 1), 3, "UMB", "")
+ && (((current + 1) == last)
+ || StringAt(original, (current + 2), 2, "ER", "")))
+ /* 'dumb','thumb' */
+ || (GetAt(original, current + 1) == 'M'))
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "M");
+ MetaphAdd(secondary, "M");
+ break;
+
+ case 'N':
+ if (GetAt(original, current + 1) == 'N')
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "N");
+ MetaphAdd(secondary, "N");
+ break;
+
+ case '\xd1': /* N with tilde */
+ current += 1;
+ MetaphAdd(primary, "N");
+ MetaphAdd(secondary, "N");
+ break;
+
+ case 'P':
+ if (GetAt(original, current + 1) == 'H')
+ {
+ MetaphAdd(primary, "F");
+ MetaphAdd(secondary, "F");
+ current += 2;
+ break;
+ }
+
+ /* also account for "campbell", "raspberry" */
+ if (StringAt(original, (current + 1), 1, "P", "B", ""))
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "P");
+ MetaphAdd(secondary, "P");
+ break;
+
+ case 'Q':
+ if (GetAt(original, current + 1) == 'Q')
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "K");
+ MetaphAdd(secondary, "K");
+ break;
+
+ case 'R':
+ /* french e.g. 'rogier', but exclude 'hochmeier' */
+ if ((current == last)
+ && !SlavoGermanic(original)
+ && StringAt(original, (current - 2), 2, "IE", "")
+ && !StringAt(original, (current - 4), 2, "ME", "MA", ""))
+ {
+ MetaphAdd(primary, "");
+ MetaphAdd(secondary, "R");
+ }
+ else
+ {
+ MetaphAdd(primary, "R");
+ MetaphAdd(secondary, "R");
+ }
+
+ if (GetAt(original, current + 1) == 'R')
+ current += 2;
+ else
+ current += 1;
+ break;
+
+ case 'S':
+ /* special cases 'island', 'isle', 'carlisle', 'carlysle' */
+ if (StringAt(original, (current - 1), 3, "ISL", "YSL", ""))
+ {
+ current += 1;
+ break;
+ }
+
+ /* special case 'sugar-' */
+ if ((current == 0)
+ && StringAt(original, current, 5, "SUGAR", ""))
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "S");
+ current += 1;
+ break;
+ }
+
+ if (StringAt(original, current, 2, "SH", ""))
+ {
+ /* germanic */
+ if (StringAt
+ (original, (current + 1), 4, "HEIM", "HOEK", "HOLM",
+ "HOLZ", ""))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ }
+ else
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "X");
+ }
+ current += 2;
+ break;
+ }
+
+ /* italian & armenian */
+ if (StringAt(original, current, 3, "SIO", "SIA", "")
+ || StringAt(original, current, 4, "SIAN", ""))
+ {
+ if (!SlavoGermanic(original))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "X");
+ }
+ else
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ }
+ current += 3;
+ break;
+ }
+
+ /*
+ * german & anglicisations, e.g. 'smith' match 'schmidt',
+ * 'snider' match 'schneider' also, -sz- in slavic language
+ * although in hungarian it is pronounced 's'
+ */
+ if (((current == 0)
+ && StringAt(original, (current + 1), 1,
+ "M", "N", "L", "W", ""))
+ || StringAt(original, (current + 1), 1, "Z", ""))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "X");
+ if (StringAt(original, (current + 1), 1, "Z", ""))
+ current += 2;
+ else
+ current += 1;
+ break;
+ }
+
+ if (StringAt(original, current, 2, "SC", ""))
+ {
+ /* Schlesinger's rule */
+ if (GetAt(original, current + 2) == 'H')
+ {
+ /* dutch origin, e.g. 'school', 'schooner' */
+ if (StringAt(original, (current + 3), 2,
+ "OO", "ER", "EN",
+ "UY", "ED", "EM", ""))
+ {
+ /* 'schermerhorn', 'schenker' */
+ if (StringAt(original, (current + 3), 2,
+ "ER", "EN", ""))
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "SK");
+ }
+ else
+ {
+ MetaphAdd(primary, "SK");
+ MetaphAdd(secondary, "SK");
+ }
+ current += 3;
+ break;
+ }
+ else
+ {
+ if ((current == 0) && !IsVowel(original, 3)
+ && (GetAt(original, 3) != 'W'))
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "S");
+ }
+ else
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "X");
+ }
+ current += 3;
+ break;
+ }
+ }
+
+ if (StringAt(original, (current + 2), 1,
+ "I", "E", "Y", ""))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ current += 3;
+ break;
+ }
+ /* else */
+ MetaphAdd(primary, "SK");
+ MetaphAdd(secondary, "SK");
+ current += 3;
+ break;
+ }
+
+ /* french e.g. 'resnais', 'artois' */
+ if ((current == last)
+ && StringAt(original, (current - 2), 2, "AI", "OI", ""))
+ {
+ MetaphAdd(primary, "");
+ MetaphAdd(secondary, "S");
+ }
+ else
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ }
+
+ if (StringAt(original, (current + 1), 1, "S", "Z", ""))
+ current += 2;
+ else
+ current += 1;
+ break;
+
+ case 'T':
+ if (StringAt(original, current, 4, "TION", ""))
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "X");
+ current += 3;
+ break;
+ }
+
+ if (StringAt(original, current, 3, "TIA", "TCH", ""))
+ {
+ MetaphAdd(primary, "X");
+ MetaphAdd(secondary, "X");
+ current += 3;
+ break;
+ }
+
+ if (StringAt(original, current, 2, "TH", "")
+ || StringAt(original, current, 3, "TTH", ""))
+ {
+ /* special case 'thomas', 'thames' or germanic */
+ if (StringAt(original, (current + 2), 2, "OM", "AM", "")
+ || StringAt(original, 0, 4, "VAN ", "VON ", "")
+ || StringAt(original, 0, 3, "SCH", ""))
+ {
+ MetaphAdd(primary, "T");
+ MetaphAdd(secondary, "T");
+ }
+ else
+ {
+ MetaphAdd(primary, "0");
+ MetaphAdd(secondary, "T");
+ }
+ current += 2;
+ break;
+ }
+
+ if (StringAt(original, (current + 1), 1, "T", "D", ""))
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "T");
+ MetaphAdd(secondary, "T");
+ break;
+
+ case 'V':
+ if (GetAt(original, current + 1) == 'V')
+ current += 2;
+ else
+ current += 1;
+ MetaphAdd(primary, "F");
+ MetaphAdd(secondary, "F");
+ break;
+
+ case 'W':
+ /* can also be in middle of word */
+ if (StringAt(original, current, 2, "WR", ""))
+ {
+ MetaphAdd(primary, "R");
+ MetaphAdd(secondary, "R");
+ current += 2;
+ break;
+ }
+
+ if ((current == 0)
+ && (IsVowel(original, current + 1)
+ || StringAt(original, current, 2, "WH", "")))
+ {
+ /* Wasserman should match Vasserman */
+ if (IsVowel(original, current + 1))
+ {
+ MetaphAdd(primary, "A");
+ MetaphAdd(secondary, "F");
+ }
+ else
+ {
+ /* need Uomo to match Womo */
+ MetaphAdd(primary, "A");
+ MetaphAdd(secondary, "A");
+ }
+ }
+
+ /* Arnow should match Arnoff */
+ if (((current == last) && IsVowel(original, current - 1))
+ || StringAt(original, (current - 1), 5, "EWSKI", "EWSKY",
+ "OWSKI", "OWSKY", "")
+ || StringAt(original, 0, 3, "SCH", ""))
+ {
+ MetaphAdd(primary, "");
+ MetaphAdd(secondary, "F");
+ current += 1;
+ break;
+ }
+
+ /* polish e.g. 'filipowicz' */
+ if (StringAt(original, current, 4, "WICZ", "WITZ", ""))
+ {
+ MetaphAdd(primary, "TS");
+ MetaphAdd(secondary, "FX");
+ current += 4;
+ break;
+ }
+
+ /* else skip it */
+ current += 1;
+ break;
+
+ case 'X':
+ /* french e.g. breaux */
+ if (!((current == last)
+ && (StringAt(original, (current - 3), 3,
+ "IAU", "EAU", "")
+ || StringAt(original, (current - 2), 2,
+ "AU", "OU", ""))))
+ {
+ MetaphAdd(primary, "KS");
+ MetaphAdd(secondary, "KS");
+ }
+
+
+ if (StringAt(original, (current + 1), 1, "C", "X", ""))
+ current += 2;
+ else
+ current += 1;
+ break;
+
+ case 'Z':
+ /* chinese pinyin e.g. 'zhao' */
+ if (GetAt(original, current + 1) == 'H')
+ {
+ MetaphAdd(primary, "J");
+ MetaphAdd(secondary, "J");
+ current += 2;
+ break;
+ }
+ else if (StringAt(original, (current + 1), 2,
+ "ZO", "ZI", "ZA", "")
+ || (SlavoGermanic(original)
+ && ((current > 0)
+ && GetAt(original, current - 1) != 'T')))
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "TS");
+ }
+ else
+ {
+ MetaphAdd(primary, "S");
+ MetaphAdd(secondary, "S");
+ }
+
+ if (GetAt(original, current + 1) == 'Z')
+ current += 2;
+ else
+ current += 1;
+ break;
+
+ default:
+ current += 1;
+ }
+
+ /*
+ * printf("PRIMARY: %s\n", primary->str); printf("SECONDARY: %s\n",
+ * secondary->str);
+ */
+ }
+
+
+ if (primary->length > 4)
+ SetAt(primary, 4, '\0');
+
+ if (secondary->length > 4)
+ SetAt(secondary, 4, '\0');
+
+ *codes = primary->str;
+ *++codes = secondary->str;
+
+ DestroyMetaString(original);
+ DestroyMetaString(primary);
+ DestroyMetaString(secondary);
+}
+
+#ifdef DMETAPHONE_MAIN
+
+/* just for testing - not part of the perl code */
+
+main(int argc, char **argv)
+{
+ char *codes[2];
+
+ if (argc > 1)
+ {
+ DoubleMetaphone(argv[1], codes);
+ printf("%s|%s\n", codes[0], codes[1]);
+ }
+}
+
+#endif
diff --git a/contrib/fuzzystrmatch/expected/fuzzystrmatch.out b/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
new file mode 100644
index 0000000..3195e1e
--- /dev/null
+++ b/contrib/fuzzystrmatch/expected/fuzzystrmatch.out
@@ -0,0 +1,244 @@
+CREATE EXTENSION fuzzystrmatch;
+SELECT soundex('hello world!');
+ soundex
+---------
+ H464
+(1 row)
+
+SELECT soundex('Anne'), soundex('Ann'), difference('Anne', 'Ann');
+ soundex | soundex | difference
+---------+---------+------------
+ A500 | A500 | 4
+(1 row)
+
+SELECT soundex('Anne'), soundex('Andrew'), difference('Anne', 'Andrew');
+ soundex | soundex | difference
+---------+---------+------------
+ A500 | A536 | 2
+(1 row)
+
+SELECT soundex('Anne'), soundex('Margaret'), difference('Anne', 'Margaret');
+ soundex | soundex | difference
+---------+---------+------------
+ A500 | M626 | 0
+(1 row)
+
+SELECT soundex(''), difference('', '');
+ soundex | difference
+---------+------------
+ | 4
+(1 row)
+
+SELECT levenshtein('GUMBO', 'GAMBOL');
+ levenshtein
+-------------
+ 2
+(1 row)
+
+SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1);
+ levenshtein
+-------------
+ 3
+(1 row)
+
+SELECT levenshtein_less_equal('extensive', 'exhaustive', 2);
+ levenshtein_less_equal
+------------------------
+ 3
+(1 row)
+
+SELECT levenshtein_less_equal('extensive', 'exhaustive', 4);
+ levenshtein_less_equal
+------------------------
+ 4
+(1 row)
+
+SELECT metaphone('GUMBO', 4);
+ metaphone
+-----------
+ KM
+(1 row)
+
+SELECT dmetaphone('gumbo');
+ dmetaphone
+------------
+ KMP
+(1 row)
+
+SELECT dmetaphone_alt('gumbo');
+ dmetaphone_alt
+----------------
+ 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)
+
+-- 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)
+
+-- Ignored characters
+SELECT daitch_mokotoff('''OBrien');
+ daitch_mokotoff
+-----------------
+ {079600}
+(1 row)
+
+SELECT daitch_mokotoff('O''Brien');
+ daitch_mokotoff
+-----------------
+ {079600}
+(1 row)
+
+-- "Difficult" cases, likely to cause trouble for other implementations.
+SELECT daitch_mokotoff('CJC');
+ daitch_mokotoff
+---------------------------------------------
+ {550000,540000,545000,450000,400000,440000}
+(1 row)
+
+SELECT daitch_mokotoff('BESST');
+ daitch_mokotoff
+-----------------
+ {743000}
+(1 row)
+
+SELECT daitch_mokotoff('BOUEY');
+ daitch_mokotoff
+-----------------
+ {710000}
+(1 row)
+
+SELECT daitch_mokotoff('HANNMANN');
+ daitch_mokotoff
+-----------------
+ {566600}
+(1 row)
+
+SELECT daitch_mokotoff('MCCOYJR');
+ daitch_mokotoff
+-----------------------------------------------------------
+ {651900,654900,654190,654490,645190,645490,641900,644900}
+(1 row)
+
+SELECT daitch_mokotoff('ACCURSO');
+ daitch_mokotoff
+-----------------------------------------------------------
+ {059400,054000,054940,054400,045940,045400,049400,044000}
+(1 row)
+
+SELECT daitch_mokotoff('BIERSCHBACH');
+ daitch_mokotoff
+-----------------------------------------------------------
+ {794575,794574,794750,794740,745750,745740,747500,747400}
+(1 row)
+
diff --git a/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8.out b/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8.out
new file mode 100644
index 0000000..b0dd488
--- /dev/null
+++ b/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8.out
@@ -0,0 +1,61 @@
+/*
+ * This test must be run in a database with UTF-8 encoding,
+ * because other encodings don't support all the characters used.
+ */
+SELECT getdatabaseencoding() <> 'UTF8'
+ AS skip_test \gset
+\if :skip_test
+\quit
+\endif
+set client_encoding = utf8;
+-- CREATE EXTENSION IF NOT EXISTS fuzzystrmatch;
+-- 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)
+
+-- 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)
+
diff --git a/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8_1.out b/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8_1.out
new file mode 100644
index 0000000..37aead8
--- /dev/null
+++ b/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8_1.out
@@ -0,0 +1,8 @@
+/*
+ * This test must be run in a database with UTF-8 encoding,
+ * because other encodings don't support all the characters used.
+ */
+SELECT getdatabaseencoding() <> 'UTF8'
+ AS skip_test \gset
+\if :skip_test
+\quit
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql b/contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql
new file mode 100644
index 0000000..f2b1555
--- /dev/null
+++ b/contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql
@@ -0,0 +1,15 @@
+/* contrib/fuzzystrmatch/fuzzystrmatch--1.0--1.1.sql */
+
+-- complain if script is sourced in psql, rather than via ALTER EXTENSION
+\echo Use "ALTER EXTENSION fuzzystrmatch UPDATE TO '1.1'" to load this file. \quit
+
+ALTER FUNCTION levenshtein(text, text) PARALLEL SAFE;
+ALTER FUNCTION levenshtein(text, text, int, int, int) PARALLEL SAFE;
+ALTER FUNCTION levenshtein_less_equal(text, text, int) PARALLEL SAFE;
+ALTER FUNCTION levenshtein_less_equal(text, text, int, int, int, int) PARALLEL SAFE;
+ALTER FUNCTION metaphone(text, int) PARALLEL SAFE;
+ALTER FUNCTION soundex(text) PARALLEL SAFE;
+ALTER FUNCTION text_soundex(text) PARALLEL SAFE;
+ALTER FUNCTION difference(text, text) PARALLEL SAFE;
+ALTER FUNCTION dmetaphone(text) PARALLEL SAFE;
+ALTER FUNCTION dmetaphone_alt(text) PARALLEL SAFE;
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 0000000..d8542a7
--- /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.1.sql
new file mode 100644
index 0000000..41de9d9
--- /dev/null
+++ b/contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql
@@ -0,0 +1,44 @@
+/* contrib/fuzzystrmatch/fuzzystrmatch--1.1.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION fuzzystrmatch" to load this file. \quit
+
+CREATE FUNCTION levenshtein (text,text) RETURNS int
+AS 'MODULE_PATHNAME','levenshtein'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION levenshtein (text,text,int,int,int) RETURNS int
+AS 'MODULE_PATHNAME','levenshtein_with_costs'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION levenshtein_less_equal (text,text,int) RETURNS int
+AS 'MODULE_PATHNAME','levenshtein_less_equal'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION levenshtein_less_equal (text,text,int,int,int,int) RETURNS int
+AS 'MODULE_PATHNAME','levenshtein_less_equal_with_costs'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION metaphone (text,int) RETURNS text
+AS 'MODULE_PATHNAME','metaphone'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION soundex(text) RETURNS text
+AS 'MODULE_PATHNAME', 'soundex'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION text_soundex(text) RETURNS text
+AS 'MODULE_PATHNAME', 'soundex'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION difference(text,text) RETURNS int
+AS 'MODULE_PATHNAME', 'difference'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION dmetaphone (text) RETURNS text
+AS 'MODULE_PATHNAME', 'dmetaphone'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
+
+CREATE FUNCTION dmetaphone_alt (text) RETURNS text
+AS 'MODULE_PATHNAME', 'dmetaphone_alt'
+LANGUAGE C IMMUTABLE STRICT PARALLEL SAFE;
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.c b/contrib/fuzzystrmatch/fuzzystrmatch.c
new file mode 100644
index 0000000..5686497
--- /dev/null
+++ b/contrib/fuzzystrmatch/fuzzystrmatch.c
@@ -0,0 +1,794 @@
+/*
+ * fuzzystrmatch.c
+ *
+ * Functions for "fuzzy" comparison of strings
+ *
+ * Joe Conway <mail@joeconway.com>
+ *
+ * contrib/fuzzystrmatch/fuzzystrmatch.c
+ * Copyright (c) 2001-2023, PostgreSQL Global Development Group
+ * ALL RIGHTS RESERVED;
+ *
+ * metaphone()
+ * -----------
+ * Modified for PostgreSQL by Joe Conway.
+ * Based on CPAN's "Text-Metaphone-1.96" by Michael G Schwern <schwern@pobox.com>
+ * Code slightly modified for use as PostgreSQL function (palloc, elog, etc).
+ * Metaphone was originally created by Lawrence Philips and presented in article
+ * in "Computer Language" December 1990 issue.
+ *
+ * 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 AUTHORS 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 AUTHORS 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 "postgres.h"
+
+#include <ctype.h>
+
+#include "mb/pg_wchar.h"
+#include "utils/builtins.h"
+#include "utils/varlena.h"
+#include "varatt.h"
+
+PG_MODULE_MAGIC;
+
+/*
+ * Soundex
+ */
+static void _soundex(const char *instr, char *outstr);
+
+#define SOUNDEX_LEN 4
+
+/* ABCDEFGHIJKLMNOPQRSTUVWXYZ */
+static const char *soundex_table = "01230120022455012623010202";
+
+static char
+soundex_code(char letter)
+{
+ letter = toupper((unsigned char) letter);
+ /* Defend against non-ASCII letters */
+ if (letter >= 'A' && letter <= 'Z')
+ return soundex_table[letter - 'A'];
+ return letter;
+}
+
+/*
+ * Metaphone
+ */
+#define MAX_METAPHONE_STRLEN 255
+
+/*
+ * Original code by Michael G Schwern starts here.
+ * Code slightly modified for use as PostgreSQL function.
+ */
+
+
+/**************************************************************************
+ metaphone -- Breaks english phrases down into their phonemes.
+
+ Input
+ word -- An english word to be phonized
+ max_phonemes -- How many phonemes to calculate. If 0, then it
+ will phonize the entire phrase.
+ phoned_word -- The final phonized word. (We'll allocate the
+ memory.)
+ Output
+ error -- A simple error flag, returns true or false
+
+ NOTES: ALL non-alpha characters are ignored, this includes whitespace,
+ although non-alpha characters will break up phonemes.
+****************************************************************************/
+
+
+/* I add modifications to the traditional metaphone algorithm that you
+ might find in books. Define this if you want metaphone to behave
+ traditionally */
+#undef USE_TRADITIONAL_METAPHONE
+
+/* Special encodings */
+#define SH 'X'
+#define TH '0'
+
+static char Lookahead(char *word, int how_far);
+static void _metaphone(char *word, int max_phonemes, char **phoned_word);
+
+/* Metachar.h ... little bits about characters for metaphone */
+
+
+/*-- Character encoding array & accessing macros --*/
+/* Stolen directly out of the book... */
+static const char _codes[26] = {
+ 1, 16, 4, 16, 9, 2, 4, 16, 9, 2, 0, 2, 2, 2, 1, 4, 0, 2, 4, 4, 1, 0, 0, 0, 8, 0
+/* a b c d e f g h i j k l m n o p q r s t u v w x y z */
+};
+
+static int
+getcode(char c)
+{
+ if (isalpha((unsigned char) c))
+ {
+ c = toupper((unsigned char) c);
+ /* Defend against non-ASCII letters */
+ if (c >= 'A' && c <= 'Z')
+ return _codes[c - 'A'];
+ }
+ return 0;
+}
+
+#define isvowel(c) (getcode(c) & 1) /* AEIOU */
+
+/* These letters are passed through unchanged */
+#define NOCHANGE(c) (getcode(c) & 2) /* FJMNR */
+
+/* These form diphthongs when preceding H */
+#define AFFECTH(c) (getcode(c) & 4) /* CGPST */
+
+/* These make C and G soft */
+#define MAKESOFT(c) (getcode(c) & 8) /* EIY */
+
+/* These prevent GH from becoming F */
+#define NOGHTOF(c) (getcode(c) & 16) /* BDH */
+
+PG_FUNCTION_INFO_V1(levenshtein_with_costs);
+Datum
+levenshtein_with_costs(PG_FUNCTION_ARGS)
+{
+ text *src = PG_GETARG_TEXT_PP(0);
+ text *dst = PG_GETARG_TEXT_PP(1);
+ int ins_c = PG_GETARG_INT32(2);
+ int del_c = PG_GETARG_INT32(3);
+ int sub_c = PG_GETARG_INT32(4);
+ const char *s_data;
+ const char *t_data;
+ int s_bytes,
+ t_bytes;
+
+ /* Extract a pointer to the actual character data */
+ s_data = VARDATA_ANY(src);
+ t_data = VARDATA_ANY(dst);
+ /* Determine length of each string in bytes */
+ s_bytes = VARSIZE_ANY_EXHDR(src);
+ t_bytes = VARSIZE_ANY_EXHDR(dst);
+
+ PG_RETURN_INT32(varstr_levenshtein(s_data, s_bytes, t_data, t_bytes,
+ ins_c, del_c, sub_c, false));
+}
+
+
+PG_FUNCTION_INFO_V1(levenshtein);
+Datum
+levenshtein(PG_FUNCTION_ARGS)
+{
+ text *src = PG_GETARG_TEXT_PP(0);
+ text *dst = PG_GETARG_TEXT_PP(1);
+ const char *s_data;
+ const char *t_data;
+ int s_bytes,
+ t_bytes;
+
+ /* Extract a pointer to the actual character data */
+ s_data = VARDATA_ANY(src);
+ t_data = VARDATA_ANY(dst);
+ /* Determine length of each string in bytes */
+ s_bytes = VARSIZE_ANY_EXHDR(src);
+ t_bytes = VARSIZE_ANY_EXHDR(dst);
+
+ PG_RETURN_INT32(varstr_levenshtein(s_data, s_bytes, t_data, t_bytes,
+ 1, 1, 1, false));
+}
+
+
+PG_FUNCTION_INFO_V1(levenshtein_less_equal_with_costs);
+Datum
+levenshtein_less_equal_with_costs(PG_FUNCTION_ARGS)
+{
+ text *src = PG_GETARG_TEXT_PP(0);
+ text *dst = PG_GETARG_TEXT_PP(1);
+ int ins_c = PG_GETARG_INT32(2);
+ int del_c = PG_GETARG_INT32(3);
+ int sub_c = PG_GETARG_INT32(4);
+ int max_d = PG_GETARG_INT32(5);
+ const char *s_data;
+ const char *t_data;
+ int s_bytes,
+ t_bytes;
+
+ /* Extract a pointer to the actual character data */
+ s_data = VARDATA_ANY(src);
+ t_data = VARDATA_ANY(dst);
+ /* Determine length of each string in bytes */
+ s_bytes = VARSIZE_ANY_EXHDR(src);
+ t_bytes = VARSIZE_ANY_EXHDR(dst);
+
+ PG_RETURN_INT32(varstr_levenshtein_less_equal(s_data, s_bytes,
+ t_data, t_bytes,
+ ins_c, del_c, sub_c,
+ max_d, false));
+}
+
+
+PG_FUNCTION_INFO_V1(levenshtein_less_equal);
+Datum
+levenshtein_less_equal(PG_FUNCTION_ARGS)
+{
+ text *src = PG_GETARG_TEXT_PP(0);
+ text *dst = PG_GETARG_TEXT_PP(1);
+ int max_d = PG_GETARG_INT32(2);
+ const char *s_data;
+ const char *t_data;
+ int s_bytes,
+ t_bytes;
+
+ /* Extract a pointer to the actual character data */
+ s_data = VARDATA_ANY(src);
+ t_data = VARDATA_ANY(dst);
+ /* Determine length of each string in bytes */
+ s_bytes = VARSIZE_ANY_EXHDR(src);
+ t_bytes = VARSIZE_ANY_EXHDR(dst);
+
+ PG_RETURN_INT32(varstr_levenshtein_less_equal(s_data, s_bytes,
+ t_data, t_bytes,
+ 1, 1, 1,
+ max_d, false));
+}
+
+
+/*
+ * Calculates the metaphone of an input string.
+ * Returns number of characters requested
+ * (suggested value is 4)
+ */
+PG_FUNCTION_INFO_V1(metaphone);
+Datum
+metaphone(PG_FUNCTION_ARGS)
+{
+ char *str_i = TextDatumGetCString(PG_GETARG_DATUM(0));
+ size_t str_i_len = strlen(str_i);
+ int reqlen;
+ char *metaph;
+
+ /* return an empty string if we receive one */
+ if (!(str_i_len > 0))
+ PG_RETURN_TEXT_P(cstring_to_text(""));
+
+ if (str_i_len > MAX_METAPHONE_STRLEN)
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("argument exceeds the maximum length of %d bytes",
+ MAX_METAPHONE_STRLEN)));
+
+ reqlen = PG_GETARG_INT32(1);
+ if (reqlen > MAX_METAPHONE_STRLEN)
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("output exceeds the maximum length of %d bytes",
+ MAX_METAPHONE_STRLEN)));
+
+ if (!(reqlen > 0))
+ ereport(ERROR,
+ (errcode(ERRCODE_ZERO_LENGTH_CHARACTER_STRING),
+ errmsg("output cannot be empty string")));
+
+ _metaphone(str_i, reqlen, &metaph);
+ PG_RETURN_TEXT_P(cstring_to_text(metaph));
+}
+
+
+/*
+ * Original code by Michael G Schwern starts here.
+ * Code slightly modified for use as PostgreSQL
+ * function (palloc, etc).
+ */
+
+/* I suppose I could have been using a character pointer instead of
+ * accessing the array directly... */
+
+/* Look at the next letter in the word */
+#define Next_Letter (toupper((unsigned char) word[w_idx+1]))
+/* Look at the current letter in the word */
+#define Curr_Letter (toupper((unsigned char) word[w_idx]))
+/* Go N letters back. */
+#define Look_Back_Letter(n) \
+ (w_idx >= (n) ? toupper((unsigned char) word[w_idx-(n)]) : '\0')
+/* Previous letter. I dunno, should this return null on failure? */
+#define Prev_Letter (Look_Back_Letter(1))
+/* Look two letters down. It makes sure you don't walk off the string. */
+#define After_Next_Letter \
+ (Next_Letter != '\0' ? toupper((unsigned char) word[w_idx+2]) : '\0')
+#define Look_Ahead_Letter(n) toupper((unsigned char) Lookahead(word+w_idx, n))
+
+
+/* Allows us to safely look ahead an arbitrary # of letters */
+/* I probably could have just used strlen... */
+static char
+Lookahead(char *word, int how_far)
+{
+ char letter_ahead = '\0'; /* null by default */
+ int idx;
+
+ for (idx = 0; word[idx] != '\0' && idx < how_far; idx++);
+ /* Edge forward in the string... */
+
+ letter_ahead = word[idx]; /* idx will be either == to how_far or at the
+ * end of the string */
+ return letter_ahead;
+}
+
+
+/* phonize one letter */
+#define Phonize(c) do {(*phoned_word)[p_idx++] = c;} while (0)
+/* Slap a null character on the end of the phoned word */
+#define End_Phoned_Word do {(*phoned_word)[p_idx] = '\0';} while (0)
+/* How long is the phoned word? */
+#define Phone_Len (p_idx)
+
+/* Note is a letter is a 'break' in the word */
+#define Isbreak(c) (!isalpha((unsigned char) (c)))
+
+
+static void
+_metaphone(char *word, /* IN */
+ int max_phonemes,
+ char **phoned_word) /* OUT */
+{
+ int w_idx = 0; /* point in the phonization we're at. */
+ int p_idx = 0; /* end of the phoned phrase */
+
+ /*-- Parameter checks --*/
+
+ /*
+ * Shouldn't be necessary, but left these here anyway jec Aug 3, 2001
+ */
+
+ /* Negative phoneme length is meaningless */
+ if (!(max_phonemes > 0))
+ /* internal error */
+ elog(ERROR, "metaphone: Requested output length must be > 0");
+
+ /* Empty/null string is meaningless */
+ if ((word == NULL) || !(strlen(word) > 0))
+ /* internal error */
+ elog(ERROR, "metaphone: Input string length must be > 0");
+
+ /*-- Allocate memory for our phoned_phrase --*/
+ if (max_phonemes == 0)
+ { /* Assume largest possible */
+ *phoned_word = palloc(sizeof(char) * strlen(word) + 1);
+ }
+ else
+ {
+ *phoned_word = palloc(sizeof(char) * max_phonemes + 1);
+ }
+
+ /*-- The first phoneme has to be processed specially. --*/
+ /* Find our first letter */
+ for (; !isalpha((unsigned char) (Curr_Letter)); w_idx++)
+ {
+ /* On the off chance we were given nothing but crap... */
+ if (Curr_Letter == '\0')
+ {
+ End_Phoned_Word;
+ return;
+ }
+ }
+
+ switch (Curr_Letter)
+ {
+ /* AE becomes E */
+ case 'A':
+ if (Next_Letter == 'E')
+ {
+ Phonize('E');
+ w_idx += 2;
+ }
+ /* Remember, preserve vowels at the beginning */
+ else
+ {
+ Phonize('A');
+ w_idx++;
+ }
+ break;
+ /* [GKP]N becomes N */
+ case 'G':
+ case 'K':
+ case 'P':
+ if (Next_Letter == 'N')
+ {
+ Phonize('N');
+ w_idx += 2;
+ }
+ break;
+
+ /*
+ * WH becomes H, WR becomes R W if followed by a vowel
+ */
+ case 'W':
+ if (Next_Letter == 'H' ||
+ Next_Letter == 'R')
+ {
+ Phonize(Next_Letter);
+ w_idx += 2;
+ }
+ else if (isvowel(Next_Letter))
+ {
+ Phonize('W');
+ w_idx += 2;
+ }
+ /* else ignore */
+ break;
+ /* X becomes S */
+ case 'X':
+ Phonize('S');
+ w_idx++;
+ break;
+ /* Vowels are kept */
+
+ /*
+ * We did A already case 'A': case 'a':
+ */
+ case 'E':
+ case 'I':
+ case 'O':
+ case 'U':
+ Phonize(Curr_Letter);
+ w_idx++;
+ break;
+ default:
+ /* do nothing */
+ break;
+ }
+
+
+
+ /* On to the metaphoning */
+ for (; Curr_Letter != '\0' &&
+ (max_phonemes == 0 || Phone_Len < max_phonemes);
+ w_idx++)
+ {
+ /*
+ * How many letters to skip because an earlier encoding handled
+ * multiple letters
+ */
+ unsigned short int skip_letter = 0;
+
+
+ /*
+ * THOUGHT: It would be nice if, rather than having things like...
+ * well, SCI. For SCI you encode the S, then have to remember to skip
+ * the C. So the phonome SCI invades both S and C. It would be
+ * better, IMHO, to skip the C from the S part of the encoding. Hell,
+ * I'm trying it.
+ */
+
+ /* Ignore non-alphas */
+ if (!isalpha((unsigned char) (Curr_Letter)))
+ continue;
+
+ /* Drop duplicates, except CC */
+ if (Curr_Letter == Prev_Letter &&
+ Curr_Letter != 'C')
+ continue;
+
+ switch (Curr_Letter)
+ {
+ /* B -> B unless in MB */
+ case 'B':
+ if (Prev_Letter != 'M')
+ Phonize('B');
+ break;
+
+ /*
+ * 'sh' if -CIA- or -CH, but not SCH, except SCHW. (SCHW is
+ * handled in S) S if -CI-, -CE- or -CY- dropped if -SCI-,
+ * SCE-, -SCY- (handed in S) else K
+ */
+ case 'C':
+ if (MAKESOFT(Next_Letter))
+ { /* C[IEY] */
+ if (After_Next_Letter == 'A' &&
+ Next_Letter == 'I')
+ { /* CIA */
+ Phonize(SH);
+ }
+ /* SC[IEY] */
+ else if (Prev_Letter == 'S')
+ {
+ /* Dropped */
+ }
+ else
+ Phonize('S');
+ }
+ else if (Next_Letter == 'H')
+ {
+#ifndef USE_TRADITIONAL_METAPHONE
+ if (After_Next_Letter == 'R' ||
+ Prev_Letter == 'S')
+ { /* Christ, School */
+ Phonize('K');
+ }
+ else
+ Phonize(SH);
+#else
+ Phonize(SH);
+#endif
+ skip_letter++;
+ }
+ else
+ Phonize('K');
+ break;
+
+ /*
+ * J if in -DGE-, -DGI- or -DGY- else T
+ */
+ case 'D':
+ if (Next_Letter == 'G' &&
+ MAKESOFT(After_Next_Letter))
+ {
+ Phonize('J');
+ skip_letter++;
+ }
+ else
+ Phonize('T');
+ break;
+
+ /*
+ * F if in -GH and not B--GH, D--GH, -H--GH, -H---GH else
+ * dropped if -GNED, -GN, else dropped if -DGE-, -DGI- or
+ * -DGY- (handled in D) else J if in -GE-, -GI, -GY and not GG
+ * else K
+ */
+ case 'G':
+ if (Next_Letter == 'H')
+ {
+ if (!(NOGHTOF(Look_Back_Letter(3)) ||
+ Look_Back_Letter(4) == 'H'))
+ {
+ Phonize('F');
+ skip_letter++;
+ }
+ else
+ {
+ /* silent */
+ }
+ }
+ else if (Next_Letter == 'N')
+ {
+ if (Isbreak(After_Next_Letter) ||
+ (After_Next_Letter == 'E' &&
+ Look_Ahead_Letter(3) == 'D'))
+ {
+ /* dropped */
+ }
+ else
+ Phonize('K');
+ }
+ else if (MAKESOFT(Next_Letter) &&
+ Prev_Letter != 'G')
+ Phonize('J');
+ else
+ Phonize('K');
+ break;
+ /* H if before a vowel and not after C,G,P,S,T */
+ case 'H':
+ if (isvowel(Next_Letter) &&
+ !AFFECTH(Prev_Letter))
+ Phonize('H');
+ break;
+
+ /*
+ * dropped if after C else K
+ */
+ case 'K':
+ if (Prev_Letter != 'C')
+ Phonize('K');
+ break;
+
+ /*
+ * F if before H else P
+ */
+ case 'P':
+ if (Next_Letter == 'H')
+ Phonize('F');
+ else
+ Phonize('P');
+ break;
+
+ /*
+ * K
+ */
+ case 'Q':
+ Phonize('K');
+ break;
+
+ /*
+ * 'sh' in -SH-, -SIO- or -SIA- or -SCHW- else S
+ */
+ case 'S':
+ if (Next_Letter == 'I' &&
+ (After_Next_Letter == 'O' ||
+ After_Next_Letter == 'A'))
+ Phonize(SH);
+ else if (Next_Letter == 'H')
+ {
+ Phonize(SH);
+ skip_letter++;
+ }
+#ifndef USE_TRADITIONAL_METAPHONE
+ else if (Next_Letter == 'C' &&
+ Look_Ahead_Letter(2) == 'H' &&
+ Look_Ahead_Letter(3) == 'W')
+ {
+ Phonize(SH);
+ skip_letter += 2;
+ }
+#endif
+ else
+ Phonize('S');
+ break;
+
+ /*
+ * 'sh' in -TIA- or -TIO- else 'th' before H else T
+ */
+ case 'T':
+ if (Next_Letter == 'I' &&
+ (After_Next_Letter == 'O' ||
+ After_Next_Letter == 'A'))
+ Phonize(SH);
+ else if (Next_Letter == 'H')
+ {
+ Phonize(TH);
+ skip_letter++;
+ }
+ else
+ Phonize('T');
+ break;
+ /* F */
+ case 'V':
+ Phonize('F');
+ break;
+ /* W before a vowel, else dropped */
+ case 'W':
+ if (isvowel(Next_Letter))
+ Phonize('W');
+ break;
+ /* KS */
+ case 'X':
+ Phonize('K');
+ if (max_phonemes == 0 || Phone_Len < max_phonemes)
+ Phonize('S');
+ break;
+ /* Y if followed by a vowel */
+ case 'Y':
+ if (isvowel(Next_Letter))
+ Phonize('Y');
+ break;
+ /* S */
+ case 'Z':
+ Phonize('S');
+ break;
+ /* No transformation */
+ case 'F':
+ case 'J':
+ case 'L':
+ case 'M':
+ case 'N':
+ case 'R':
+ Phonize(Curr_Letter);
+ break;
+ default:
+ /* nothing */
+ break;
+ } /* END SWITCH */
+
+ w_idx += skip_letter;
+ } /* END FOR */
+
+ End_Phoned_Word;
+} /* END metaphone */
+
+
+/*
+ * SQL function: soundex(text) returns text
+ */
+PG_FUNCTION_INFO_V1(soundex);
+
+Datum
+soundex(PG_FUNCTION_ARGS)
+{
+ char outstr[SOUNDEX_LEN + 1];
+ char *arg;
+
+ arg = text_to_cstring(PG_GETARG_TEXT_PP(0));
+
+ _soundex(arg, outstr);
+
+ PG_RETURN_TEXT_P(cstring_to_text(outstr));
+}
+
+static void
+_soundex(const char *instr, char *outstr)
+{
+ int count;
+
+ Assert(instr);
+ Assert(outstr);
+
+ /* Skip leading non-alphabetic characters */
+ while (*instr && !isalpha((unsigned char) *instr))
+ ++instr;
+
+ /* If no string left, return all-zeroes buffer */
+ if (!*instr)
+ {
+ memset(outstr, '\0', SOUNDEX_LEN + 1);
+ return;
+ }
+
+ /* Take the first letter as is */
+ *outstr++ = (char) toupper((unsigned char) *instr++);
+
+ count = 1;
+ while (*instr && count < SOUNDEX_LEN)
+ {
+ if (isalpha((unsigned char) *instr) &&
+ soundex_code(*instr) != soundex_code(*(instr - 1)))
+ {
+ *outstr = soundex_code(*instr);
+ if (*outstr != '0')
+ {
+ ++outstr;
+ ++count;
+ }
+ }
+ ++instr;
+ }
+
+ /* Fill with 0's */
+ while (count < SOUNDEX_LEN)
+ {
+ *outstr = '0';
+ ++outstr;
+ ++count;
+ }
+
+ /* And null-terminate */
+ *outstr = '\0';
+}
+
+PG_FUNCTION_INFO_V1(difference);
+
+Datum
+difference(PG_FUNCTION_ARGS)
+{
+ char sndx1[SOUNDEX_LEN + 1],
+ sndx2[SOUNDEX_LEN + 1];
+ int i,
+ result;
+
+ _soundex(text_to_cstring(PG_GETARG_TEXT_PP(0)), sndx1);
+ _soundex(text_to_cstring(PG_GETARG_TEXT_PP(1)), sndx2);
+
+ result = 0;
+ for (i = 0; i < SOUNDEX_LEN; i++)
+ {
+ if (sndx1[i] == sndx2[i])
+ result++;
+ }
+
+ PG_RETURN_INT32(result);
+}
diff --git a/contrib/fuzzystrmatch/fuzzystrmatch.control b/contrib/fuzzystrmatch/fuzzystrmatch.control
new file mode 100644
index 0000000..8b6e9fd
--- /dev/null
+++ b/contrib/fuzzystrmatch/fuzzystrmatch.control
@@ -0,0 +1,6 @@
+# fuzzystrmatch extension
+comment = 'determine similarities and distance between strings'
+default_version = '1.2'
+module_pathname = '$libdir/fuzzystrmatch'
+relocatable = true
+trusted = true
diff --git a/contrib/fuzzystrmatch/meson.build b/contrib/fuzzystrmatch/meson.build
new file mode 100644
index 0000000..3ff84eb
--- /dev/null
+++ b/contrib/fuzzystrmatch/meson.build
@@ -0,0 +1,48 @@
+# Copyright (c) 2022-2023, PostgreSQL Global Development Group
+
+fuzzystrmatch_sources = files(
+ 'daitch_mokotoff.c',
+ 'dmetaphone.c',
+ 'fuzzystrmatch.c',
+)
+
+daitch_mokotoff_h = custom_target('daitch_mokotoff',
+ input: 'daitch_mokotoff_header.pl',
+ output: 'daitch_mokotoff.h',
+ command: [perl, '@INPUT@', '@OUTPUT@'],
+)
+generated_sources += daitch_mokotoff_h
+fuzzystrmatch_sources += daitch_mokotoff_h
+
+if host_system == 'windows'
+ fuzzystrmatch_sources += rc_lib_gen.process(win32ver_rc, extra_args: [
+ '--NAME', 'fuzzystrmatch',
+ '--FILEDESC', 'fuzzystrmatch - similarities and distance between strings',])
+endif
+
+fuzzystrmatch = shared_module('fuzzystrmatch',
+ fuzzystrmatch_sources,
+ include_directories: include_directories('.'),
+ kwargs: contrib_mod_args,
+)
+contrib_targets += fuzzystrmatch
+
+install_data(
+ 'fuzzystrmatch.control',
+ 'fuzzystrmatch--1.0--1.1.sql',
+ 'fuzzystrmatch--1.1.sql',
+ 'fuzzystrmatch--1.1--1.2.sql',
+ kwargs: contrib_data_args,
+)
+
+tests += {
+ 'name': 'fuzzystrmatch',
+ 'sd': meson.current_source_dir(),
+ 'bd': meson.current_build_dir(),
+ 'regress': {
+ 'sql': [
+ 'fuzzystrmatch',
+ 'fuzzystrmatch_utf8',
+ ],
+ },
+}
diff --git a/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql b/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
new file mode 100644
index 0000000..0b4bb9b
--- /dev/null
+++ b/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql
@@ -0,0 +1,67 @@
+CREATE EXTENSION fuzzystrmatch;
+
+
+SELECT soundex('hello world!');
+
+SELECT soundex('Anne'), soundex('Ann'), difference('Anne', 'Ann');
+SELECT soundex('Anne'), soundex('Andrew'), difference('Anne', 'Andrew');
+SELECT soundex('Anne'), soundex('Margaret'), difference('Anne', 'Margaret');
+SELECT soundex(''), difference('', '');
+
+
+SELECT levenshtein('GUMBO', 'GAMBOL');
+SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1);
+SELECT levenshtein_less_equal('extensive', 'exhaustive', 2);
+SELECT levenshtein_less_equal('extensive', 'exhaustive', 4);
+
+
+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');
+
+-- 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');
+
+-- Ignored characters
+SELECT daitch_mokotoff('''OBrien');
+SELECT daitch_mokotoff('O''Brien');
+
+-- "Difficult" cases, likely to cause trouble for other implementations.
+SELECT daitch_mokotoff('CJC');
+SELECT daitch_mokotoff('BESST');
+SELECT daitch_mokotoff('BOUEY');
+SELECT daitch_mokotoff('HANNMANN');
+SELECT daitch_mokotoff('MCCOYJR');
+SELECT daitch_mokotoff('ACCURSO');
+SELECT daitch_mokotoff('BIERSCHBACH');
diff --git a/contrib/fuzzystrmatch/sql/fuzzystrmatch_utf8.sql b/contrib/fuzzystrmatch/sql/fuzzystrmatch_utf8.sql
new file mode 100644
index 0000000..f42c01a
--- /dev/null
+++ b/contrib/fuzzystrmatch/sql/fuzzystrmatch_utf8.sql
@@ -0,0 +1,26 @@
+/*
+ * This test must be run in a database with UTF-8 encoding,
+ * because other encodings don't support all the characters used.
+ */
+
+SELECT getdatabaseencoding() <> 'UTF8'
+ AS skip_test \gset
+\if :skip_test
+\quit
+\endif
+
+set client_encoding = utf8;
+
+-- CREATE EXTENSION IF NOT EXISTS fuzzystrmatch;
+
+-- Accents
+SELECT daitch_mokotoff('Müller');
+SELECT daitch_mokotoff('Schäfer');
+SELECT daitch_mokotoff('Straßburg');
+SELECT daitch_mokotoff('Éregon');
+
+-- 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');
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-03 01:18:42 +0000