Come calcolare in modo efficiente la somiglianza del coseno tra milioni di stringhe

Question

Ho bisogno di calcolare la somiglianza del coseno tra stringhe in una lista. Ad esempio, ho una lista di oltre 10 milioni di stringhe, ogni stringa deve determinare la somiglianza tra se stessa e ogni altra stringa nella lista. Qual è l'algoritmo migliore che posso usare per eseguire in modo efficiente e rapido tale compito? L'algoritmo divide et impera è applicabile?

EDIT

voglio per determinare quali stringhe sono più simile ad una stringa ed essere in grado di avere una misura/punteggio associato con la somiglianza. Penso che ciò che voglio fare coincida con il clustering in cui inizialmente non si conosce il numero di cluster.

Answer 1

Lavorare con la matrice trasposta. Questo è ciò che Mahout fa su Hadoop per eseguire questo tipo di attività velocemente (o semplicemente usare Mahout).

In sostanza, il calcolo della somiglianza del coseno è ingenuo. Perché finisci per calcolare un sacco di 0 * qualcosa. Invece, è meglio lavorare nelle colonne e lasciare tutti gli 0 lì.

Answer 2

Si potrebbe provare SimString.

È una libreria C++ (con collegamenti Python o Ruby) per la corrispondenza approssimativa delle stringhe.

Afferma di trovare stringhe con alta somiglianza coseno in meno di 1 millisecondo per un database di 13 milioni di stringhe.

L'algoritmo utilizzato è descritto here in base all'eliminazione delle liste invertite.