[ALGORITMO] Determinazione differenza tra stringhe

[menphisx]

Mi serirebbe riuscire a trovare un buon algoritmo per calcolare la differenza tra stinghe, in pratica quello che devo fare è data una stringa: "Pubblica Amministrazion", devo trovare tutte le stringhe simili, del tipo:
"Pubblica Amministrzione"
"Pubblica Ammnstrazne"
"Pbblica Ammnstrazione"
"Amministrazione Pubblica"
"Ammnstr Pubblica",

cioè data la prima stringa, confrontandola con altre, l'algoritmo deve darmi in output solo le stringhe come quelle sopra.
Cioè se confonta pubblica amministrazione con pubblica panetteria, non dovrebbe restituire nulla.

Qualche idea?

Marco.

[MacApp]

Originariamente inviato da menphisx
Qualche idea?

http://it.wikipedia.org/wiki/Espressione_regolare

[menphisx]

Originariamente inviato da MacApp
http://it.wikipedia.org/wiki/Espressione_regolare

Grazie della risposta, ma davvero non saprei come implementare un'espressione regolare per trovare le stringhe simili. Hai una qualche idea da cui partire?
Piuttosto è che l'algoritmo è generico e non specifico per una stringa....

Grazie,
Marco.

[rsdpzed]

questa, che è una funzione che google implementa su larga scala e in multilingua, secondo me è il risultato di un algoritmo genetico.
Dal post non è chiaro se al momento del controllo tu hai sia la stringa esatta che la tringa potenzialmente simile che vuoi verificare, pare di si.
Volendo si puo provare a fare qualcosa di rudimentale:
In base alla lunghezza della stringa totale ti calcoli un range di lunghezze di sottostringhe da controllare significativo, diciamo nel caso specifico 4 - 5.
Suddividi la stringa da controllare in tante sottostringhe da 4 e poi in tante sottostringhe da 5 e le inserisci in una lista di Test.
Cerca per ogni sottostringa della lista se c'è un corrispondente nella stringa originale.
Se la media pesata (i test da 5 valgono piu dei test da 4) dei test passati supera un certo target, diciamo 70% sul totale dei test, allora la stringa corrisponde.
Spero sia un buon inizio da cui partire, ovviamente questo presuppone che tu abbia la stringa esatta con cui controllare quella potenzialmente simile.

[menphisx]

Originariamente inviato da rsdpzed
questa, che è una funzione che google implementa su larga scala e in multilingua, secondo me è il risultato di un algoritmo genetico.
Dal post non è chiaro se al momento del controllo tu hai sia la stringa esatta che la tringa potenzialmente simile che vuoi verificare, pare di si.
Volendo si puo provare a fare qualcosa di rudimentale:
In base alla lunghezza della stringa totale ti calcoli un range di lunghezze di sottostringhe da controllare significativo, diciamo nel caso specifico 4 - 5.
Suddividi la stringa da controllare in tante sottostringhe da 4 e poi in tante sottostringhe da 5 e le inserisci in una lista di Test.
Cerca per ogni sottostringa della lista se c'è un corrispondente nella stringa originale.
Se la media pesata (i test da 5 valgono piu dei test da 4) dei test passati supera un certo target, diciamo 70% sul totale dei test, allora la stringa corrisponde.
Spero sia un buon inizio da cui partire, ovviamente questo presuppone che tu abbia la stringa esatta con cui controllare quella potenzialmente simile.

Si diciamo che ho la stringa quasi esatta.
Nel senso che non so' se c'è l'ho.
Diciamo che data una stringa x, in un insieme Y, devo trovare tutte quelle simili, e metterla in un sottoinsieme z.
Poi successivamente, data la stringa successiva a x, trovare tutte quelle simili, e metterle in un sottoinsieme z1, poi via z2, z3, z4.... ecc...
Quando ho tutti i sottoinsiemi, semplicemente devo fare delle operazioni di pulizia, cioè eliminare tutte le stringhe scorrette e lasciare solo quella corretta, se non c'è, l'aggiungo io.
Ho capito più o meno quello che vuoi fare, ma hai un esempio pratico in mente?
Non in un linguaggio specifico non voglio codice pronto, anche perchè non mi serve, nella mia situazione devo per forza scrivermi il mio.
Intendo dalla stringa "Pubblica Amministrazione", quali sono i primi step da fare, per trovare nella lista delle stringhe, ammesso che ci siano, le varie stringhe, Pubblica Ammnstrazione, Pubblica Ammnstrzion, Pubblica Ammanstzione, ecc?
Nel mio caso si tratta di un DB, di 1700 stringhe, in cui sicuramente ci sono delle ripetizioni del genere.
L'algoritmo genetico mi interessa da implementare, ma forse è un po' lungo, semmai mi interessa anche sapere come google implementa certe cose, non c'è documentazione al riguardo?

Marco.