F.21. fuzzystrmatch — вычисление схожести и расстояния между строками #
Модуль fuzzystrmatch
содержит несколько функций для вычисления схожести и расстояния между строками.
Внимание
В настоящее время функции soundex
, metaphone
, dmetaphone
и dmetaphone_alt
плохо работают с многобайтными кодировками (в частности, с UTF-8). Используйте функции daitch_mokotoff
или levenshtein
в работе с такими данными.
Данный модуль считается «доверенным», то есть его могут устанавливать обычные пользователи, имеющие право CREATE
в текущей базе данных.
F.21.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.21.2. Daitch-Mokotoff Soundex #
Как и исходная система Soundex, система Daitch-Mokotoff Soundex сопоставляет похожие по звучанию имена и преобразует их в один и тот же код. Однако Daitch-Mokotoff Soundex значительно полезнее для неанглийских имён, чем исходная система. Основные улучшения по сравнению с исходной системой перечислены ниже:
Код основан на первых шести значимых буквах, а не на четырёх.
Буква или комбинация букв сопоставляется с десятью возможными кодами, а не с семью.
Если две последовательные буквы имеют один звук, они заменяются цифрой.
Когда буква или комбинация букв могут иметь разные звуки, генерируется несколько кодов, чтобы охватить все возможные варианты.
Эта функция генерирует коды Daitch-Mokotoff Soundex для входных данных:
daitch_mokotoff(источник
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, см. Раздел 62.4 и следующий пример:
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.4.
F.21.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.21.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.21.5. Double Metaphone #
Алгоритм Double Metaphone (Двойной метафон) вычисляет две строки «похожего звучания» для заданной строки — «первичную» и «альтернативную». В большинстве случаев они совпадают, но для неанглоязычных имён в особенности они могут быть весьма различными, в зависимости от произношения. Эти функции вычисляют первичный и альтернативный коды:
dmetaphone(source text) returns text dmetaphone_alt(source text) returns text
Длина входных строк может быть любой.
Пример:
test=# SELECT dmetaphone('gumbo'); dmetaphone ------------ KMP (1 row)