Нечеткое сравнение строк в Oracle – PL/SQL пакет UTL_MATCH

Нечеткое сравнение строк может потребоваться при выполнении многих задач. Одна из типичных задач – выверка данных и поиск нечетких дубликатов. Когда, например, надо сопоставить  “’Медведев” и “Медведёв” и затем как-то объединить эти строки.
Для решения такого плана задач существуют различные специализированные инструменты, например, Russian Context Optimizer (RCO). Обладая многими замечательными возможностями такие продукты, однако, стоят немалых денег, что не всегда приемлемо. 
В базе данных Oracle начиная с версии 11g официально появился новый пакет UTL_MATCH, который включает в себя несколько любопытных функций для нечеткого сравнения строк. Эти функции основаны на алгоритме вычисления дистанции Левенштейна и алгоритме сходства Джаро-Винклера.
При вычислении дистанции Левенштейна вычисляется минимальное количество вставок, удалений и замен символов, требуемых для приведения первой строки ко второй. Если дистанция равна нулю, то это означает, что сравниваемые строки идентичны. Чем больше числовая величина дистанции, тем менее похожи друг на друга строки.
В алгоритме сходства Джаро-Винклера вычисляется степень похожести двух строк на основании перестановок символов и поиска похожих фрагментов. Две строки считаются идентичными, если степень их похожести равна единице. Отличающиеся строки имеют степень похожести меньше единицы. Соответственно, чем меньше значение похожести, тем менее соответствуют друг другу строки.
Боле подробно про теоретические основы нечеткого сравнения строк рекомендую почитать в следующих статьях:
Нас же в этой статье больше интересует практическое использование этих алгоритмов посредством стандартного PL/SQL пакета базы данных Oracle – UTL_MATCH.

EDIT_DISTANCE

Функция EDIT_DISTANCE пакета UTL_MATCH вычисляет дистанцию Левенштейна между двумя заданными строками. Пример использования функции:

1
SELECT utl_match.edit_distance('первая строка', 'строчка вторая') Distance FROM dual;
Результат выполнения функции:
EDIT_DISTANCE
Мы получили, что требуется 18 операций для приведения первой строки ко второй.

EDIT_DISTANCE_SIMILARITY

Эта функция аналогична предыдущей с той разницей, что она выдает процент схожести заданных строк. Например:

1
SELECT utl_match.edit_distance_similarity('первая строка', 'строчка вторая') Similarity FROM dual;
Получим результат:
EDIT_DISTANCE_SIMILARITY
Иными словами строки согласно алгоритму дистанции Левенштейна похожи друг на друга примерно на треть.

JARO_WINKLER

Функция JARO_WINKLER пакета UTL_MATCH вычисляет числовую величину схожести  между двумя заданными строками по алгоритму Джаро-Винклера.  Пример использования функции:

1
SELECT utl_match.jaro_winkler('первая строка','строчка вторая') FROM dual;
Результат выполнения функции:
JARO_WINKLER
Согласно полученному значению заданные строки имеют степень схожести между собой примерно на три четверти.

JARO_WINKLER_SIMILARITY

Эта функция аналогична предыдущей с той разницей, что результат представлен в виде целочисленного процента:

1
SELECT utl_match.jaro_winkler_similarity('первая строка','строчка вторая') Similarity FROM dual;
Результат выполнения:
JARO_WINKLER_SIMILARITY

Итоги

В результате, на взгляд автора, предпочтительнее использование функций, основанных на алгоритме Джаро-Винклера, так как этот алгоритм показывает наиболее приближенные к реальности результаты. Однако дистанции Левенштейна могут быть также успешно использованы для сравнения однословных строк, для которых он более приспособлен. Также дистанции Левенштейна могут быть в этом случае более гибкими, так как позволяют вычислять производные величины схожести, основываясь не только на значении вычисленной дистанции, но так же и на отношении дистанции к длине сравниваемых строк. 
В любом случае наличие в базе данных Oracle стандартных функций для нечеткого сравнения строк может быть очень полезно во многих случаях, когда не требуются возможности платных сторонних продуктов.

Related Post

Получение списка значений в Oracle SELECT... Иногда в SQL запросе требуе...
Аппроксимация на PL/SQL Для некоторого класса за...
Поиск курса валюты Необходимо написать SQL зk...
Создание DIRECTORY в Oracle   Объект DIRECTORY может потребоваться для работы пакета UTL_FILE или иных PL/SQL процедур и функций, которым требуется создание или чтение файлов оп...

3 thoughts on “Нечеткое сравнение строк в Oracle – PL/SQL пакет UTL_MATCH

  1. Добрый день!
    Подскажите, а почему вы вызываете эти процедуры при помощи SELECT ? И что это за таблица “dual” ? Есть же обычный вариант вызова – название функции и скобки?

  2. Это стандартный способ получения результата функции при помощи select. Dual – это псевдотаблица в oracle, про нее можно уточнить в документации. Еще используется, если надо получить результат вычисления чего либо, например, пишут, select 6*4-3 from dual

  3. Не знаете а насколько быстро будет работать эта функция? На практике могут встречаться таблицы с большим количеством строк. Может посоветуете какие-нибудь приемы для ускорения подобных выборок. Я так понимаю даже если построить индекс по столбцу таблицы, по которому осуществляется поиск – это не поможет в плане ускорения? А вообще конечно это здорово что появилась такая возможность. Давно ждал 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *