Come si ricercano in un campo testo valori approssimativamente uguali ad un valore passato?
La questione non è per niente banale e richiede una definizione esatta di quel "approssimativamente" e d'altra parte quella definizione dipende dall'ambito di utilizzo.

Una richieta naturale durante la ricerca di testi è la posibilità di lavorare case insentive e quindi potere trovare "I promessi sposi" anche cercando "I PROMESSI SPOSI". La richiesta è tanto ovvia che la collation di default di sql server è per l'appunto case insensitive e i confronti tra stringhe, a meno di precisare una collation diversa, non distinguono maiuscole e minuscole.

In moltissimi ambiti è possibile sfruttare collation ancora meno selettive al fine di avere confronti ancora più liberi. Restando in ambito librario risulta fastidiosissimo ricercare "Sepulveda" e non trovare nulla poichè la scrittura corretta di questo nome è "Sepùlveda". Una collation accent insensitive risolve questo problema.

Le possibilità delle collation tuttavia finiscono qui. Non riusciamo, per esempio eseguire ricerche che scovino parole apostrofate anziché accentate, tipo perche' e perché.

Su questo tipo di ricerche può venire in aiuto la full text search che permette confronti avanzatisimi, soprattutto sul piano semantico. La full text search permette di scovare un titolo come "L'uomo che sussurrava ai cavalli" cercando "Gli uomini che sussurreranno alle cavalle". Tale ricerca permette infatti identità di genere, di tempo, di coniugazione e di declinazione, ricerche parziali e coì via.

Ma ancora non sono soddisfatti tutti i casi di similarietà.

Se infatti i termini di ricerca non hanno valenza semantica chiara [nomi, codici e così via] la full text search serve a poco. Come scoprire che:

134Abcdefg36 è tuttosommato molto simile a 134Abcdefgh36?

La questione è decisiva in una serie di ambiti in cui il PC dovrebbe essere di supporto nella scelta. Molte aziente produttrici per esempio generano codici simili per prodotti simili. Recentemente ho lavorato ad un database di sacchetti per aspirapolvere e ho scoperto che se il mio aspirapolvere monta il sacchetto as125 e il negoziante non l'ha in casa, potrei tranquillamente acquistare un as125e che è del tutto identico ma, magari, fatto di una carta leggermente diversa.

Nativamente SQL mette a disposizione le funzioni SOUNDEX e DIFFERENCE che eseguono una valutazione fonetica del testo ma si rivelano quasi sempre inadatte allo scopo suddetto.

Cercando qua e là sono incappato nella cosiddetta Distanza di Levenshtein, definita come il numero di passaggi [aggiunte, eliminazioni, modifiche] minimo necessari per passare dalla parola A alla parola B.

L'algoritmo ufficiale per il calcolo di tale distanza è assolutamente banale [http://it.wikipedia.org/wiki/Distanza_di_Levenshtein] ma per ricrearlo in TSQL è necessario codice artificioso e poco performante non essendo gestite le matrici. Inoltre, lavorare su un centinaio di migliaia di codici con una funzione del genere in TSQL uccide il server e l'utente.

In SQL 2005 è però possibile creare funzioni in c# o in un qualche altro linguaggio compilabile all'interno del CLR e questi linguaggi offrono tutti gli strumenti e la potenza per affrontare seriamente il discorso distanza Levenshtein. Ci ho lavorato qualche mese fa e ne è venuta questa routine:

[CODE_C#]
public static int Levenshtein(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        char[] ss=s.ToCharArray();
        char[] tt=t.ToCharArray();
        int[,] d=new int[n+1,m+1];
        int i,j;

        if(n==0) return m;
        if(m==0) return n;

        for(i=0;i<n+1;i++) d[i,0]=i;
        for(i=0;i<m+1;i++) d[0,i]=i;

        for(i=1;i<n+1;i++)
            for(j=1;j<m+1;j++)
               d[i,j]=System.Math.Min(
        System.Math.Min(d[i-1,j]+1,d[i,j-1]+1),
                d[i - 1, j - 1] + (ss[i - 1] == tt[j - 1] ? 0 : 1));

        return d[n, m];
    }
[/CODE_C#]

Compilato e acquisito in SQL ho fatto un test su 100.000 codici generati casualmente e, con una certa sorpresa, la ricerca è risultata molto efficiente. Quindi mi sono buttato su un test più serio, sfruttando codici reali e lavorando su una oluzione più avanzata che si occupasse, passando un testo, di scovare i primi 10 risultati in ordine di distanza Levenshtein.
Per ottimizzare un po' il codice ho scritto una stored procedure che lavora per passi, sfruttando il fatto che se due termini hanno un numero di lettere differente avranno distanza Levenshtein almeno pari alla differenza di lunghezze.

Quindi, per ridurre le chiamate alla funzione comincio a lavorare sui soli termini di lunghezza pari al termine cercato e poi mi allontano piano piano sfruttando un campo calcolato e indicizzato che contiene la lunghezza incriminata.

Come ulteriore complicazione, il mio caso reale, richiede che ogni codice sia associato a un certo tipo e che di ogni tipo venga estratto al più un codice. La tabella di codici contiene quindi un ID_Tipo per questo scopo

create table t_Codici(ID_Codice uniqueidentifier primary key,
    Codice varchar(255) not null,
    ID_Tipo uniqueidentifier not null,
    L  as len([Codice]))

La procedura assume invece un aspetto del tipo:

create procedure [dbo].[p_Find](@Codice varchar(255))
as

declare @lev table(Codice varchar(255),ID_Tipo uniqueidentifier, lev int)
declare @res table(Codice varchar(255),ID_Tipo uniqueidentifier primary key,lev int)

declare @k int,@r int,@maxresults int

select @k=0,@r=0,@maxresults=10

while 1=1
    begin
    insert into @res
    select top(@maxresults) max(Codice),ID_Tipo,@k from @lev 
    where lev=@k
    group by ID_Tipo
    
    set @maxresults=@maxresults-@@rowcount
    if @maxresults<1 break
    
    delete @lev where ID_Tipo in(Select ID_Tipo from @Res)

    insert into @lev
    select Codice,ID_Tipo,dbo.f_Levenshtein(lower(@Codice),lower(Codice)) from t_AS_Codici
    where (l=len(@Codice)-@k or l=len(@Codice)+@k)
    and ID_Tipo not in(Select ID_Tipo from @Res)

    insert into @res
    select top(@maxresults) max(Codice),ID_Tipo,@k from @lev 
    where lev=@k
    group by ID_Tipo
    
    set @maxresults=@maxresults-@@rowcount
    if @maxresults<1 break

    delete @lev where ID_Tipo in(Select ID_Tipo from @Res)
    
    set @k=@k+1

    if @k>10 break
    end

select Codice,ID_Tipo,10-Lev Level from @res
order by lev, abs(len(@Codice)-len(Codice))

La ricerca di 'Vampir' [il nome storpiato di un aspirapolvere] su 120.000 codici genera in meno di 2 secondi questo output [esattamente quello atteso]:

Codice        Level [=10-Distanza Levenshtein]

VAMPYR     9
VAMP90     8
CAMPI        8
VAMPYR6    8
VAMPYR8    8
VAMPYR4    8
VAMPYR5    8
ASPIRA        7
AMBIA        7
VS1PR        7