Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1p8LER-000553-5T for pgsql-hackers@arkaria.postgresql.org; Thu, 22 Dec 2022 13:03:31 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1p8LEP-000347-Pi for pgsql-hackers@arkaria.postgresql.org; Thu, 22 Dec 2022 13:03:29 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1p8LEP-00033y-89 for pgsql-hackers@lists.postgresql.org; Thu, 22 Dec 2022 13:03:29 +0000 Received: from sid.nimrod.no ([2001:8c0:9340:1::2]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1p8LEH-0004Gt-M3 for pgsql-hackers@lists.postgresql.org; Thu, 22 Dec 2022 13:03:28 +0000 Received: from sid.nimrod.no (sid.nimrod.no [195.139.160.2]) by sid.nimrod.no (8.14.7/8.14.7) with ESMTP id 2BMC0hHg007724; Thu, 22 Dec 2022 13:00:44 +0100 DKIM-Filter: OpenDKIM Filter v2.11.0 sid.nimrod.no 2BMC0hHg007724 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nimrod.no; s=n20181209; t=1671710444; bh=urag21GPzFGocoLQfRMGuSpx0tVKg/q4pIEL0F4jlzk=; h=From:To:Cc:Subject:References:Date:In-Reply-To:From; b=Ytfxpj+EGPzqE+L57cObqhQMj3oi6OWeMIUG1W0Kp3dceon9fOAiYm0e0BYiYCXj5 uWi1LE6LINL+QJ+xlnQSZBXeIbOi5I/VP1iaBeTaDdb3epvMHKKHv/5sv540iv7EWV tWY5I2PXEh8INFNnbzc7Wy04sG3l0oSqgTR/gzKhx3nTY8CR11hhagSpHbSRKu3Jvf EW60aAiTUVSuznJAQ9qOJ+PLlAyA55uNc+IKVcKr0yPnVQ1H7GgDKjqRQ4fjVqKFYo 3ikxVyrUHxMAJTI1j5JsDjMpe1PvA8SDYG8lHWKQqciagqPcUFoHk+BQ9yEhwGWmca 95a12QEhH5Fgg== From: Dag Lem To: Andres Freund Cc: PostgreSQL Hackers , Thomas Munro , Julien Rouhaud Subject: Re: daitch_mokotoff module Organization: Nimrod References: <20220102213150.y2tpuwqhruu5t2y5@alap3.anarazel.de> <3461033.1641177713@sss.pgh.pa.us> <20220103191609.s3gendov5hecml7g@alap3.anarazel.de> <20221207185656.nlaj2o5kcbgbadcp@awork3.anarazel.de> Date: Thu, 22 Dec 2022 13:00:43 +0100 In-Reply-To: (Dag Lem's message of "Wed, 21 Dec 2022 10:26:05 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --=-=-= Content-Type: text/plain I noticed that the Meson builds failed in Cfbot, the updated patch adds a missing "include_directories" line to meson.build. Best regards Dag Lem --=-=-= Content-Type: text/x-patch; charset=utf-8 Content-Disposition: inline; filename=v8-daitch_mokotoff.patch Content-Transfer-Encoding: quoted-printable diff --git a/contrib/fuzzystrmatch/Makefile b/contrib/fuzzystrmatch/Makefile index 0704894f88..12baf2d884 100644 --- a/contrib/fuzzystrmatch/Makefile +++ b/contrib/fuzzystrmatch/Makefile @@ -3,14 +3,15 @@ MODULE_big =3D fuzzystrmatch OBJS =3D \ $(WIN32RES) \ + daitch_mokotoff.o \ dmetaphone.o \ fuzzystrmatch.o =20 EXTENSION =3D fuzzystrmatch -DATA =3D fuzzystrmatch--1.1.sql fuzzystrmatch--1.0--1.1.sql +DATA =3D fuzzystrmatch--1.1.sql fuzzystrmatch--1.1--1.2.sql fuzzystrmatch-= -1.0--1.1.sql PGFILEDESC =3D "fuzzystrmatch - similarities and distance between strings" =20 -REGRESS =3D fuzzystrmatch +REGRESS =3D fuzzystrmatch fuzzystrmatch_utf8 =20 ifdef USE_PGXS PG_CONFIG =3D pg_config @@ -22,3 +23,14 @@ top_builddir =3D ../.. 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 $< $@ + +distprep: daitch_mokotoff.h + +maintainer-clean: + rm -f daitch_mokotoff.h diff --git a/contrib/fuzzystrmatch/daitch_mokotoff.c b/contrib/fuzzystrmatc= h/daitch_mokotoff.c new file mode 100644 index 0000000000..d4ad95c283 --- /dev/null +++ b/contrib/fuzzystrmatch/daitch_mokotoff.c @@ -0,0 +1,596 @@ +/* + * Daitch-Mokotoff Soundex + * + * Copyright (c) 2021 Finance Norway + * Author: Dag Lem + * + * This implementation of the Daitch-Mokotoff Soundex System aims at high + * performance. + * + * - The processing of each phoneme is initiated by an O(1) table lookup. + * - For phonemes containing more than one character, a coding tree is tra= versed + * 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, DaitchMokotoffSo= undex.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 "U= E", + * 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 correctl= y in + * dmsoundex.php when double digit codes are involved. E.g. "BESST" yiel= ds + * 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 + * + * Permission to use, copy, modify, and distribute this software and its + * documentation for any purpose, without fee, and without a written agree= ment + * is hereby granted, provided that the above copyright notice and this + * paragraph and the following two paragraphs appear in all copies. + * + * IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUD= ING + * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS + * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF = THE + * POSSIBILITY OF SUCH DAMAGE. + * + * THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY + * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER = IS + * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS= TO + * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. +*/ + +#include "postgres.h" + +#include "lib/stringinfo.h" +#include "mb/pg_wchar.h" +#include "utils/builtins.h" +#include "utils/memutils.h" + + +/* + * The soundex coding chart table is adapted from from + * https://www.jewishgen.org/InfoFiles/Soundex.html + * See daitch_mokotoff_header.pl for details. +*/ + +#define DM_CODE_DIGITS 6 + +/* 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; + +/* Generated coding chart table */ +#include "daitch_mokotoff.h" + +/* Node in soundex code tree */ +struct dm_node +{ + int soundex_length; /* Length of generated soundex code */ + char soundex[DM_CODE_DIGITS + 1]; /* 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; + /* Nodes branching out from this node. */ + struct dm_node *children[DM_MAX_ALTERNATE_CODES + 1]; + /* Next node in linked list. Alternating index for each iteration. */ + struct dm_node *next[2]; +}; + +typedef struct dm_node dm_node; + + +/* Internal C implementation */ +static int daitch_mokotoff_coding(char *word, StringInfo soundex); + + +PG_FUNCTION_INFO_V1(daitch_mokotoff); + +Datum +daitch_mokotoff(PG_FUNCTION_ARGS) +{ + text *arg =3D PG_GETARG_TEXT_PP(0); + char *string; + StringInfoData soundex; + text *retval; + MemoryContext old_ctx, + tmp_ctx; + + tmp_ctx =3D AllocSetContextCreate(CurrentMemoryContext, + "daitch_mokotoff temporary context", + ALLOCSET_DEFAULT_SIZES); + old_ctx =3D MemoryContextSwitchTo(tmp_ctx); + + string =3D pg_server_to_any(text_to_cstring(arg), VARSIZE_ANY_EXHDR(arg),= PG_UTF8); + initStringInfo(&soundex); + + if (!daitch_mokotoff_coding(string, &soundex)) + { + /* No encodable characters in input. */ + MemoryContextSwitchTo(old_ctx); + MemoryContextDelete(tmp_ctx); + PG_RETURN_NULL(); + } + + string =3D pg_any_to_server(soundex.data, soundex.len, PG_UTF8); + MemoryContextSwitchTo(old_ctx); + retval =3D cstring_to_text(string); + MemoryContextDelete(tmp_ctx); + + PG_RETURN_TEXT_P(retval); +} + + +/* Template for new node in soundex code tree. */ +static const dm_node start_node =3D { + .soundex_length =3D 0, + .soundex =3D "000000 ", /* Six digits + joining space */ + .is_leaf =3D 0, + .last_update =3D 0, + .code_digit =3D '\0', + .prev_code_digits =3D {'\0', '\0'}, + .next_code_digits =3D {'\0', '\0'}, + .prev_code_index =3D 0, + .next_code_index =3D 0, + .children =3D {NULL}, + .next =3D {NULL} +}; + +/* Dummy soundex codes at end of input. */ +static const dm_codes end_codes[2] =3D +{ + { + "X", "X", "X" + } +}; + + +/* 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] =3D node->next_code_digits[0]; + node->prev_code_digits[1] =3D node->next_code_digits[1]; + node->next_code_digits[0] =3D '\0'; + node->next_code_digits[1] =3D '\0'; + node->prev_code_index =3D node->next_code_index; + node->next_code_index =3D 0; + node->is_leaf =3D 0; + node->last_update =3D 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 |=3D code_index; + + if (!node->next_code_digits[0]) + { + node->next_code_digits[0] =3D code_digit; + } + else if (node->next_code_digits[0] !=3D code_digit) + { + node->next_code_digits[1] =3D 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 =3D 1; + + if (first_node[ix_node] =3D=3D NULL) + { + first_node[ix_node] =3D node; + } + else + { + last_node[ix_node]->next[ix_node] =3D node; + } + + last_node[ix_node] =3D node; + node->next[ix_node] =3D 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, StringInfo so= undex) +{ + dm_node **nodes; + dm_node *node; + int i; + + for (nodes =3D parent->children, i =3D 0; (node =3D nodes[i]); i++) + { + if (node->code_digit =3D=3D code_digit) + { + /* Found existing child node. Skip completed nodes. */ + return node->soundex_length < DM_CODE_DIGITS ? node : NULL; + } + } + + /* Create new child node. */ + Assert(i < DM_MAX_ALTERNATE_CODES); + node =3D palloc(sizeof(dm_node)); + nodes[i] =3D node; + + *node =3D start_node; + memcpy(node->soundex, parent->soundex, sizeof(parent->soundex)); + node->soundex_length =3D parent->soundex_length; + node->soundex[node->soundex_length++] =3D code_digit; + node->code_digit =3D code_digit; + node->next_code_index =3D node->prev_code_index; + + if (node->soundex_length < DM_CODE_DIGITS) + { + return node; + } + else + { + /* Append completed soundex code to soundex string. */ + appendBinaryStringInfoNT(soundex, node->soundex, DM_CODE_DIGITS + 1); + 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 * nod= e, int ix_node, + int letter_no, int prev_code_index, int next_code_index, + const char *next_code_digits, int digit_no, + StringInfo soundex) +{ + int i; + char next_code_digit =3D next_code_digits[digit_no]; + int num_dirty_nodes =3D 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 =3D=3D 'X' || + (digit_no =3D=3D 0 && + (node->prev_code_digits[0] =3D=3D next_code_digit || + node->prev_code_digits[1] =3D=3D next_code_digit))) + { + /* The code digit is the same as one of the previous (i.e. not added). */ + dirty_nodes[num_dirty_nodes++] =3D node; + } + + if (next_code_digit !=3D 'X' && + (digit_no > 0 || + node->prev_code_digits[0] !=3D next_code_digit || + node->prev_code_digits[1])) + { + /* The code digit is different from one of the previous (i.e. added). */ + node =3D find_or_create_child_node(node, next_code_digit, soundex); + if (node) + { + initialize_node(node, letter_no); + dirty_nodes[num_dirty_nodes++] =3D node; + } + } + + for (i =3D 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, + StringInfo soundex) +{ + int i, + j, + code_index; + dm_node *node, + *last_node[2]; + const dm_code *code, + *next_code; + int ix_node_next =3D (*ix_node + 1) & 1; /* Alternating index: 0, 1 */ + + /* Initialize for new linked list of leaves. */ + first_node[ix_node_next] =3D NULL; + last_node[ix_node_next] =3D NULL; + + /* Process all nodes. */ + for (node =3D first_node[*ix_node]; node; node =3D node->next[*ix_node]) + { + /* One or two alternate code sequences. */ + for (i =3D 0; i < 2 && (code =3D codes[i]) && code[0][0]; i++) + { + /* Coding for previous letter - before vowel: 1, all other: 2 */ + int prev_code_index =3D (code[0][0] > '1') + 1; + + /* One or two alternate next code sequences. */ + for (j =3D 0; j < 2 && (next_code =3D next_codes[j]) && next_code[0][0]= ; j++) + { + /* Determine which code to use. */ + if (letter_no =3D=3D 0) + { + /* This is the first letter. */ + code_index =3D 0; + } + else if (next_code[0][0] <=3D '1') + { + /* The next letter is a vowel. */ + code_index =3D 1; + } + else + { + /* All other cases. */ + code_index =3D 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 =3D ix_node_next; +} + + +/* Mapping from ISO8859-1 to upper-case ASCII */ +static const char iso8859_1_to_ascii_upper[] =3D +/* +"`abcdefghijklmnopqrstuvwxyz{|}~ =C2=A1= =C2=A2=C2=A3=C2=A4=C2=A5=C2=A6=C2=A7=C2=A8=C2=A9=C2=AA=C2=AB=C2=AC =C2=AE= =C2=AF=C2=B0=C2=B1=C2=B2=C2=B3=C2=B4=C2=B5=C2=B6=C2=B7=C2=B8=C2=B9=C2=BA=C2= =BB=C2=BC=C2=BD=C2=BE=C2=BF=C3=80=C3=81=C3=82=C3=83=C3=84=C3=85=C3=86=C3=87= =C3=88=C3=89=C3=8A=C3=8B=C3=8C=C3=8D=C3=8E=C3=8F=C3=90=C3=91=C3=92=C3=93=C3= =94=C3=95=C3=96=C3=97=C3=98=C3=99=C3=9A=C3=9B=C3=9C=C3=9D=C3=9E=C3=9F=C3=A0= =C3=A1=C3=A2=C3=A3=C3=A4=C3=A5=C3=A6=C3=A7=C3=A8=C3=A9=C3=AA=C3=AB=C3=AC=C3= =AD=C3=AE=C3=AF=C3=B0=C3=B1=C3=B2=C3=B3=C3=B4=C3=B5=C3=B6=C3=B7=C3=B8=C3=B9= =C3=BA=C3=BB=C3=BC=C3=BD=C3=BE=C3=BF" +*/ +"`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~ ! = ?AAAAAAECEEEEIIIIDNOOOOO*OUUUUYDSAAAAAAECEEEEIIIIDNOO= OOO/OUUUUYDY"; + + +/* Return next character, converted from UTF-8 to uppercase ASCII. */ +static char +read_char(unsigned char *str, int *ix) +{ + /* Substitute character for skipped code points. */ + const char na =3D '\x1a'; + pg_wchar c; + + /* Decode UTF-8 character to ISO 10646 code point. */ + str +=3D *ix; + c =3D utf8_to_unicode(str); + *ix +=3D pg_utf_mblen(str); + + if (c >=3D (unsigned char) '[' && c <=3D (unsigned char) ']') + { + /* ASCII characters [, \, and ] are reserved for =C4=84, =C4=98, and =C5= =A2/=C8=9A. */ + return na; + } + else if (c < 0x60) + { + /* Non-lowercase ASCII character. */ + return c; + } + else if (c < 0x100) + { + /* ISO-8859-1 code point, converted to upper-case ASCII. */ + return iso8859_1_to_ascii_upper[c - 0x60]; + } + else + { + /* Conversion of non-ASCII characters in the coding chart. */ + switch (c) + { + case 0x0104: + case 0x0105: + /* =C4=84/=C4=85 */ + return '['; + case 0x0118: + case 0x0119: + /* =C4=98/=C4=99 */ + return '\\'; + case 0x0162: + case 0x0163: + case 0x021A: + case 0x021B: + /* =C5=A2/=C5=A3 or =C8=9A/=C8=9B */ + return ']'; + default: + return na; + } + } +} + + +/* Read next ASCII character, skipping any characters not in [A-\]]. */ +static char +read_valid_char(char *str, int *ix) +{ + char c; + + while ((c =3D read_char((unsigned char *) str, ix))) + { + if (c >=3D 'A' && c <=3D ']') + { + break; + } + } + + return c; +} + + +/* Return sound coding for "letter" (letter sequence) */ +static const dm_codes * +read_letter(char *str, int *ix) +{ + char c, + cmp; + int i, + j; + const dm_letter *letters; + const dm_codes *codes; + + /* First letter in sequence. */ + if (!(c =3D read_valid_char(str, ix))) + { + return NULL; + } + letters =3D &letter_[c - 'A']; + codes =3D letters->codes; + i =3D *ix; + + /* Any subsequent letters in sequence. */ + while ((letters =3D letters->letters) && (c =3D read_valid_char(str, &i))) + { + for (j =3D 0; (cmp =3D letters[j].letter); j++) + { + if (cmp =3D=3D c) + { + /* Letter found. */ + letters =3D &letters[j]; + if (letters->codes) + { + /* Coding for letter sequence found. */ + codes =3D letters->codes; + *ix =3D i; + } + break; + } + } + if (!cmp) + { + /* The sequence of letters has no coding. */ + break; + } + } + + return codes; +} + + +/* Generate all Daitch-Mokotoff soundex codes for word, separated by space= . */ +static int +daitch_mokotoff_coding(char *word, StringInfo soundex) +{ + int i =3D 0; + int letter_no =3D 0; + int ix_node =3D 0; + const dm_codes *codes, + *next_codes; + dm_node *first_node[2], + *node; + + /* First letter. */ + if (!(codes =3D read_letter(word, &i))) + { + /* No encodable character in input. */ + return 0; + } + + /* Starting point. */ + first_node[ix_node] =3D palloc(sizeof(dm_node)); + *first_node[ix_node] =3D 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 =3D read_letter(word, &i); + + /* Update leaf nodes. */ + update_leaves(first_node, &ix_node, letter_no, + codes, next_codes ? next_codes : end_codes, + soundex); + + codes =3D next_codes; + letter_no++; + } + + /* Append all remaining (incomplete) soundex codes. */ + for (node =3D first_node[ix_node]; node; node =3D node->next[ix_node]) + { + appendBinaryStringInfoNT(soundex, node->soundex, DM_CODE_DIGITS + 1); + } + + /* Terminate string at the final space. */ + soundex->len--; + soundex->data[soundex->len] =3D '\0'; + + return 1; +} diff --git a/contrib/fuzzystrmatch/daitch_mokotoff_header.pl b/contrib/fuzz= ystrmatch/daitch_mokotoff_header.pl new file mode 100755 index 0000000000..807b5fb8c5 --- /dev/null +++ b/contrib/fuzzystrmatch/daitch_mokotoff_header.pl @@ -0,0 +1,260 @@ +#!/bin/perl +# +# Generation of types and lookup tables for Daitch-Mokotoff soundex. +# +# Copyright (c) 2021 Finance Norway +# Author: Dag Lem +# +# Permission to use, copy, modify, and distribute this software and its +# documentation for any purpose, without fee, and without a written agreem= ent +# is hereby granted, provided that the above copyright notice and this +# paragraph and the following two paragraphs appear in all copies. +# +# IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR +# DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDI= NG +# LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS +# DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF T= HE +# POSSIBILITY OF SUCH DAMAGE. +# +# THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, +# INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY +# AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS +# ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS = TO +# PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. +# + +use strict; +use warnings; +use utf8; +use open IO =3D> ':utf8', ':std'; +use Data::Dumper; + +die "Usage: $0 OUTPUT_FILE\n" if @ARGV !=3D 1; +my $output_file =3D $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 %alternates; +my $table =3D [{}, [["","",""]]]; +while () { + chomp; + my ($letters, $codes) =3D split(/\s+/); + my @codes =3D map { [ split(/,/) ] } split(/\|/, $codes); + + # Find alternate code transitions for calculation of storage. + # The first character ("start of a name") can never yield more than two a= lternate codes, + # and is not considered here. + if (@codes > 1) { + for my $j (1..2) { # Codes for "before a vowel" and "any other" + for my $i (0..1) { # Alternate codes + # Identical code digits for adjacent letters are collapsed. + # For each possible non-transition due to code digit + # collapsing, find all alternate transitions. + my ($present, $next) =3D ($codes[$i][$j], $codes[($i + 1)%2][$j]); + next if length($present) !=3D 1; + $next =3D $present ne substr($next, 0, 1) ? substr($next, 0, 1) : subs= tr($next, -1, 1); + $alternates{$present}{$next} =3D 1; + } + } + } + my $key =3D "codes_" . join("_or_", map { join("_", @$_) } @codes); + my $val =3D join(",\n", map { "\t{\n\t\t" . join(", ", map { "\"$_\"" } @= $_) . "\n\t}" } @codes); + $codes{$key} =3D $val; + + for my $letter (split(/,/, $letters)) { + my $ref =3D $table->[0]; + # Link each character to the next in the letter combination. + my @c =3D split(//, $letter); + my $last_c =3D pop(@c); + for my $c (@c) { + $ref->{$c} //=3D [ {}, undef ]; + $ref->{$c}[0] //=3D {}; + $ref =3D $ref->{$c}[0]; + } + # The sound code for the letter combination is stored at the last charac= ter. + $ref->{$last_c}[1] =3D $key; + } +} +close(DATA); + +# Add alternates by following transitions to 'X' (not coded). +my $alt_x =3D $alternates{"X"}; +delete $alt_x->{"X"}; +while (my ($k, $v) =3D each %alternates) { + if (delete $v->{"X"}) { + for my $x (keys %$alt_x) { + $v->{$x} =3D 1; + } + } +} + +# Find the maximum number of alternate codes in one position. +# Add two for any additional final code digit transitions. +my $max_alt =3D (sort { $b <=3D> $a } (map { scalar keys %$_ } values %alt= ernates))[0] + 2; + +print $OUTPUT < + * + * This file is generated by daitch_mokotoff_header.pl + * + * Permission to use, copy, modify, and distribute this software and its + * documentation for any purpose, without fee, and without a written agree= ment + * is hereby granted, provided that the above copyright notice and this + * paragraph and the following two paragraphs appear in all copies. + * + * IN NO EVENT SHALL THE AUTHOR OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUD= ING + * LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS + * DOCUMENTATION, EVEN IF THE AUTHOR OR DISTRIBUTORS HAVE BEEN ADVISED OF = THE + * POSSIBILITY OF SUCH DAMAGE. + * + * THE AUTHOR AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY + * AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER = IS + * ON AN "AS IS" BASIS, AND THE AUTHOR AND DISTRIBUTORS HAS NO OBLIGATIONS= TO + * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. + */ + +#define DM_MAX_ALTERNATE_CODES $max_alt + +/* Codes for letter sequence at start of name, before a vowel, and any oth= er. */ +EOF + +for my $key (sort keys %codes) { + print $OUTPUT "static const dm_codes $key\[2\] =3D\n{\n" . $codes{$key} .= "\n};\n"; +} + +print $OUTPUT <[0]; + for my $key (sort keys %$h) { + $ref =3D $h->{$key}; + my $children =3D "NULL"; + if (defined $ref->[0]) { + $children =3D "letter_$letter$key"; + hash2code($ref, "$letter$key"); + } + my $codes =3D $ref->[1] // "NULL"; + push(@letters, "\t{\n\t\t'$key', $children, $codes\n\t}"); + } + + print $OUTPUT "static const dm_letter letter_$letter\[\] =3D\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 =3D 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: +# +# =C4=84 =3D> a (use '[' for table lookup) +# =C4=98 =3D> e (use '\\' for table lookup) +# =C5=A2 =3D> 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/expected/fuzzystrmatch.out b/contrib/fuz= zystrmatch/expected/fuzzystrmatch.out index 493c95cdfa..f62ddad4ee 100644 --- a/contrib/fuzzystrmatch/expected/fuzzystrmatch.out +++ b/contrib/fuzzystrmatch/expected/fuzzystrmatch.out @@ -65,3 +65,174 @@ SELECT dmetaphone_alt('gumbo'); KMP (1 row) =20 +-- Wovels +SELECT daitch_mokotoff('Augsburg'); + daitch_mokotoff=20 +----------------- + 054795 +(1 row) + +SELECT daitch_mokotoff('Breuer'); + daitch_mokotoff=20 +----------------- + 791900 +(1 row) + +SELECT daitch_mokotoff('Freud'); + daitch_mokotoff=20 +----------------- + 793000 +(1 row) + +-- The letter "H" +SELECT daitch_mokotoff('Halberstadt'); + daitch_mokotoff=20 +----------------- + 587943 587433 +(1 row) + +SELECT daitch_mokotoff('Mannheim'); + daitch_mokotoff=20 +----------------- + 665600 +(1 row) + +-- Adjacent sounds +SELECT daitch_mokotoff('Chernowitz'); + daitch_mokotoff=20 +----------------- + 596740 496740 +(1 row) + +-- Adjacent letters with identical adjacent code digits +SELECT daitch_mokotoff('Cherkassy'); + daitch_mokotoff=20 +----------------- + 595400 495400 +(1 row) + +SELECT daitch_mokotoff('Kleinman'); + daitch_mokotoff=20 +----------------- + 586660 +(1 row) + +-- More than one word +SELECT daitch_mokotoff('Nowy Targ'); + daitch_mokotoff=20 +----------------- + 673950 +(1 row) + +-- Padded with "0" +SELECT daitch_mokotoff('Berlin'); + daitch_mokotoff=20 +----------------- + 798600 +(1 row) + +-- Other examples from https://www.avotaynu.com/soundex.htm +SELECT daitch_mokotoff('Ceniow'); + daitch_mokotoff=20 +----------------- + 567000 467000 +(1 row) + +SELECT daitch_mokotoff('Tsenyuv'); + daitch_mokotoff=20 +----------------- + 467000 +(1 row) + +SELECT daitch_mokotoff('Holubica'); + daitch_mokotoff=20 +----------------- + 587500 587400 +(1 row) + +SELECT daitch_mokotoff('Golubitsa'); + daitch_mokotoff=20 +----------------- + 587400 +(1 row) + +SELECT daitch_mokotoff('Przemysl'); + daitch_mokotoff=20 +----------------- + 794648 746480 +(1 row) + +SELECT daitch_mokotoff('Pshemeshil'); + daitch_mokotoff=20 +----------------- + 746480 +(1 row) + +SELECT daitch_mokotoff('Rosochowaciec'); + daitch_mokotoff=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20 +--------------------------------------------------------- + 945755 945754 945745 945744 944755 944754 944745 944744 +(1 row) + +SELECT daitch_mokotoff('Rosokhovatsets'); + daitch_mokotoff=20 +----------------- + 945744 +(1 row) + +-- Ignored characters +SELECT daitch_mokotoff('''OBrien'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('O''Brien'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +-- "Difficult" cases, likely to cause trouble for other implementations. +SELECT daitch_mokotoff('CJC'); + daitch_mokotoff=20=20=20=20=20=20=20=20=20=20=20=20=20=20 +------------------------------------------- + 550000 540000 545000 450000 400000 440000 +(1 row) + +SELECT daitch_mokotoff('BESST'); + daitch_mokotoff=20 +----------------- + 743000 +(1 row) + +SELECT daitch_mokotoff('BOUEY'); + daitch_mokotoff=20 +----------------- + 710000 +(1 row) + +SELECT daitch_mokotoff('HANNMANN'); + daitch_mokotoff=20 +----------------- + 566600 +(1 row) + +SELECT daitch_mokotoff('MCCOYJR'); + daitch_mokotoff=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20 +--------------------------------------------------------- + 651900 654900 654190 654490 645190 645490 641900 644900 +(1 row) + +SELECT daitch_mokotoff('ACCURSO'); + daitch_mokotoff=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20 +--------------------------------------------------------- + 059400 054000 054940 054400 045940 045400 049400 044000 +(1 row) + +SELECT daitch_mokotoff('BIERSCHBACH'); + daitch_mokotoff=20=20=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20 +--------------------------------------------------------- + 794575 794574 794750 794740 745750 745740 747500 747400 +(1 row) + diff --git a/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8.out b/contri= b/fuzzystrmatch/expected/fuzzystrmatch_utf8.out new file mode 100644 index 0000000000..32d8260383 --- /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 =3D utf8; +-- CREATE EXTENSION IF NOT EXISTS fuzzystrmatch; +-- Accents +SELECT daitch_mokotoff('M=C3=BCller'); + daitch_mokotoff=20 +----------------- + 689000 +(1 row) + +SELECT daitch_mokotoff('Sch=C3=A4fer'); + daitch_mokotoff=20 +----------------- + 479000 +(1 row) + +SELECT daitch_mokotoff('Stra=C3=9Fburg'); + daitch_mokotoff=20 +----------------- + 294795 +(1 row) + +SELECT daitch_mokotoff('=C3=89regon'); + daitch_mokotoff=20 +----------------- + 095600 +(1 row) + +-- Special characters added at https://www.jewishgen.org/InfoFiles/Soundex= .html +SELECT daitch_mokotoff('g=C4=85szczu'); + daitch_mokotoff=20 +----------------- + 564000 540000 +(1 row) + +SELECT daitch_mokotoff('brz=C4=99czy'); + daitch_mokotoff=20=20=20=20=20=20=20 +----------------------------- + 794640 794400 746400 744000 +(1 row) + +SELECT daitch_mokotoff('=C5=A3amas'); + daitch_mokotoff=20 +----------------- + 364000 464000 +(1 row) + +SELECT daitch_mokotoff('=C8=9Bamas'); + daitch_mokotoff=20 +----------------- + 364000 464000 +(1 row) + diff --git a/contrib/fuzzystrmatch/expected/fuzzystrmatch_utf8_1.out b/cont= rib/fuzzystrmatch/expected/fuzzystrmatch_utf8_1.out new file mode 100644 index 0000000000..37aead89c0 --- /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.1--1.2.sql b/contrib/fu= zzystrmatch/fuzzystrmatch--1.1--1.2.sql new file mode 100644 index 0000000000..b9d7b229a3 --- /dev/null +++ b/contrib/fuzzystrmatch/fuzzystrmatch--1.1--1.2.sql @@ -0,0 +1,8 @@ +/* contrib/fuzzystrmatch/fuzzystrmatch--1.1--1.2.sql */ + +-- complain if script is sourced in psql, rather than via ALTER EXTENSION +\echo Use "ALTER EXTENSION fuzzystrmatch UPDATE TO '1.2'" to load this fil= e. \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.control b/contrib/fuzzystr= match/fuzzystrmatch.control index 3cd6660bf9..8b6e9fd993 100644 --- a/contrib/fuzzystrmatch/fuzzystrmatch.control +++ b/contrib/fuzzystrmatch/fuzzystrmatch.control @@ -1,6 +1,6 @@ # fuzzystrmatch extension comment =3D 'determine similarities and distance between strings' -default_version =3D '1.1' +default_version =3D '1.2' module_pathname =3D '$libdir/fuzzystrmatch' relocatable =3D true trusted =3D true diff --git a/contrib/fuzzystrmatch/meson.build b/contrib/fuzzystrmatch/meso= n.build index e6d06149ce..73178794c2 100644 --- a/contrib/fuzzystrmatch/meson.build +++ b/contrib/fuzzystrmatch/meson.build @@ -1,7 +1,16 @@ fuzzystrmatch_sources =3D files( - 'fuzzystrmatch.c', + 'daitch_mokotoff.c', 'dmetaphone.c', + 'fuzzystrmatch.c', +) + +daitch_mokotoff_h =3D custom_target('daitch_mokotoff', + input: 'daitch_mokotoff_header.pl', + output: 'daitch_mokotoff.h', + command: [perl, '@INPUT@', '@OUTPUT@'], ) +generated_sources +=3D daitch_mokotoff_h +fuzzystrmatch_sources +=3D daitch_mokotoff_h =20 if host_system =3D=3D 'windows' fuzzystrmatch_sources +=3D rc_lib_gen.process(win32ver_rc, extra_args: [ @@ -11,6 +20,7 @@ endif =20 fuzzystrmatch =3D shared_module('fuzzystrmatch', fuzzystrmatch_sources, + include_directories: include_directories('.'), kwargs: contrib_mod_args, ) contrib_targets +=3D fuzzystrmatch @@ -19,6 +29,7 @@ install_data( 'fuzzystrmatch.control', 'fuzzystrmatch--1.0--1.1.sql', 'fuzzystrmatch--1.1.sql', + 'fuzzystrmatch--1.1--1.2.sql', kwargs: contrib_data_args, ) =20 @@ -29,6 +40,7 @@ tests +=3D { 'regress': { 'sql': [ 'fuzzystrmatch', + 'fuzzystrmatch_utf8', ], }, } diff --git a/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql b/contrib/fuzzystr= match/sql/fuzzystrmatch.sql index f05dc28ffb..db05c7d6b6 100644 --- a/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql +++ b/contrib/fuzzystrmatch/sql/fuzzystrmatch.sql @@ -19,3 +19,48 @@ SELECT metaphone('GUMBO', 4); =20 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/fuz= zystrmatch/sql/fuzzystrmatch_utf8.sql new file mode 100644 index 0000000000..f42c01a1bb --- /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 =3D utf8; + +-- CREATE EXTENSION IF NOT EXISTS fuzzystrmatch; + +-- Accents +SELECT daitch_mokotoff('M=C3=BCller'); +SELECT daitch_mokotoff('Sch=C3=A4fer'); +SELECT daitch_mokotoff('Stra=C3=9Fburg'); +SELECT daitch_mokotoff('=C3=89regon'); + +-- Special characters added at https://www.jewishgen.org/InfoFiles/Soundex= .html +SELECT daitch_mokotoff('g=C4=85szczu'); +SELECT daitch_mokotoff('brz=C4=99czy'); +SELECT daitch_mokotoff('=C5=A3amas'); +SELECT daitch_mokotoff('=C8=9Bamas'); diff --git a/doc/src/sgml/fuzzystrmatch.sgml b/doc/src/sgml/fuzzystrmatch.s= gml index 382e54be91..08781778f8 100644 --- a/doc/src/sgml/fuzzystrmatch.sgml +++ b/doc/src/sgml/fuzzystrmatch.sgml @@ -241,4 +241,101 @@ test=3D# SELECT dmetaphone('gumbo'); =20 + + Daitch-Mokotoff Soundex + + + Compared to the American Soundex System implemented in the + soundex function, the major improvements of the + Daitch-Mokotoff Soundex System are: + + + + + Information is coded to the first six meaningful letters rather than + four. + + + + + The initial letter is coded rather than kept as is. + + + + + Where two consecutive letters have a single sound, they are coded as= a + single number. + + + + + When a letter or combination of letters may have two different sound= s, + it is double coded under the two different codes. + + + + + A letter or combination of letters maps into ten possible codes rath= er + than seven. + + + + + + + daitch_mokotoff + + + + The following function generates Daitch-Mokotoff soundex codes for matc= hing + of similar-sounding input: + + + +daitch_mokotoff(text source) returns text + + + + Since a Daitch-Mokotoff soundex code consists of only 6 digits, + source should be preferably a single word or name. + Any alternative soundex codes are separated by space, which makes the r= eturned + text suited for use in Full Text Search, see and + . + + + + Example: + + + +CREATE OR REPLACE FUNCTION soundex_name(v_name text) RETURNS text AS $$ + SELECT string_agg(daitch_mokotoff(n), ' ') + FROM regexp_split_to_table(v_name, '\s+') AS n +$$ LANGUAGE sql STRICT IMMUTABLE PARALLEL SAFE; + +CREATE OR REPLACE FUNCTION soundex_tsvector(v_name text) RETURNS tsvector = AS $$ + SELECT to_tsvector('simple', soundex_name(v_name)) +$$ LANGUAGE sql STRICT IMMUTABLE PARALLEL SAFE; + +CREATE OR REPLACE FUNCTION soundex_tsquery(v_name text) RETURNS tsquery AS= $$ + SELECT to_tsquery('simple', quote_literal(soundex_name(v_name))) +$$ LANGUAGE sql STRICT IMMUTABLE PARALLEL SAFE; + +-- Note that searches could be more efficient with the tsvector in a separ= ate column +-- (no recalculation on table row recheck). +CREATE TABLE s (nm text); +CREATE INDEX ix_s_txt ON s USING gin (soundex_tsvector(nm)) WITH (fastupda= te =3D off); + +INSERT INTO s VALUES ('John Doe'); +INSERT INTO s VALUES ('Jane Roe'); +INSERT INTO s VALUES ('Public John Q.'); +INSERT INTO s VALUES ('George Best'); + +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john'); +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('jane doe'); +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john public= '); +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('besst, gior= gio'); + + + --=-=-=--