Levenshtein Distance: miglioramenti nella logica dell'algoritmo

La scorsa volta, partendo dalla necessità di testare un algoritmo che consentisse di correlare automaticamente tra loro le news, ho parlato di Levenshtein Distance: cos'è, e come si calcola. Ora vediamo un po' come fare a risparmiare un po' di tempo macchina - che, visto che il problema è fondamentalmente di volume di calcoli, ci servirà senz'altro. Prima di iniziare, mi permetto di consigliare la rilettura della "puntata precedente": non perché sia degna di Dostoevskij, ma perché altrimenti è realmente difficile seguire il filo del discorso.

E’ evidente che l’algoritmo presentato la volta scorsa è estremamente costoso dal punto di vista computazionale, visto che - se la lunghezza della prima stringa è m, e della seconda è n - richiede m*n confronti.
Prima di ragionare su ottimizzazioni del codice ("premature optimization is the root of all evils", citando a memoria Knuth; in generale, non è mai una buona idea ottimizzare localmente del codice, quando si deve ancora ragionare sulla sua logica di funzionamento), ci sono un paio di considerazioni necessarie per risparmiare un po’ di calcoli:

- l’andamento dei valori della matrice - per definizione - ha la seguente logica: lungo una diagonale, i numeri non sono mai decrescenti. Ogni valore è superiore, uguale o inferiore di uno a quello alla sua sinistra, e stessa cosa vale per la cella superiore. In notazione:
- da questo discende logicamente (provate un po’ a ragionarci sopra) che l’algoritmo per il calcolo di una cella può essere semplificato come: se i due caratteri corrispondenti sono uguali, il valore della cella è identico a quello della diagonale superiore. Altrimenti, è il minimo tra quello della cella a sinistra, della cella in alto o della cella diagonale, +1. Sembra una sciocchezza, ma la considerazione fa risparmiare un bel po’ di lavoro alla cpu

- in realtà, quando andiamo a vedere se le news sono correlate, non ci interessa sapere la LD: ci interessa solo sapere se questo valore è inferiore ad un determinato livello (in tal caso, le parole sono considerate simili). Ma se noi sappiamo che lungo la diagonale i valori non possono calare, ogni volta che ci troviamo sulla stessa diagonale dell’ultima cella (cioè quella che al termine darà la LD) possiamo verificare se il valore è superiore al livello massimo accettabile; se è così, possiamo già ritornare dalla procedura con la certezza che le parole sono sufficientemente dissimili, senza bisogno di ulteriori calcoli. Così, tanto per prendere l’esempio di prima, e prendendo come differenza massima accettabile 4, abbiamo che:
da questo punto in poi possiamo sospendere i calcoli, e ritornare che le parole sono troppo dissimili.

- infine, un’ultima considerazione: se le due parole sono lunghe rispettivamente m e n, e il limite accettabile è k, se (m-n) > k possiamo già essere sicuri che le parole sono troppo dissimili, ancora prima di avere compilato anche solo una cella della matrice.

- in realtà, se le stringhe sono uguali non dovrebbe essere necessario alcun calcolo (la LD è zero per definizione, e inferiore a qualsiasi limite). Tuttavia, per come è implementato l’operatore di uguaglianza tra stringhe in c++, un tale test rallenta l’algoritmo piuttosto che accelerarlo. Devo provare a sostituire il confronto tra stringhe c++ con il classico confronto tra stringhe in c (strcmp, per gli addetti ai lavori), a vedere se dà risultati più confortanti

Salta all’occhio come buona parte delle celle calcolate non serva a nulla, e difatti ci sono fior di articoli in rete che suggeriscono algoritmi in grado di ridurre le celle calcolate (facendo una ricerca su Ukkonen, che è un po’ il capostipite di queste ottimizzazioni, si trova materiale di ottimo livello). Tuttavia, questo introduce una mole di calcoli che verrebbe ammortizzato nel caso le stringhe da confrontare fossero molto lunghe (si pensi a due sequenze di DNA, per esempio), mentre rischia di essere controproducente nel caso che stiamo trattando noi. Devo dire che questa è solo una sensazione, perché non ho ritenuto di investire tempo nell’implementare ottimizzazioni (non c’è codice pronto) e fare un po’ di test.

Per oggi è tutto. Solo un’ultima cosa: io - dell’intera materia - sono , come già detto, un novizio. Chiunque avesse consigli o suggerimenti, o anche implementazioni ottimizzate della LD in c++ (o c) a sottopormi, sappia che il suo contributo sarebbe sicuramente apprezzato.