Este artigo foi traduzido por máquina.

Dados dinâmicos

Fazendo a correspondência de padrões em registros de banco de dados com o F#

Ambar Ray

Baixe o código de exemplo

Os dados usados pelos aplicativos simplesmente não aparecerem fora do ar. Para acabar com um banco de dados cheia de dados úteis, você terá que ir através de meios de alguns. Para iniciar, você provavelmente realizar uma extração, transformação e carregamento (ETL) processam em alguma coleção de dados dimensionais. Isso geralmente inclui a limpeza, remoção e padronizar os dados. Isso é apenas para obter os dados em um formulário que trabalha em seu banco de dados.

Após a etapa ETL, convém percorrer os registros e certifique-se de que sejam úteis e consistente. Isso normalmente significa a implementação de um processo de correspondência e a eliminação da duplicação. Em seguida, você algumas nome e endereço de análise. Com essas informações, você pode iniciar um processo de correspondência e iniciar identificando duplicatas.

Existem quatro algoritmos correspondentes comuns usados para processos de eliminação da duplicação de atributo: correspondência absoluta, correspondência parcial, Soundex e pesquisa corresponder. Esses algoritmos podem ser executados com os dados e, depois que a pontuação de correspondência de porcentagem é calculada, você pode optar por descartar ou armazenar os dados.

Como um exercício, implementei esses quatro algoritmos correspondentes usando a correspondência de padrões F # e recursos de programação assíncronos para calcular rapidamente a agregação coincide com a pontuação. Neste artigo, mostrarei minha implementação dos algoritmos de correspondência e como crio o agregado correspondem a pontuação. O objetivo deste artigo é apresentar alguns dos recursos da linguagem F # como programação funcional, programação imperativa e sistema de inferência de tipo implícito e demonstrar como você pode usar F # para realizar algumas tarefas de gerenciamento de dados significativos com rapidez e facilidade.

Preparando os dados

Começarei com o carregamento de dados dimensionais de vários sistemas transacionais em uma tabela temporária. A fonte de dados pode ser um banco de dados relacional, um arquivo simples, um arquivo do Excel ou um arquivo XML. O processo ETL normalmente usa uma ferramenta como o SSIS (SQL Server Integration Services) 2008 limpeza, remoção e padronizar os dados de entrada e, subseqüentemente, carregar as tabelas de estágios. As tabelas de estágios e de banco de dados mestre são mantidas em um hub de dados mestre.

Como mencionado anteriormente, eu uso um aplicativo separado criado com F # e o Windows Presentation Foundation (WPF) para cuidar do processo de correspondência e a eliminação da duplicação. Em projetos reais, geraria o ADO.NET Entity Framework modelos na camada de acesso a dados. Esses modelos de modelam as tabelas de dados mestre, juntamente com todas as tabelas de pesquisa presentes no hub dados mestre.

Em seguida, a camada acima deve expor o modelo subjacente por meio dos serviços Windows Communication Foundation (WCF). A camada de lógica comercial acima implementaria as rotinas de correspondência e a eliminação da duplicação, bem como os métodos de análise. Finalmente, a camada de apresentação apresentaria várias interfaces de usuário para o Gerenciador de dados. Figura 1 ilustra a arquitetura do aplicativo.

Figura 1 arquitetura de aplicativos de gerenciamento de dados mestre

Não vou demonstrar todo o aplicativo aqui, apenas a implementação dos algoritmos de análise e correspondentes. As seções subseqüentes explicará a implementação dos algoritmos de análise e correspondentes na camada de lógica comercial.

Introdução

Para os fins desse cenário, vamos supor que a linha de dados são recuperados do banco de dados por meio da camada de acesso a dados e serviços de dados do WCF é armazenado na lista <T>objetos para processamento posterior. Essas lista <T>objetos serão preenchidos com dados de teste para implementar os algoritmos pertinentes.

O banco de dados mestre contém todas as as tabelas de origem, bem como tabelas de estágios e de histórico. Por exemplo, a Figura 2 mostra a composição de uma entidade de dados do cliente.

Figura 2 entidade Customer

CUSTFIRSTNAME
CUSTLASTNAME
CUSTHOUSENO
CUSTSTREETNAME
CUSTSTREETTYPE
CUSTCITY
CUSTSTATE
CUSTPOSTCODE
CUSTMOBILE
CUSTCOUNTRY
CUSTID
CUSTACTIVEFLAG

O algoritmo de correspondência pode ser explicado por meio do fluxograma na a Figura 3 .

Figura 3 O processo de correspondência

Etapa 1 não é realmente parte do processo correspondente, mas na verdade um precursor. Dados cleansed e padronizados para um formato preferido antes de serem enviado para análise.

Nome de análise

O processo de análise na etapa 2 também é uma precursora para o processo de correspondência. Nesta etapa, os nomes individuais são analisados fora dos dados. Supondo que uma saudação pode ser digitada junto com o primeiro nome, ele deve ser dividido (analisada) em elementos individuais: saudação e nome. Assim, se Mr. John é fornecido no campo nome, com Mr. sendo a saudação e John sendo o nome real, em seguida, o algoritmo funcionará da seguinte maneira:

  1. Selecione a primeira palavra que foi encerrada com um espaço (A posição) como W1.
  2. Identifique se W1 é uma saudação pela correspondência com uma lista de pesquisa. Nesse caso, ignore a saudação e prossiga para a etapa 4.
  3. Se W1 não é uma saudação, considere o primeiro nome. Não considere o trecho de seqüência de caracteres para análise adicional.
  4. Se W1 é identificado como uma saudação, identifica a próxima ocorrência de um espaço ou um final de seqüência de caracteres (posição B). Considere a palavra envolto em posicionar a e posicione b como nome. Não considere o trecho de seqüência de caracteres para análise adicional.

Por exemplo, a seqüência "Mr. John"seria analisado como mostrado na a Figura 4 .

Figura 4 exemplo de análise de nome

Name M r .   J o h n
Posição 1 2 3 4 5 6 7 8

A posição 1 para a posição 3 constituiria a saudação. Saudação é opcional e deve ser preenchida somente se a primeira palavra coincida com uma lista completa dos valores possíveis. (Verifique uma pressuposição que cada parte do nome, incluindo a saudação, deve ser seguido por um espaço. Uma exceção é feita para o campo Sobrenome.) Em a Figura 4 , posição 5 à posição 8 constituiria o primeiro nome.

A implementação desse algoritmo de análise em F # tem esta aparência:

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]

Esse código eu fiz a correspondência de padrões usando o "match" e "com" palavras-chave da linguagem F #, seguido de padrões coincidentes regras, cada um seguido de "->" símbolo.

Desmembramento de endereços

A próxima etapa é analisar de linha de endereço. Linhas de endereço 1 e 2 (concatenado) devem ser divididas (analisadas) em uma casa ou criação de número, nome da rua, tipo de rua, apartamentos tipo (opcional, que constitui o Apt, simples ou Suite) e número do apartamento (opcional). Se as informações de cidade, estado e país são fornecidas nas linhas de endereço 1 e 2, elas devem ser omitidos.

Um endereço combinado deve ser analisado em um número da casa, o nome da rua, o tipo de rua e, se aplicável, um tipo de apartamento e o número do apartamento. Para ilustrar, vejamos um exemplo:

421, East Drachman St, Suite 5A, Tucson, Arizona, ao lado do McDonald

Nesse caso os elementos de endereço são analisados como mostrado na a Figura 5 .

Figura 5 exemplo de análise de endereço

Casa 'não'. Nome da rua Tipo de rua Tipo de rua Número do apartamento Descritor de localização
421 Drachman Leste Rua Suite 5A ao lado do McDonald

Observe que as informações de cidade e estado são analisados separadamente como {cidade, estado, país, CEP} = {'Tucson', 'AZ', 'EUA', '85705'} e são omitidos da linha de endereço.

Vejamos as etapas necessárias para analisar a linha de endereço:

  1. Defina uma exaustiva pesquisa para o tipo de rua e o tipo de apartamento.
  2. Defina um país exaustiva ou pesquisa específicas da região para o estado. Estado de pesquisa deve ser definida como tal que AZ e Arizona são identificados como o mesmo (mas não é considerada ortografia incorreta).
  3. Concatene endereço 1 e 2 do endereço em um único endereço de linha.
  4. Pesquise a cadeia de caracteres de linha de endereço do lado direito de cidade válida, nome do estado ou CEP em relação a pesquisas correspondentes. Se verdadeiro, vá para a etapa 5;Caso contrário, vá para a etapa 6.
  5. Remova a cidade, estado ou CEP informações se encontrado na seqüência de linha de endereço.
  6. Identifica os tokens de rua e o apartamento usando a estrutura de rua {[número] [nome] [tipo]}, {[tipo] [número]} apartamento. Identificação de token é baseada em pesquisa [tipo] com relação a valores no tipo de rua e pesquisa do tipo apartment, respectivamente.
  7. Considere a possibilidade de qualquer trecho da cadeia de caracteres restantes após a etapa 6 para fazer parte de um descritor de localização.

A implementação desse algoritmo é mostrada na a Figura 6 . Nesse código que usei ao loops para examinar o estado, cidade e CEP tabelas de pesquisa para localizar uma correspondência. A principal função ParseAddress usa isso para eliminar a cidade, estado e CEP informações a partir da linha de endereço.

Figura 6 linhas de endereço de análise

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

Correspondência e eliminação de duplicação

O processo de correspondência e a eliminação da duplicação na etapa 3 (consulte a Figura 3 ) começa com a identificação dos seguintes três tipos de atributos:

  • Atributos de identidade, incluindo Cust_ID, nome (First_Name, Last_Name), endereço (House_no., Street_Name, cidade, estado, Zip_Code, país), Mob_Phone e assim por diante.
  • Atributos de discriminação, como data de nascimento (DOB).
  • Atributos de registro de qualificação, como país, região ou CEP.

O aplicativo pede ao usuário selecionar esses atributos. Pelo menos uma de cada identidade, atributos de discriminação e qualificação de registro precisam ser selecionado. Observe que se todos os registros são sinalizados devido a inconsistências ou erros na identidade e atributos de discriminação no processo de limpeza e padronização, esses registros não devem ser considerados para fins de correspondência.

Como mencionado anteriormente, correspondência será realizada com base em quatro rotinas: correspondência absoluta, correspondência parcial, Soundex e pesquisa corresponder. O programa solicitará ao usuário selecionar quais rotinas serão usadas para cada atributo. Pelo menos uma rotina deve ser selecionada para cada atributo, embora todos os quatro podem ser selecionados para um atributo.

Pesos apropriados precisam ser atribuídos para cada atributo de identidade de acordo com sua importância para o processo de negócios — por exemplo, identificar um cliente (etapa 4). Da mesma forma, pesos precisam ser atribuído a cada rotina para cada atributo. O programa deve solicitar ao usuário para definir os níveis de importância em uma escala de 1 a 5.

Finalmente, chegar à etapa 5 e começar a executar a correspondência com base nos atributos de discriminação para obter a correspondência de windows. Assim, se DOB é definido como o atributo de discriminação, e em seguida, separado do windows precisa ser formada com base no DOB. Isso significa que os registros dentro da mesma janela teria o mesmo valor de DOB. Nas etapas subseqüentes, o processo de correspondência será executado dentro do windows individual e não dentro de registros em janelas diferentes.

Correspondência absoluta

Na etapa 6, realizo uma correspondência absoluta para todos os atributos. Esta rotina compara dois campos e procura por apenas uma correspondência exata. Uma pontuação de 100 é atribuída por uma correspondência exata. Qualquer outro resultado é pontuado 0.

Por exemplo, se o campo 1 contém "João" e 2 do campo "João", uma correspondência exata e recebe uma pontuação de 100. Se o campo 1 contém "Lisa" e 2 do campo "Laura", ele não é uma correspondência exata e recebe uma pontuação igual a 0.

A implementação desse algoritmo de correspondência absoluto é:

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

Correspondência parcial

Em seguida, eu posso executar uma rotina de correspondência parcial de todos os atributos. A correspondência parcial é usada para determinar a relação com um valor em branco. Isso é útil quando tem alguns registros, por exemplo, o cliente primeiro nome, mas não o sobrenome do cliente, ou vice versa. Às vezes, um campo estiver em branco em ambos os registros. O algoritmo de correspondência parcial se encarrega de correspondentes a esses registros em que um dos campos importantes talvez foram deixado em branco.

Espaços em branco e zeros são considerados o mesmo valor. Para a correspondência absoluta, uma correspondência exata é pontuada 100. Um valor de campo em branco em vez de um valor de campo não vazio é pontuado 75, enquanto um valor de campo em branco em vez de um valor de campo em branco é pontuado 65. Qualquer outro resultado é pontuado 0.

A implementação do algoritmo de correspondência parcial é:

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

Observe que esse código é semelhante a correspondência absoluta.

Correspondência Soundex

Agora posso executar o algoritmo Soundex para atributos de nome, sobrenome, nome da rua, cidade, estado e país individualmente. O algoritmo Soundex detecta palavras com som similar usando o algoritmo a seguir:

  1. Capitalizar todas as letras na seqüência de caracteres.
  2. Reter a primeira letra da seqüência de caracteres.
  3. Após a primeira posição, converter todas as ocorrências das seguintes letras em branco: A, E, I, O, U, W, Y.
  4. Alterar letras dos conjuntos predeterminados de número correspondente, conforme mostrado na a Figura 7 .
  5. Remova todos os pares consecutivos de dígitos duplicados e espaços em branco da seqüência de caracteres que resultou após a etapa 4.
  6. Retorne os quatro primeiros caracteres da seqüência de caracteres, preenchido com zeros à direita se necessário.

Figura 7 conversão de letra Soundex

Carta Número correspondente
B, F, P, V 1
C, G, J, K, Q, S, X, Z 2
D, T 3
L 4
M, N 5
R 6

Os valores de pontuação para a rotina Soundex são um pouco diferentes. Como antes, se as duas seqüências são iguais elas seja pontuadas 100. Se uma seqüência de caracteres está em branco e a outra é não-vazios, eles seja pontuados 50. Se ambas as seqüências de caracteres estão em branco seja pontuados 0. E se nenhuma seqüência está em branco e não sejam iguais, eles seja pontuados 0.

A implementação desse algoritmo em F # é mostrada na a Figura 8 .

Figura 8 Correspondência 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

Nesse código Soundex conversão é feito usando padronagem correspondentes, mantendo intacta ao primeiro caractere. Os seguintes dois loops for localizar caracteres consecutivos de duplicados e substituir o segundo tal caractere por um espaço em branco. As próximas duas loops for descartam os espaços em branco, removendo com eficácia as duplicatas. Assim, os quatro loops for descartam juxtaposed caracteres duplicados.

A seguir dois se instruções extrair os quatro primeiros caracteres e, se necessário, preencher com zeros para torná-lo pelo menos quatro caracteres. A correspondência de padrões final implementa a pontuação para a rotina Soundex.

Correspondência de pesquisa

Por fim, realizo uma correspondência de pesquisa para o atributo de tipo de rua. Tabela de pesquisa a rua será referenciada para padronizar o tipo de rua, da seguinte forma:

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

Esse código examina a tabela de pesquisa Rua para encontrar uma correspondência do nome da rua usando um while loop e retorna as pontuações se uma correspondência for encontrada.

Os resultados de pontuação.

Na etapa 7 do processo correspondente, recupero as pontuações dos processos correspondentes para cada atributo. Assim, para nome, se não há nenhuma correspondência para a rotina de correspondência absoluta, mas há uma correspondência para a rotina Soundex, as pontuações de rotina de correspondência para nome seria 0 e 100, respectivamente.

Na etapa 8, a pontuação de correspondência ponderada para cada atributo é determinada, dando o atributo uma pontuação de 1 a 5. Por exemplo, se a pontuação correspondente absoluta 0 é ponderada como 5 e a pontuação Soundex de 100 é ponderada como 4, em seguida, a pontuação agregada para primeiro nome seria:

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

Supondo que todos os algoritmos de correspondência são selecionados, a implementação desta pontuação ponderada é mostrada na a Figura 9 .

Figura 9 agregados de pontuação

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

Esse código pressupõe que todos os três rotinas de correspondência são chamadas para cada atributo (embora não para o atributo rua, para o qual a correspondência de pesquisa deve ser executada). Primeiro, Func delegados são declarados para cada rotina de correspondência. Em seguida, os delegados são invocados de maneira assíncrona usando o método BeginInvoke. Depois de aguardar as tarefas a serem concluídas via WaitHandle.WaitAll, os resultados são coletados usando métodos EndInvoke que usam parâmetros IAsyncResult retornados durante chamadas BeginInvoke. Finalmente, a pontuação de correspondência agregada é retornada como a última expressão na função.

Na etapa 9, as pontuações de correspondência agregada de cada atributo são multiplicadas por pesos de atributos individuais, e em seguida, adicionadas e expresso como uma porcentagem coincide com a pontuação entre os dois registros (consulte a Figura 10 ).

Figura 10 ponderada de pontuação

// 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

O método Task.Factory.StartNew da biblioteca paralela de tarefas para F # é usado para chamar a pontuação de correspondência agregada para cada par de atributos das duas linhas de dados que estão sendo comparados, seguido por um loop for que calcula o resultado cumulativo. Finalmente, a pontuação de correspondência de porcentagem é retornada.

Coincidir com limites — o limite superior e limite inferior para pontuações — são definidos pelo usuário. O sistema solicitará ao usuário para definir os limites superiores e inferiores. Um registro coincide com a pontuação acima do limite superior é considerado uma correspondência automática, enquanto um registro corresponder pontuação abaixo do limite inferior será rejeitado e é considerado um novo registro. Uma pontuação entre e inclusive desses dois limites deve ser indicada para análise.

Com isso, você concluiu a correspondência de registro e o processo de eliminação da duplicação. Duplicações óbvias podem ser excluídas, e você pode passar em registros sinalizados para revisão para um ser humano real ou um processo de revisão através de programação mais abrangente.

Ambar Ray é um arquiteto de soluções, trabalhando em tecnologias Microsoft. Ray tem quase 12 anos de experiência no setor de TI.

Graças aos seguintes especialistas técnicos para revisão deste artigo: Don Syme, o grupo técnico de excelência de Ltd. TechMahindra