2 мая 2012 г.

Нечеткое сравнение строк (fuzzy string match) в Excel с помощью Fuzzy Lookup

Еще одна проблема, которую часто приходится решать при обработке данных для последующего анализа - это сопоставление информации из разных источников. В наиболее простом случае это может быть сопоставление двух таблиц, в которых один из столбцов полностью или частично совпадают. В случае, если обработка данных проходит в СУБД, то задача решается написанием простого SQL-запроса (при условии, что исходные таблицы правильно созданы и имеют идентификаторы). В Excel для решения подобных задач существует замечательная функция ВПР (VLOOKUP), которая  берет значение в одном из столбцов таблицы и возвращает значение из другого столбца.
Однако практическое использование этой функции для обработки обычных данных, может оказать довольно проблематичным. Что делать, если значения "почти" совпадают, но не совсем точно? К примеру, в одной из таблиц сравниваемая ячейка имеет запятую, а в другой нет? Или в одной используется "-", а  в другой "–" и так далее. 
Я с подобными трудностями  постоянно сталкиваюсь как минимум в двух случаях:

  1. При обработке данных по отдельным регионам РФ или странам мира. Проблема заключается в том, что разные страны или регионы могут иметь в разных источниках слегка отличающиеся названия. К примеру, " г. Москва" или "Москва (город)", "Белоруссия" или "Республика Беларусь", "Ханты-Мансийский автономный округ - Югра" или " Ханты-Мансийский авт. округ - Югра" и так далее. Примеров может быть множество, причем зачастую один и тот же источник (тот же Росстат) может использовать в разных публикациях или разных источниках немного отличающиеся названия регионов. Формально существует ГОСТ 7.67-2003, который определяет как должны называться страны и российские регионы "по стандарту", но на практике в точности ему никто не следует даже в официальных статистических публикациях. Да и ГОСТ сам себе уже старый (2003 год) и странный.  к примеру, в нем определены "Башкирия (Республика Башкортостан)", но просто "Татарстан". Почему именно так понять решительно невозможно, запомнить - тем более. Названия стран в английском языке также могут именоваться слегка по разному. Классическое "USA", "U.S." или "United States"?
  2. Названия видов экономической деятельности ( поОКВЭД). Формально тоже существует официальный вариант названий, выложенный на сайте Росстата. Но и сам Росстат ему не следует. К примеру, в ЦБСД названия видов деятельности часто имеют такой вид "Предоставление усл. по добыче нефти и газа" вместо "Предоставление услуг по добыче нефти и газа" (11.2) или "Добыча и произ-ство соли" вместо "Добыча и производство соли" и так далее. ЦБСД при выдаче результатов по видам экономической деятельности не сохраняет код вида, поэтому идентификация возможно только по названию. Новая информационная система - "Новая межведомственная информационно-статистическая система"-  имеет одинаковые названия видов в соответствии со стандартом и даже умеет выдавать результаты в формате SDMХ, в котором присутствуют коды видов деятельности, но она обновляется с большим опозданием. 
Этими примерами все не ограничивается. Подобная проблема возникает постоянно, когда нужно объединить информацию из разных источников, относящихся к одной и той же сущности, которая не имеет однозначного идентификатора. 
Что же делать?
Первый и достаточно очевидный ответ - сделать все вручную. Метод вполне хороший и оправдывает себя, если количество "сущностей" не слишком велико, и задача возникает лишь эпизодически. 
Если же речь о других масштабах, к примеру, раскидать данные по всем более чем двум тысячам видам деятельности и имеет регулярный характер, можно подумать об автоматизации, по крайней мере частичной. 
В терминах обработки текстов подобная задача носит стандартное название "fuzzy string match". Существует множество алгоритмов для решения задач. Хорошее их описание на русском языке есть на хабрахабре. Общая идея всех алгоритмов - разработка некоторой метрики оценки "схожести" строк. Полностью одинаковые строки имеют метрику 1.0, полностью не совпадающие строки - 0.0. Пользователь задает "точку отсечения" строк, которые будут считаться одинаковыми - к примеру, это может быть 0.9 и алгоритм считает, что строки которые значение метрики больше являются одинаковыми. Один из наиболее известных метрик - расстояние Левенштейна (по имени советского математика из Института им. Келдыша). Расстояние Левенштейна определяет минимальное количество вставок, замен или удалений символов, необходимое для того, чтобы превратить одну строку в другую. 
Алгоритмы - это хорошо, но как воспользоваться их возможностями без необходимости того, чтобы программировать самому? 
Я знаю два бесплатных инструмента, которые можно использовать прямо "с колес" без особых знаний тонкостей алгоритмов: 
  1. Google Refine. Как называет его сама Google, " a power tool for working with messy data".  Программа бесплатно скачивается и устанавливается на десктоп. Работает в окне браузера. Позволяет открыть локальный файл или документ Google Docs и сопоставить "похожие" значения. Для нечеткого сравнения программа предлагает несколько алгоритмов, подробно описанных в документации. Вообще программа умеет много чего, и имеет смысл поразбираться в ней, благо документация написана хорошо, есть даже видеоролики с иллюстрациями разных возможностей. Проблема для меня заключается в том, что передача файлов и обратно в Google Refine занимает время. Работа в веб-браузере понятна, но не очень удобна (для меня по крайней мере), поэтому я использовал несколько раз Google Refine для обработки бюджетной статистики и обработки большой таблицы со статистикой по странам по разным странам, но не нашел программу уж очень удобной для быстрой работы. 
  2. Надстройка Fuzzy Lookup для Excel, написанная самой Microsoft. Программа также бесплатно скачивается и устанавливается в Excel. Внешний вид выглядит примерно так (обработка таблиц с видами деятельности): 

В архиве есть файл с примером, который показывает как все работает. Важное, что нужно запомнить для  того, чтобы сравнивать таблицы: нужно их создать в виде "таблицы" (то есть Вставка-Таблица). Первой выбирается таблица из которой берутся исходные значения, второй - которые сопоставляются с исходными. Можно выбрать несколько столбцов, по которым будет проводиться сопоставление столбцов, для этого надо добавить несколько столбцов в Match Columns. В Output Columns можно выводить не все имеющиеся столбцы, и лишь те, что нужно. Это довольно удобно. К примеру, стандартная функция ВПР ничего подобного не умеет, поэтому надстройкой Fuzzly Lookup можно пользоваться и для "четкого" сопоставления разных таблиц.
Алгоритм работы программы не описывается, но на практике он дает вполне нормальные результаты и для строк на русском языке. Главное не забыть, проверить результаты сопоставления и исправить возможные ошибки алгоритма вручную. Для этого надо обратить на строки, в которых Fuzzy.Lookup.Similarity отличается от 1 и удостовериться, что "автоматическое" сопоставление сработало правильно. 


P.S. Функция ВПР имеет параметр "Интервальный просмотр", который можно поставить на значение "1". Это будет означать приблизительное соответствие . Но я не рекомендую его использовать ни при каких обстоятельствах, так как результаты этой "приблизительности" абсолютно непонятны. Можно легко получить неправильные значения. Ошибку же крайне сложно будет обнаружить пост-фактум.