path: root/doc/src/sgml/fuzzystrmatch.sgml

<!-- doc/src/sgml/fuzzystrmatch.sgml -->

<sect1 id="fuzzystrmatch" xreflabel="fuzzystrmatch">
 <title>fuzzystrmatch &mdash; 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 &mdash; <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') &gt; 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>&amp;&amp;</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) &amp;&amp; daitch_mokotoff('Swartzenegger');
SELECT * FROM s WHERE daitch_mokotoff(nm) &amp;&amp; daitch_mokotoff('Jane');
SELECT * FROM s WHERE daitch_mokotoff(nm) &amp;&amp; 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), '|') || ')', '&amp;')::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 &mdash; 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>