動的データ

F# によるデータベース レコードのパターン マッチング

Ambar Ray

コード サンプルのダウンロード

アプリケーションが使用するデータは、どこからともなく現れたりはしません。最終的にデータベースを有用なデータで満たすには、いくつかの処理を経る必要があります。まず、ディメンション データのコレクションに対して、抽出、変換、および読み込み (ETL) プロセスを実行することになるでしょう。これには、通常、データのクリーンアップ、排除、および正規化が含まれます。これは、データベースで有効な形式にデータを整えるための処理に過ぎません。

ETL プロセスが完了したら、レコードを検証して、レコードが有用で整合性が保たれていることを確認します。これには、通常、マッチングと重複除去のプロセスを実装することになります。次に、名前と住所の解析を行います。この情報が用意できたら、マッチング プロセスを開始し、重複の特定に取り掛かることができます。

属性の重複除去のプロセスによく使用されるマッチング アルゴリズムには、絶対一致、部分一致、SOUNDEX、ルックアップ一致の 4 種類があります。これらのアルゴリズムをデータに対して実行できます。いったん一致スコア (パーセント単位) が計算されたら、データを破棄するか格納するかを決定できます。

今回、演習として、F# のパターン マッチング機能と非同期プログラミング機能を使用して、これら 4 種類のマッチング アルゴリズムを実装し、集計一致スコアをすばやく計算できるようにしてみました。この記事では、このマッチング アルゴリズムの実装を紹介し、集計一致スコアをどのように計算するかを説明します。この記事の究極の目的は、関数型プログラミング、命令型プログラミング、型の推論システムなど、F# の機能のいくつかを紹介することと、F# を使用して重要なデータ管理タスクをすばやく容易に実現する方法を実例を基に説明することです。

データを準備する

まず、ディメンション データをさまざまなトランザクション システムからステージング テーブルに読み込みます。データ ソースには、リレーショナル データベース、フラット ファイル、Excel ファイル、または XML ファイルを使用できます。ETL プロセスでは、SQL Server Integration Services (SSIS) 2008 のようなツールを使用して、入力データのクリーンアップ、排除、および正規化を行い、その後、データをステージング テーブルに読み込みます。ステージング テーブルとマスター データベースは、マスター データ ハブ内に保持されます。

前述のとおり、マッチングと重複除去のプロセスに、F# と Windows Presentation Foundation (WPF) で作成した個別のアプリケーションを使用します。実際のプロジェクトでは、まず、データ アクセス層に ADO.NET Entity Framework モデルを生成します。これらのモデルにより、マスター データ ハブ内にあるすべてのルックアップ テーブルと合わせてマスター データ テーブルがモデル化されます。

次に、その上の層から、基盤のモデルを Windows Communication Foundation (WCF) サービスを利用して公開します。その上のビジネス ロジック層には、マッチングと重複除去のルーチンと、解析メソッドを実装します。最後に、プレゼンテーション層から、データ マネージャーにさまざまな GUI を提供します。図 1 に、このアプリケーションのアーキテクチャを示します。

図 1 マスター データ管理アプリケーションのアーキテクチャ

ここでは、アプリケーション全体を紹介することはせず、マッチングと解析アルゴリズムの実装についてのみ説明します。その後、マッチングと解析アルゴリズムのビジネス ロジック層への実装について説明します。

はじめに

このシナリオでは、行データをデータ アクセス層を介して取得し、その後、後続の処理のために WCF Data Services が List<T> オブジェクトに格納されるものとします。これらの List<T> オブジェクトには、適切なアルゴリズムの実装に必要なテスト データが設定されます。

マスター データベースには、すべてのソース テーブルとステージング テーブルおよび履歴テーブルが保持されます。一例として、図 2 に Customer データ エンティティの構成を示します。

図 2 Customer エンティティ

CUSTFIRSTNAME

CUSTLASTNAME

CUSTHOUSENO

CUSTSTREETNAME

CUSTSTREETTYPE

CUSTCITY

CUSTSTATE

CUSTPOSTCODE

CUSTMOBILE

CUSTCOUNTRY

CUSTID

CUSTACTIVEFLAG

マッチング アルゴリズムは、図 3 のフローチャートによって表すことができます。

図 3 マッチング プロセス

手順 1. は、実際にはマッチング プロセスの一環ではなく、むしろ前処理に当たります。解析に送る前に、データをクリーンアップし、望ましい形式に正規化します。

名前の解析

手順 2. の解析プロセスも、マッチング プロセスの前処理の 1 つです。この手順では、データから個々の名前を取り出し、解析します。敬称が名 (下の名前) と併せて入力されているものとし、個々の要素 (敬称と名) に分解 (解析) します。つまり、名のフィールドに「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	beside McDonald’s

市町村および州の情報は {city, state, country, zip} = {‘ Tucson’, ‘AZ’, ‘USA’, ‘85705’} として別途解析し、住所から削除していることに注意してください。

では、住所の解析に必要な手順を見ていきましょう。

1. ストリートの種類と集合住宅の種類について、完全なルックアップを定義します。
2. 各国または地域に即した州の完全なルックアップを定義します。州のルックアップは、AZ と Arizona は同じと認識されるように定義します (ただし、スペルの誤りは考慮しません)。
3. 住所 1 と住所 2 を連結して、1 行の住所にします。
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 参照) では、まず、次の 3 種類の属性を特定します。

• Cust_ID、名前 (First_Name、Last_Name)、住所 (House_no.、Street_Name、City、State、Zip_Code、Country)、Mob_Phone などの ID 属性。
• 誕生日 (DOB) などの識別属性。
• 国、地域、または郵便番号などのレコードを修飾する属性。

ユーザーに、これらの属性を選択するよう求めます。ID 属性、識別属性、およびレコード修飾属性を少なくとも 1 つずつ選択する必要があります。クリーンアップと正規化プロセスで、ID 属性および識別属性に不整合またはエラーがあるとレコードにフラグを設定している場合、それらのレコードはマッチング プロセスの対象とはしないことに注意してください。

前述のとおり、マッチングは絶対一致、部分一致、SOUNDEX、ルックアップ一致の 4 種類のルーチンを基に実行します。属性ごとに使用するルーチンを選択するようユーザーに求めます。属性ごとに少なくとも 1 つのルーチンが選択される必要がありますが、4 種類すべてを 1 つの属性に選択することもできます。

ビジネス プロセス (顧客の特定など) に対する重要度に応じて、各 ID 属性に適切な重みを割り当てる必要があります (手順 4.)。同様に、各属性の各ルーチンに重みを割り当てることも必要です。ユーザーに、1 ～ 15 の 15 段階で重みを定義するよう求めます。

最後に、手順 5. に進み、識別属性を基にマッチングを実行して、一致データを表示するウィンドウを生成します。したがって、DOB が識別属性として定義されていれば、DOB を基に個別のウィンドウを作成する必要があります。つまり、同じウィンドウ内のレコードは、DOB の値が同じになります。後続の手順では、複数のウィンドウにまたがりレコード間のマッチングを行うのではなく、個々のウィンドウ内でマッチング プロセスを実行します。

絶対一致

手順 6. では、すべての属性を対象に絶対一致を実行します。このルーチンでは、2 つのフィールドを比較して、完全一致のみを検索します。完全一致には、スコアとして 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

部分一致

次は、すべての属性を対象に部分一致ルーチンを実行します。部分一致は、空白値との関係を判断するために使用します。これは、たとえば、顧客の名があっても姓がない、またはその逆のパターンのレコードがある場合に役立ちます。場合によっては、どちらのレコードでも、あるフィールドが空白のこともあります。部分一致アルゴリズムは、重要なフィールドの 1 つが空白のままになっているようなレコードのマッチングに対応できます。

空白とゼロは、同じ値であると見なします。部分一致では、完全一致の場合にスコアを 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. 2 番目の文字からは、A、E、I、O、U、W、Y の各文字をすべて空白に変換します。
4. 図 7 に示す、事前に定義した対応表に従い、文字を対応する数字に変換します。
5. 手順 4. の処理後の文字列から、同じ数字および空白が 2 つ続いている部分をすべて削除します。
6. 文字列の最初の 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 変換を行っています。続く 2 つの for ループでは、連続する同じ文字を検索し、そのような文字の 2 番目の文字を空白で置き換えています。次の 2 つの for ループでは、空白を破棄することで、重複を削除しています。したがって、この 4 つの for ループで、連続する同じ文字を破棄しています。

次の 2 つの if ステートメントでは、最初の 4 文字を抜き出し、必要に応じてゼロを埋め込んで、少なくとも 4 文字になるようにしています。最後のパターン マッチングで、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

このコードでは、3 種類のルーチンがすべて、各属性に対して呼び出されることを想定しています (ただし、ストリート属性にはルックアップ一致を実行するため、ストリート属性は除きます)。まず、Func デリゲートを一致ルーチンごとに宣言します。次に、BeginInvoke メソッドを使用して、非同期にこのデリゲートを呼び出します。WaitHandle.WaitAll によってタスクの完了を待機したら、BeginInvoke 呼び出し中に返された IAsyncResult パラメーターを受け取る EndInvoke メソッドによって、結果を収集します。最後に、この関数の最後の式によって、集計一致スコアが返されます。

手順 9. では、各属性の集計一致スコアに、各属性の重みを掛けたうえで、合算し、2 レコード間の一致スコアとしてパーセントで表します (図 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 Parallel Library の Task.Factory.StartNew メソッドを使用して、比較対象の 2 列の各属性の組に対して集計一致スコアを呼び出し、次の for ループで総計を計算しています。最後に、パーセントの一致スコアを返します。

一致しきい値 (スコアのしきい値の上限と下限) は、ユーザーが定義します。システムによって、上限と下限のしきい値を定義するように求められます。一致スコアが上限のしきい値を超えているレコードは自動的に一致と見なし、一致スコアが下限のしきい値を下回っているレコードは拒否して、新しい顧客レコードであると見なします。上限のしきい値以下で下限のしきい値以上のスコアは、レビュー対象としてマークします。

以上で、レコードのマッチングおよび重複除去プロセスは完了です。明白な重複は削除でき、レビュー対象としてマークしたレコードは、人間またはより詳細なプログラムによるレビュー プロセスに渡すことができます。

Ambar Ray はマイクロソフト テクノロジを扱うソリューション アーキテクトです。約 12 年にわたる IT 業界の経験があります。

この記事のレビューに協力してくれた TechMahindra Ltd. の Technical Excellence Group の Don Syme 氏に心より感謝いたします。