Acelerar levenshtein / similar_text em PHP

Question

Atualmente, estou usando similar_text para comparar uma string contra uma lista de ~ 50.000 que funciona embora devido ao número de comparações é muito lento. Demora cerca de 11 minutos para comparar ~ 500 cordas únicas.

Antes de executar este eu faço verificar as bases de dados para ver se ele foi processado no passado, então toda vez que após a corrida inital é perto de imediato.

Estou certo de usar levenshtein seria ligeiramente mais rápido ea função Distância Levenshtein alguém postou na aparência manuais interessante. Estou faltando alguma coisa que poderia fazer este significativamente mais rápido?

Answer 1

No final, ambos levenshtein e similar_text foram muito lento com o número de cordas que tinha que passar, mesmo com lotes de cheques e só usá-los um deles como um último recurso.

Como uma experiência, eu portado parte do código para C # para ver o quanto mais rápido seria código sobre interperated. Ele correu em cerca de 3 minutos com o mesmo conjunto de dados.

Em seguida eu adicionei um campo extra para a mesa e usou a extensão dupla metaphone PECL para gerar chaves para cada linha. Os resultados foram bons, embora uma vez que alguns números incluídos neste duplicatas causado. Eu acho que eu poderia, então, ter executado cada um através das funções acima, mas não decidiu.

No final, eu optou pela abordagem mais simples, MySQLs texto completo que funcionou muito bem. Ocasionalmente há erros, embora eles são fáceis de detectar e corrigir. Também corre muito rápido, em cerca de 3-4 segundos.

Answer 2

Talvez você poderia 'curto-circuito' algumas verificações de primeiro comparando a sua string para uma correspondência exata (e por primeiro comparando se o comprimento idêntico), e se é ignorar a chamada similar_text mais caro.

Como @ Jason observou, um O (n ^ 3) algoritmo é nunca vai ser uma boa escolha.

Answer 3

Ao usar levenshtein autômato (autômato que corresponde a uma string com k distância) você pode fazer um cheque de correspondência em O(n), onde n é o comprimento da corda que você está verificando. Construindo o autômato vai levar O(kn), onde k é a distância máxima e n comprimento da corda base.