Qual è l'algoritmo che dovrei usare per vedere quanto 2 stringhe corrispondono?

Question

Qual è l'algoritmo che dovrei usare per vedere quanto 2 stringhe corrispondono?

#1 da (1 voti)

0

Supponiamo di avere 2 stringhe:

string1 = "home/lisa/Music/some_files/01.05 - Garden Ground.mp3"
string2 = "Music/Jim Smith/Unknown/(Deluxe Version/Garden Ground).mp3"
string4 = "Music/Jim Smith/Unknown/00 - Garden Ground.mp3"

Fondamentalmente, voglio sapere se la stringa 2 contiene lo stesso file mp3 della stringa 1. Nell'esempio sopra, puoi vedere questo è il caso di Garden Ground.mp3. Qual è il modo migliore per farlo? Dovrei provare la distanza di Levenshtein? Ho pensato di fare un'espressione regolare, ma non c'è garanzia che la stringa 2 sarà formattata con parentesi nello stesso identico posto ogni volta. In effetti, la stringa 2 potrebbe apparire come la stringa 4, ad esempio.

data-structures algorithms string-matching

posta Nona 14.03.2015 - 09:31

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms string-matching

SOC e configurazione autoinizializzante Qual è il modo migliore per esporre i servizi ai dispositivi mobili? [chiuso]

score 1 · Answer 1

Non penso che nessun algoritmo esistente possa funzionare nel tuo caso. Nel tuo caso, non stai cercando la somiglianza tra le stringhe, ma se le stringhe contengono valori simili. La distanza di Levenstein riguarda la similarità delle stringhe, non se le stringhe contengono valori simili.

Nel tuo caso, l'algoritmo più semplice sarebbe (pseudocodice).

Ottieni il nome di ogni file senza directory (presumo che la directory non abbia importanza)
Dividi ogni nome in parole in base a separatori predefiniti ('', '-', ';', '.', ecc. devi fare qualche prova-e-errore qui per trovare i separatori corretti)
Confronta quante parole sono uguali tra due nomi (ad esempio, nel tuo caso ci sono 2 parole uguali tra ciascuno dei file)
Se il conteggio delle stesse parole supera una soglia, considerale uguale a

L'ultimo passaggio è ovviamente il più difficile. Calcolare la soglia per minimizzare i falsi positivi e negativi è una vera sfida. La più semplice è la soglia assoluta (ad esempio count > = 2 corrisponde al tuo caso), ma potrebbe non essere sufficiente. La soglia relativa (ad esempio count / totalWordsCount > 50%) potrebbe funzionare, ma è più difficile da testare e dipende molto dai separatori selezionati.