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 1mwlXE-0007vI-L5 for pgsql-hackers@arkaria.postgresql.org; Mon, 13 Dec 2021 13:38:33 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1mwlXD-0004GK-3M for pgsql-hackers@arkaria.postgresql.org; Mon, 13 Dec 2021 13:38:31 +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 1mwlXC-0004GB-Ic for pgsql-hackers@lists.postgresql.org; Mon, 13 Dec 2021 13:38:30 +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 1mwlX8-0007VF-B7 for pgsql-hackers@lists.postgresql.org; Mon, 13 Dec 2021 13:38:29 +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 1BDDcM3w025439 for ; Mon, 13 Dec 2021 14:38:23 +0100 DKIM-Filter: OpenDKIM Filter v2.11.0 sid.nimrod.no 1BDDcM3w025439 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nimrod.no; s=n20181209; t=1639402703; bh=EZxdnXWk1PEsIiLQ7IzmOrda+W4se72uq1uNzbiqnpg=; h=From:To:Subject:References:Date:In-Reply-To:From; b=mCWtBRDwsTcZ+5zklYEzeSFPuCzYoryu5+YoNG03VI2aJrcFfJspuend8ZSqfC1m7 ZIdGV/TSASzkdJff7v24oMLUPhTXsi/5pDI1mSeEqPjVtzgze8+Q4UbrMn7vmWDmFC 8nXm8PzSer1sTxEebcaQlvLGGqlKFWlh5ZqSxW0nh6ArTKKa71OC2dDm9/Zsre1/ey QSrp3QwFppe5aOCRkI3mdnGVjX5i/i83JDCfX7KS94Cc8RkWwG4MFME081XOq+SEyc AfsJ+x6rEMwVtd++vzoom7TWZZdboXNq5TI/QSJrgF3T3Jl3OvLWfP9vYl9mA9Zj8k b+qGyU19HqJNg== From: Dag Lem To: PostgreSQL Hackers Subject: Re: daitch_mokotoff module Organization: Nimrod References: Date: Mon, 13 Dec 2021 14:38:22 +0100 In-Reply-To: (Dag Lem's message of "Fri, 03 Dec 2021 21:07:29 +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 Please find attached an updated patch, with the following fixes: * Replaced remaining malloc/free with palloc/pfree. * Made "make check" pass. * Updated notes on other implementations. Best regards Dag Lem --=-=-= Content-Type: text/x-patch; charset=utf-8 Content-Disposition: inline; filename=v2-daitch_mokotoff.patch Content-Transfer-Encoding: quoted-printable diff --git a/contrib/Makefile b/contrib/Makefile index 87bf87ab90..5e1111a729 100644 --- a/contrib/Makefile +++ b/contrib/Makefile @@ -14,6 +14,7 @@ SUBDIRS =3D \ btree_gist \ citext \ cube \ + daitch_mokotoff \ dblink \ dict_int \ dict_xsyn \ diff --git a/contrib/daitch_mokotoff/Makefile b/contrib/daitch_mokotoff/Mak= efile new file mode 100644 index 0000000000..baec5e31d4 --- /dev/null +++ b/contrib/daitch_mokotoff/Makefile @@ -0,0 +1,25 @@ +# contrib/daitch_mokotoff/Makefile + +MODULE_big =3D daitch_mokotoff +OBJS =3D \ + $(WIN32RES) \ + daitch_mokotoff.o + +EXTENSION =3D daitch_mokotoff +DATA =3D daitch_mokotoff--1.0.sql +PGFILEDESC =3D "daitch_mokotoff - Daitch-Mokotoff Soundex System" + +HEADERS =3D daitch_mokotoff.h + +REGRESS =3D daitch_mokotoff + +ifdef USE_PGXS +PG_CONFIG =3D pg_config +PGXS :=3D $(shell $(PG_CONFIG) --pgxs) +include $(PGXS) +else +subdir =3D contrib/daitch_mokotoff +top_builddir =3D ../.. +include $(top_builddir)/src/Makefile.global +include $(top_srcdir)/contrib/contrib-global.mk +endif diff --git a/contrib/daitch_mokotoff/daitch_mokotoff--1.0.sql b/contrib/dai= tch_mokotoff/daitch_mokotoff--1.0.sql new file mode 100644 index 0000000000..0b5a643175 --- /dev/null +++ b/contrib/daitch_mokotoff/daitch_mokotoff--1.0.sql @@ -0,0 +1,8 @@ +/* contrib/daitch_mokotoff/daitch_mokotoff--1.0.sql */ + +-- complain if script is sourced in psql, rather than via CREATE EXTENSION +\echo Use "CREATE EXTENSION daitch_mokotoff" 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/daitch_mokotoff/daitch_mokotoff.c b/contrib/daitch_mok= otoff/daitch_mokotoff.c new file mode 100644 index 0000000000..a7f1fd8541 --- /dev/null +++ b/contrib/daitch_mokotoff/daitch_mokotoff.c @@ -0,0 +1,549 @@ +/* + * 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: + * + * - "J" is considered a vowel in dmlat.php + * - The official rules for "RS" are commented out in dmlat.php + * - Identical code digits for adjacent letters are not collapsed correctl= y in + * dmsoundex.php when double digit codes are involved. E.g. "BESST" yiel= ds + * 744300 instead of 743000 as for "BEST". + * - "Y" is not considered a vowel in DaitchMokotoffSoundex.java + * - Both dmlat.php and dmrules.txt have the same unofficial rules for "UE= ". + * - Coding of MN/NM + M/N differs between dmsoundex.php and DaitchMokotof= fSoundex.java + * - No other known implementation yields the correct set of codes for e.g. + * "CJC" (550000 540000 545000 450000 400000 440000). + * + * Permission to use, copy, modify, and distribute this software and its + * documentation for any purpose, without fee, and without a written 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 "daitch_mokotoff.h" + +#ifndef DM_MAIN + +#include "postgres.h" +#include "utils/builtins.h" +#include "mb/pg_wchar.h" + +#else /* DM_MAIN */ + +#include +#include + +void * +palloc(size_t size) +{ + void *ptr; + + ptr =3D malloc(size); + + if (ptr =3D=3D NULL) + { + fprintf(stderr, "Unable to allocate memory\n"); + exit(EXIT_FAILURE); + } + + return ptr; +} + +#define pfree free + +#endif /* DM_MAIN */ + +#include +#include + + +/* Internal C implementation */ +static char *_daitch_mokotoff(char *word, char *soundex, size_t n); + + +#ifndef DM_MAIN + +PG_MODULE_MAGIC; + +PG_FUNCTION_INFO_V1(daitch_mokotoff); +Datum +daitch_mokotoff(PG_FUNCTION_ARGS) +{ + text *arg =3D PG_GETARG_TEXT_PP(0); + char *string, + *tmp_soundex; + text *soundex; + + /* + * The maximum theoretical soundex size is several KB, however in practice + * anything but contrived synthetic inputs will yield a soundex size of + * less than 100 bytes. We thus allocate and free a temporary work buffer, + * and return only the actual soundex result. + */ + string =3D pg_server_to_any(text_to_cstring(arg), VARSIZE_ANY_EXHDR(arg),= PG_UTF8); + tmp_soundex =3D palloc(DM_MAX_SOUNDEX_CHARS); + + _daitch_mokotoff(string, tmp_soundex, DM_MAX_SOUNDEX_CHARS); + + soundex =3D cstring_to_text(pg_any_to_server(tmp_soundex, strlen(tmp_soun= dex), PG_UTF8)); + pfree(tmp_soundex); + + PG_RETURN_TEXT_P(soundex); +} + +#endif /* DM_MAIN */ + + +typedef dm_node dm_nodes[DM_MAX_NODES]; +typedef dm_node * dm_leaves[DM_MAX_LEAVES]; + + +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'}, + .next_nodes =3D {NULL} +}; + + +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->is_leaf =3D 0; + node->last_update =3D last_update; + } +} + + +static void +add_next_code_digit(dm_node * node, char code_digit) +{ + 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; + } +} + + +static void +set_leaf(dm_leaves leaves_next, int *num_leaves_next, dm_node * node) +{ + if (!node->is_leaf) + { + node->is_leaf =3D 1; + leaves_next[(*num_leaves_next)++] =3D node; + } +} + + +static dm_node * find_or_create_node(dm_nodes nodes, int *num_nodes, dm_no= de * node, char code_digit) +{ + dm_node **next_nodes; + dm_node *next_node; + + for (next_nodes =3D node->next_nodes; (next_node =3D *next_nodes); next_n= odes++) + { + if (next_node->code_digit =3D=3D code_digit) + { + return next_node; + } + } + + next_node =3D &nodes[(*num_nodes)++]; + *next_nodes =3D next_node; + + *next_node =3D start_node; + memcpy(next_node->soundex, node->soundex, sizeof(next_node->soundex)); + next_node->soundex_length =3D node->soundex_length; + next_node->soundex[next_node->soundex_length++] =3D code_digit; + next_node->code_digit =3D code_digit; + + return next_node; +} + + +static int +update_node(dm_nodes nodes, dm_node * node, int *num_nodes, dm_leaves leav= es_next, int *num_leaves_next, int char_number, char next_code_digit, char = next_code_digit_2) +{ + int i; + int num_dirty_nodes =3D 0; + dm_node *dirty_nodes[2]; + + initialize_node(node, char_number); + + if (node->soundex_length =3D=3D DM_MAX_CODE_DIGITS) + { + /* Keep completed soundex code. */ + set_leaf(leaves_next, num_leaves_next, node); + return 0; + } + + if (next_code_digit =3D=3D 'X' || + 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' && + (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_node(nodes, num_nodes, node, next_code_digit); + initialize_node(node, char_number); + 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_digit); + + if (next_code_digit_2) + { + update_node(nodes, dirty_nodes[i], num_nodes, leaves_next, num_leaves_n= ext, char_number, next_code_digit_2, '\0'); + } + else + { + set_leaf(leaves_next, num_leaves_next, dirty_nodes[i]); + } + } + + return 1; +} + + +static int +update_leaves(dm_nodes nodes, int *num_nodes, dm_leaves leaves[2], int *ix= _leaves, int *num_leaves, int char_number, dm_codes codes) +{ + int i, + j; + char *code; + int num_leaves_next =3D 0; + int ix_leaves_next =3D (*ix_leaves + 1) % 2; + int finished =3D 1; + + for (i =3D 0; i < *num_leaves; i++) + { + dm_node *node =3D leaves[*ix_leaves][i]; + + /* One or two alternate code sequences. */ + for (j =3D 0; j < 2 && (code =3D codes[j]) && code[0]; j++) + { + /* One or two sequential code digits. */ + if (update_node(nodes, node, num_nodes, leaves[ix_leaves_next], &num_le= aves_next, char_number, code[0], code[1])) + { + finished =3D 0; + } + } + } + + *ix_leaves =3D ix_leaves_next; + *num_leaves =3D num_leaves_next; + + return finished; +} + + +static const char tr_accents_iso8859_1[] =3D +/* +"=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" +*/ +"AAAAAAECEEEEIIIIDNOOOOO*OUUUUYDsaaaaaaeceeeeiiiidnooooo/ouuuuydy"; + +static char +unaccent_iso8859_1(unsigned char c) +{ + return c >=3D 192 ? tr_accents_iso8859_1[c - 192] : c; +} + + +/* Convert an UTF-8 character to ISO-8859-1. + * Unconvertable characters are returned as '?'. + * NB! Beware of the domain specific conversion of =C4=84, =C4=98, and =C5= =A2/=C8=9A. + */ +static char +utf8_to_iso8859_1(char *str, int *len) +{ + const char unknown =3D '?'; + unsigned char c; + unsigned int code_point; + + *len =3D 1; + c =3D (unsigned char) str[0]; + if (c < 0x80) + { + /* ASCII code point. */ + return c; + } + else if (c < 0xE0) + { + /* Two-byte character. */ + if (!str[1]) + { + /* The UTF-8 character is cut short (invalid code point). */ + return unknown; + } + *len =3D 2; + code_point =3D ((c & 0x1F) << 6) | (str[1] & 0x3F); + if (code_point < 0x100) + { + /* ISO-8859-1 code point. */ + return code_point; + } + else if (code_point =3D=3D 0x0104 || code_point =3D=3D 0x0105) + { + /* =C4=84/=C4=85 */ + return '['; + } + else if (code_point =3D=3D 0x0118 || code_point =3D=3D 0x0119) + { + /* =C4=98/=C4=99 */ + return '\\'; + } + else if (code_point =3D=3D 0x0162 || code_point =3D=3D 0x0163 || + code_point =3D=3D 0x021A || code_point =3D=3D 0x021B) + { + /* =C5=A2/=C5=A3 or =C8=9A/=C8=9B */ + return ']'; + } + else + { + return unknown; + } + } + else if (c < 0xF0) + { + /* Three-byte character. */ + if (!str[2]) + { + /* The UTF-8 character is cut short (invalid code point). */ + *len =3D 2; + } + else + { + *len =3D 3; + } + return unknown; + } + else + { + /* Four-byte character. */ + if (!str[3]) + { + /* The UTF-8 character is cut short (invalid code point). */ + *len =3D 3; + } + else + { + *len =3D 4; + } + return unknown; + } +} + + +static char +read_char(char *str, int *len) +{ + return toupper(unaccent_iso8859_1(utf8_to_iso8859_1(str, len))); +} + + +static char +read_valid_char(char *str, int *len) +{ + int c; + int i, + ilen; + + for (i =3D 0, ilen =3D 0; (c =3D read_char(&str[i], &ilen)) && (c < 'A' |= | c > ']'); i +=3D ilen) + { + } + + *len =3D i + ilen; + return c; +} + + +static char * +_daitch_mokotoff(char *word, char *soundex, size_t n) +{ + int c, + cmp; + int i, + ilen, + i_ok, + j, + jlen, + k; + int first_letter =3D 1; + int ix_leaves =3D 0; + int num_nodes =3D 0, + num_leaves =3D 0; + dm_letter *letter, + *letters; + dm_codes *codes_ok, + codes; + + dm_node *nodes =3D palloc(sizeof(dm_nodes)); + dm_leaves *leaves =3D palloc(2 * sizeof(dm_leaves)); + + /* Starting point. */ + nodes[num_nodes++] =3D start_node; + leaves[ix_leaves][num_leaves++] =3D &nodes[0]; + + for (i =3D 0; (c =3D read_valid_char(&word[i], &ilen)); i +=3D ilen) + { + /* First letter in sequence. */ + letter =3D &letter_[c - 'A']; + codes_ok =3D letter->codes; + i_ok =3D i; + + /* Subsequent letters. */ + for (j =3D i + ilen; (letters =3D letter->letters) && (c =3D read_valid_= char(&word[j], &jlen)); j +=3D jlen) + { + for (k =3D 0; (cmp =3D letters[k].letter); k++) + { + if (cmp =3D=3D c) + { + /* Coding for letter found. */ + break; + } + } + if (!cmp) + { + /* The sequence of letters has no coding. */ + break; + } + + letter =3D &letters[k]; + if (letter->codes) + { + codes_ok =3D letter->codes; + i_ok =3D j; + ilen =3D jlen; + } + } + + /* Determine which code to use. */ + if (first_letter) + { + /* This is the first letter. */ + j =3D 0; + first_letter =3D 0; + } + else if ((c =3D read_valid_char(&word[i_ok + ilen], &jlen)) && strchr(DM= _VOWELS, c)) + { + /* The next letter is a vowel. */ + j =3D 1; + } + else + { + /* All other cases. */ + j =3D 2; + } + memcpy(codes, codes_ok[j], sizeof(codes)); + + /* Update leaves. */ + if (update_leaves(nodes, &num_nodes, leaves, &ix_leaves, &num_leaves, i,= codes)) + { + /* All soundex codes are completed to six digits. */ + break; + } + + /* Prepare for next letter sequence. */ + i =3D i_ok; + } + + /* Concatenate all generated soundex codes. */ + for (i =3D 0, j =3D 0; i < num_leaves && j + DM_MAX_CODE_DIGITS + 1 <=3D = n; i++, j +=3D DM_MAX_CODE_DIGITS + 1) + { + memcpy(&soundex[j], leaves[ix_leaves][i]->soundex, DM_MAX_CODE_DIGITS + = 1); + } + + /* Terminate string. */ + soundex[j - (j !=3D 0)] =3D '\0'; + + pfree(leaves); + pfree(nodes); + + return soundex; +} + + +#ifdef DM_MAIN + +/* For testing */ + +int +main(int argc, char **argv) +{ + char *soundex; + + if (argc !=3D 2) + { + fprintf(stderr, "Usage: %s string\n", argv[0]); + return -1; + } + + soundex =3D palloc(DM_MAX_SOUNDEX_CHARS); + + _daitch_mokotoff(argv[1], soundex, DM_MAX_SOUNDEX_CHARS); + + printf("%s\n", soundex); + pfree(soundex); + + return 0; +} + +#endif diff --git a/contrib/daitch_mokotoff/daitch_mokotoff.control b/contrib/dait= ch_mokotoff/daitch_mokotoff.control new file mode 100644 index 0000000000..c5aed8e46e --- /dev/null +++ b/contrib/daitch_mokotoff/daitch_mokotoff.control @@ -0,0 +1,5 @@ +# daitch_mokotoff extension +comment =3D 'Daitch-Mokotoff Soundex System' +default_version =3D '1.0' +module_pathname =3D '$libdir/daitch_mokotoff' +relocatable =3D true diff --git a/contrib/daitch_mokotoff/daitch_mokotoff.h b/contrib/daitch_mok= otoff/daitch_mokotoff.h new file mode 100644 index 0000000000..8fcb98f1cf --- /dev/null +++ b/contrib/daitch_mokotoff/daitch_mokotoff.h @@ -0,0 +1,1110 @@ +/* + * Types and lookup tables for Daitch-Mokotoff Soundex + * + * Copyright (c) 2021 Finance Norway + * Author: Dag Lem + * + * 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. + */ + +#include + +#define DM_MAX_CODE_DIGITS 6 +#define DM_MAX_ALTERNATE_CODES 5 +#define DM_MAX_NODES 1564 +#define DM_MAX_LEAVES 1250 +#define DM_MAX_SOUNDEX_CHARS (DM_MAX_NODES*(DM_MAX_CODE_DIGITS + 1)) +#define DM_VOWELS "AEIOUY" + +typedef char dm_code[2 + 1]; /* One or two sequential code digits + NUL */ +typedef dm_code dm_codes[2]; /* One or two alternate code sequences */ + +struct dm_letter +{ + char letter; + struct dm_letter *letters; + dm_codes *codes; +}; + +struct dm_node +{ + int soundex_length; + char soundex[DM_MAX_CODE_DIGITS + 1]; + int is_leaf; + int last_update; + char code_digit; + + /* + * One or two alternate code digits leading to this node - repeated code + * digits and 'X' lead back to the same node. + */ + char prev_code_digits[2]; + char next_code_digits[2]; + struct dm_node *next_nodes[DM_MAX_ALTERNATE_CODES + 1]; +}; + +typedef struct dm_letter dm_letter; +typedef struct dm_node dm_node; + +static dm_codes codes_0_1_X[] =3D +{ + { + "0" + }, + { + "1" + }, + { + "X" + } +}; +static dm_codes codes_0_7_X[] =3D +{ + { + "0" + }, + { + "7" + }, + { + "X" + } +}; +static dm_codes codes_0_X_X[] =3D +{ + { + "0" + }, + { + "X" + }, + { + "X" + } +}; +static dm_codes codes_1_1_X[] =3D +{ + { + "1" + }, + { + "1" + }, + { + "X" + } +}; +static dm_codes codes_1_X_X[] =3D +{ + { + "1" + }, + { + "X" + }, + { + "X" + } +}; +static dm_codes codes_1or4_Xor4_Xor4[] =3D +{ + { + "1", "4" + }, + { + "X", "4" + }, + { + "X", "4" + } +}; +static dm_codes codes_2_43_43[] =3D +{ + { + "2" + }, + { + "43" + }, + { + "43" + } +}; +static dm_codes codes_2_4_4[] =3D +{ + { + "2" + }, + { + "4" + }, + { + "4" + } +}; +static dm_codes codes_3_3_3[] =3D +{ + { + "3" + }, + { + "3" + }, + { + "3" + } +}; +static dm_codes codes_3or4_3or4_3or4[] =3D +{ + { + "3", "4" + }, + { + "3", "4" + }, + { + "3", "4" + } +}; +static dm_codes codes_4_4_4[] =3D +{ + { + "4" + }, + { + "4" + }, + { + "4" + } +}; +static dm_codes codes_5_54_54[] =3D +{ + { + "5" + }, + { + "54" + }, + { + "54" + } +}; +static dm_codes codes_5_5_5[] =3D +{ + { + "5" + }, + { + "5" + }, + { + "5" + } +}; +static dm_codes codes_5_5_X[] =3D +{ + { + "5" + }, + { + "5" + }, + { + "X" + } +}; +static dm_codes codes_5or45_5or45_5or45[] =3D +{ + { + "5", "45" + }, + { + "5", "45" + }, + { + "5", "45" + } +}; +static dm_codes codes_5or4_5or4_5or4[] =3D +{ + { + "5", "4" + }, + { + "5", "4" + }, + { + "5", "4" + } +}; +static dm_codes codes_66_66_66[] =3D +{ + { + "66" + }, + { + "66" + }, + { + "66" + } +}; +static dm_codes codes_6_6_6[] =3D +{ + { + "6" + }, + { + "6" + }, + { + "6" + } +}; +static dm_codes codes_7_7_7[] =3D +{ + { + "7" + }, + { + "7" + }, + { + "7" + } +}; +static dm_codes codes_8_8_8[] =3D +{ + { + "8" + }, + { + "8" + }, + { + "8" + } +}; +static dm_codes codes_94or4_94or4_94or4[] =3D +{ + { + "94", "4" + }, + { + "94", "4" + }, + { + "94", "4" + } +}; +static dm_codes codes_9_9_9[] =3D +{ + { + "9" + }, + { + "9" + }, + { + "9" + } +}; +static dm_codes codes_X_X_6orX[] =3D +{ + { + "X" + }, + { + "X" + }, + { + "6", "X" + } +}; + +static dm_letter letter_A[] =3D +{ + { + 'I', NULL, codes_0_1_X + }, + { + 'J', NULL, codes_0_1_X + }, + { + 'U', NULL, codes_0_7_X + }, + { + 'Y', NULL, codes_0_1_X + }, + { + '\0' + } +}; +static dm_letter letter_CH[] =3D +{ + { + 'S', NULL, codes_5_54_54 + }, + { + '\0' + } +}; +static dm_letter letter_CS[] =3D +{ + { + 'Z', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_CZ[] =3D +{ + { + 'S', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_C[] =3D +{ + { + 'H', letter_CH, codes_5or4_5or4_5or4 + }, + { + 'K', NULL, codes_5or45_5or45_5or45 + }, + { + 'S', letter_CS, codes_4_4_4 + }, + { + 'Z', letter_CZ, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_DR[] =3D +{ + { + 'S', NULL, codes_4_4_4 + }, + { + 'Z', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_DS[] =3D +{ + { + 'H', NULL, codes_4_4_4 + }, + { + 'Z', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_DZ[] =3D +{ + { + 'H', NULL, codes_4_4_4 + }, + { + 'S', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_D[] =3D +{ + { + 'R', letter_DR, NULL + }, + { + 'S', letter_DS, codes_4_4_4 + }, + { + 'T', NULL, codes_3_3_3 + }, + { + 'Z', letter_DZ, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_E[] =3D +{ + { + 'I', NULL, codes_0_1_X + }, + { + 'J', NULL, codes_0_1_X + }, + { + 'U', NULL, codes_1_1_X + }, + { + 'Y', NULL, codes_0_1_X + }, + { + '\0' + } +}; +static dm_letter letter_F[] =3D +{ + { + 'B', NULL, codes_7_7_7 + }, + { + '\0' + } +}; +static dm_letter letter_I[] =3D +{ + { + 'A', NULL, codes_1_X_X + }, + { + 'E', NULL, codes_1_X_X + }, + { + 'O', NULL, codes_1_X_X + }, + { + 'U', NULL, codes_1_X_X + }, + { + '\0' + } +}; +static dm_letter letter_K[] =3D +{ + { + 'H', NULL, codes_5_5_5 + }, + { + 'S', NULL, codes_5_54_54 + }, + { + '\0' + } +}; +static dm_letter letter_M[] =3D +{ + { + 'N', NULL, codes_66_66_66 + }, + { + '\0' + } +}; +static dm_letter letter_N[] =3D +{ + { + 'M', NULL, codes_66_66_66 + }, + { + '\0' + } +}; +static dm_letter letter_O[] =3D +{ + { + 'I', NULL, codes_0_1_X + }, + { + 'J', NULL, codes_0_1_X + }, + { + 'Y', NULL, codes_0_1_X + }, + { + '\0' + } +}; +static dm_letter letter_P[] =3D +{ + { + 'F', NULL, codes_7_7_7 + }, + { + 'H', NULL, codes_7_7_7 + }, + { + '\0' + } +}; +static dm_letter letter_R[] =3D +{ + { + 'S', NULL, codes_94or4_94or4_94or4 + }, + { + 'Z', NULL, codes_94or4_94or4_94or4 + }, + { + '\0' + } +}; +static dm_letter letter_SCHTC[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SCHTSC[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SCHTS[] =3D +{ + { + 'C', letter_SCHTSC, NULL + }, + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SCHT[] =3D +{ + { + 'C', letter_SCHTC, NULL + }, + { + 'S', letter_SCHTS, NULL + }, + { + '\0' + } +}; +static dm_letter letter_SCH[] =3D +{ + { + 'D', NULL, codes_2_43_43 + }, + { + 'T', letter_SCHT, codes_2_43_43 + }, + { + '\0' + } +}; +static dm_letter letter_SC[] =3D +{ + { + 'H', letter_SCH, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SHC[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SHTC[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SHTS[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SHT[] =3D +{ + { + 'C', letter_SHTC, NULL + }, + { + 'S', letter_SHTS, NULL + }, + { + '\0' + } +}; +static dm_letter letter_SH[] =3D +{ + { + 'C', letter_SHC, NULL + }, + { + 'D', NULL, codes_2_43_43 + }, + { + 'T', letter_SHT, codes_2_43_43 + }, + { + '\0' + } +}; +static dm_letter letter_STC[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_STR[] =3D +{ + { + 'S', NULL, codes_2_4_4 + }, + { + 'Z', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_STSC[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_STS[] =3D +{ + { + 'C', letter_STSC, NULL + }, + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_ST[] =3D +{ + { + 'C', letter_STC, NULL + }, + { + 'R', letter_STR, NULL + }, + { + 'S', letter_STS, NULL + }, + { + '\0' + } +}; +static dm_letter letter_SZC[] =3D +{ + { + 'S', NULL, codes_2_4_4 + }, + { + 'Z', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_SZ[] =3D +{ + { + 'C', letter_SZC, NULL + }, + { + 'D', NULL, codes_2_43_43 + }, + { + 'T', NULL, codes_2_43_43 + }, + { + '\0' + } +}; +static dm_letter letter_S[] =3D +{ + { + 'C', letter_SC, codes_2_4_4 + }, + { + 'D', NULL, codes_2_43_43 + }, + { + 'H', letter_SH, codes_4_4_4 + }, + { + 'T', letter_ST, codes_2_43_43 + }, + { + 'Z', letter_SZ, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TC[] =3D +{ + { + 'H', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TR[] =3D +{ + { + 'S', NULL, codes_4_4_4 + }, + { + 'Z', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TSC[] =3D +{ + { + 'H', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TS[] =3D +{ + { + 'C', letter_TSC, NULL + }, + { + 'H', NULL, codes_4_4_4 + }, + { + 'Z', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TTC[] =3D +{ + { + 'H', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TTSC[] =3D +{ + { + 'H', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TTS[] =3D +{ + { + 'C', letter_TTSC, NULL + }, + { + 'Z', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TT[] =3D +{ + { + 'C', letter_TTC, NULL + }, + { + 'S', letter_TTS, codes_4_4_4 + }, + { + 'Z', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_TZ[] =3D +{ + { + 'S', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_T[] =3D +{ + { + 'C', letter_TC, codes_4_4_4 + }, + { + 'H', NULL, codes_3_3_3 + }, + { + 'R', letter_TR, NULL + }, + { + 'S', letter_TS, codes_4_4_4 + }, + { + 'T', letter_TT, NULL + }, + { + 'Z', letter_TZ, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_U[] =3D +{ + { + 'E', NULL, codes_0_X_X + }, + { + 'I', NULL, codes_0_1_X + }, + { + 'J', NULL, codes_0_1_X + }, + { + 'Y', NULL, codes_0_1_X + }, + { + '\0' + } +}; +static dm_letter letter_ZDZ[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_ZD[] =3D +{ + { + 'Z', letter_ZDZ, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_ZHDZ[] =3D +{ + { + 'H', NULL, codes_2_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_ZHD[] =3D +{ + { + 'Z', letter_ZHDZ, NULL + }, + { + '\0' + } +}; +static dm_letter letter_ZH[] =3D +{ + { + 'D', letter_ZHD, codes_2_43_43 + }, + { + '\0' + } +}; +static dm_letter letter_ZSC[] =3D +{ + { + 'H', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_ZS[] =3D +{ + { + 'C', letter_ZSC, NULL + }, + { + 'H', NULL, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_Z[] =3D +{ + { + 'D', letter_ZD, codes_2_43_43 + }, + { + 'H', letter_ZH, codes_4_4_4 + }, + { + 'S', letter_ZS, codes_4_4_4 + }, + { + '\0' + } +}; +static dm_letter letter_[] =3D +{ + { + 'A', letter_A, codes_0_X_X + }, + { + 'B', NULL, codes_7_7_7 + }, + { + 'C', letter_C, codes_5or4_5or4_5or4 + }, + { + 'D', letter_D, codes_3_3_3 + }, + { + 'E', letter_E, codes_0_X_X + }, + { + 'F', letter_F, codes_7_7_7 + }, + { + 'G', NULL, codes_5_5_5 + }, + { + 'H', NULL, codes_5_5_X + }, + { + 'I', letter_I, codes_0_X_X + }, + { + 'J', NULL, codes_1or4_Xor4_Xor4 + }, + { + 'K', letter_K, codes_5_5_5 + }, + { + 'L', NULL, codes_8_8_8 + }, + { + 'M', letter_M, codes_6_6_6 + }, + { + 'N', letter_N, codes_6_6_6 + }, + { + 'O', letter_O, codes_0_X_X + }, + { + 'P', letter_P, codes_7_7_7 + }, + { + 'Q', NULL, codes_5_5_5 + }, + { + 'R', letter_R, codes_9_9_9 + }, + { + 'S', letter_S, codes_4_4_4 + }, + { + 'T', letter_T, codes_3_3_3 + }, + { + 'U', letter_U, codes_0_X_X + }, + { + 'V', NULL, codes_7_7_7 + }, + { + 'W', NULL, codes_7_7_7 + }, + { + 'X', NULL, codes_5_54_54 + }, + { + 'Y', NULL, codes_1_X_X + }, + { + 'Z', letter_Z, codes_4_4_4 + }, + { + 'a', NULL, codes_X_X_6orX + }, + { + 'e', NULL, codes_X_X_6orX + }, + { + 't', NULL, codes_3or4_3or4_3or4 + }, + { + '\0' + } +}; diff --git a/contrib/daitch_mokotoff/daitch_mokotoff_header.pl b/contrib/da= itch_mokotoff/daitch_mokotoff_header.pl new file mode 100755 index 0000000000..26e67fe5df --- /dev/null +++ b/contrib/daitch_mokotoff/daitch_mokotoff_header.pl @@ -0,0 +1,274 @@ +#!/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; + +# 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 can never yield more than two alternate codes, and = is not considered here. + for my $c (@codes[1..2]) { + if (@$c > 1) { + for my $i (0..1) { + my ($a, $b) =3D (substr($c->[$i], -1, 1), substr($c->[($i + 1)%2], 0, = 1)); + $alternates{$a}{$b} =3D 1 if $a ne $b; + } + } + } + my $key =3D "codes_" . join("_", map { join("or", @$_) } @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); + +# Find the maximum number of alternate codes in one position. +my $alt_x =3D $alternates{"X"}; +while (my ($k, $v) =3D each %alternates) { + if (defined delete $v->{"X"}) { + for my $x (keys %$alt_x) { + $v->{$x} =3D 1; + } + } +} +my $max_alt =3D (reverse sort (2, map { scalar keys %$_ } values %alternat= es))[0]; + +# The maximum number of nodes and leaves in the soundex tree. +# These are safe estimates, but in practice somewhat higher than the actua= l maximums. +# Note that the first character can never yield more than two alternate co= des, +# hence the calculations are performed as sums of two subtrees. +my $digits =3D 6; +# Number of nodes (sum of geometric progression). +my $max_nodes =3D 2 + 2*(1 - $max_alt**($digits - 1))/(1 - $max_alt); +# Number of leaves (exponential of base number). +my $max_leaves =3D 2*$max_alt**($digits - 2); + +print < + * + * 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. + */ + +#include + +#define DM_MAX_CODE_DIGITS $digits +#define DM_MAX_ALTERNATE_CODES $max_alt +#define DM_MAX_NODES $max_nodes +#define DM_MAX_LEAVES $max_leaves +#define DM_MAX_SOUNDEX_CHARS (DM_MAX_NODES*(DM_MAX_CODE_DIGITS + 1)) +#define DM_VOWELS "AEIOUY" + +typedef char dm_code[2 + 1]; /* One or two sequential code digits + NUL */ +typedef dm_code dm_codes[2]; /* One or two alternate code sequences */ + +struct dm_letter +{ + char letter; + struct dm_letter *letters; + dm_codes *codes; +}; + +struct dm_node +{ + int soundex_length; + char soundex[DM_MAX_CODE_DIGITS + 1]; + int is_leaf; + int last_update; + char code_digit; + + /* + * One or two alternate code digits leading to this node - repeated code + * digits and 'X' lead back to the same node. + */ + char prev_code_digits[2]; + char next_code_digits[2]; + struct dm_node *next_nodes[DM_MAX_ALTERNATE_CODES + 1]; +}; + +typedef struct dm_letter dm_letter; +typedef struct dm_node dm_node; + +EOF + +for my $key (sort keys %codes) { + print "static dm_codes $key\[\] =3D\n{\n" . $codes{$key} . "\n};\n"; +} + +print "\n"; + +sub hash2code { + my ($ref, $letter) =3D @_; + + my @letters =3D (); + + my $h =3D $ref->[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 "static dm_letter letter_$letter\[\] =3D\n{\n"; + for (@letters) { + print "$_,\n"; + } + print "\t{\n\t\t'\\0'\n\t}\n"; + print "};\n"; +} + +hash2code($table, ''); + + +# Table adapted from https://www.jewishgen.org/InfoFiles/Soundex.html +# +# X =3D NC (not coded) +# +# Note that the following letters are coded with substitute 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) +# + +__DATA__ +AI,AJ,AY 0,1,X +AU 0,7,X +a X,X,6|X +A 0,X,X +B 7,7,7 +CHS 5,54,54 +CH 5|4,5|4,5|4 +CK 5|45,5|45,5|45 +CZ,CS,CSZ,CZS 4,4,4 +C 5|4,5|4,5|4 +DRZ,DRS 4,4,4 +DS,DSH,DSZ 4,4,4 +DZ,DZH,DZS 4,4,4 +D,DT 3,3,3 +EI,EJ,EY 0,1,X +EU 1,1,X +e X,X,6|X +E 0,X,X +FB 7,7,7 +F 7,7,7 +G 5,5,5 +H 5,5,X +IA,IE,IO,IU 1,X,X +I 0,X,X +J 1|4,X|4,X|4 +KS 5,54,54 +KH 5,5,5 +K 5,5,5 +L 8,8,8 +MN 66,66,66 +M 6,6,6 +NM 66,66,66 +N 6,6,6 +OI,OJ,OY 0,1,X +O 0,X,X +P,PF,PH 7,7,7 +Q 5,5,5 +RZ,RS 94|4,94|4,94|4 +R 9,9,9 +SCHTSCH,SCHTSH,SCHTCH 2,4,4 +SCH 4,4,4 +SHTCH,SHCH,SHTSH 2,4,4 +SHT,SCHT,SCHD 2,43,43 +SH 4,4,4 +STCH,STSCH,SC 2,4,4 +STRZ,STRS,STSH 2,4,4 +ST 2,43,43 +SZCZ,SZCS 2,4,4 +SZT,SHD,SZD,SD 2,43,43 +SZ 4,4,4 +S 4,4,4 +TCH,TTCH,TTSCH 4,4,4 +TH 3,3,3 +TRZ,TRS 4,4,4 +TSCH,TSH 4,4,4 +TS,TTS,TTSZ,TC 4,4,4 +TZ,TTZ,TZS,TSZ 4,4,4 +t 3|4,3|4,3|4 +T 3,3,3 +UI,UJ,UY 0,1,X +U,UE 0,X,X +V 7,7,7 +W 7,7,7 +X 5,54,54 +Y 1,X,X +ZDZ,ZDZH,ZHDZH 2,4,4 +ZD,ZHD 2,43,43 +ZH,ZS,ZSCH,ZSH 4,4,4 +Z 4,4,4 diff --git a/contrib/daitch_mokotoff/expected/daitch_mokotoff.out b/contrib= /daitch_mokotoff/expected/daitch_mokotoff.out new file mode 100644 index 0000000000..57825aeb99 --- /dev/null +++ b/contrib/daitch_mokotoff/expected/daitch_mokotoff.out @@ -0,0 +1,472 @@ +CREATE EXTENSION daitch_mokotoff; +-- https://www.jewishgen.org/InfoFiles/Soundex.html +SELECT daitch_mokotoff('GOLDEN'); + daitch_mokotoff=20 +----------------- + 583600 +(1 row) + +SELECT daitch_mokotoff('Alpert'); + daitch_mokotoff=20 +----------------- + 087930 +(1 row) + +SELECT daitch_mokotoff('Breuer'); + daitch_mokotoff=20 +----------------- + 791900 +(1 row) + +SELECT daitch_mokotoff('Freud'); + daitch_mokotoff=20 +----------------- + 793000 +(1 row) + +SELECT daitch_mokotoff('Haber'); + daitch_mokotoff=20 +----------------- + 579000 +(1 row) + +SELECT daitch_mokotoff('Manheim'); + daitch_mokotoff=20 +----------------- + 665600 +(1 row) + +SELECT daitch_mokotoff('Mintz'); + daitch_mokotoff=20 +----------------- + 664000 +(1 row) + +SELECT daitch_mokotoff('Topf'); + daitch_mokotoff=20 +----------------- + 370000 +(1 row) + +SELECT daitch_mokotoff('Kleinman'); + daitch_mokotoff=20 +----------------- + 586660 +(1 row) + +SELECT daitch_mokotoff('Ben Aron'); + daitch_mokotoff=20 +----------------- + 769600 +(1 row) + +SELECT daitch_mokotoff('AUERBACH'); + daitch_mokotoff=20 +----------------- + 097500 097400 +(1 row) + +SELECT daitch_mokotoff('OHRBACH'); + daitch_mokotoff=20 +----------------- + 097500 097400 +(1 row) + +SELECT daitch_mokotoff('LIPSHITZ'); + daitch_mokotoff=20 +----------------- + 874400 +(1 row) + +SELECT daitch_mokotoff('LIPPSZYC'); + daitch_mokotoff=20 +----------------- + 874500 874400 +(1 row) + +SELECT daitch_mokotoff('LEWINSKY'); + daitch_mokotoff=20 +----------------- + 876450 +(1 row) + +SELECT daitch_mokotoff('LEVINSKI'); + daitch_mokotoff=20 +----------------- + 876450 +(1 row) + +SELECT daitch_mokotoff('SZLAMAWICZ'); + daitch_mokotoff=20 +----------------- + 486740 +(1 row) + +SELECT daitch_mokotoff('SHLAMOVITZ'); + daitch_mokotoff=20 +----------------- + 486740 +(1 row) + +-- 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) + +-- https://familypedia.fandom.com/wiki/Daitch-Mokotoff_Soundex +SELECT daitch_mokotoff('Peters'); + daitch_mokotoff=20 +----------------- + 739400 734000 +(1 row) + +SELECT daitch_mokotoff('Peterson'); + daitch_mokotoff=20 +----------------- + 739460 734600 +(1 row) + +SELECT daitch_mokotoff('Moskowitz'); + daitch_mokotoff=20 +----------------- + 645740 +(1 row) + +SELECT daitch_mokotoff('Moskovitz'); + daitch_mokotoff=20 +----------------- + 645740 +(1 row) + +SELECT daitch_mokotoff('Auerbach'); + daitch_mokotoff=20 +----------------- + 097500 097400 +(1 row) + +SELECT daitch_mokotoff('Uhrbach'); + daitch_mokotoff=20 +----------------- + 097500 097400 +(1 row) + +SELECT daitch_mokotoff('Jackson'); + daitch_mokotoff=20=20=20=20=20=20=20 +----------------------------- + 154600 145460 454600 445460 +(1 row) + +SELECT daitch_mokotoff('Jackson-Jackson'); + daitch_mokotoff=20=20=20=20=20=20=20=20=20=20= =20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20 +----------------------------------------------------------------------- + 154654 154645 154644 145465 145464 454654 454645 454644 445465 445464 +(1 row) + +-- Perl Text::Phonetic::DaitchMokotoff 006_daitchmokotoff.t +-- Tests covered above are omitted. +SELECT daitch_mokotoff('M=C3=BCller'); + daitch_mokotoff=20 +----------------- + 689000 +(1 row) + +SELECT daitch_mokotoff('schmidt'); + daitch_mokotoff=20 +----------------- + 463000 +(1 row) + +SELECT daitch_mokotoff('schneider'); + daitch_mokotoff=20 +----------------- + 463900 +(1 row) + +SELECT daitch_mokotoff('fischer'); + daitch_mokotoff=20 +----------------- + 749000 +(1 row) + +SELECT daitch_mokotoff('weber'); + daitch_mokotoff=20 +----------------- + 779000 +(1 row) + +SELECT daitch_mokotoff('meyer'); + daitch_mokotoff=20 +----------------- + 619000 +(1 row) + +SELECT daitch_mokotoff('wagner'); + daitch_mokotoff=20 +----------------- + 756900 +(1 row) + +SELECT daitch_mokotoff('schulz'); + daitch_mokotoff=20 +----------------- + 484000 +(1 row) + +SELECT daitch_mokotoff('becker'); + daitch_mokotoff=20 +----------------- + 759000 745900 +(1 row) + +SELECT daitch_mokotoff('hoffmann'); + daitch_mokotoff=20 +----------------- + 576600 +(1 row) + +SELECT daitch_mokotoff('sch=C3=A4fer'); + daitch_mokotoff=20 +----------------- + 479000 +(1 row) + +-- Apache Commons DaitchMokotoffSoundexTest.java +-- testAccentedCharacterFolding +SELECT daitch_mokotoff('Stra=C3=9Fburg'); + daitch_mokotoff=20 +----------------- + 294795 +(1 row) + +SELECT daitch_mokotoff('Strasburg'); + daitch_mokotoff=20 +----------------- + 294795 +(1 row) + +SELECT daitch_mokotoff('=C3=89regon'); + daitch_mokotoff=20 +----------------- + 095600 +(1 row) + +SELECT daitch_mokotoff('Eregon'); + daitch_mokotoff=20 +----------------- + 095600 +(1 row) + +-- testAdjacentCodes +SELECT daitch_mokotoff('AKSSOL'); + daitch_mokotoff=20 +----------------- + 054800 +(1 row) + +SELECT daitch_mokotoff('GERSCHFELD'); + daitch_mokotoff=20=20=20=20=20=20=20 +----------------------------- + 594578 594783 545783 547830 +(1 row) + +-- testEncodeBasic +-- Tests covered above are omitted. +-- testEncodeIgnoreApostrophes +SELECT daitch_mokotoff('OBrien'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('''OBrien'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('O''Brien'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('OB''rien'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('OBr''ien'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('OBri''en'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('OBrie''n'); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +SELECT daitch_mokotoff('OBrien'''); + daitch_mokotoff=20 +----------------- + 079600 +(1 row) + +-- testEncodeIgnoreHyphens +SELECT daitch_mokotoff('KINGSMITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('-KINGSMITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('K-INGSMITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KI-NGSMITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KIN-GSMITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KING-SMITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KINGS-MITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KINGSM-ITH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KINGSMI-TH'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KINGSMIT-H'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +SELECT daitch_mokotoff('KINGSMITH-'); + daitch_mokotoff=20 +----------------- + 565463 +(1 row) + +-- testEncodeIgnoreTrimmable +SELECT daitch_mokotoff(E' \t\n\r Washington \t\n\r '); + daitch_mokotoff=20 +----------------- + 746536 +(1 row) + +SELECT daitch_mokotoff('Washington'); + daitch_mokotoff=20 +----------------- + 746536 +(1 row) + +-- testSoundexBasic +-- Tests covered above are omitted. +-- testSoundexBasic2 +-- Tests covered above are omitted. +-- testSoundexBasic3 +-- Tests covered above are omitted. +-- testSpecialRomanianCharacters +SELECT daitch_mokotoff('=C5=A3amas'); -- t-cedila + daitch_mokotoff=20 +----------------- + 364000 464000 +(1 row) + +SELECT daitch_mokotoff('=C8=9Bamas'); -- t-comma + daitch_mokotoff=20 +----------------- + 364000 464000 +(1 row) + +-- Contrived case which is not handled correctly by 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) + diff --git a/contrib/daitch_mokotoff/sql/daitch_mokotoff.sql b/contrib/dait= ch_mokotoff/sql/daitch_mokotoff.sql new file mode 100644 index 0000000000..eafc24ee87 --- /dev/null +++ b/contrib/daitch_mokotoff/sql/daitch_mokotoff.sql @@ -0,0 +1,121 @@ +CREATE EXTENSION daitch_mokotoff; + + +-- https://www.jewishgen.org/InfoFiles/Soundex.html +SELECT daitch_mokotoff('GOLDEN'); +SELECT daitch_mokotoff('Alpert'); +SELECT daitch_mokotoff('Breuer'); +SELECT daitch_mokotoff('Freud'); +SELECT daitch_mokotoff('Haber'); +SELECT daitch_mokotoff('Manheim'); +SELECT daitch_mokotoff('Mintz'); +SELECT daitch_mokotoff('Topf'); +SELECT daitch_mokotoff('Kleinman'); +SELECT daitch_mokotoff('Ben Aron'); + +SELECT daitch_mokotoff('AUERBACH'); +SELECT daitch_mokotoff('OHRBACH'); +SELECT daitch_mokotoff('LIPSHITZ'); +SELECT daitch_mokotoff('LIPPSZYC'); +SELECT daitch_mokotoff('LEWINSKY'); +SELECT daitch_mokotoff('LEVINSKI'); +SELECT daitch_mokotoff('SZLAMAWICZ'); +SELECT daitch_mokotoff('SHLAMOVITZ'); + + +-- 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'); + + +-- https://familypedia.fandom.com/wiki/Daitch-Mokotoff_Soundex +SELECT daitch_mokotoff('Peters'); +SELECT daitch_mokotoff('Peterson'); +SELECT daitch_mokotoff('Moskowitz'); +SELECT daitch_mokotoff('Moskovitz'); +SELECT daitch_mokotoff('Auerbach'); +SELECT daitch_mokotoff('Uhrbach'); +SELECT daitch_mokotoff('Jackson'); +SELECT daitch_mokotoff('Jackson-Jackson'); + + +-- Perl Text::Phonetic::DaitchMokotoff 006_daitchmokotoff.t +-- Tests covered above are omitted. +SELECT daitch_mokotoff('M=C3=BCller'); +SELECT daitch_mokotoff('schmidt'); +SELECT daitch_mokotoff('schneider'); +SELECT daitch_mokotoff('fischer'); +SELECT daitch_mokotoff('weber'); +SELECT daitch_mokotoff('meyer'); +SELECT daitch_mokotoff('wagner'); +SELECT daitch_mokotoff('schulz'); +SELECT daitch_mokotoff('becker'); +SELECT daitch_mokotoff('hoffmann'); +SELECT daitch_mokotoff('sch=C3=A4fer'); + + +-- Apache Commons DaitchMokotoffSoundexTest.java + +-- testAccentedCharacterFolding +SELECT daitch_mokotoff('Stra=C3=9Fburg'); +SELECT daitch_mokotoff('Strasburg'); + +SELECT daitch_mokotoff('=C3=89regon'); +SELECT daitch_mokotoff('Eregon'); + +-- testAdjacentCodes +SELECT daitch_mokotoff('AKSSOL'); +SELECT daitch_mokotoff('GERSCHFELD'); + +-- testEncodeBasic +-- Tests covered above are omitted. + +-- testEncodeIgnoreApostrophes +SELECT daitch_mokotoff('OBrien'); +SELECT daitch_mokotoff('''OBrien'); +SELECT daitch_mokotoff('O''Brien'); +SELECT daitch_mokotoff('OB''rien'); +SELECT daitch_mokotoff('OBr''ien'); +SELECT daitch_mokotoff('OBri''en'); +SELECT daitch_mokotoff('OBrie''n'); +SELECT daitch_mokotoff('OBrien'''); + +-- testEncodeIgnoreHyphens +SELECT daitch_mokotoff('KINGSMITH'); +SELECT daitch_mokotoff('-KINGSMITH'); +SELECT daitch_mokotoff('K-INGSMITH'); +SELECT daitch_mokotoff('KI-NGSMITH'); +SELECT daitch_mokotoff('KIN-GSMITH'); +SELECT daitch_mokotoff('KING-SMITH'); +SELECT daitch_mokotoff('KINGS-MITH'); +SELECT daitch_mokotoff('KINGSM-ITH'); +SELECT daitch_mokotoff('KINGSMI-TH'); +SELECT daitch_mokotoff('KINGSMIT-H'); +SELECT daitch_mokotoff('KINGSMITH-'); + +-- testEncodeIgnoreTrimmable +SELECT daitch_mokotoff(E' \t\n\r Washington \t\n\r '); +SELECT daitch_mokotoff('Washington'); + +-- testSoundexBasic +-- Tests covered above are omitted. + +-- testSoundexBasic2 +-- Tests covered above are omitted. + +-- testSoundexBasic3 +-- Tests covered above are omitted. + +-- testSpecialRomanianCharacters +SELECT daitch_mokotoff('=C5=A3amas'); -- t-cedila +SELECT daitch_mokotoff('=C8=9Bamas'); -- t-comma + + +-- Contrived case which is not handled correctly by other implementations. +SELECT daitch_mokotoff('CJC'); diff --git a/doc/src/sgml/contrib.sgml b/doc/src/sgml/contrib.sgml index d3ca4b6932..0788db060d 100644 --- a/doc/src/sgml/contrib.sgml +++ b/doc/src/sgml/contrib.sgml @@ -105,6 +105,7 @@ CREATE EXTENSION module_name; &citext; &cube; &dblink; + &daitch-mokotoff; &dict-int; &dict-xsyn; &earthdistance; diff --git a/doc/src/sgml/daitch-mokotoff.sgml b/doc/src/sgml/daitch-mokoto= ff.sgml new file mode 100644 index 0000000000..6dbc817eca --- /dev/null +++ b/doc/src/sgml/daitch-mokotoff.sgml @@ -0,0 +1,92 @@ + + + + daitch_mokotoff + + + daitch_mokotoff + + + + The daitch_mokotoff module provides an implementati= on + of the Daitch-Mokotoff Soundex System. + + + + Compared to the American Soundex System implemented in + the fuzzystrmatch module, 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 sounds, + it is double coded under the two different codes. + + + + + A letter or combination of letters maps into ten possible codes rather + than seven. + + + + + The daitch_mokotoff function shown in + generates Daitch-Mok= otoff + soundex codes for matching of similar-sounding names. + + + + <filename>daitch_mokotoff</filename> Functions + + + + + Function + + + Description + + + + + + + + daitch_mokotoff ( name= text ) + text + + + Generates Daitch-Mokotoff soundex codes. + + + + +
+ + + daitch_mokotoff + + + daitch_mokotoff generates Daitch-Mokotoff soundex c= odes for the specified name. Since alternate soundex= codes are separated by spaces, the returned text is suited for use in Full= Text Search, see . + + + diff --git a/doc/src/sgml/filelist.sgml b/doc/src/sgml/filelist.sgml index 89454e99b9..9ac43e5928 100644 --- a/doc/src/sgml/filelist.sgml +++ b/doc/src/sgml/filelist.sgml @@ -117,6 +117,7 @@ + --=-=-= Content-Type: text/plain Dag Lem writes: > Hello, > > Please find attached a patch for the daitch_mokotoff module. > > This implements the Daitch-Mokotoff Soundex System, as described in > https://www.avotaynu.com/soundex.htm > > The module is used in production at Finance Norway. > > In order to verify correctness, I have compared generated soundex codes > with corresponding results from the implementation by Stephen P. Morse > at https://stevemorse.org/census/soundex.html > > Where soundex codes differ, the daitch_mokotoff module has been found > to be correct. The Morse implementation uses a few unofficial rules, > and also has an error in the handling of adjacent identical code > digits. Please see daitch_mokotoff.c for further references and > comments. > > For reference, detailed instructions for soundex code comparison are > attached. > > > Best regards > > Dag Lem > --=-=-=--