Optimisation de l'algorithme de distance de Levenshtein

Question

J'ai une procédure stockée qui utilise la distance de Levenshtein pour déterminer le résultat le plus proche de ce que l'utilisateur a tapé. La seule chose qui affecte vraiment la vitesse est la fonction qui calcule la distance de Levenshtein pour tous les enregistrements avant de sélectionner l'enregistrement avec la plus faible distance (j'ai vérifié cela en mettant un 0 à la place de l'appel à la fonction Levenshtein). La table a 1,5 million d'enregistrements, donc même le moindre ajustement peut raser quelques secondes. À l'heure actuelle, tout cela dure plus de 10 minutes. Voici la méthode que j'utilise:

ALTER function dbo.Levenshtein 
( 
    @Source nvarchar(200), 
    @Target nvarchar(200) 
) 
RETURNS int 
AS 
BEGIN 
DECLARE @Source_len int, @Target_len int, @i int, @j int, @Source_char nchar, @Dist int, @Dist_temp int, @Distv0 varbinary(8000), @Distv1 varbinary(8000) 

SELECT @Source_len = LEN(@Source), @Target_len = LEN(@Target), @Distv1 = 0x0000, @j = 1, @i = 1, @Dist = 0 

WHILE @j <= @Target_len 
BEGIN 
    SELECT @Distv1 = @Distv1 + CAST(@j AS binary(2)), @j = @j + 1 
END 

WHILE @i <= @Source_len 
BEGIN 
    SELECT @Source_char = SUBSTRING(@Source, @i, 1), @Dist = @i, @Distv0 = CAST(@i AS binary(2)), @j = 1 

WHILE @j <= @Target_len 
BEGIN 
    SET @Dist = @Dist + 1 
    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j-1, 2) AS int) + 
        CASE WHEN @Source_char = SUBSTRING(@Target, @j, 1) THEN 0 ELSE 1 END 

    IF @Dist > @Dist_temp 
    BEGIN 
     SET @Dist = @Dist_temp 
    END 

    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j+1, 2) AS int)+1 

    IF @Dist > @Dist_temp SET @Dist = @Dist_temp 
    BEGIN 
     SELECT @Distv0 = @Distv0 + CAST(@Dist AS binary(2)), @j = @j + 1 
    END 
END 

SELECT @Distv1 = @Distv0, @i = @i + 1 
END 

RETURN @Dist 
END 

Où dois-je aller?

Answer 1

La façon dont j'ai fait cela dans le passé est de stocker la "base de données" (en fait un dictionnaire de mots pour un correcteur d'orthographe) comme un trie. Puis j'ai utilisé une routine branchée-et-liée pour rechercher les entrées correspondantes les plus proches. Pour les petites distances, le temps qu'il faut est exponentiel dans la distance. Pour les grandes distances, il est linéaire dans la taille du dictionnaire, comme vous le voyez maintenant.

L'embranchement est fondamentalement une marche en arborescence en profondeur du trie, mais avec un budget d'erreur. A chaque nœud, vous gardez une trace de la distance levenshtein actuelle, et si elle dépasse le budget, vous élaguez cette branche de l'arbre.

D'abord vous faites la marche avec un budget de zéro. Cela ne trouvera que des correspondances exactes. Si vous ne trouvez pas de correspondance, vous l'utilisez avec un budget de un. Cela trouvera des matchs à une distance de 1. Si vous n'en trouvez pas, alors vous le faites avec un budget de 2, et ainsi de suite. Cela semble inefficace, mais puisque chaque promenade prend tellement plus de temps que la précédente, le temps est dominé par la dernière marche que vous faites.

Ajouté: les grandes lignes de code (pardonnez mon C):

// dumb version of trie node, indexed by letter. You can improve. 
typedef struct tnodeTag { 
    tnodeTag* p[128]; 
} tnode; 

tnode* top; // the top of the trie 

void walk(tnode* p, char* s, int budget){ 
    int i; 
    if (*s == 0){ 
    if (p == NULL){ 
     // print the current trie path 
    } 
    } 
    else if (budget >= 0){ 
    // try deleting this letter 
    walk(p, s+1, budget-1); 
    // try swapping two adjacent letters 
    if (s[1]){ 
     swap(s[0], s[1]); 
     walk(p, s, budget-1); 
     swap(s[0], s[1]); 
    } 
    if (p){ 
     for (i = 0; i < 128; i++){ 
     // try exact match 
     if (i == *s) walk(p->p[i], s+1, budget); 
     // try replacing this character 
     if (i != *s) walk(p->p[i], s+1, budget-1); 
     // try inserting this letter 
     walk(p->p[i], s, budget-1); 
     } 
    } 
    } 
} 

Fondamentalement, vous simulez la suppression d'une lettre en sautant et la recherche au même noeud. Vous simulez l'insertion d'une lettre en descendant le trie sans avancer s. Vous simulez de remplacer une lettre en agissant comme si la lettre correspondait, même si ce n'est pas le cas. Quand vous avez compris, vous pouvez ajouter d'autres incompatibilités possibles, comme remplacer 0 avec O et 1 avec L ou I - des trucs idiots comme ça.

Vous souhaitez probablement ajouter un argument de tableau de caractères pour représenter le mot actuel que vous trouvez dans le fichier.