Comparando a distância da string com base em hashes pré -computados

Question

Eu tenho uma grande lista (mais de 200.000) de strings que eu gostaria de comparar a uma determinada string. A string fornecida é inserida por um usuário, por isso pode estar ligeiramente incorreto.

O que eu esperava fazer era criar algum tipo de hash pré -computado em cada string para adicioná -la à lista. Este hash conteria informações como o comprimento da string, a adição de todos os caracteres etc.

Minha pergunta é: algo assim já existe? Certamente haveria algo que me permite evitar correr Distância de Levenshtein em cada string da lista?

Ou talvez haja uma terceira opção que ainda não pensei?

Answer 1

Parece que você quer usar um pouco de hash difuso. Existem muitas funções de hash disponíveis que podem fazer coisas assim. O velho clássico "SoundEx"O algoritmo pode até funcionar.

Outro pensamento - se você estimar que a probabilidade de uma entrada incorreta é baixa, poderá realmente estar bem tendo um acerto direto de 99,9% das vezes, voltando ao SoundEx, o que pode capturar 90% dos casos restantes e depois pesquisar o todo Lista para os 0,01% restantes do tempo.

Também vale a pena verificar esta discussão:Como encontrar a melhor combinação difusa para uma string em um grande banco de dados de string