fuzzystrmatch — определение сходства и расстояния между строками
Эта страница переведена при помощи нейросети GigaChat.
Модуль fuzzystrmatch предоставляет несколько функций для определения сходства и расстояния между строками.
В настоящее время функции soundex, metaphone, dmetaphone, и dmetaphone_alt не работают хорошо с многобайтовыми кодировками (такими как UTF-8). Используйте daitch_mokotoff или levenshtein с такими данными.
Этот модуль считается «надежным», то есть его могут устанавливать обычные пользователи, которые имеют привилегию CREATE для текущей базы данных.
Soundex
Система Soundex представляет собой метод сопоставления похожих по звучанию имен путем преобразования их в один и тот же код. Первоначально он использовался Бюро переписи населения США в 1880, 1900 и 1910 годах. Обратите внимание, что Soundex не очень полезен для имен, не являющихся английскими.
Модуль fuzzystrmatch предоставляет две функции для работы с кодами Soundex:
soundex(text) returns text
difference(text, text) returns int
Функция soundex преобразует строку в ее код Soundex. Функция difference преобразует две строки в их коды Soundex, а затем сообщает количество совпадающих позиций кода. Поскольку коды Soundex состоят из четырех символов, результат варьируется от нуля до четырех, где ноль означает отсутствие совпадения, а четыре - точное совпадение (таким образом, функция неправильно названа – 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;
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:
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');
Для индексации и сопоставления любого числа имен в любом порядке можно использовать функции полного текстового поиска:
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 во время проверки индексов, вместо индекса выражения можно использовать индекс отдельного столбца. Для этого можно использовать сохраняемый генерируемый столбец.
Левенштейн
Эта функция вычисляет расстояние Левенштейна между двумя строками:
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 могут быть любой непустой строкой длиной не более 255 символов. Параметры стоимости определяют, сколько стоит вставка символа, удаление или замена соответственно. Можно опустить параметры стоимости, как во второй версии функции, в этом случае они все принимают значение 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)
Metaphone
Metaphone, как и Soundex, построен на идее составления кода, представляющего входную строку. Две строки считаются похожими, если у них одинаковый код.
Эта функция вычисляет код метафона входной строки:
metaphone(source text, max_output_length int) returns text
source должен быть непустой строкой с максимальной длиной 255 символов. max_output_length устанавливает максимальную длину выходного кода метафона, если длиннее, вывод усекается до этой длины.
Пример:
test=# SELECT metaphone('GUMBO', 4);
metaphone
-----------
KM
(1 row)
Double Metaphone
Система Double Metaphone вычисляет две строки «похожего звучания» для заданной входной строки – одну «первичную» и другую «альтернативную». В большинстве случаев они одинаковы, но особенно для имен, не являющихся английскими, они могут немного отличаться в зависимости от произношения. Эти функции вычисляют первичный и альтернативный коды:
dmetaphone(source text) returns text
dmetaphone_alt(source text) returns text
Нет ограничения на длину входных строк.
Пример:
test=# SELECT dmetaphone('gumbo');
dmetaphone
------------
KMP
(1 row)