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.