F.17. fuzzystrmatch — вычисление схожести и расстояния между строками #

Модуль fuzzystrmatch содержит несколько функций для вычисления схожести и расстояния между строками.

Внимание

В настоящее время функции soundex, metaphone, dmetaphone и dmetaphone_alt плохо работают с многобайтными кодировками (в частности, с UTF-8). Используйте функции daitch_mokotoff или levenshtein в работе с такими данными.

Данный модуль считается «доверенным», то есть его могут устанавливать обычные пользователи, имеющие право CREATE в текущей базе данных.

F.17.1. Soundex #

Система Soundex позволяет вычислить похожие по звучанию имена, приводя их к одинаковым кодам. Изначально она использовалась для обработки данных переписи населения США в 1880, 1900 и 1910 г. Заметьте, что эта система не очень полезна для неанглоязычных имён.

Модуль fuzzystrmatch предоставляет две функции для работы с кодами Soundex:

soundex(text) returns text
difference(text, text) returns int

Функция soundex преобразует строку в код Soundex. Функция difference преобразует две строки в их коды Soundex и затем сообщает количество совпадающих позиций в этих кодах. Так как коды Soundex состоят из четырёх символов, результатом может быть число от нуля до четырёх (0 обозначает полное несоответствие, а 4 — точное совпадение). (Таким образом, имя этой функции не вполне корректное — лучшим именем для неё было бы similarity.)

Несколько примеров использования:

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;

F.17.2. Daitch-Mokotoff Soundex #

Как и исходная система Soundex, система Daitch-Mokotoff Soundex сопоставляет похожие по звучанию имена и преобразует их в один и тот же код. Однако Daitch-Mokotoff Soundex значительно полезнее для неанглийских имён, чем исходная система. Основные улучшения по сравнению с исходной системой перечислены ниже:

  • Код основан на первых шести значимых буквах, а не на четырёх.

  • Буква или комбинация букв сопоставляется с десятью возможными кодами, а не с семью.

  • Если две последовательные буквы имеют один звук, они заменяются цифрой.

  • Когда буква или комбинация букв могут иметь разные звуки, генерируется несколько кодов, чтобы охватить все возможные варианты.

Эта функция генерирует коды Daitch-Mokotoff Soundex для входных данных:

daitch_mokotoff(source text) returns text[]

Результат может содержать один или несколько кодов в зависимости от количества возможных вариантов произношения, поэтому он представляется в виде массива.

Поскольку код Daitch-Mokotoff Soundex состоит всего из 6 цифр, рекомендуется передавать в source одно слово или имя.

Несколько примеров:

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}

Для сопоставления отдельных имён возвращаемые текстовые массивы могут сравниваться напрямую с использованием оператора &&: любое пересечение можно считать совпадением. Для повышения эффективности можно использовать индекс GIN, см. Главу 70 и следующий пример:

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');

Для индексации и сопоставления любого количества имён в любом порядке можно использовать функции полнотекстового поиска. См. Главу 12 и следующий пример:

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');

Если желательно избежать пересчёта кодов Soundex при перепроверке индекса, вместо индекса по выражению можно использовать индекс по отдельному столбцу. Для этого можно использовать хранимый генерируемый столбец; см. Раздел 5.3.

F.17.3. Левенштейн #

Эта функция вычисляет расстояние Левенштейна между двумя строками:

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

И в source, и в target может быть передана любая строка, отличная от NULL, не длиннее 255 символов. Параметры стоимости (ins_cost, del_cost, sub_cost) определяют цену добавления, удаления или замены символов, соответственно. Эти параметры можно опустить, как во второй версии функции; в этом случае все они по умолчанию равны 1.

Функция levenshtein_less_equal является ускоренной версией функции Левенштейна, предназначенной для использования, только когда интерес представляют небольшие расстояния. Если фактическое расстояние меньше или равно max_d, то levenshtein_less_equal возвращает точное его значение; в противном случае она возвращает значение, большее чем max_d. Если значение max_d отрицательное, она работает так же, как функция levenshtein.

Примеры:

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)

F.17.4. Metaphone #

Metaphone, как и Soundex, построен на идее составления кода, представляющего входную строку. Две строки признаются похожими, если их коды совпадают.

Эта функция вычисляет код метафона входной строки:

metaphone(source text, max_output_length int) returns text

В качестве source должна передаваться строка, отличная от NULL, не длиннее 255 символов. Параметр max_output_length задаёт максимальную длину выходного кода метафона; если код оказывается длиннее, он обрезается до этой длины.

Пример:

test=# SELECT metaphone('GUMBO', 4);
 metaphone
-----------
 KM
(1 row)

F.17.5. Double Metaphone #

Алгоритм Double Metaphone (Двойной метафон) вычисляет две строки «похожего звучания» для заданной строки — «первичную» и «альтернативную». В большинстве случаев они совпадают, но для неанглоязычных имён в особенности они могут быть весьма различными, в зависимости от произношения. Эти функции вычисляют первичный и альтернативный коды:

dmetaphone(source text) returns text
dmetaphone_alt(source text) returns text

Длина входных строк может быть любой.

Пример:

test=# SELECT dmetaphone('gumbo');
 dmetaphone
------------
 KMP
(1 row)