マッチ キーの定義に関するテクニック
効果的であると同時に実用的でもあるマッチングを行うには、精度とパフォーマンスのバランスを取る必要があります。マッチングに最高の精度を求めるなら、レコードを他のすべてのレコードと逐一付き合わせる必要がありますが、処理するレコードが多いと耐え難いほどのパフォーマンス低下を招くため、実用的ではありません。マッチング処理に関わるレコードの数を制限するため、マッチングする可能性が高いレコードだけを比較の対象とするのが賢明です。そうするには、マッチ キーを使用します。マッチ キーとは、ユーザが指定したアルゴリズムで各レコードに対して生成される値です。レコードから値がアルゴリズムに渡され、マッチ キー値が生成されます。この値は、レコードに新しいフィールドとして保存されます。
例えば、次のような入力レコードがあり、
名 - Fred
姓 - Mertz
郵便番号 - 21114-1687
性別コード - M
次のようなレコードのデータを組み合わせてマッチ キーを生成するマッチ キー ルールを定義したとします。
入力フィールド | 開始位置 | 長さ |
---|---|---|
郵便番号 | 1 | 5 |
郵便番号 | 7 | 4 |
姓 | 1 | 5 |
名 | 1 | 5 |
性別コード | 1 | 1 |
次のようなキーになります。
211141687MertzFredM
マッチ キーが同じレコードは、同じマッチ グループにまとめられます。マッチング処理では、さらにグループ内のレコードが比較され、マッチングが判定されます。
マッチ グループのサイズとパフォーマンス
マッチ キーによってマッチ グループのサイズが決定されます。これは、データフローのパフォーマンスが決定されるということでもあります。マッチ グループのサイズが倍になると、実行時間も倍に伸びます。例えば、マッチングの可能性があるレコードをグループに 20 個含めるマッチ キーを定義した場合、10 個しかレコードを含めないマッチ キーを使う場合と比較して、処理に倍の時間がかかります。マッチ キー ルールを引き締めると、マッチ グループに含まれるレコードが少なくなり、マッチングするレコードを除外してしまう恐れが大きくなります。マッチ キー ルールを緩めると、マッチングするレコードがグループから除外される可能性は低くなりますが、グループのサイズは大きくなります。データに適したバランスを取るには、実際に処理するデータとよく似たデータを使ってさまざまなマッチ キー ルールをテストする必要があります。
密度
マッチ キーを設計する際に重要なのは、データの密度を考慮することです。密度とは、データがマッチ グループ間に分散する度合いを意味します。パフォーマンスは、実行しなければならない比較の回数で決まるので、小数の大きなマッチ グループを生成するマッチ キーは、大量の小さなマッチ グループを生成するマッチ キーと比べてパフォーマンスを低下させます。
この因果関係を具体的に理解するために、マッチングしたい名前と住所のレコードが 100 万件あると想定します。マッチ キーとして、郵便番号の先頭 3 バイトと姓の頭文字を使うと仮定します。レコードが全米から集められた場合は、このマッチ キーは十分な数のマッチ グループを生成し、実用に耐えるパフォーマンスを示すと予想できます。しかし、レコードがすべてニューヨーク州のものだとしたらどうでしょうか。郵便番号はどれも "100" で始まるので、最大でもマッチ グループは 26 個しか生成されません。マッチ グループは大きくなり、平均で約 38,000 のレコードが含まれる計算になります。
マッチ グループごとに発生する比較の最大回数は、以下の数式で求められます。
N * (N-1) / 2
ここで N は、マッチ グループに含まれるレコードの数です。
つまり、26 個のマッチ グループのそれぞれに 38,000 のレコードがあると、実行される比較の最大回数は約 187 億回に達します。計算の過程はこのようになります。
最初に、マッチ グループごとの比較の最大回数を計算します。
38,000 * (38,000-1) / 2 = 721,981,000
次に、この計算結果にマッチ グループの数を掛けます。
721,981,000 * 26 = 18,771,506,000
仮に、郵便番号の先頭 3 バイトに 100 とおりの値があるとしたら、生成されるマッチ グループは 2,600 個になり、それぞれに含まれるレコード数は平均 380 になるでしょう。この場合、比較の最大回数は 1 億 8,700 万回で、100 分の 1 に減ります。レコードがすべてニューヨーク州のデータであれば、郵便番号の先頭 4 バイト、ないしは 5 バイトをマッチ キーに使うことを検討するのが良いでしょう。生成されるマッチ グループの数が増え、比較の総数が減ります。若干のマッチング漏れが生じるでしょうが、それと引き換えに実行時間が大幅に短縮されます。
実際には、この例で使用したようなマッチ キーは、データに偏りがあるため、等しいサイズでマッチ グループを生成しません。例えば、姓が "S" で始まる人は、"X" で始まる人より多いでしょう。このような事情から、最も大きなマッチ グループをなるべく小さくすることに気を配る必要があります。レコードが 100,000 個あるマッチ グループは、レコードが 10,000 個のマッチ グループの 10 倍の大きさですが、比較の回数は 100 倍であり、時間も 100 倍かかります。例えば、郵便番号の 5 バイトと AddressLine1 フィールドの 6 バイトをマッチ キーに使うとします。最初の印象では、かなり上等なマッチ キーが得られそうです。問題は、私書箱の住所です。ほとんどのマッチ グループは実用的な大きさに収まりますが、10002PO BOX のようなキーで若干の非常に大きなマッチ グループが生成されます。このような大きなマッチ グループを分割するには、マッチ キーを修正して、私書箱番号の先頭 2 桁を含めます。
マッチ キーをマッチ ルールに合わせる
- マッチ キーには、マッチ ルールで正確なマッチングを得るために必要なフィールドが含まれる必要があります。
- マッチ キーでは、マッチ ルールで使用されるものと同じ種類のアルゴリズムを使用します。例えば、発音に基づくアルゴリズムを使うマッチ ルールと組み合わせるマッチ キーであれば、発音に基づくアルゴリズムを使うように設計します。
- マッチ キーの作成には、マッチ ルールで使われるすべてのフィールドの値を使います。
- マッチ キーで使われる 1 つ以上のフィールドにデータの欠落があった場合、マッチ キーにどのような影響が現れるか考慮してください。例えば、ミドルネームの頭文字をマッチ キーの一部に使用し、データに John A.Smith のレコードと John Smith のレコードが含まれるとします。マッチ ルールを設定して、ミドルネームの頭文字フィールドに値がなければ無視することにしました。こうすると、先ほどの 2 つのレコードはマッチ ルールによって一致とみなされます。ただし、マッチ キーはミドルネームの頭文字を使うので、2 つのレコードは別のマッチ グループに分かれてしまい、互いに比較されません。そのため、マッチ ルールの意図した結果になりません。