Scoprire quanto sono simili due stringhe

Sto cercando un algoritmo che prende 2 stringhe e mi 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ù simili in una lista di possibili valori 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 riesco a ricordare 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 trade-off?

Ok, quindi gli algoritmi standard sono:

1) Distanza di Hamming Solo per corde della stessa lunghezza, ma molto efficienti. Fondamentalmente conta semplicemente il numero di caratteri distinti. Non utile per la ricerca fuzzy del testo in lingua naturale.

2) Distanza di Levenstein . La distanza di Levenstein misura la distanza in termini di numero di “operazioni” necessarie 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 dynamic.

3) Levenstein generalizzato / (distanza Damerau-Levenshtein) 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 inserito 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 di bitap (come grep).

In generale, probabilmente vorrai considerare un’implementazione della terza opzione implementata in una sorta di ricerca di un vicino più vicino basata su un albero kd

  • Distanza Levenstein
  • Distanza di Hamming
  • soundex
  • metaphone

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

Stai cercando la distanza di Levenshtein