go backsqlschool blogs list

Implementing Fuzzy string matching/comparing

by Antonios Chatzipavlis

Πολλές φορές χρειαζόμαστε σε 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.

Τιμή Αλγόριθμος
0 The Levenshtein edit distance algorithm
1 The Jaccard similarity coefficient algorithm
2 A form of the Jaro-Winkler distance algorithm
3 Longest common subsequence algorithm

Ο αλγόριθμος του 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*/

Ημερομηνία: 01 September 2012 01:26
Share it:

Σχόλια - Comments

user-gravatar

Στις 01 Sep 2012 @ 3:15 AM o/η Μάρκος Σαμούχος έγραψε:

Γεια σου Αντώνη,Μια διευκρινιστική ερώτηση: Επρόκειτο για δύο πίνακες που θα μπορούσαν να κληρονομούν κοινά πεδία από κάποιον τρίτο, αλλά κάτι τέτοιο δεν υλοποιήθηκε κατά το στάδιο της ανάπτυξης της εφαρμογής; Πχ επαφές -> πελάτες, προμηθευτές. Ό,τι είναι και πελάτης και προμηθευτής κληρονομεί το ίδιο ContactID. Οπότε μπορούν να διαχωριστούν οι αμιγώς πελάτες - προμηθευτές από εκείνους που έχουν διπλή ιδιότητα (εκτός και αν στις επαφές υπάρχουν διπλοεγγραφές). Και το ΑΦΜ, δεν βοηθάει;Ρωτάω γιατί δυσκολεύομαι να συλλάβω την αιτία του προβλήματος. Κάτι τέτοιο θα περίμενα να συμβεί σε μία σχέση προϊόντος - πρώτης ύλης, παρά πελάτη - προμηθευτή. Φαντάζομαι ότι όταν το προϊόν είναι ταυτόχρονα και πρώτη ύλη, άστα να πάνε! Ειδικότερα αν κατά την παραγωγική διαδικασία γίνεται σύνθεση ή/και αποσύνθεση πρώτων υλών για την οποία τηρούνται ενδιάμεσα δεδομένα. Άντε βγάλε report μετά...

user-gravatar

Στις 01 Sep 2012 @ 6:28 PM o/η antonch έγραψε:

Πραγματικά είναι εύλογη η απορία σου και ήμουν σίγουρος ότι κάποιος θα την εξέφραζε όταν έγγραφα το post αυτό. Αν θα προσέξεις έχω γράψει «ας πούμε πελάτης, ας πούμε προμηθευτής». Ο λόγος που το έκανα αυτό ήταν αφενός να γίνει περισσότερο κατανοητό το σενάριο αφετέρου δεν μπορώ να αναφέρω τις πραγματικές καθώς πρόκειται μια ιδιαίτερου χειρισμού εφαρμογή που η αναφορά σε αυτή πιθανολογώ ότι θα μου δημιουργούσε νομικά προβλήματα. Έτσι αποφάσισα να χρησιμοποιήσω ένα όσο το δυνατόν ανώδυνο παράδειγμα. Σίγουρα σε αυτές τις οντότητες θα μπορούσες μέσω του ΑΦΜ να κάνεις μια χαρά την δουλειά σου. Επίσης να αναφέρω ότι δεν υπάρχει σχεδιαστικό λάθος στην εφαρμογή και φυσικά στην database. Απλά πρόκειται για δύο οντότητες που μέχρι τώρα δεν είχαν καμία επαφή αλλά επειδή οι ανάγκες όπως γνωρίζεις αλλάζουν ζητήθηκε στο συγκεκριμένο report να εμπλακούν και οι δύο.

user-gravatar

Στις 01 Sep 2012 @ 9:00 PM o/η Μάρκος Σαμούχος έγραψε:

Να σου πω την αλήθεια, το κατάλαβα αυτό από την αρχή (μια πιθανή νομική εμπλοκή). Απλά έσπαγα το κεφάλι μου σε τι είδους εφαρμογή και υπό ποιες συνθήκες θα μπορούσε κανείς να βρεθεί μπροστά σ' ένα τέτοιο πρόβλημα. Το μόνο που μου ερχόταν στο μυαλό ήταν κάποιας μορφής "βιομηχανικού τύπου" λογισμικό που κάνει tracking σε οντότητες που μετασχηματίζονται κατά τη διάρκεια μιας παραγωγικής διαδικασίας. Δηλαδή, πρόκειται για ένα σχόλιο με εντελώς ακαδημαϊκό χαρακτήρα. Το post σου έδινε μια λύση κι έψαχνα να βρω ένα πρόβλημα για να την εντάξω! Καταλαβαίνεις, δουλειά δεν είχε ο... Αυτά!!!

user-gravatar

Στις 10 Apr 2014 @ 1:42 PM o/η AndreasV έγραψε:

Πολύ ενδιαφέρον το άρθρο και με αρκετές πτυχές που αναδεικνύουν κάποια λίγο "ξεχασμένα" χαρακτηριστικά (ή με καλύτερα Ελληνικά features) του SQL Server (call me SQL CLR).Να πούμε για αυτόν που το διαβάζει και δεν έχει ασχοληθεί πολύ με το θέμα οτι ο αλγόριθμος αυτός επιστρέφει απλά το ελάχιστο πλήθος των αλλαγών (ειδαγωγές, διαγραφές ή αντικαταστάσεις) που πρέπει να γίνουν στο ένα string για να οδηγηθεί κάποιος στο άλλο.Επίσης, υπάρχει και υλοποίηση που εκφράζεται και ως ποσοστιαίο αποτέλεσμα (από 0 έως 1) που ίσως βολεύει κάποιους σε ορισμένες περιπτώσεις.

user-gravatar

Στις 10 Apr 2014 @ 6:02 PM o/η AndreasV έγραψε:

Sorry για το 2ο post (δυστυχώς δεν μπορώ να κάνω editing to προηγούμενο μου).Μια παρατήρηση τεχνική για να αποφύγουμε το "σκάσιμο" της συνάρτησης:Καλό θα ήταν να ελέγχουμε για τιμές null στις παραμέτρους που περνάμε... ;)Thnx!!

user-gravatar

Στις 10 Apr 2014 @ 10:30 PM o/η Antonios Chatzipavlis έγραψε:

Σωστή η παρατήρηση και είμαι 100% μαζί σου, αλλά εδώ δεν γράφουμε κώδικα παραγωγής, απλά εστιάζουμε στο συγκεκριμένο θέμα και προσπαθούμε να το κάνουμε όσο πιο απλό μπορούμε για να γίνει κατανοητό. Εξάλλου πιστεύω ότι όταν κάποιος βρίσκει κάποιον κώδικα από τον ιστό τον ραφινάρει σύμφωνα με τις ανάγκες του.

Αφήστε το σχόλιο σας - Leave your comment

Τα σχόλια έχουν κλείσει.
Επιτρέπονται μόνο τα σχόλια από τα μέλη του SqlSchool.gr.


newsletter subscription

Εάν επιθυμείτε να λαμβάνετε ενημέρωση από εμάς, δώστε μας το e-mail σας.
PASS chapter logo
Official Professional Association for SQL Server (PASS) chapter for Greece
Join to PASS