本文章是由機器翻譯。

動態資料

使用 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 是真正的名字），則該演算法的工作原理如下：

1. 選擇以空格結尾的第一個單詞（位置 A）作為 W1。
2. 通過匹配查找清單來識別 W1 是否是稱呼。如果是，則忽略該稱呼並繼續執行步驟 4。
3. 如果 W1 不是稱呼，則考慮它是名字。不考慮對該段字串做進一步解析。
4. 如果 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	旁 McDonald’s

請注意，城市和州/省資訊將分別解析為 {city, state, country, zip} = {‘ Tucson’, ‘AZ’, ‘USA’, ‘85705’}，並從位址行中忽略這些資訊。

讓我們看看解析該位址行所需執行的步驟：

1. 定義街道類型和公寓類型的詳盡查找。
2. 為州/省定義特定于國家或地區的詳盡查找。 對州/省查找的定義應將 AZ 和 Arizona 視為同一個州（但不考慮拼寫錯誤）。
3. 將位址 1 和位址 2 連接為一個位址行。
4. 在位址行字串中從右側開始搜索與相應查找匹配的有效城市、州/省名稱或郵遞區號。 如果找到了，則繼續執行步驟 5；否則繼續執行步驟 6。
5. 如果在位址行字串中找到城市、州/省或郵遞區號資訊，則刪除這些資訊。
6. 使用結構 Street {[Number] [Name] [Type]} 和 Apartment {[Type] [Number]} 識別街道和公寓標記。 標記標識基於對街道類型和公寓類型查找中的值分別進行的 [Type] 搜索。
7. 執行步驟 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 演算法使用以下演算法檢測發音相似的單詞：

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。 如果兩個字串都不為空，而且它們不相同，則得分為 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.的卓越技術團隊