begriffs open source - ai-pg/blob - full-docs/txt/fuzzystrmatch.txt

   1
   2 F.16. fuzzystrmatch — determine string similarities and distance #
   3
   4    F.16.1. Soundex
   5    F.16.2. Daitch-Mokotoff Soundex
   6    F.16.3. Levenshtein
   7    F.16.4. Metaphone
   8    F.16.5. Double Metaphone
   9
  10    The fuzzystrmatch module provides several functions to determine
  11    similarities and distance between strings.
  12
  13 Caution
  14
  15    At present, the soundex, metaphone, dmetaphone, and dmetaphone_alt
  16    functions do not work well with multibyte encodings (such as UTF-8).
  17    Use daitch_mokotoff or levenshtein with such data.
  18
  19    This module is considered “trusted”, that is, it can be installed by
  20    non-superusers who have CREATE privilege on the current database.
  21
  22 F.16.1. Soundex #
  23
  24    The Soundex system is a method of matching similar-sounding names by
  25    converting them to the same code. It was initially used by the United
  26    States Census in 1880, 1900, and 1910. Note that Soundex is not very
  27    useful for non-English names.
  28
  29    The fuzzystrmatch module provides two functions for working with
  30    Soundex codes:
  31 soundex(text) returns text
  32 difference(text, text) returns int
  33
  34    The soundex function converts a string to its Soundex code. The
  35    difference function converts two strings to their Soundex codes and
  36    then reports the number of matching code positions. Since Soundex codes
  37    have four characters, the result ranges from zero to four, with zero
  38    being no match and four being an exact match. (Thus, the function is
  39    misnamed — similarity would have been a better name.)
  40
  41    Here are some usage examples:
  42 SELECT soundex('hello world!');
  43
  44 SELECT soundex('Anne'), soundex('Ann'), difference('Anne', 'Ann');
  45 SELECT soundex('Anne'), soundex('Andrew'), difference('Anne', 'Andrew');
  46 SELECT soundex('Anne'), soundex('Margaret'), difference('Anne', 'Margaret');
  47
  48 CREATE TABLE s (nm text);
  49
  50 INSERT INTO s VALUES ('john');
  51 INSERT INTO s VALUES ('joan');
  52 INSERT INTO s VALUES ('wobbly');
  53 INSERT INTO s VALUES ('jack');
  54
  55 SELECT * FROM s WHERE soundex(nm) = soundex('john');
  56
  57 SELECT * FROM s WHERE difference(s.nm, 'john') > 2;
  58
  59 F.16.2. Daitch-Mokotoff Soundex #
  60
  61    Like the original Soundex system, Daitch-Mokotoff Soundex matches
  62    similar-sounding names by converting them to the same code. However,
  63    Daitch-Mokotoff Soundex is significantly more useful for non-English
  64    names than the original system. Major improvements over the original
  65    system include:
  66      * The code is based on the first six meaningful letters rather than
  67        four.
  68      * A letter or combination of letters maps into ten possible codes
  69        rather than seven.
  70      * Where two consecutive letters have a single sound, they are coded
  71        as a single number.
  72      * When a letter or combination of letters may have different sounds,
  73        multiple codes are emitted to cover all possibilities.
  74
  75    This function generates the Daitch-Mokotoff soundex codes for its
  76    input:
  77 daitch_mokotoff(source text) returns text[]
  78
  79    The result may contain one or more codes depending on how many
  80    plausible pronunciations there are, so it is represented as an array.
  81
  82    Since a Daitch-Mokotoff soundex code consists of only 6 digits, source
  83    should be preferably a single word or name.
  84
  85    Here are some examples:
  86 SELECT daitch_mokotoff('George');
  87  daitch_mokotoff
  88 -----------------
  89  {595000}
  90
  91 SELECT daitch_mokotoff('John');
  92  daitch_mokotoff
  93 -----------------
  94  {160000,460000}
  95
  96 SELECT daitch_mokotoff('Bierschbach');
  97                       daitch_mokotoff
  98 -----------------------------------------------------------
  99  {794575,794574,794750,794740,745750,745740,747500,747400}
 100
 101 SELECT daitch_mokotoff('Schwartzenegger');
 102  daitch_mokotoff
 103 -----------------
 104  {479465}
 105
 106    For matching of single names, returned text arrays can be matched
 107    directly using the && operator: any overlap can be considered a match.
 108    A GIN index may be used for efficiency, see Section 65.4 and this
 109    example:
 110 CREATE TABLE s (nm text);
 111 CREATE INDEX ix_s_dm ON s USING gin (daitch_mokotoff(nm)) WITH (fastupdate = off
 112 );
 113
 114 INSERT INTO s (nm) VALUES
 115   ('Schwartzenegger'),
 116   ('John'),
 117   ('James'),
 118   ('Steinman'),
 119   ('Steinmetz');
 120
 121 SELECT * FROM s WHERE daitch_mokotoff(nm) && daitch_mokotoff('Swartzenegger');
 122 SELECT * FROM s WHERE daitch_mokotoff(nm) && daitch_mokotoff('Jane');
 123 SELECT * FROM s WHERE daitch_mokotoff(nm) && daitch_mokotoff('Jens');
 124
 125    For indexing and matching of any number of names in any order, Full
 126    Text Search features can be used. See Chapter 12 and this example:
 127 CREATE FUNCTION soundex_tsvector(v_name text) RETURNS tsvector
 128 BEGIN ATOMIC
 129   SELECT to_tsvector('simple',
 130                      string_agg(array_to_string(daitch_mokotoff(n), ' '), ' '))
 131   FROM regexp_split_to_table(v_name, '\s+') AS n;
 132 END;
 133
 134 CREATE FUNCTION soundex_tsquery(v_name text) RETURNS tsquery
 135 BEGIN ATOMIC
 136   SELECT string_agg('(' || array_to_string(daitch_mokotoff(n), '|') || ')', '&')
 137 ::tsquery
 138   FROM regexp_split_to_table(v_name, '\s+') AS n;
 139 END;
 140
 141 CREATE TABLE s (nm text);
 142 CREATE INDEX ix_s_txt ON s USING gin (soundex_tsvector(nm)) WITH (fastupdate = o
 143 ff);
 144
 145 INSERT INTO s (nm) VALUES
 146   ('John Doe'),
 147   ('Jane Roe'),
 148   ('Public John Q.'),
 149   ('George Best'),
 150   ('John Yamson');
 151
 152 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john');
 153 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('jane doe');
 154 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('john public');
 155 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('besst, giorgio');
 156 SELECT * FROM s WHERE soundex_tsvector(nm) @@ soundex_tsquery('Jameson John');
 157
 158    If it is desired to avoid recalculation of soundex codes during index
 159    rechecks, an index on a separate column can be used instead of an index
 160    on an expression. A stored generated column can be used for this; see
 161    Section 5.4.
 162
 163 F.16.3. Levenshtein #
 164
 165    This function calculates the Levenshtein distance between two strings:
 166 levenshtein(source text, target text, ins_cost int, del_cost int, sub_cost int)
 167 returns int
 168 levenshtein(source text, target text) returns int
 169 levenshtein_less_equal(source text, target text, ins_cost int, del_cost int, sub
 170 _cost int, max_d int) returns int
 171 levenshtein_less_equal(source text, target text, max_d int) returns int
 172
 173    Both source and target can be any non-null string, with a maximum of
 174    255 characters. The cost parameters specify how much to charge for a
 175    character insertion, deletion, or substitution, respectively. You can
 176    omit the cost parameters, as in the second version of the function; in
 177    that case they all default to 1.
 178
 179    levenshtein_less_equal is an accelerated version of the Levenshtein
 180    function for use when only small distances are of interest. If the
 181    actual distance is less than or equal to max_d, then
 182    levenshtein_less_equal returns the correct distance; otherwise it
 183    returns some value greater than max_d. If max_d is negative then the
 184    behavior is the same as levenshtein.
 185
 186    Examples:
 187 test=# SELECT levenshtein('GUMBO', 'GAMBOL');
 188  levenshtein
 189 -------------
 190            2
 191 (1 row)
 192
 193 test=# SELECT levenshtein('GUMBO', 'GAMBOL', 2, 1, 1);
 194  levenshtein
 195 -------------
 196            3
 197 (1 row)
 198
 199 test=# SELECT levenshtein_less_equal('extensive', 'exhaustive', 2);
 200  levenshtein_less_equal
 201 ------------------------
 202                       3
 203 (1 row)
 204
 205 test=# SELECT levenshtein_less_equal('extensive', 'exhaustive', 4);
 206  levenshtein_less_equal
 207 ------------------------
 208                       4
 209 (1 row)
 210
 211 F.16.4. Metaphone #
 212
 213    Metaphone, like Soundex, is based on the idea of constructing a
 214    representative code for an input string. Two strings are then deemed
 215    similar if they have the same codes.
 216
 217    This function calculates the metaphone code of an input string:
 218 metaphone(source text, max_output_length int) returns text
 219
 220    source has to be a non-null string with a maximum of 255 characters.
 221    max_output_length sets the maximum length of the output metaphone code;
 222    if longer, the output is truncated to this length.
 223
 224    Example:
 225 test=# SELECT metaphone('GUMBO', 4);
 226  metaphone
 227 -----------
 228  KM
 229 (1 row)
 230
 231 F.16.5. Double Metaphone #
 232
 233    The Double Metaphone system computes two “sounds like” strings for a
 234    given input string — a “primary” and an “alternate”. In most cases they
 235    are the same, but for non-English names especially they can be a bit
 236    different, depending on pronunciation. These functions compute the
 237    primary and alternate codes:
 238 dmetaphone(source text) returns text
 239 dmetaphone_alt(source text) returns text
 240
 241    There is no length limit on the input strings.
 242
 243    Example:
 244 test=# SELECT dmetaphone('gumbo');
 245  dmetaphone
 246 ------------
 247  KMP
 248 (1 row)