Migliorare l'algoritmo, il tool

Visto che in qualche maniera il wm mi ha coinvolto nell’ottimizzazione dell’algoritmo per la correlazione tra news, vediamo un attimo di parlare un po’ di più su quanto sto facendo.

In estrema sintesi, l’algoritmo ragiona sintetizzando una news nelle sue 10 parole chiave, e considerando correlate le news che hanno similitudini tra le loro parole chiave. Questa ovviamente è una semplificazione - l’algoritmo è più complesso di così.
Visto che il "comportamento" dell’algoritmo è determinato da una decina di parametri, e visto che ogni parametro ha un range tra 0 e 10 (solo valori interi), il calcolo combinatorio ci dice che - dato che il numero di disposizioni con ripetizione di n simboli a gruppi di k è n^k (ovvero n elevato alla k) - le combinazioni possibili sono 10^10, dieci miliardi. Alcune combinazioni sono illogiche (cioè prevedono combinazioni di parametri che sono in contrasto con la logica dell’algoritmo), ma comunque il numero presumibilmente rimarrà piuttosto elevato (difficilmente sotto la decina di milioni, il ché comunque comporta un calo di tre ordini di grandezza).

Abbiamo due problemi:
1. come affrontare problemi combinatori complessi; qui è stata fondamentale la collaborazione di un altro vecchio amico di pc-facile, Bianconiglio; rimando la questione - assolutamente interessante - ad un'altra data, anche perché sto ancora testando varie soluzioni, e non potrei fornire altro che teoria.
2. come ottimizzare un algoritmo specifico, in un linguaggio specifico.

In merito al punto 2, è chiaro che - stante il numero di soluzioni possibili del problema - è assolutamente cruciale che l’algoritmo funzioni alla massima velocità possibile. Il primo passo è stato dunque portarlo in un linguaggio efficiente - ho usato il c++, che fornisce (a mio parere) una buona sintesi tra efficienza e comodità (il c è probabilmente più efficiente, ma per i miei gusti troppo di basso livello per essere comodo). Inoltre, è probabilmente il linguaggio in cui mi sento maggiormente competente.

La Levenshtein Distance
L’algoritmo fa uso - sia quando sintetizza una news in 10 parole chiave, sia quando confronta le parole chiave di news diverse - del concetto di Levenshtein Distance (da ora in poi, LD).
Al di là del nome esoterico, questo valore esprime la distanza tra due parole, intendendola come numero di "operazioni" da farsi sulla prima per ottenere la seconda - dove le operazioni possibili sono l’aggiunta di un carattere, la sottrazione di un carattere o la sostituzione di un carattere. Tanto per fare un esempio, per passare da "SCAPOLO" a "INSCATOLARE" servono: l’aggiunta di due caratteri (I e N), la sostituzione di due caratteri (P e O con T e E), l’aggiunta di due caratteri (R e E). La Levenshtein è di 6.

Documentandomi un po’ (personalmente, non avevo mai sentito parlare della LD fino ad una quindicina di giorni fa), ho trovato che l’algoritmo di base per il calcolo della LD è il seguente:

- si costruisce una bella matrice di dimensioni (lunghezza prima stringa+1, lunghezza seconda stringa +1)
- si riempie la prima riga e la prima colonna con i numeri naturali a partire da 0

Quindi, la situazione di partenza è la seguente:
A questo punto si prosegue per colonne. La regola è che, per ogni cella:
- si calcola il "costo": se i due caratteri corrispondenti della stringa sono uguali, il costo è 1. Altrimenti è 0
- il valore della cella è il minimo tra: quello della cella affianco + 1, quello della cella sopra +1, quello della cella nella diagonale in alto a sinistra + il costo (come calcolato sopra).
Tanto per intenderci, riporto la compilazione delle colonne. Evidenzio in neretto un caso in cui il costo è zero, cioè i caratteri sono uguali.

La LD è il valore dell’ultima cella in basso a destra (in questo caso 6).