Come utilizzare gli alberi kd per determinare la somiglianza della stringa?

Question

Sto cercando di utilizzare i vicini più vicini a k ​​per il problema di similarità delle stringhe, ad esempio una stringa e una knowledge base, voglio produrre stringhe k che sono simili alla mia stringa data. Ci sono tutorial che spiegano come utilizzare kd-trees per eseguire in modo efficiente questa ricerca di stringhe vicine al vicino più vicino? La lunghezza della stringa non supererà più di 20 caratteri.

Answer 1

Probabilmente uno dei post più interessanti del blog che avevo letto circa un anno fa: Levenstein Automata. Dai un'occhiata a quell'articolo. Fornisce non solo una descrizione dell'algoritmo ma anche un codice da seguire. Tecnicamente, non è un albero di kd ma è abbastanza correlato agli algoritmi di correzione delle stringhe e di dizionario che si potrebbero incontrare/utilizzare nel mondo reale.

Ha anche un altro post sul blog su BK-trees che sono molto meglio per la corrispondenza fuzzy per stringhe e lookup di stringhe dove ci sono i mispellings. Ecco un'altra risorsa contenente il codice sorgente per un BK-tree (questo non riesco a verificare l'accuratezza o l'implementazione corretta.)