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