Trovare come due stringhe simili sono

Question

Sto cercando un algoritmo che richiede 2 stringhe e restituirà un "fattore di somiglianza".

Fondamentalmente, avrò un input che può essere scritto in modo errato, avere delle lettere trasposte, ecc. E devo trovare le corrispondenze più vicine in una lista di valori possibili che ho.

Questo non è per la ricerca in un database. Avrò un elenco in memoria di circa 500 stringhe a cui competere, tutte con meno di 30 caratteri, quindi può essere relativamente lento.

So che questo esiste, l'ho visto prima, ma non ricordo il suo nome.

---

Modifica: Grazie per aver segnalato Levenshtein e Hamming. Ora, quale devo implementare? Fondamentalmente misurano cose diverse, entrambe possono essere utilizzate per quello che voglio, ma non sono sicuro quale sia più appropriato.

Ho letto gli algoritmi, Hamming sembra ovviamente più veloce. Dal momento che nessuno dei due scoprirà due personaggi che vengono trasposti (cioè Jordan e Jodran), che ritengo sarà un errore comune, che sarà più preciso per quello che voglio? Qualcuno può dirmi qualcosa sui compromessi?

Answer 1

Ok, quindi gli algoritmi standard sono:

1) Hamming distance Buono solo per le stringhe della stessa lunghezza, ma molto efficiente. Fondamentalmente conta semplicemente il numero di caratteri distinti. Non utile per la ricerca fuzzy del testo in linguaggio naturale.

2) . La distanza di Levenstein misura la distanza in termini di numero di "operazioni" richieste per trasformare una stringa in un'altra. Queste operazioni includono l'inserimento, la cancellazione e la sottostringa. L'approccio standard per calcolare la distanza di Levenstein è utilizzare la programmazione dinamica.

3) Generalized Levenstein/(Damerau–Levenshtein distance) Questa distanza prende in considerazione anche le trasposizioni di caratteri in una parola, ed è probabilmente la distanza di modifica più adatta per la corrispondenza fuzzy del testo immesso manualmente. L'algoritmo per calcolare la distanza è un po 'più complicato rispetto alla distanza di Levenstein (rilevare le trasposizioni non è facile). Le implementazioni più comuni sono una modifica dell'algoritmo bitap (come grep).

In generale si sarebbe probabilmente prendere in considerazione l'attuazione della terza opzione implementata in una sorta di ricerca vicino più prossimo sulla base di un albero kd

Answer 2

Stai cercando il Levenshtein distance

Answer 3

• Levenstein distanza
• distanza di Hamming
• soundex
• metaphone

Answer 4

il Damerau-Levenshtein distance è simile alla distanza Levenshtein, ma include anche trasposizione a due caratteri. la pagina di wikipedia (collegata) include pseudocodice che dovrebbe essere abbastanza semplice da implementare.