Πολλές φορές χρειαζόμαστε σε strings να  κάνουμε συγκρίσεις για το αν αυτά είναι όμοια ή πόσο κοντά είναι το ένα στο άλλο. Αυτό όπως καταλαβαίνει κανείς εγκυμονεί αρκετούς κινδύνους, παραδοχές και πολλά ακόμα που πρέπει να λάβουμε υπόψη, ειδικά αν δεν έχουμε βάλει αυστηρούς ελέγχους στο τι πληκτρολογεί ο χρήστης.

Παρ’ ότι στον SQL Server έχουμε την SOUNDEX και την DIFFERENCE υπάρχουν περιπτώσεις που δεν μας είναι αρκετές για ικανοποιήσουμε τις ανάγκες μας.

Για αυτές τις περιπτώσεις θα πρέπει να δράσουμε κάπως διαφορετικά και θα πρέπει να δημιουργήσουμε εμείς κάτι το οποίο να καλύπτει τις ανάγκες αυτές.

Αφορμή για τον post αυτό είναι όταν πριν από  λίγο καιρό ήμουν παρόν σε μια συζήτηση δύο συναδέλφων που διαδραματίζονταν μπροστά μου και επειδή μου άρεσε το θέμα ζήτησα να συμμετάσχω και εγώ σε αυτή.

Το πρόβλημα

Οι συνάδελφοι αντιμετώπιζαν ένα πρόβλημα το οποίο ήταν το εξής:

Σε μία εφαρμογή η οποία είχε υλοποιηθεί πριν από πολλά χρόνια και τρέχει ήδη άλλα τόσα σε παραγωγικό περιβάλλον είχε έρθει μια νέα απαίτηση από τον πελάτη που έπρεπε να καλυφθεί.

Η απαίτηση αυτή αφορούσε ένα report στατιστικών που μέχρι τώρα έβγαινε με βάση τις κινήσεις μιας οντότητας ας πούμε ότι αυτή είναι ο πελάτης και η νέα απαίτηση ζητούσε να βγαίνει συνδυαστικά με ακόμα μια οντότητα που ας πούμε είναι ο προμηθευτής. Βέβαια ζητούσε αν ένας πελάτης είναι και προμηθευτής και το αντίστροφο να μην εμφανίζετε δύο φορές αλλά μία και τα δεδομένα του να είναι αθροιστικά.

Δυστυχώς δεν υπήρχε κάποιο πεδίο μεταξύ τους που να είναι κοινό και να τις χαρακτηρίζει μοναδικά παρά μόνο η «επωνυμία». Αλλά και αυτή δεν ήταν η ίδια παντού καθώς είναι πεδίο το οποίο πληκτρολογεί χρήστης και δεν είχε κάποιους κανόνες ή δεν γίνονταν ανάκτηση αυτού από κάποιες προσυμφωνημένες τιμές.

Από την ποιοτική έρευνα που έγινε στα δεδομένα είδαμε ότι υπήρχαν πολλές ομοιότητες αλλά και διαφορές. Για τις μεν πρώτες τα πράγματα ήταν απλά για τις δεύτερες όμως…

Οι πρώτες σκέψεις

Αρχική σκέψη για την λύση του προβλήματος ήταν  να φτιαχτεί μια νέα function στον κώδικα της εφαρμογής  να διαβάζει τα δεδομένα και από τους δύο πίνακες και να κάνεις συγκρίσεις ώστε να παραχθεί ένα αποτέλεσμα τέτοιο που να επιτρέπει την εξαγωγή του report. Όμως αυτή η λύση είχε πολλά θέματα που έπρεπε να αντιμετωπιστούν και το κυριότερο επειδή θα άλλαζε ο source code αυτή η έκδοση θα έπρεπε να περάσει ξανά από όλες τις διαδικασίες που ο πελάτης έχει για την εγκατάσταση λογισμικού στους clients. Όπως καταλαβαίνει κανείς αυτό θέλει χρόνο και ο πελάτης ήθελα να δει άμεσα κάποια πράγματα για να σχηματίσει μια εικόνα ώστε να πάρει αποφάσεις.

Δεύτερη σκέψη ήταν να γραφτεί κάτι στον SQL Server και να χρησιμοποιηθεί στην stored procedure που παρήγαγε το report. Αυτή ήταν μια καλή λύση καθώς δεν θα άλλαζε το source code και οι διαδικασίες του πελάτη σε τέτοιες περιπτώσεις είναι σαφώς γρηγορότερες. Έτσι οι συνάδελφοι είχαν προσανατολιστεί στην συγκεκριμένη προσέγγιση.

Είχαν δοκιμάσει αρκετά και είχαν φτάσει αρκετά κοντά αλλά τους έλλειπε κάτι ακόμα για να δώσουν λύση που να αγγίζει το 100%.

Η εμπλοκή μου

Μου άρεσε η πρόκληση αυτή έτσι αποφάσισα να ασχοληθώ.

Integration Services

Από την αρχή το μυαλό μου πήγε στα Integration Services (SSIS) και το Fuzzy lookup αλλά έτσι όπως ήταν δομημένα τα πράγματα περισσότερη δουλειά  θα έβαζα παρά θα έδινα λύση. Παρόλα αυτά όμως ήμουν εστιασμένος σε κάτι fuzzy.

Πραγματικά εκείνη την στιγμή τα 5 εγκεφαλικά κύτταρα που μου έχει δώσει ο Θεός και από τα οποία τα 5,5 είναι καμένα άρχισαν να δουλεύουν σε ασύγχρονους ρυθμούς και το SQLOS του μυαλού μου άρχισε να δημιουργεί πολλαπλούς schedulers. Φυσικά ένα τσιγάρο πάντα βοηθάει σε αυτές τις περιπτώσεις.

Master Data Services

Γνωρίζοντας ότι ο πελάτης είναι σε SQL Server 2008 R2 μου ήρθε μια ιδέα να ρωτήσω αν έχει εγκατεστημένα τα Master Data Services (MDS)  του SQL Server. Δυστυχώς όμως δεν τα είχε και ούτε είχε την πρόθεση να τα εγκαταστήσει. Θα αναρωτιέστε βέβαια πως ήρθαν στο μυαλό μου τα MDS ναι μεν θα μπορούσαν να είχαν δώσει λύση στο συγκεκριμένο πρόβλημα αλλά θα έπρεπε αυτό να είχε γίνει εδώ και πολύ καιρό…

Αυτό που με ώθησε να σκεφτώ τα MDS ήταν το γεγονός ότι εκτός από γραφικό περιβάλλον που έχουν υπάρχει και API και αυτό είναι γραμμένο σε .NET άρα είναι CLR. Επειδή έχω ασχοληθεί με αυτά γνωρίζω εφόσον έχεις στήσει αυτά υπάρχει μια function στην MDS database η Similarity. Αν πας και πάρεις το script της συγκεκριμένης function από την MDS DB θα σου τα μαρτυρήσει όλα όπως παρακάτω:

ALTER FUNCTION [mdq].[Similarity](@input1 nvarchar(4000), @input2 nvarchar(4000),
                          @method tinyint, @containmentBias float, @minScoreHint float)
RETURNS [float] WITH EXECUTE AS CALLER, RETURNS NULL ON NULL INPUT
AS
    EXTERNAL NAME [Microsoft.MasterDataServices.DataQuality].[Microsoft.MasterDataServices.DataQuality.SqlClr].[Similarity]
GO

Αν κοιτάξεις καλύτερα θα δεις ότι στο assembly Microsoft.MasterDataServices.DataQuality υπάρχει μια μέθοδος η Similarity η οποία κάνει αυτό που οι συνάδελφοι ζητούσαν.

Σαν τεμπέλης που είμαι ή θα χρησιμοποιούσα αυτή ή θα έβαζα το assembly στη βάση των συναδέλφων και θα έφτιαχνα την function. Όμως όπως είπα τζίφος. Παρόλα αυτά όμως είχα εστιαστεί προς την συγκεκριμένη κατεύθυνση και ο λόγος για μένα ήταν προφανής καθώς στην συγκεκριμένη μέθοδο όπως φαίνεται υπάρχει η @method parameter η οποία παίρνει τις εξής τιμές οι οποίες φαίνονται στον παρακάτω πίνακα και στην ουσία υποδηλώνουν τον αλγόριθμο που θα χρησιμοποιηθεί για να γίνει η σύγκριση των strings.

Ο αλγόριθμος του Levenshtein

Από τα μαθητικά μου χρόνια ο μόνος αλγόριθμος που θυμόμουν ήταν αυτός του Levenshtein αλλά και αυτόν δεν τον θυμόμουν και καλά. Αλλά αυτό δεν μου ήταν και μεγάλο πρόβλημα για τον βρω καθώς κουβαλάω πάντα μαζί μου, σε ηλεκτρονική μορφή φυσικά, το απόλυτο εργαλείο αλγορίθμων και όχι μόνο για databases. Αυτό δεν είναι άλλο από την Encyclopedia of Database Systems. Έκανα σε αυτή μερικές αναζητήσεις και όπως πάντα βρήκα λύση. Στην σελίδα 374 ο έλληνας καθηγητής Δημ. Γουνόπουλος μιλάει για Cluster and Distance Measure. Συγκεκριμένα αναφέρει στους ορισμούς του Cluster και του Distance όπως παρακάτω:

Clustering

Clustering is the assignment of objects to groups of similar objects (clusters). The objects are typically described as vectors of features (also called attributes).So if one has n attributes, object x is described as a vector (x1,..,xn). Attributes can be numerical (scalar) or categorical. The assignment can be hard, where each object belongs to one cluster, or fuzzy, where an object can belong to several clusters with a probability. The clusters can be overlapping, though typically they are disjoint.  Fundamental in the clustering process is the use of a distance measure.

Distance Measure

In the clustering setting, a distance (or equivalently a similarity) measure is a function that quantifies the similarity between two objects.

Φυσικά το συγκεκριμένο κείμενο δεν έχει κώδικα αλλά μαθηματικούς τύπους (σειρές συγκεκριμένα) και προτάσεις αλγορίθμων προτείνοντας για την περίπτωση των strings την μέθοδο του Levenshtein η οποία είναι extension της μεθόδου του Hamming (μόνο για αριθμούς). Όπως αναφέρει ο καθηγητής η  «Levenshtein, distance, is an extension of the Hamming distance, and is typically used for measuring the distance between two strings of characters. The edit distance is defined as the minimum number of insertions, deletions or substitutions that it takes to transform one sting to another». Μπορείτε να διαβάσετε για αυτή στην Wikipedia αν δεν έχετε την εγκυκλοπαίδεια. Βέβαια υπάρχουν και άλλοι αλγόριθμοι αλλά αποφάσισα να υλοποιήσω την συγκεκριμένη αφού φρεσκάρισα την μνήμη μου σχετικά με αυτή. Εν συντομία η συγκεκριμένη μέθοδος συγκρίνει δύο strings και αν είναι ίδια επιστρέφει 0 αλλιώς επιστρέφει μια τιμή που όσο μεγαλύτερη είναι τόσο περισσότερο ανόμοια είναι αυτά μεταξύ τους.

Ο αλγόριθμος του Levenshtein σε T-SQL Function

Αυτό ήταν, μετά από την σχετική προθέρμανση δακτύλων και καρπών τα δάκτυλα ακούμπησαν πληκτρολόγιο ώστε να γράψω αυτόν τον αλγόριθμο σε αγνό παρθένο T-SQL. To αποτέλεσμα ήταν το παρακάτω.

CREATE FUNCTION dbo.fn_StrSimilarityByLevenshtein(@string1 nvarchar(4000), @string2 nvarchar(4000)) 
RETURNS int
AS
/*
 * Fuzzy strigns matching/comparing usign the Levenshtein method.
 * SQLSCHOOL.GR 2012
*/

BEGIN
    DECLARE @len1 int, @len2 int;
    DECLARE @i int, @j int, @k int;
    DECLARE @char_string1 nchar;
    DECLARE @cvar0 varbinary(8000), @cvar1 varbinary(8000);
    DECLARE @rv_distanse int; 

    SET @len1 = LEN(@string1);
    SET @len2 = LEN(@string2);
    SET @cvar1 = 0x0000;
    SET @j = 1;
    SET @i = 1;
    SET @rv_distanse = 0;

    WHILE (@j <= @len2)
    BEGIN
        SET @cvar1 = @cvar1 + CAST(@j AS binary(2));
        SET @j = @j + 1;
    END

    WHILE ( @i <= @len1 )
    BEGIN
        SET    @char_string1 = SUBSTRING(@string1, @i, 1);
        SET    @rv_distanse = @i;
        SET @cvar0 = CAST(@i AS binary(2));
        SET @j = 1;
        
        WHILE (@j <= @len2)
        BEGIN
            SET @rv_distanse = @rv_distanse + 1;
            SET @k = CAST(SUBSTRING(@cvar1, @j+@j-1, 2) AS int) +
                          CASE 
                                WHEN @char_string1 = SUBSTRING(@string2, @j, 1) 
                                THEN 0 
                                ELSE 1 
                          END;
            IF @rv_distanse > @k SET @rv_distanse = @k
            SET @k = CAST(SUBSTRING(@cvar1, @j+@j+1, 2) AS int)+1;
            IF @rv_distanse > @k SET @rv_distanse = @k;
            SET @cvar0 = @cvar0 + CAST(@rv_distanse AS binary(2));
            SET @j = @j + 1;
        END
        SET @cvar1 = @cvar0; 
        SET @i = @i + 1;
    END
    RETURN @rv_distanse;
END;
GO

Πράγματι η χρήση της μέσα στην stored procedure του συναδέλφου έδωσε εξαιρετικά αποτελέσματα που έφτασαν το 100%. Η λύση ήταν απλή δεν χρειάστηκε πολύς χρόνος για την υλοποίηση της και σας την προτείνω ανεπιφύλακτα, όμως σε πολύ μεγάλο αριθμό δεδομένων υπάρχει μια σχετική καθυστέρηση. Στην δική μας περίπτωση ο όγκος των δεδομένων δεν ήταν μεγάλος και αυτή δούλεψε σφαίρα.

Ο αλγόριθμος του Levenshtein σε SQL-CLR Function

Μετά από μερικές μέρες και ενώ είχα ξεχάσει το θέμα και έκανα μια ανασκόπηση για το τι έχω κάνει και τι θα κάνω την θυμήθηκα και καθώς ήμουν καθισμένος αναπαυτικά στην καρέκλα μου αποφάσισα ότι είναι μια καλή ευκαιρία να δοκιμάσω να την υλοποιήσω με SQL-CLR.
Αυτό ήταν, μετά από την σχετική προθέρμανση δακτύλων και καρπών τα δάκτυλα ακούμπησαν πληκτρολόγιο ώστε να γράψω αυτόν τον αλγόριθμο σε SQL-CLR. To αποτέλεσμα ήταν το παρακάτω.

public partial class FuzzyFunctions
{
    [Microsoft.SqlServer.Server.SqlFunction]
    public static int FuzzyStringCompareByLevenshtein ( SqlString string1 , SqlString string2 )
    {
        string s1 =  string1.Value;
        string s2 =  string2.Value;
        int len1 = s1.Length;
        int len2 = s2.Length;
        int[,] rv = new int[len1 + 1 , len2 + 1];

        for ( int i = 0; i <= len1; i++ )
            rv[i , 0] = i;

        for ( int j = 0; j <= len2; j++ )
            rv[0 , j] = j;

        for ( int j = 1; j <= len2; j++ )
        {
            for ( int i = 1; i <= len1; i++ )
            {
                if ( s1[i - 1] == s2[j - 1] )
                    rv[i , j] = rv[i - 1 , j - 1];
                else
                    rv[i , j] = Math.Min 
                                ( Math.Min 
                                           ( rv[i - 1 , j] + 1 ,           
                                             rv[i , j - 1] + 1 ) ,     
                                             rv[i - 1 , j - 1] + 1 );  
            }
        }
        return rv[len1 , len2];
    }
    
}

Σύγκριση των υλοποιήσεων

Δοκιμάζοντας και τις δύο είδα ότι σε σχετικά μικρό αριθμό εγγράφων (κάτω από 10000) δεν υπήρχε σημαντική διαφορά σε ταχύτητα εκτέλεσης, όμως σε μεγάλο αριθμό εγγραφών η υλοποίηση με SQL-CLR πετούσε. Μπορώ να πω ότι ήταν και 40% καλύτερη από την υλοποίηση με T-SQL.

Επίλογος

Εγώ πλέον έχω στην φαρέτρα μου και τις δύο και όταν αντιμετωπίσω ξανά το ίδιο πρόβλημα έχω τις λύσεις έτοιμες. Τώρα όμως που διαβάζετε αυτό το post τις έχετε και εσείς ελπίζω να τις ευχαριστηθείτε.

Οδηγίες Εγκατάστασης

Για την έκδοση σε T-SQL τα πράγματα είναι απλά. Copy το script από το post, paste σε ένα query window και execute.

Για την SQL CLR έκδοση χρειάζονται περισσότερα βήματα.

1. Θα πρέπει να ανοίξεις το Visual Studio και να δημιουργήσουμε ένα project Visual C# SQL CRL Database Project.
2. Θα σε ρωτήσει σε ποιον SQL Server & Database θέλεις να συνδεθείς και το μόνο που έχεις να κάνεις είναι να επιλέξεις αυτή που θέλεις.
3. Αφού όλα είναι έτοιμα για το συγκεκριμένο project, σε αυτό θα πρέπει να βάλεις (με δεξί κλικ add ) ένα User-Defined Function.
4. Σε αυτό το UDF κάνουμε paste τον κώδικα που υπάρχει στο post.
5. Εάν είστε σε SQL Server 2008 R2 και έχει χρησιμοποιήσει Visual Studio 2010 θα πρέπει από τα properties του project να αλλάξετε την έκδοση του .NET από 4.0 σε 3.5 καθώς ο SQL Server 2008 R2 δεν το ξέρει το 4.0
6. Κάντε build & deploy και θα σας φτιάξει τα πάντα στην βάση σας.

/*antonch*/