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

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

Метод хэширования

Метод хэшировния построен на принципе преобразования исходной строки в некий суррогатный код – хэш (hash), посредством некоторой функции (хэш-функции). В идеале, при таком преобразовании схожие строки имеют одинаковый хэш, что и позволяет их сопоставить.

Хэш-алгоритмы традиционно использовались и используются для связывания записей, в чем можно убедиться, ознакомившись с альманахом Федерального Комитета США по методам статистики, посвященному сопоставлению записей [8]. В этом альманахе описано достаточно много различных методов, так что автор рекомендует потратить время на его изучение.

Самыми известными хэш-преобразованиями являются алгоритмы Soundex [2] и MetaPhone.

Алгоритм MetaPhone адаптирован к особенностям русского языка Петром Каньковски из Новосибирска и прекрасно описан в его статье [6], где можно познакомиться с реализацией данного алгоритма на VB. Заметим, что такой алгоритм преобразования можно реализовать и средствами SQL.

Итак, при наличии функции преобразования, генерирующей общий хэш для похожих строк, процесс сравнения сводится к хэш-трансформации эталонов (синонимов) и рабочих строк и их последующего строгого сравнения. Строки, которые имеют одинаковый хэш считаются похожими.

Все достаточно просто, если не учитывать затраты на подбор подходящей функции преобразования.

Возможности оптимизации

Качество нечеткого сравнения можно улучшить, если работать не с фразами, а с отдельными словами, составляющими эти фразы. Здесь есть два пути оптимизации:

1. Оценить значимость каждого слова по частоте его повторяемости, которая легко вычисляется при формировании словаря.
   Если слово встречается слишком часто или слишком редко, то с большой вероятностью оно не оказывает существенного влияния на результат сравнения. Таким образом, используя статистические методы оценки (например, доверительный интервал, рассчитанный с применением критериев Стьюдента) [3] , возможно исключить из процесса сравнения незначимые⁷ слова. Это позволит улучшить результаты для обоих описанных методов;
2. Рассчитать хэш для каждого слова, что позволит получить более взвешенные результаты при использовании метода хэширования, т.к. для фразы подобрать хэш функцию гораздо сложнее, чем для отдельного слова.

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

ER диаграмма подсистемы

Стоит напомнить, что одной из целей создания подсистемы является условие ее реализации средствами РСУБД. Исходя из этого условия, была спроектирована некоторая типовая структура РБД, обеспечивающая работоспособность подсистемы и позволяющая использовать всю мощь языка SQL для сопоставления записей.

Логическая схема этой базы данных представлена в виде IDEF1X диаграммы и содержит следующие сущности:

Таблица 2. Сущности подсистемы

Рис.2 IDEF1X диаграмма подсистемы сопоставления записей (щёлкните для просмотра)

На диаграмме видно, что существуют две формально несвязанные⁸ области, предназначенные для хранения и обработки трансформированных данных эталонного набора и множества рабочих наборов. Собственно, цель подсистемы воссоздать связи между этими областями, оперируя обычными SQL-запросами.

• Таким образом, вся работа по связыванию записей, возлагаемая на РСУБД, сводится к трем этапам:
• Загрузка и инициализация сравниваемых наборов, в ходе которой происходит заполнение нужных таблиц
• Выполнение объединяющих (INNER JOIN) подзапросов к таблицам:
  • «Синоним» и «Рабочий набор» для строгого сравнения
  • «Би-грам индекс синонима» и «Би-грам индекс рабочего набора» для нечеткого сравнения
  • «Хэш-таблица предметной области» и «Хэш-таблица рабочего набора» для нечеткого сравнения
• Добавление записей в набор «Синоним» - расширение словаря синонимов.

Результирующие таблицы для подобных запросов на диаграмме не указаны, т.к. они являются вспомогательными и могут иметь различную реализацию⁹, что зависит от размеров наборов, используемой платформы и предпочтений разработчика.

⁷⁾ Однако нужно учесть, что статистика работает с вероятностями, и это не дает 100% уверенности в правомочности исключения из процесса сравнения тех или иных конкретных слов.

⁸⁾ Не связанные с помощью механизма DRI (Declarative Referential Integrity).

⁹⁾ Эти таблицы могут быть временными, представлены с помощью VIEW и т.п.

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

• Часть 3
• Часть 5

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

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