Подсистема сопоставления записей в хранилище данных (часть 3)

Автор: Дмитрий Орлов

Методы нечеткого сравнения

Разобравшись с принципом работы подсистемы легко заметить, что основной вклад в эффективность работы подсистемы вносит именно стадия нечеткого сравнения. О том, как осуществлять нечеткий поиск и сравнение написано достаточно много [5,7,8], однако большинство алгоритмов невозможно⁵ адаптировать к особенностям РСУБД. Рассмотрим вкратце два основных метода, которые достаточно просто реализовать с использованием языка SQL.

Метод Q-грам

Это - самый простой и очевидный метод, который, тем не менее, может показать хорошие результаты для некоторых видов данных, например географических названий.

Суть метод проста – сравниваемые строки режутся на подстроки длины Q (Q-грамы), далее осуществляется сравнение наборов подстрок и, исходя из количества совпавших подстрок, можно сделать выводы об их похожести или непохожести [10].

Критериями, в данном случае, могут служить следующие величины:

• Количество совпавших подстрок с учетом длин сравниваемых строк;
• Количество совпавших подстрок с учетом их позиций в сравниваемых строках;
• Количество совпавших подстрок с учетом их позиций в сравниваемых строках и длин сравниваемых строк;
• Количество совпавших подстрок с учетом допустимого интервала отклонения их позиций в сравниваемых строках и допустимого отклонения длин сравниваемых строк.

Судя по опытным данным, наиболее оптимальным является деление на подстроки длины Q = 2 (би-грамы).

Рассмотрим пример:

Таблица 1. Исходные данные

Количество Q-грам в строке рассчитывается по следующей формуле:

К = Длина строки – Q + 1

В случае би-грам для эталона эта величина равна 19, а для рабочей строки 16. Сами би-грамы приведены в таблице 2.

В случае би-грам для эталона эта величина равна 19, а для рабочей строки 16. Сами би-грамы приведены в таблице 2.

Таблица 2. Би-грамы

Теперь можно продемонстрировать, как результат сравнения зависит от критерия идентичности, в очередной раз подчеркнув важность и сложность задачи по формированию критериев.

Определим два различных критерия идентичности:

КИ1 = Количество совпадений/ Кэталона

КИ2 = Количество совпадений * 2 / (Кэталона + Крабочей строки)

Для нашего случая они таковы (количество совпадений не учитывает повторяемость подстроки ТА):

КИ1 = 14/19 = 0.73

КИ2 = 14 * 2/(19+16) = 0.8

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

Тогда, согласно критерию КИ1 – строки разные, а для КИ2 – похожие. В общем - есть простор для творчества.
Основными достоинствами данного метода являются его простота и легкость реализации.

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

Недостатком же является необходимость работать с огромным количеством записей – Q-грамами.

⁵⁾ Здесь имеется ввиду возможность реализации на диалекте SQL, близком к стандарту SQL-92, т.е. не рассматриваются варианты с применением расширенных хранимых процедур и функций, реализованных на других языках программирования.

⁶⁾ Курсивом выделены совпадающие подстроки

Продолжение следует...

• Часть 2
• Часть 4

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

Если вы нашли в сети интересные ссылки на ресурсы по технологиям хранилищ данных, OLAP, CRM или data mining, и хотите поделиться ими с другими, присылайте их. Я с удовольствием размещу их на этом сайте.