forma eficiente de calcular a pontuação de semelhança de cordas quando o tamanho da amostra é grande?

StackOverflow https://stackoverflow.com/questions/1609742

Pergunta

Vamos dizer que você tem uma lista de 10.000 endereços de e-mail, e você gostaria de saber o que alguns dos mais próximos "vizinhos" dessa lista são - definido como endereços de email que estão suspeito perto para outros endereços de e-mail na sua lista .

Eu estou ciente de como calcular a Levenshtein distância entre duas cadeias (graças a esta questão ), o que dará me uma pontuação de quantas operações são necessárias para transformar uma string em outra.

Vamos dizer que eu definir o "suspeito perto para outro endereço de e-mail" como duas cordas ter um Levenshtein pontuação inferior a N.

Existe uma maneira mais eficiente de encontrar pares de cordas cuja pontuação é inferior a este limiar além de comparar cada corda possível todas as outras cordas possível na lista? Em outras palavras, pode este tipo de problema pode ser resolvido mais rápido do que O(n^2)?

é Levenshtein marcar uma má escolha de algoritmos para este problema?

Foi útil?

Solução

Sim - você pode encontrar todas as strings dentro de uma determinada distância de uma string em O (log n) usando um BK-Tree . soluções alternativas que envolvem a geração de cada corda com a distância n pode ser mais rápido para uma distância levenshtein de 1, mas a quantidade de trabalho rapidamente balões fora de controle para distâncias mais longas.

Outras dicas

Você pode fazê-lo com Levenshtein em O(kl), onde k é a sua distância máxima e l é a cadeia de máxima.

Basicamente, quando você sabe como calcular básica Levenshtein então é fácil de descobrir que cada resultado que é mais longe do que k da diagonal principal tem que ser maior do que k. Então, se você calcular diagonal principal com 2k + 1 largura será suficiente.

Se você tem 10.000 endereços de e-mail que você não vai precisar de um algoritmo mais rápido. Computador pode calcular com O(N^2) rápido o suficiente.

Levenshtein é muito bom para este tipo de problema.

Também o que você pode considerar está transformando-mails com soundex antes de comparar. Você provavelmente obterá melhores resultados.

Este problema é conhecido como agrupamento e é uma parte de um maior desduplicação problema (onde você começa a decidir qual membro do cluster é o "direito" um) , também conhecido como merge-purga .

Uma vez eu li alguns trabalhos de pesquisa sobre exatamente este assunto (os nomes estão abaixo) e, basicamente, os autores utilizaram um limitado tamanho janela deslizante mais de uma lista ordenada de strings. Eles só comparar (usando um href="http://en.wikipedia.org/wiki/Edit_distance" rel="nofollow noreferrer"> algoritmo editar distância dentro a janela, reduzindo assim a complexidade computacional. Se quaisquer duas cordas parecia semelhante, eles foram combinados em uma aglomerado (através da inserção de uma ficha em uma tabela agregado separado).

A primeira passagem através da lista foi seguido por uma segunda passagem , onde as cordas foram revertida antes de ser ordenado. Desta forma, as cordas com cabeças diferentes teve outra chance de chegar perto o suficiente para ser avaliada como parte da mesma janela. Nesta segunda passagem, se uma cadeia parecia perto o suficiente para dois (ou mais) cordas na janela, e aquelas cordas já estavam partes de seus próprios clusters (encontrado pela primeira passagem), os dois grupos seria, então, fundiu (atualizando a tabela de cluster) ea cadeia atual seria adicionado ao recém-fundidas cluster. Esta abordagem de agrupamento é conhecido como o união-find algoritmo.

Em seguida, eles melhoraram o algoritmo através da substituição da janela com uma lista de top X protótipos substancialmente únicas . Cada nova cadeia seria comparado com cada um dos principais X protótipos. Se corda parecia perto o suficiente para um dos protótipos, que passaria então a ser adicionado ao aglomerado de protótipo . Se nenhum dos protótipos parecia bastante semelhante, a corda se tornaria um novo protótipo, empurrando o protótipo mais antigo fora da lista top X. (Havia uma lógica heurística empregada para decidir qual das cordas em conjunto do protótipo deve ser usado como o novo modelo representativo de todo o cluster). Novamente, se a string se parecia com vários protótipos, todos os seus grupos seriam fundidas.

Uma vez eu implementado este algoritmo para deduplicação de registros de nome / endereço com tamanhos das listas de ser em torno de 10-50 milhões de discos e funcionou muito muito rápido (e encontrou duplicatas bem também).

Em geral, para tais problemas, a parte mais complicada, claro, é encontrar o valor correto do limiar semelhança . A idéia é capturar todos os dups w / o produzir muitos falsos positivos . Dados com características diferentes tende a exigir limiares diferentes. A escolha de um algoritmo editar distância também é importante porque alguns algoritmos são melhores para erros de OCR enquanto outros são melhores para erros de digitação e outros ainda são melhores para erros fonéticos (como quando a obtenção de um nome através do telefone).

Uma vez que o algoritmo de agrupamento é implementado, uma boa maneira de testar isso é para obter uma lista de amostras únicas e artificialmente mutação cada amostra para produzir suas variações, preservando o fato de que todas as variações têm vêm do mesmo pai. Esta lista é então embaralhado e alimentado para o algoritmo. Comparando o agrupamento original com o agrupamento produzida pelo algoritmo de desduplicação lhe dará a pontuação eficiência .

Bibliografia:

Hernandez M. 1995 A fusão / Purge Problema para grandes bases de dados.

Monge A. 1997, a Um Algoritmo Domain-Independent eficiente para a detecção de banco de dados Aproximadamente Duplicate Records.

Eu não acho que você pode fazer melhor do que O (n ^ 2), mas você pode fazer algumas otimizações menores que poderiam ser apenas o suficiente de um aumento de velocidade para tornar a sua aplicação utilizável:

  • Você poderia primeiro ordenar todos os endereços de e-mail por Th parte após o @ e endereços única comparar onde que é o mesmo
  • Você pode parar de calcular a distância entre dois endereços quando se torna maior do que n

EDIT:. Na verdade, você pode fazer melhor do que O (n ^ 2), basta olhar para Nick Johnsons resposta abaixo

10.000 endereços de email não parecer muito. Para a busca de similaridade em um espaço maior que você pode usar shingling e min-hashing . Este algoritmo é um pouco mais complicado de implementar, mas é muito mais eficiente em um grande espaço.

É possível fazer melhor, com a condição de reverter o problema.

Suponho aqui que os seus 10.000 endereços são bastante 'fixo', caso contrário você terá que adicionar um mecanismo de atualização.

A idéia é usar a distância Levenshtein, mas no modo 'reverso', no Python: 

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

O método generate_level gera todas as variações possíveis do conjunto anterior, menos as variações que já existem em um nível anterior. Ele preserva a 'origem' como o valor associado à chave.

Então, você apenas tem que pesquisar a sua palavra nos diversos set: 

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

Fazendo isso, você calcular os vários conjuntos de uma vez (que leva algumas vezes ... mas então você pode serializar-lo e mantê-lo para sempre).

E, em seguida, pesquisa é muito mais eficiente do que O (n ^ 2), embora dando-lhe exatamente é meio difícil, uma vez que depende do tamanho dos conjuntos que são gerados.

Para referência, tem uma olhada em: http://norvig.com/spell-correct.html

Vamos dizer que você tem 3 cordas:

1 - "abc" 2 - "bcd" 3 - "cde"

O L Distância entre 1 e 2 é de 2 (subtrair 'a', adicione 'd'). A L Distância entre 2 e 3 é de 2 (subtrair 'b', adicione 'e').

A sua pergunta é se podemos inferir um L Distância entre 1 e 3, usando os 2 comparações acima. A resposta é não.

O L Distância entre 1 e 3 é de 3 (substitua cada personagem), não há nenhuma maneira que este pode ser inferida por causa das notas dos 2 primeiros cálculos. As pontuações não revelam se eliminações, inserções ou operações de substituição foram realizados.

Então, eu diria que Levenshtein é uma má escolha para uma grande lista.

Se você realmente está comparando os endereços de e-mail, em seguida, uma maneira óbvia de fazer isso seria combinar um algoritmo levenshtein com mapeamento de domínio. Não consigo pensar em momentos em que eu me inscrevi para algo várias vezes usando o mesmo domínio, mas as variações na parte nome de usuário do endereço de e-mail.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top