Динамические данные

Поиск записей в базе данных с помощью алгоритмов сравнения с образцом в F#

Эмбар Рей

Загрузка примера кода

Данные, используемые вашим приложением, не появляются из ниоткуда. Чтобы в итоге получить базу данных с полезной информацией, вам придется слегка попотеть. Для начала вам, вероятно, понадобится выполнить процесс извлечения, преобразования и загрузки (extract, transform and load, ETL) применительно к некоему набору многомерных данных (dimensional data). При этом, как правило, осуществляется чистка, отсечение (pruning) и стандартизация данных. И все это просто для того, чтобы получить данные в той форме, в которой их можно разместить в ваше базе данных.

После этапа ETL вы захотите перебрать все записи и убедиться, что они полезны и согласованы. Обычно это подразумевает реализацию процесса сравнения и дедупликации. Далее вы осуществляете разбор имен и адресов в том или ином виде. Эта информация позволяет начать процесс поиска, сравнения и выявления дубликатов.

Существует четыре распространенных алгоритма поиска, применяемых в процессе дедупликации атрибутов (attribute deduplication processes): абсолютное совпадение, частичное совпадение, Soundex и по таблице поиска. Используя эти алгоритмы к данным и вычисляя степень совпадения в процентах, вы можете решать, сохранять или отбрасывать анализируемые данные.

В качестве упражнения я реализовал эти четыре алгоритма поиска, используя сравнение по образцу в F# (pattern matching) и средства асинхронного программирования для быстрого подсчета совокупной степени совпадения. В этой статье я поясню свою реализацию алгоритмов поиска и то, как я вычисляю совокупную степень совпадения (aggregate match score). Конечная цель статьи — продемонстрировать некоторые средства F#, такие как функциональное программирование, императивное программирование и систему неявного распознавания типов (implicit type inference system), а также показать, как с помощью F# можно легко и быстро выполнять некоторые важные задачи, связанные с управлением данными.

Подготовка данных

Я начну с загрузки многомерных данных из различных транзакционных систем в промежуточную таблицу (staging table). Источниками данных могли бы быть реляционная база данных, плоский файл (flat file), таблицы Excel или XML-файл. В процессе ETL часто используется такой инструмент, как SQL Server Integration Services (SSIS) 2008, для чистки, отсечения и стандартизации входящих данных и последующей загрузки промежуточных таблиц. Промежуточные таблицы и база данных master хранятся в концентраторе эталонных данных (master data hub).

Как упоминалось, я использую отдельное приложение, созданное на F# и Windows Presentation Foundation (WPF) и отвечающее за процесс сравнения и дедупликации. В реальных проектах вы должны сначала сгенерировать модели ADO.NET Entity Framework на уровне доступа к данным. Эти модели описывают таблицы эталонных данных наряду со всеми таблицами поиска, присутствующими в концентраторе эталонных данных.

Затем выше расположенный уровень должен предоставлять доступ к нижележащей модели через WCF-сервисы (Windows Communication Foundation). Уровень бизнес-логики должен реализовать процедуры сравнения и дедупликации, а также методы разбора. Наконец, презентационный уровень предоставляет лицу, управляющему данными, различные GUI. Архитектура приложения показана на рис. 1.

Рис. 1. Архитектура приложения для управления эталонными данными

Я не собираюсь демонстрировать здесь все приложение — только реализацию алгоритмов поиска и разбора. В следующих разделах поясняется реализация этих алгоритмов на уровне бизнес-логики.

Приступаем

Для наших целей предположим, что данные строк (row data) извлекаются из базы данных через уровень доступа к данным и WCF Data Services и впоследствии хранятся в объектах List<T> для дальнейшей обработки. Эти объекты List<T> будут заполняться тестовыми данными для реализации соответствующих алгоритмов.

База данных master содержит все исходные таблицы (source tables), а также промежуточные таблицы и таблицы истории (history tables). В качестве примера в табл. 1 показано, из чего состоит сущность данных Customer.

Табл. 2. Сущность Customer

CUSTFIRSTNAME

CUSTLASTNAME

CUSTHOUSENO

CUSTSTREETNAME

CUSTSTREETTYPE

CUSTCITY

CUSTSTATE

CUSTPOSTCODE

CUSTMOBILE

CUSTCOUNTRY

CUSTID

CUSTACTIVEFLAG

Алгоритм поиска можно пояснить с помощью схемы на рис. 2.

Рис. 3. Процесс сравнения

Этап 1 на самом деле не является частью процесса сравнения — это подготовка. Данные чистятся и стандартизуются в выбранный формат до того, как передаются для разбора.

Разбор имен

Процесс разбора на этапе Step 2 также предшествует процессу сравнения. На этом этапе имена разбираются на данные. Допуская ввод обращения (salutation) вместе с первым именем, его следует разделить (разобрать) на индивидуальные элементы: обращение и первое имя. Таким образом, если в поле First Name содержится «Mr.John», где «Mr.»— обращение, а «John» — само первое имя, тогда алгоритм будет работать следующим образом.

1. Выбирает первое слово, заканчивающееся пробелом (позиция A), как W1.
2. Определяет, является ли W1 обращением, сравнивая со списком поиска (lookup list). Если да, игнорирует обращение и переходит в п. 4.
3. Если W1 — не обращение, значит, это первое имя. Дальнейший разбор этого фрагмента строки прекращается.
4. Если W1 определяется как обращение, выполняется поиск следующего вхождения пробела или конца строки (позиция B). Слово, заключенное между позициями A и B, считается первым именем. Дальнейший разбор этого фрагмента строки прекращается.

Например, строка «Mr.John» была бы разобрана, как показано в табл. 2.

Табл. 4. Пример разбора имени

Имя	M	r	.		J	o	h	n
Позиция	1	2	3	4	5	6	7	8

Позиции 1–3 образуют обращение. Оно не обязательно и заполняется, только если первое слово совпадает с одним из значений в обширном списке возможных обращений. (Я делаю допущение, что каждая часть имени, включая обращение, действительно разделяется пробелом. Исключение делается только для поля последнего имени.) В табл. 4 позиции 5–8 образуют первое имя.

Реализация этого алгоритма разбора на F# выглядит так:

let ParseName(strName : string)=
  let input = strName.Trim()
  let splitNames = input.Split([|" "|], StringSplitOptions.None)
  match splitNames.[0] with
    | "Mr" | "Mr." | "Mrs" | "Mrs." | "Dr" | "Dr." | "Kum" | "Kum." 
      -> splitNames.[1]
    | _-> splitNames.[0]

В этом коде я выполняю поиск по образцу (pattern matching), используя ключевые слова match и with в F#, за которыми указываются правила поиска по образцу, а за каждым из них — символ «->».

Разбор адреса

Следующий шаг — разбор строки адреса. Строки 1 и 2 адреса (сцепленные) нужно разделить (разобрать) на номер строения или дома, название улицы, тип улицы (street type), тип квартиры (apartment type) (необязателен, представляет собой Apt, Flat или Suite) и номер квартиры (необязателен). Если в строках 1 и 2 адреса предоставляется информация о городе, штате и стране, тогда те данные нужно опускать.

Комбинированный адрес (combined address) требуется разобрать на номер дома, название улицы, тип улицы и, если применимо, на тип и номер квартиры. Для иллюстрации рассмотрим пример:

421, East Drachman St, Suite 5A, Tucson, Arizona, beside McDonald’s

В этом случае элементы адреса разбираются, как показано в табл. 3.

Табл. 5. Пример разбора адреса

Номер дома	Название улицы	Тип квартиры	Тип квартиры	Номер квартиры	Описание местонахождения
421	East Drachman	Улица	Люкс	5A	Рядом с Макдональдс

Обратите внимание на то, что информация о городе и штате разбирается отдельно как city, state, country, zip = {‘ Tucson’, ‘AZ’, ‘USA’, ‘85705’} и опускается из строки адреса.

Ниже перечислены шаги, необходимые для разбора строки адреса.

1. Определяем полный поиск (exhaustive lookup) типов улицы и квартиры.
2. Определяем полный, но специфичный для страны или региона, поиск штата. Поиск штата должен быть определен так, чтобы AZ и Arizona идентифицировались как одно и то же (неправильное написание во внимание не принимается).
3. Сцепляем адрес 1 и адрес 2 в одну строку адреса.
4. Ищем в строке адреса, начиная от правой стороны, город, штат или ZIP-код (аналог почтового индекса) с учетом соответствующей информации в списках поиска. Если результат — true, переходим в п. 5, иначе — в п. 6.
5. Удаляем информацию о городе, штате или ZIP-коде, если она найдена в строке адреса.
6. Определяем части, относящиеся к улице и квартире, используя структуру Street [Number] [Name] [Type], Apartment [Type] [Number]. Идентификация частей основывается на поиске [Type] с учетом значений в соответствующих списках поиска для типов улицы и квартиры.
7. Считаем любые оставшиеся порции строки после п. 6 как часть описания местонахождения.

Реализация этого алгоритма на F# показана на рис. 6. В этом коде я использую циклы while, чтобы перебирать таблицы поиска для штатов, городов и ZIP-кодов в поисках совпадения. Основная функция ParseAddress использует это для исключения информации о городе, штате и ZIP-коде из строки адреса.

Рис. 6. Разбор строк адреса

let MatchCityStateZip (addressPart : string) = 
  // Match with a state
  let stateMatchFound = stateNameTable |> 
    List.exists (fun (part1,part2) -> 
    part1 = addressPart || part2 = addressPart) 
  // Match with a city
  let cityMatchFound = cities |> List.exists (fun city -> 
    city = addressPart)
  // Match with a ZIP code
  let zipMatchFound = zipCodes |> List.exists (fun zipCode -> 
    zipCode = addressPart)
  stateMatchFound || cityMatchFound || zipMatchFound

// The main parsing address algorithm is as follows:
let ParseAddress (strAddress : string) = 
  let mutable finalAddress = strAddress
  // Split the address
  let addressParts = strAddress.Split([|","|], 
    StringSplitOptions.None)
  // Remove city, state and ZIP information from the address
  for i = 0 to addressParts.Length - 1 do
    let currPart = addressParts.[i].Trim()
    if MatchCityStateZip currPart then
      // Index of current address part in original string
      let currIndex = finalAddress.IndexOf currPart
      // Remove city, state, ZIP information along with the 
      // following whitespace or comma
      finalAddress <- finalAddress.Remove(currIndex, currPart.Length)
  let finalAddress = finalAddress.Replace(", ,",",")
  let finalAddress = finalAddress.TrimEnd([|','; ' '|])
  finalAddress

Сравнение и дедупликация

Процесс сравнения и дедупликации на этапе 3 (рис. 3) начинается с идентификации следующих трех типов атрибутов:

• атрибутов идентификации (Identity attributes), в том числе Cust_ID, имени (First_Name, Last_Name), адреса (House_no., Street_Name, City, State, Zip_Code, Country), Mob_Phone и др.;
• отличительных атрибутов (discriminating attributes), таких как дата рождения (date of birth, DOB);
• атрибутов, определяющих записи (record-qualifying attributes), например страна, регион или почтовый индекс.

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

Как упоминалось, сравнение осуществляется на основе четырех процедур: абсолютное совпадение, частичное совпадение, Soundex и по таблице поиска. Программа будет предлагать пользователю выбрать, какие процедуры следует применять для каждого атрибута. Как минимум, для каждого атрибута нужно выбрать по одной процедуре, хотя допустим выбор и всех четырех процедур для атрибута.

Каждому атрибуту идентификации нужно присвоить весовую долю в зависимости от его значимости в бизнес-процессе, например идентификации клиента (этап 4). Аналогично весовые доли назначаются каждой процедуре для каждого атрибута. Программа должна предлагать пользователю указать весовые доли по шкале от 1 до 5.

Наконец, мы добираемся до этапа 5 и начинаем выполнять сравнение на основе отличительных атрибутов, чтобы получить окна сравнения (match windows). Таким образом, если DOB определена как отличительный атрибут, нужно будет сформировать отдельные окна на основе DOB. То есть записи внутри одного и того же окна должны иметь одно и то же значение DOB. На следующих этапах процесс сравнения будет выполняться внутри индивидуальных окон, а не для записей из разных окон.

Абсолютное совпадение

На этапе 6 я выполняю поиск по абсолютному совпадению для всех атрибутов. Эта процедура сравнивает два поля и ищет только точное совпадение. Каждому точному совпадению присваивается 100 баллов. Любой другой результат — 0 баллов.

Например, если и в поле 1, и в поле 2 содержится «John», это точное совпадение, и ему присваивается 100 баллов. Если в поле 1 содержится «Lisa», а в поле 2 — «Laura», это не точное совпадение, и оно получает 0 баллов.

Реализация этого алгоритма сравнения на абсолютное совпадение выглядит так:

let AbsoluteMatch (attrOfFirstRec : string) (attrOfSecondRec : string) =
  let attrRec01 = attrOfFirstRec.Trim().ToLower()
  let attrRec02 = attrOfSecondRec.Trim().ToLower()
  match attrRec01, attrRec02 with
    | "", "" -> 100
    | _, _ -> if attrRec01 = attrRec02 then 100 else 0

Частичное совпадение

Затем я выполняю процедуру поиска по частичному совпадению для всех атрибутов. Частичное совпадение используется, чтобы определить отношение как пустое значение (blank value). Это полезно, когда в некоторых записях есть, например, первое имя клиента, но отсутствует последнее (фамилия) или наоборот. Иногда какое-то поле пустое в обеих записях. Алгоритм поиска по частичному совпадению как раз и сравнивает эти записи, где одно из важных полей может быть пустым.

Пустые и нулевые значения считаются идентичными. Как и в случае абсолютного совпадения, точное совпадение оценивается в 100 баллов.Пустое значение поля в одной записи и заполненное в другой оценивается в 75 баллов, тогда как при наличии пустых значений в этих полях назначается 65 баллов.Любой другой результат дает 0 баллов.

Реализация этого алгоритма сравнения на частичное совпадение выглядит так:

let PartialMatch (attrOfFirstRec : string) (attrOfSecondRec : string) =
  let attrRec01 = attrOfFirstRec.Trim().ToLower()
  let attrRec02 = attrOfSecondRec.Trim().ToLower()
  match attrRec01, attrRec02 with
    | "", "" -> 65
    | _, "" | "", _-> 75
    | _, _ -> if attrRec01 = attrRec02 then 100 else 0

Обратите внимание на сходство этого кода с предыдущим.

Поиск совпадений Soundex

Теперь я выполняю алгоритм Soundex индивидуально для атрибутов первого имени, последнего имени (фамилии), названия улицы, города, штата и страны. Этот алгоритм распознает похоже звучащие слова, используя следующий алгоритм.

1. Переводит все буквы в строке в верхний регистр.
2. Сохраняет первую букву строки.
3. После первой позиции преобразует все вхождения следующих букв в пустые значения: A, E, I, O, U, W, Y.
4. Заменяет все буквы из предопределенных наборов соответствующими цифрами (табл. 7).
5. Удаляет все последующие пары дублируемых цифр и пустых значений из строки, полученной после выполнения п. 4.
6. Возвращает первые четыре символа строки, дополненной при необходимости концевыми нулями.

Табл. 7. Преобразование букв в Soundex

Буква	Соответствующая цифра
B, F, P, V	1
C, G, J, K, Q, S, X, Z	2
D, T	3
L	4
M, N	5
R	6

Назначение баллов в процедуре Soundex несколько отличается. Как и раньше, если обе строки идентичны, результат равен 100 баллов.Если одна строка пустая, а другая — нет, результат оценивается в 50 баллов.Если обе строки пустые, результат равен 0 баллов.То же самое происходит и в том случае, когда ни одна из строк не пуста и они не равны.

Реализация этого алгоритма на F# показана на рис. 8.

Рис. 8. Поиск совпадений Soundex

let SoundexMatch (attr1:string, attr2:string) = 
  let conv c = 
    match c with
    | 'A' | 'E' | 'I' | 'O' | 'U' | 'W' | 'Y' -> ' '
    | 'B' | 'F' | 'P' | 'V' -> '1'
    | 'C' | 'G' | 'J' | 'K' | 'Q' | 'S' | 'X' | 'Z' -> '2'
    | 'D' | 'T' -> '3'
    | 'L' -> '4'
    | 'M' | 'N' -> '5'
    | 'R' -> '6'
    | _ -> c

  let convertSoundex (inp:string) = 
    // Capitalize all letters in the string
    let chars = inp.ToUpper().ToCharArray() 
    let chars = 
      [| // Retain the first letter of the string
      yield chars.[0] 
      // Keep the first character, and remove pairwise-duplicates
      // Change letters from the predetermined sets to 
      // corresponding number 
      for (c1,c2) in Seq.pairwise (Seq.map conv chars) do
        // Remove all consecutive pairs of duplicate digits 
        // and blanks from the string 
        if c1 <> c2 && c2 <> ' ' then yield c2 |]
    // Convert back to a string
    String chars

  // Retain first four characters of resultant strings padded 
  // with trailing zeros if needed; leave unchanged if any 
  // string is blank
  let adjustResult (result:string) = 
    match result.Length with 
    | n when n >= 4 -> result.Substring(0, 4)
    | 0 -> result
    | n -> result + String.replicate (4 - n) "0"

  let attr1Result = attr1 |> convertSoundex |> adjustResult
  let attr2Result = attr2 |> convertSoundex |> adjustResult

  match attr1Result, attr2Result with
  | "", "" -> 0
  | "", _ | _, "" -> 50
  | _, _ -> if (attr1Result = attr2Result) then 100 else 0

В этом коде преобразование Soundex выполняется с применением поиска совпадений по образцу, оставляя первый символ нетронутым. В следующих двух циклах for отыскиваются последовательные дубликаты символов и каждый второй такой символ заменяется пробелом. В следующих двух циклах for удаляются пробелы, что в конечном счете приводит к удалению любых дубликатов. Таким образом, с помощью четырех циклов for мы удаляем смежные дублированные символы.

Далее посредством двух выражений if извлекаются первые четыре символа и при необходимости они дополняются нулями, чтобы в строке было минимум четыре символа. В заключение алгоритм поиска по образцу реализует расчет баллов для процедуры Soundex.

Сравнение по таблице поиска

Наконец, я выполняю сравнение по таблице поиска для атрибута типа улицы. Для стандартизации типа улиц я ссылаюсь на таблицу поиска улиц (street lookup table):

let LookupMatch (streetName : string) =
  let mutable streetMatchFound = false
  let mutable i = 0
  while ((no streetMatchFound) && (i < streetNames.Length)) do
    if (streetName = streetNames.[i]) then
      streetMatchFound <- true
  match streetMatchFound with
  | true -> 100
  | false -> 0

Этот код сканирует таблицу поиска улиц в поисках совпадения с названием улицы в цикле while, а затем возвращает баллы в зависимости от найденного совпадения.

Оценка результатов

На этапе 7 процесса сравнения я получаю количества баллов для каждого атрибута. Таким образом, если для первого имени процедура поиска абсолютного совпадения ничего не нашла, но процедура Soundex обнаружила совпадение, то баллы для первого имени будут соответственно 0 и 100.

На этапе 8 определяется весовая оценка совпадения для каждого атрибута, что в итоге дает атрибуту оценку от 1 до 5. Например, если нулевой балл, полученный при анализе процедурой поиска абсолютного совпадения, имеет вес 5, а 100 баллов, полученные после выполнения Soundex, имеют вес 4, то совокупная оценка для первого имени будет такой:

[(0x5)+(100x4)]/(5+4) ~ 44%

При допущении, что выбираются все алгоритмы поиска совпадения, реализация вычисления взвешенных оценок выглядит так, как показано на рис. 9.

Рис. 9. Процедура подсчета совокупной оценки совпадения

let WeightedAverage results = 
  let cumulativeWeight = results |> 
    Array.sumBy (fun (r, weight) -> r * weight) 
  let totalWeight = results |> 
    Array.sumBy (fun (r, weight) -> weight) 
  cumulativeWeight / totalWeight

// Aggregate match score
// Calling the match routine which in turn calls absolute match, 
// Partial Match and Soundex Match routines in parallel
let FindAggregateMatchScore row = 
  let resultsWithWeights = 
    Async.Parallel [ async { return AbsoluteMatch row, 5 } 
                     async { return PartialMatch row, 5 } 
                     async { return SoundexMatch row, 4} ]
    |> Async.RunSynchronously

  WeightedAverage resultsWithWeights

В этом коде предполагается, что для каждого атрибута вызываются все три процедуры поиска совпадения (но не для атрибута «улица», для которого нужно осуществлять сравнение по таблице поиска). Сначала для каждой процедуры поиска совпадения объявляются делегаты Func. Эти делегаты потом запускаются асинхронно с помощью метода BeginInvoke. После ожидания завершения задач на WaitHandle.WaitAll результаты собираются методами EndInvoke, которые принимают IAsyncResult-параметры, возвращаемые вызовами BeginInvoke. Наконец, совокупная оценка совпадения возвращается как последнее выражение в функции.

На этапе 9 совокупная оценка совпадения каждого атрибута умножается на весовые значения индивидуальных атрибутов, полученные значения суммируются, а результат выражается в процентах совпадения двух записей (рис. 10).

Рис. 10. Взвешенная оценка

// Percentage match score
let FindPercentageMatchScore(rows : seq<string * string>) = 
  let results = 
    Async.Parallel [ for row in rows -> 
    async { return FindAggregateMatchScore row } ] 
    |> Async.RunSynchronously

  // Apply a weight of 5 for the first attribute and a weight 
  // of 4 for second and a weight of 3 for all other attributes
  let resultsWithWeights = results |> 
    Array.mapi (fun i r -> 
    r, (match i with 0 -> 5 | 1 -> 4 | _ -> 3)) 

  WeightedAverage resultsWithWeights

Метод Task.Factory.StartNew из библиотеки Task Parallel Library для F# используется, чтобы вызывать процедуру подсчета совокупной оценки совпадения для каждой пары атрибутов двух сравниваемых строк данных, а в последующем цикле for вычисляется кумулятивный результат. Потом возвращается оценка совпадения в процентах.

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

На этом процесс сравнения и дедупликации записей заканчивается. Очевидные дубликаты удаляются, и вы можете передать записи, помеченные флагами, для анализа вручную или в более сложный процесс программного анализа.

Эмбар Рей (Ambar Ray) — архитектор решений на основе технологий Microsoft. Имеет почти 12-летний опыт работы в индустрии информационных технологий.

Выражаю благодарность за рецензирование статьи экспертам Дону Сайму (Don Syme), Technical Excellence Group of TechMahindra Ltd.