diff options
Diffstat (limited to 'doc/src/sgml/fuzzystrmatch.sgml')
| -rw-r--r-- | doc/src/sgml/fuzzystrmatch.sgml | 399 |
1 files changed, 399 insertions, 0 deletions
diff --git a/doc/src/sgml/fuzzystrmatch.sgml b/doc/src/sgml/fuzzystrmatch.sgml new file mode 100644 index 0000000..bcadc44 --- /dev/null +++ b/doc/src/sgml/fuzzystrmatch.sgml @@ -0,0 +1,399 @@ +<!-- doc/src/sgml/fuzzystrmatch.sgml --> + +<sect1 id="fuzzystrmatch" xreflabel="fuzzystrmatch"> + <title>fuzzystrmatch — determine string similarities and distance</title> + + <indexterm zone="fuzzystrmatch"> + <primary>fuzzystrmatch</primary> + </indexterm> + + <para> + The <filename>fuzzystrmatch</filename> module provides several + functions to determine similarities and distance between strings. + </para> + + <caution> + <para> + At present, the <function>soundex</function>, <function>metaphone</function>, + <function>dmetaphone</function>, and <function>dmetaphone_alt</function> functions do + not work well with multibyte encodings (such as UTF-8). + Use <function>daitch_mokotoff</function> + or <function>levenshtein</function> with such data. + </para> + </caution> + + <para> + This module is considered <quote>trusted</quote>, that is, it can be + installed by non-superusers who have <literal>CREATE</literal> privilege + on the current database. + </para> + + <sect2 id="fuzzystrmatch-soundex"> + <title>Soundex</title> + + <para> + The Soundex system is a method of matching similar-sounding names + by converting them to the same code. It was initially used by the + United States Census in 1880, 1900, and 1910. Note that Soundex + is not very useful for non-English names. + </para> + + <para> + The <filename>fuzzystrmatch</filename> module provides two functions + for working with Soundex codes: + </para> + + <indexterm> + <primary>soundex</primary> + </indexterm> + + <indexterm> + <primary>difference</primary> + </indexterm> + +<synopsis> +soundex(text) returns text +difference(text, text) returns int +</synopsis> + + <para> + The <function>soundex</function> function converts a string to its Soundex code. + The <function>difference</function> function converts two strings to their Soundex + codes and then reports the number of matching code positions. Since + Soundex codes have four characters, the result ranges from zero to four, + with zero being no match and four being an exact match. (Thus, the + function is misnamed — <function>similarity</function> would have been + a better name.) + </para> + + <para> + Here are some usage examples: + </para> + +<programlisting> +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'); + +CREATE TABLE s (nm text); + +INSERT INTO s VALUES ('john'); +INSERT INTO s VALUES ('joan'); +INSERT INTO s VALUES ('wobbly'); +INSERT INTO s VALUES ('jack'); + +SELECT * FROM s WHERE soundex(nm) = soundex('john'); + +SELECT * FROM s WHERE difference(s.nm, 'john') > 2; +</programlisting> + </sect2> + + <sect2 id="fuzzystrmatch-daitch-mokotoff"> + <title>Daitch-Mokotoff Soundex</title> + + <para> + Like the original Soundex system, Daitch-Mokotoff Soundex matches + similar-sounding names by converting them to the same code. + However, Daitch-Mokotoff Soundex is significantly more useful for + non-English names than the original system. + Major improvements over the original system include: + + <itemizedlist spacing="compact" mark="bullet"> + <listitem> + <para> + The code is based on the first six meaningful letters rather than four. + </para> + </listitem> + <listitem> + <para> + A letter or combination of letters maps into ten possible codes rather + than seven. + </para> + </listitem> + <listitem> + <para> + Where two consecutive letters have a single sound, they are coded as a + single number. + </para> + </listitem> + <listitem> + <para> + When a letter or combination of letters may have different sounds, + multiple codes are emitted to cover all possibilities. + </para> + </listitem> + </itemizedlist> + </para> + + <indexterm> + <primary>daitch_mokotoff</primary> + </indexterm> + + <para> + This function generates the Daitch-Mokotoff soundex codes for its input: + </para> + +<synopsis> +daitch_mokotoff(<parameter>source</parameter> text) returns text[] +</synopsis> + + <para> + The result may contain one or more codes depending on how many plausible + pronunciations there are, so it is represented as an array. + </para> + + <para> + Since a Daitch-Mokotoff soundex code consists of only 6 digits, + <parameter>source</parameter> should be preferably a single word or name. + </para> + + <para> + Here are some examples: + </para> + +<programlisting> +SELECT daitch_mokotoff('George'); + daitch_mokotoff +----------------- + {595000} + +SELECT daitch_mokotoff('John'); + daitch_mokotoff +----------------- + {160000,460000} + +SELECT daitch_mokotoff('Bierschbach'); + daitch_mokotoff +----------------------------------------------------------- + {794575,794574,794750,794740,745750,745740,747500,747400} + +SELECT daitch_mokotoff('Schwartzenegger'); + daitch_mokotoff +----------------- + {479465} +</programlisting> + + <para> + For matching of single names, returned text arrays can be matched + directly using the <literal>&&</literal> operator: any overlap + can be considered a match. A GIN index may + be used for efficiency, see <xref linkend="gin"/> and this example: + </para> + +<programlisting> +CREATE TABLE s (nm text); +CREATE INDEX ix_s_dm ON s USING gin (daitch_mokotoff(nm)) WITH (fastupdate = off); + +INSERT INTO s (nm) VALUES + ('Schwartzenegger'), + ('John'), + ('James'), + ('Steinman'), + ('Steinmetz'); + +SELECT * FROM s WHERE daitch_mokotoff(nm) && daitch_mokotoff('Swartzenegger'); +SELECT * FROM s WHERE daitch_mokotoff(nm) && daitch_mokotoff('Jane'); +SELECT * FROM s WHERE daitch_mokotoff(nm) && daitch_mokotoff('Jens'); +</programlisting> + + <para> + For indexing and matching of any number of names in any order, Full Text + Search features can be used. See <xref linkend="textsearch"/> and this + example: + </para> + +<programlisting> +CREATE FUNCTION soundex_tsvector(v_name text) RETURNS tsvector +BEGIN ATOMIC + SELECT to_tsvector('simple', + string_agg(array_to_string(daitch_mokotoff(n), ' '), ' ')) + FROM regexp_split_to_table(v_name, '\s+') AS n; +END; + +CREATE FUNCTION soundex_tsquery(v_name text) RETURNS tsquery +BEGIN ATOMIC + SELECT string_agg('(' || array_to_string(daitch_mokotoff(n), '|') || ')', '&')::tsquery + FROM regexp_split_to_table(v_name, '\s+') AS n; +END; + +CREATE TABLE s (nm text); +CREATE INDEX ix_s_txt ON s USING gin (soundex_tsvector(nm)) WITH (fastupdate = off); + +INSERT INTO s (nm) VALUES + ('John Doe'), + ('Jane Roe'), + ('Public John Q.'), + ('George Best'), + ('John Yamson'); + +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john'); +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('jane doe'); +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john public'); +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('besst, giorgio'); +SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('Jameson John'); +</programlisting> + + <para> + If it is desired to avoid recalculation of soundex codes during index + rechecks, an index on a separate column can be used instead of an index on + an expression. A stored generated column can be used for this; see + <xref linkend="ddl-generated-columns"/>. + </para> + </sect2> + + <sect2 id="fuzzystrmatch-levenshtein"> + <title>Levenshtein</title> + + <para> + This function calculates the Levenshtein distance between two strings: + </para> + + <indexterm> + <primary>levenshtein</primary> + </indexterm> + + <indexterm> + <primary>levenshtein_less_equal</primary> + </indexterm> + +<synopsis> +levenshtein(source text, target text, ins_cost int, del_cost int, sub_cost int) returns int +levenshtein(source text, target text) returns int +levenshtein_less_equal(source text, target text, ins_cost int, del_cost int, sub_cost int, max_d int) returns int +levenshtein_less_equal(source text, target text, max_d int) returns int +</synopsis> + + <para> + Both <literal>source</literal> and <literal>target</literal> can be any + non-null string, with a maximum of 255 characters. The cost parameters + specify how much to charge for a character insertion, deletion, or + substitution, respectively. You can omit the cost parameters, as in + the second version of the function; in that case they all default to 1. + </para> + + <para> + <function>levenshtein_less_equal</function> is an accelerated version of the + Levenshtein function for use when only small distances are of interest. + If the actual distance is less than or equal to <literal>max_d</literal>, + then <function>levenshtein_less_equal</function> returns the correct + distance; otherwise it returns some value greater than <literal>max_d</literal>. + If <literal>max_d</literal> is negative then the behavior is the same as + <function>levenshtein</function>. + </para> + + <para> + Examples: + </para> + +<screen> +test=# SELECT levenshtein('GUMBO', 'GAMBOL'); + levenshtein +------------- + 2 +(1 row) + +test=# SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1); + levenshtein +------------- + 3 +(1 row) + +test=# SELECT levenshtein_less_equal('extensive', 'exhaustive', 2); + levenshtein_less_equal +------------------------ + 3 +(1 row) + +test=# SELECT levenshtein_less_equal('extensive', 'exhaustive', 4); + levenshtein_less_equal +------------------------ + 4 +(1 row) +</screen> + </sect2> + + <sect2 id="fuzzystrmatch-metaphone"> + <title>Metaphone</title> + + <para> + Metaphone, like Soundex, is based on the idea of constructing a + representative code for an input string. Two strings are then + deemed similar if they have the same codes. + </para> + + <para> + This function calculates the metaphone code of an input string: + </para> + + <indexterm> + <primary>metaphone</primary> + </indexterm> + +<synopsis> +metaphone(source text, max_output_length int) returns text +</synopsis> + + <para> + <literal>source</literal> has to be a non-null string with a maximum of + 255 characters. <literal>max_output_length</literal> sets the maximum + length of the output metaphone code; if longer, the output is truncated + to this length. + </para> + + <para> + Example: + </para> + +<screen> +test=# SELECT metaphone('GUMBO', 4); + metaphone +----------- + KM +(1 row) +</screen> + </sect2> + + <sect2 id="fuzzystrmatch-double-metaphone"> + <title>Double Metaphone</title> + + <para> + The Double Metaphone system computes two <quote>sounds like</quote> strings + for a given input string — a <quote>primary</quote> and an + <quote>alternate</quote>. In most cases they are the same, but for non-English + names especially they can be a bit different, depending on pronunciation. + These functions compute the primary and alternate codes: + </para> + + <indexterm> + <primary>dmetaphone</primary> + </indexterm> + + <indexterm> + <primary>dmetaphone_alt</primary> + </indexterm> + +<synopsis> +dmetaphone(source text) returns text +dmetaphone_alt(source text) returns text +</synopsis> + + <para> + There is no length limit on the input strings. + </para> + + <para> + Example: + </para> + +<screen> +test=# SELECT dmetaphone('gumbo'); + dmetaphone +------------ + KMP +(1 row) +</screen> + </sect2> + +</sect1> |