Em primeiro lugar, a distância Levenshtein é definida como o número mínimo de edições necessárias para transformar a string A em string B, onde uma edição é a inserção ou exclusão de um único caractere ou a substituição de um caractere por outro caractere. Então é muito a "diferença entre duas cordas", para uma certa definição de distância. =)

Parece que você está procurando uma função de distância F(A, B) que fornece uma distância entre as strings A e B e um limite N onde as strings com distância menor que N uma da outra são candidatas a erros de digitação. Além da distância Levenshtein, você também pode considerar Needleman–Wunsch . É basicamente a mesma coisa, mas permite fornecer uma função para o quão próximo um determinado caractere está de outro caractere. Você pode usar esse algoritmo com um conjunto de pesos que refletem as posições das teclas em um teclado QWERTY para fazer um bom trabalho ao encontrar erros de digitação. Isso teria problemas com teclados internacionais.

Se você tiver k strings e quiser encontrar possíveis erros de digitação, o número de comparações que você precisa fazer é O(k^2). Além disso, cada comparação é O(len(A)*len(B)). Então, se você tem um milhão de cordas, vai ter problemas se fizer as coisas com ingenuidade. Aqui estão algumas sugestões sobre como acelerar as coisas:

• Desculpe se isso for óbvio, mas a distância de Levenshtein é simétrica, portanto, certifique-se de não calcular F(A, B) e F(B, A).
• abs(len(A) - len(B)) é um limite inferior na distância entre as strings A e B. Portanto, você pode pular a verificação de strings cujos comprimentos são muito diferentes.

Um problema que você pode encontrar é que "1st St." tem uma distância bastante alta de "First Street", mesmo que você provavelmente queira considerá-los idênticos. A maneira mais fácil de lidar com isso é provavelmente transformar strings em uma forma canônica antes de fazer as comparações. Então você pode deixar todas as strings em minúsculas, usar um dicionário que mapeie "1st" para "first", etc. Esse dicionário pode ficar muito grande, mas não conheço uma maneira melhor de lidar com esses problemas.

Desde que você marcou esta pergunta com php, estou assumindo que você deseja usar php para isso. O PHP tem uma função levenshtein() integrada, mas ambas as strings devem ter 255 caracteres ou menos. Se isso não for o suficiente, você terá que fazer o seu próprio. Alternativamente, você investiga usando o diflib do Python.