动态数据

2015-07-09

使用 F# 对数据库记录进行模式匹配

Ambar Ray

应用程序使用的数据不会凭空出现。为了获得满载有用数据的数据库，您要过几道难关。开始时，您可能需要对一些维度数据集合执行提取、转换和加载 (ETL) 过程。这通常包括对数据的清理、修剪和标准化。这样做只是为了得到适用于数据库的数据格式。

执行 ETL 步骤后，您需要检查记录，并确保这些记录有用且一致。这通常意味着实施匹配和删除重复项的过程。接下来，您将执行一些名称和地址解析。获得这些信息后，即可开始匹配过程并识别重复项。

有四种常见的匹配算法可用于删除属性重复项的过程：绝对匹配、部分匹配、Soundex 匹配和查找匹配。可对数据运行这些算法，一旦计算出百分比匹配得分，便可确定是丢弃还是存储这些数据。

作为一个练习，我已经使用 F# 模式匹配和异步编程功能实现了这四种匹配算法，以便快速计算聚合匹配得分。在本文中，我将向您演示匹配算法的实现过程以及如何生成聚合匹配得分。本文的最终目的是展现一些 F# 功能（例如，功能性编程、命令式编程和隐式类型推断系统），并演示如何使用 F# 快捷地完成一些重要的数据管理任务。

准备数据

开始时，我将在分段表中从各种事务性系统中加载维度数据。数据源可以是关系数据库、平面文件、Excel 文件或 XML 文件。ETL 过程通常使用诸如 SQL Server Integration Services (SSIS) 2008 之类的工具来清理、修剪和标准化传入的数据，随后再将这些数据加载到分段表中。分段表和主数据库都保存在一个主数据集散地。

正如前文所述，我使用通过 F# 和 Windows Presentation Foundation (WPF) 构建的独立应用程序来处理匹配和删除重复项的过程。在实际项目中，需要首先在数据访问层生成 ADO.NET 实体框架模型。这些模型将针对主数据集散地所含主数据表和所有查找表进行建模。

接下来，上一层应通过 Windows Communication Foundation (WCF) 服务公开底层模型。上面的业务逻辑层将实现匹配和删除重复项的例程以及解析方法。最后，呈现层将向数据管理人员显示各种 GUI。图 1 描述了应用程序的体系结构。

图 1 主数据管理应用程序体系结构

我不会在此处演示整个应用程序，而只是演示匹配和解析算法的实现。下面几节将解释如何在业务逻辑层中实现匹配和解析算法。

入门

为了实现本方案，我们假定将通过数据访问层从数据库中检索行数据，并且随后会将 WCF 数据服务存储在 List<T> 对象中以便做进一步的处理。这些 List<T> 对象将填入测试数据以实现相关算法。

主数据库包含所有源表以及分段和历史表。作为一个示例，图 2 显示了 Customer 数据实体的组成。

图 2 Customer 实体

CUSTFIRSTNAME

CUSTLASTNAME

CUSTHOUSENO

CUSTSTREETNAME

CUSTSTREETTYPE

CUSTCITY

CUSTSTATE

CUSTPOSTCODE

CUSTMOBILE

CUSTCOUNTRY

CUSTID

CUSTACTIVEFLAG

图 3 所示的流程图可以解释匹配算法。

图 3 匹配过程

步骤 1 实际并不是匹配过程的一部分，只是一个预备步骤。先对数据进行清理，并将其标准化为所需格式，然后发送数据以进行解析。

名称解析

步骤 2 中的解析过程也是匹配过程的一个预备步骤。在此步骤中，将从数据中解析出各个名称。假定输入的称呼中可以包含名字，则应将它分解（解析）为单个的元素：称呼和名字。因此，如果名字字段中提供了 Mr.John（其中 Mr.是称呼，John 是真正的名字），则该算法的工作原理如下：

选择以空格结尾的第一个单词（位置 A）作为 W1。
通过匹配查找列表来识别 W1 是否是称呼。如果是，则忽略该称呼并继续执行步骤 4。
如果 W1 不是称呼，则考虑它是名字。不考虑对该段字符串做进一步解析。
如果 W1 经识别为称呼，则识别下一个空格或字符串结尾（位置 B）。考虑将位置 A 和位置 B 之间的单词作为名字。不考虑对该段字符串做进一步解析。

例如，字符串“Mr.John”将如图 4 所示进行解析。

图 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]

在这段代码中，我使用 F# 中的关键字“match”和“with”进行模式匹配，在关键字后面使用模式匹配规则，再后面是“->”符号。

地址解析

下一步是地址行解析。地址行 1 和 2（相连的）应分解（解析）为门牌号码、街道名称、街道类型、公寓类型（可选，包括 Apt、Flat 或 Suite）和公寓号码（可选）。如果地址行 1 和 2 中提供了国家/地区、州/省和城市信息，则将忽略这些内容。

组合地址应解析为门牌号码、街道名称、街道类型以及（如果适用）公寓类型和公寓号码。我们通过下面的示例来说明：

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

在本例中，地址元素将如图 5 所示进行解析。

图 5 地址解析示例

门牌号码	街道名称	街道类型	街道类型	公寓号码	位置描述
421	East Drachman	Street	Suite	5A	beside McDonald’s

请注意，城市和州/省信息将分别解析为 {city, state, country, zip} = {‘ Tucson’, ‘AZ’, ‘USA’, ‘85705’}，并从地址行中忽略这些信息。

让我们看看解析该地址行所需执行的步骤：

定义街道类型和公寓类型的详尽查找。
为州/省定义特定于国家或地区的详尽查找。对州/省查找的定义应将 AZ 和 Arizona 视为同一个州（但不考虑拼写错误）。
将地址 1 和地址 2 连接为一个地址行。
在地址行字符串中从右侧开始搜索与相应查找匹配的有效城市、州/省名称或邮政编码。如果找到了，则继续执行步骤 5；否则继续执行步骤 6。
如果在地址行字符串中找到城市、州/省或邮政编码信息，则删除这些信息。
使用结构 Street {[Number] [Name] [Type]} 和 Apartment {[Type] [Number]} 识别街道和公寓标记。标记标识基于对街道类型和公寓类型查找中的值分别进行的 [Type] 搜索。
执行步骤 6 后，剩余的字符串段归为位置描述。

此算法的实现如图 6 所示。在这段代码中，我使用 while 循环扫描州/省、城市和邮政编码查找表以查找匹配项。主函数 ParseAddress 使用匹配项从地址行中删除城市、州/省和邮政编码信息。

图 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）以标识下面三种属性开始：

标识属性，包括 Cust_ID、名称（First_Name、Last_Name）、地址（House_no.、Street_Name、City、State、Zip_Code、Country）、Mob_Phone 等等。
区分属性，例如出生日期 (DOB)。
记录限定属性，例如国家、地区或邮政编码。

该应用程序将提示用户选择这些属性。至少需从标识属性、区分属性和记录限定属性中分别选择一个属性。请注意，如果由于标识属性和区分属性在清理和标准化过程中出现不一致或错误而对任何记录进行了标记，则不应将这些记录用于匹配目的。

如上所述，应基于四种例程执行匹配：绝对匹配、部分匹配、Soundex 匹配和查找匹配。该程序将提示用户选择用于每个属性的例程。至少应为每个属性选择一个例程，也可以为一个属性选择所有四种例程。

需要根据每个标识属性对业务过程（例如，标识客户（步骤 4））的重要性为其分配适当的权重。类似地，也需要为每个属性的每个例程分配权重。该程序应提示用户定义介于 1 至 5 之间的权重。

最后，我们进入步骤 5 并开始基于区分属性执行匹配以获取匹配窗口。因此，如果 DOB 定义为区分属性，那么需要基于 DOB 生成单独的窗口。这意味着同一窗口内的记录将具有相同的 DOB 值。在后续步骤中，将在单个窗口中而不是在不同窗口的记录中执行匹配过程。

绝对匹配

在步骤 6 中，将针对所有属性执行绝对匹配。此例程比较两个字段并且仅查找精确匹配项。将为精确匹配分配 100 分。任何其他结果均得 0 分。

例如，如果字段 1 包含“John”，而字段 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

部分匹配

接下来，可以针对所有属性执行部分匹配例程。部分匹配用于确定与空值的关系。例如，当某些记录具有客户名字而没有客户姓氏，或者具有客户姓氏而没有客户名字时，这很有用。有时，一个字段在两个记录中都为空。部分匹配算法可对其中一个重要字段可能为空的记录进行匹配。

空值和零被视为相同的值。至于绝对匹配，精确匹配的得分为 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 算法。 Soundex 算法使用以下算法检测发音相似的单词：

将字符串中的所有字母转换为大写。
保留字符串的第一个字母。
在第一个位置后，将出现的以下字母全都转换为空值：A、E、I、O、U、W、Y。
将预定集中的字母更改为对应的数字，如图 7 所示。
从步骤 4 得到的字符串中删除所有连续的重复数字和空值对。
返回字符串的前四个字符，不足四个字符时添加尾随零。

图 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。如果两个字符串都不为空，而且它们不相同，则得分为 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 例程的得分。

查找匹配

最后，针对街道类型属性执行查找匹配。将引用街道查找表来标准化街道类型，如下所示：

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 的得分。例如，如果绝对匹配得分为 0 且权重为 5，而 Soundex 得分为 100 且权重为 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 方法收集结果，该方法采用在 BeginInvoke 调用期间返回的 IAsyncResult 参数。最后，将返回该函数的最后一个表达式中的聚合匹配得分。

在步骤 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

F# 任务并行库中的 Task.Factory.StartNew 方法用于调用所比较两行数据的每对属性的聚合匹配得分，后跟一个计算累积结果的 for 循环。最后，返回百分比匹配得分。

匹配阈值（得分的上限阈值和下限阈值）由用户定义。系统将要求用户定义上限阈值和下限阈值。得分大于上限阈值的记录匹配将视为自动匹配，而得分低于下限阈值的记录匹配将被拒绝并被视为一个新的客户记录。介于这两个阈值之间（包含这两个阈值）的得分将标记出来以供检查。

这样，您就完成了记录匹配和删除重复项的过程。可以删除明显的重复项，并将标记待查的记录传递给真人或者功能更强大的编程检查过程。

Ambar Ray 是一位致力于开发 Microsoft 技术的解决方案架构师。Ray 有近 12 年的 IT 行业从业经验。

衷心感谢以下技术专家对本文的审阅：Don Syme、TechMahindra Ltd. 的卓越技术团队

通过