Stringhe che si assomigliano...

[rinosan_76bis]

Salve a tutti... spulciando qua e la ho trovato il modo (ancora da usare per me) di rintracciaRE 2 stringhe simili usando la funzione di Levenshtein. Con questa funzione casa e caso sono riconosciute come simili.
Fin qui credo che provando si dovrebbe riuscire.
Ma volendo associare frasi come

- palestra judo
- judo palestra
- judo palestre
- palestre judo
- palestre di judo

Voi che strada prendereste?
Ad esempio il di controllo se è una di quelle particelle "stupide" italiane e tutto sommato non lo conteggio... ma per il resto come fareste?
Rino

[satifal]

Per quanto riguarda le singole parole credo che Levenshtein vada benissimo, per le parole composte credo che l'unica sia scomporle in parole singole con explode() e poi implementare un algoritmno che verifichi il numero di parole della prima frase presenti nella seconda utilizzando ad esempio in_array() e magari applicando anche Levenshtein su ogni singola parola.

[rinosan_76bis]

fin qui c'ero anche io, ma devo ammettere che non mi piaceva l'idea... nel senso che rischio di fare un sacco di cicli e di ammazzare la macchina (questa è la mia paura) allora cercavo qualche idea più ottimizzata, cmq grazie per la risposta

Di stanotte mi è venuta in mente una soluzione possibile, ve la scrivo e se vi va la analizziamo assieme per capire limiti e pregi:

- se tolgo gli spazi tra le parole e le considero 1 unica parola che succede?

Di sicuro quando le parole sono in ordine inverso le perdo, nel senso che l'ugualianza non c'è, ma per lo stesso ordine dovrebbe andare no?

Quindi potrei fare come primo controllo questo in modo che se è già "simile" mi evito poi il ciclo descritto da Satifal, giusto?
Altre idee?

[satifal]

Considera che l'algoritmo che cerchi di implementare non è comunque banale, soprattutto nel caso pessimo.
L'idea di concatenare le parole potrebbe migliorare un po' la situazione nei casi migliori ma la funzione Levenshtein ha comunque una complessità O(m * n).
Se le parole sono in ordine te la cavi con una complessità non troppo elevata in caso contrario dubito che tu possa evitare di eseguire una serie di cicli e di confronti.

[rinosan_76bis]

Quindi dici che è stupido fare quel controllo?
Nel caso dei cicli, tu come faresti a decidere se sono simili le parole... nel senso, io faccio il confronto ciclando, nel caso migliore 1 parola è simile e le altre no... come faccio però a fine ciclo a decidere se delle 2 parole entrambe hanno una corrispondenza?

[rinosan_76bis]

e mi sorge un altro dubbio... se la corrispondenza dovesse essere per significato... tipo palestre->palestra OK ma case -> cose NO sarebbe praticamente impossibile o si può, secondo te/voi?