doc/src/sgml/fuzzystrmatch.sgml

   1 <!-- doc/src/sgml/fuzzystrmatch.sgml -->
   2
   3 <sect1 id="fuzzystrmatch" xreflabel="fuzzystrmatch">
   4  <title>fuzzystrmatch &mdash; determine string similarities and distance</title>
   5
   6  <indexterm zone="fuzzystrmatch">
   7   <primary>fuzzystrmatch</primary>
   8  </indexterm>
   9
  10  <para>
  11   The <filename>fuzzystrmatch</filename> module provides several
  12   functions to determine similarities and distance between strings.
  13  </para>
  14
  15  <caution>
  16   <para>
  17    At present, the <function>soundex</function>, <function>metaphone</function>,
  18    <function>dmetaphone</function>, and <function>dmetaphone_alt</function> functions do
  19    not work well with multibyte encodings (such as UTF-8).
  20    Use <function>daitch_mokotoff</function>
  21    or <function>levenshtein</function> with such data.
  22   </para>
  23  </caution>
  24
  25  <para>
  26   This module is considered <quote>trusted</quote>, that is, it can be
  27   installed by non-superusers who have <literal>CREATE</literal> privilege
  28   on the current database.
  29  </para>
  30
  31  <sect2 id="fuzzystrmatch-soundex">
  32   <title>Soundex</title>
  33
  34   <para>
  35    The Soundex system is a method of matching similar-sounding names
  36    by converting them to the same code.  It was initially used by the
  37    United States Census in 1880, 1900, and 1910.  Note that Soundex
  38    is not very useful for non-English names.
  39   </para>
  40
  41   <para>
  42    The <filename>fuzzystrmatch</filename> module provides two functions
  43    for working with Soundex codes:
  44   </para>
  45
  46   <indexterm>
  47    <primary>soundex</primary>
  48   </indexterm>
  49
  50   <indexterm>
  51    <primary>difference</primary>
  52   </indexterm>
  53
  54 <synopsis>
  55 soundex(text) returns text
  56 difference(text, text) returns int
  57 </synopsis>
  58
  59   <para>
  60    The <function>soundex</function> function converts a string to its Soundex code.
  61    The <function>difference</function> function converts two strings to their Soundex
  62    codes and then reports the number of matching code positions.  Since
  63    Soundex codes have four characters, the result ranges from zero to four,
  64    with zero being no match and four being an exact match.  (Thus, the
  65    function is misnamed &mdash; <function>similarity</function> would have been
  66    a better name.)
  67   </para>
  68
  69   <para>
  70    Here are some usage examples:
  71   </para>
  72
  73 <programlisting>
  74 SELECT soundex('hello world!');
  75
  76 SELECT soundex('Anne'), soundex('Ann'), difference('Anne', 'Ann');
  77 SELECT soundex('Anne'), soundex('Andrew'), difference('Anne', 'Andrew');
  78 SELECT soundex('Anne'), soundex('Margaret'), difference('Anne', 'Margaret');
  79
  80 CREATE TABLE s (nm text);
  81
  82 INSERT INTO s VALUES ('john');
  83 INSERT INTO s VALUES ('joan');
  84 INSERT INTO s VALUES ('wobbly');
  85 INSERT INTO s VALUES ('jack');
  86
  87 SELECT * FROM s WHERE soundex(nm) = soundex('john');
  88
  89 SELECT * FROM s WHERE difference(s.nm, 'john') &gt; 2;
  90 </programlisting>
  91  </sect2>
  92
  93  <sect2 id="fuzzystrmatch-daitch-mokotoff">
  94   <title>Daitch-Mokotoff Soundex</title>
  95
  96   <para>
  97    Like the original Soundex system, Daitch-Mokotoff Soundex matches
  98    similar-sounding names by converting them to the same code.
  99    However, Daitch-Mokotoff Soundex is significantly more useful for
 100    non-English names than the original system.
 101    Major improvements over the original system include:
 102
 103    <itemizedlist spacing="compact" mark="bullet">
 104     <listitem>
 105      <para>
 106       The code is based on the first six meaningful letters rather than four.
 107      </para>
 108     </listitem>
 109     <listitem>
 110      <para>
 111       A letter or combination of letters maps into ten possible codes rather
 112       than seven.
 113      </para>
 114     </listitem>
 115     <listitem>
 116      <para>
 117       Where two consecutive letters have a single sound, they are coded as a
 118       single number.
 119      </para>
 120     </listitem>
 121     <listitem>
 122      <para>
 123       When a letter or combination of letters may have different sounds,
 124       multiple codes are emitted to cover all possibilities.
 125      </para>
 126     </listitem>
 127    </itemizedlist>
 128   </para>
 129
 130   <indexterm>
 131    <primary>daitch_mokotoff</primary>
 132   </indexterm>
 133
 134   <para>
 135    This function generates the Daitch-Mokotoff soundex codes for its input:
 136   </para>
 137
 138 <synopsis>
 139 daitch_mokotoff(<parameter>source</parameter> text) returns text[]
 140 </synopsis>
 141
 142   <para>
 143    The result may contain one or more codes depending on how many plausible
 144    pronunciations there are, so it is represented as an array.
 145   </para>
 146
 147   <para>
 148    Since a Daitch-Mokotoff soundex code consists of only 6 digits,
 149    <parameter>source</parameter> should be preferably a single word or name.
 150   </para>
 151
 152   <para>
 153    Here are some examples:
 154   </para>
 155
 156 <programlisting>
 157 SELECT daitch_mokotoff('George');
 158  daitch_mokotoff
 159 -----------------
 160  {595000}
 161
 162 SELECT daitch_mokotoff('John');
 163  daitch_mokotoff
 164 -----------------
 165  {160000,460000}
 166
 167 SELECT daitch_mokotoff('Bierschbach');
 168                       daitch_mokotoff
 169 -----------------------------------------------------------
 170  {794575,794574,794750,794740,745750,745740,747500,747400}
 171
 172 SELECT daitch_mokotoff('Schwartzenegger');
 173  daitch_mokotoff
 174 -----------------
 175  {479465}
 176 </programlisting>
 177
 178   <para>
 179    For matching of single names, returned text arrays can be matched
 180    directly using the <literal>&amp;&amp;</literal> operator: any overlap
 181    can be considered a match.  A GIN index may
 182    be used for efficiency, see <xref linkend="gin"/> and this example:
 183   </para>
 184
 185 <programlisting>
 186 CREATE TABLE s (nm text);
 187 CREATE INDEX ix_s_dm ON s USING gin (daitch_mokotoff(nm)) WITH (fastupdate = off);
 188
 189 INSERT INTO s (nm) VALUES
 190   ('Schwartzenegger'),
 191   ('John'),
 192   ('James'),
 193   ('Steinman'),
 194   ('Steinmetz');
 195
 196 SELECT * FROM s WHERE daitch_mokotoff(nm) &amp;&amp; daitch_mokotoff('Swartzenegger');
 197 SELECT * FROM s WHERE daitch_mokotoff(nm) &amp;&amp; daitch_mokotoff('Jane');
 198 SELECT * FROM s WHERE daitch_mokotoff(nm) &amp;&amp; daitch_mokotoff('Jens');
 199 </programlisting>
 200
 201   <para>
 202    For indexing and matching of any number of names in any order, Full Text
 203    Search features can be used. See <xref linkend="textsearch"/> and this
 204    example:
 205   </para>
 206
 207 <programlisting>
 208 CREATE FUNCTION soundex_tsvector(v_name text) RETURNS tsvector
 209 BEGIN ATOMIC
 210   SELECT to_tsvector('simple',
 211                      string_agg(array_to_string(daitch_mokotoff(n), ' '), ' '))
 212   FROM regexp_split_to_table(v_name, '\s+') AS n;
 213 END;
 214
 215 CREATE FUNCTION soundex_tsquery(v_name text) RETURNS tsquery
 216 BEGIN ATOMIC
 217   SELECT string_agg('(' || array_to_string(daitch_mokotoff(n), '|') || ')', '&amp;')::tsquery
 218   FROM regexp_split_to_table(v_name, '\s+') AS n;
 219 END;
 220
 221 CREATE TABLE s (nm text);
 222 CREATE INDEX ix_s_txt ON s USING gin (soundex_tsvector(nm)) WITH (fastupdate = off);
 223
 224 INSERT INTO s (nm) VALUES
 225   ('John Doe'),
 226   ('Jane Roe'),
 227   ('Public John Q.'),
 228   ('George Best'),
 229   ('John Yamson');
 230
 231 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john');
 232 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('jane doe');
 233 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john public');
 234 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('besst, giorgio');
 235 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('Jameson John');
 236 </programlisting>
 237
 238   <para>
 239    If it is desired to avoid recalculation of soundex codes during index
 240    rechecks, an index on a separate column can be used instead of an index on
 241    an expression.  A stored generated column can be used for this; see
 242    <xref linkend="ddl-generated-columns"/>.
 243   </para>
 244  </sect2>
 245
 246  <sect2 id="fuzzystrmatch-levenshtein">
 247   <title>Levenshtein</title>
 248
 249   <para>
 250    This function calculates the Levenshtein distance between two strings:
 251   </para>
 252
 253   <indexterm>
 254    <primary>levenshtein</primary>
 255   </indexterm>
 256
 257   <indexterm>
 258    <primary>levenshtein_less_equal</primary>
 259   </indexterm>
 260
 261 <synopsis>
 262 levenshtein(source text, target text, ins_cost int, del_cost int, sub_cost int) returns int
 263 levenshtein(source text, target text) returns int
 264 levenshtein_less_equal(source text, target text, ins_cost int, del_cost int, sub_cost int, max_d int) returns int
 265 levenshtein_less_equal(source text, target text, max_d int) returns int
 266 </synopsis>
 267
 268   <para>
 269    Both <literal>source</literal> and <literal>target</literal> can be any
 270    non-null string, with a maximum of 255 characters.  The cost parameters
 271    specify how much to charge for a character insertion, deletion, or
 272    substitution, respectively.  You can omit the cost parameters, as in
 273    the second version of the function; in that case they all default to 1.
 274   </para>
 275
 276   <para>
 277    <function>levenshtein_less_equal</function> is an accelerated version of the
 278    Levenshtein function for use when only small distances are of interest.
 279    If the actual distance is less than or equal to <literal>max_d</literal>,
 280    then <function>levenshtein_less_equal</function> returns the correct
 281    distance; otherwise it returns some value greater than <literal>max_d</literal>.
 282    If <literal>max_d</literal> is negative then the behavior is the same as
 283    <function>levenshtein</function>.
 284   </para>
 285
 286   <para>
 287    Examples:
 288   </para>
 289
 290 <screen>
 291 test=# SELECT levenshtein('GUMBO', 'GAMBOL');
 292  levenshtein
 293 -------------
 294            2
 295 (1 row)
 296
 297 test=# SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1);
 298  levenshtein
 299 -------------
 300            3
 301 (1 row)
 302
 303 test=# SELECT levenshtein_less_equal('extensive', 'exhaustive', 2);
 304  levenshtein_less_equal
 305 ------------------------
 306                       3
 307 (1 row)
 308
 309 test=# SELECT levenshtein_less_equal('extensive', 'exhaustive', 4);
 310  levenshtein_less_equal
 311 ------------------------
 312                       4
 313 (1 row)
 314 </screen>
 315  </sect2>
 316
 317  <sect2 id="fuzzystrmatch-metaphone">
 318   <title>Metaphone</title>
 319
 320   <para>
 321    Metaphone, like Soundex, is based on the idea of constructing a
 322    representative code for an input string.  Two strings are then
 323    deemed similar if they have the same codes.
 324   </para>
 325
 326   <para>
 327    This function calculates the metaphone code of an input string:
 328   </para>
 329
 330   <indexterm>
 331    <primary>metaphone</primary>
 332   </indexterm>
 333
 334 <synopsis>
 335 metaphone(source text, max_output_length int) returns text
 336 </synopsis>
 337
 338   <para>
 339    <literal>source</literal> has to be a non-null string with a maximum of
 340    255 characters.  <literal>max_output_length</literal> sets the maximum
 341    length of the output metaphone code; if longer, the output is truncated
 342    to this length.
 343   </para>
 344
 345   <para>
 346    Example:
 347   </para>
 348
 349 <screen>
 350 test=# SELECT metaphone('GUMBO', 4);
 351  metaphone
 352 -----------
 353  KM
 354 (1 row)
 355 </screen>
 356  </sect2>
 357
 358  <sect2 id="fuzzystrmatch-double-metaphone">
 359   <title>Double Metaphone</title>
 360
 361   <para>
 362    The Double Metaphone system computes two <quote>sounds like</quote> strings
 363    for a given input string &mdash; a <quote>primary</quote> and an
 364    <quote>alternate</quote>.  In most cases they are the same, but for non-English
 365    names especially they can be a bit different, depending on pronunciation.
 366    These functions compute the primary and alternate codes:
 367   </para>
 368
 369   <indexterm>
 370    <primary>dmetaphone</primary>
 371   </indexterm>
 372
 373   <indexterm>
 374    <primary>dmetaphone_alt</primary>
 375   </indexterm>
 376
 377 <synopsis>
 378 dmetaphone(source text) returns text
 379 dmetaphone_alt(source text) returns text
 380 </synopsis>
 381
 382   <para>
 383    There is no length limit on the input strings.
 384   </para>
 385
 386   <para>
 387    Example:
 388   </para>
 389
 390 <screen>
 391 test=# SELECT dmetaphone('gumbo');
 392  dmetaphone
 393 ------------
 394  KMP
 395 (1 row)
 396 </screen>
 397  </sect2>
 398
 399 </sect1>