[SQL] Limiet toevoegen aan levenhstein stored function?

[Xthemes.us]

Hallo,

Ik heb de onderstaande stored function, (lichtelijk aangepast van stackoverflow) en zou daar graag een limiet aan toevoegen (vandaar de 'l' parameter).

MySQL:

DELIMITER $$
DROP FUNCTION IF EXISTS LEVENSHTEIN $$
CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255), l TINYINT, dam BOOLEAN)
RETURNS TINYINT
DETERMINISTIC
BEGIN
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
    DECLARE s1_char, s2_char CHAR;
    -- max strlen=255
    DECLARE cv0, cv1, cv2 VARBINARY(256);
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
    IF s1 = s2 THEN
        RETURN 0;
    ELSEIF s1_len = 0 THEN
        RETURN s2_len;
    ELSEIF s2_len = 0 THEN
        RETURN s1_len;
    ELSE
        WHILE j <= s2_len DO
            SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
        END WHILE;
        WHILE i <= s1_len DO
            SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
            WHILE j <= s2_len DO
                SET c = c + 1;
                SET s2_char = SUBSTRING(s2, j, 1);
                IF s1_char = s2_char THEN
                    SET cost = 0; ELSE SET cost = 1;
                END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
                IF c > c_temp THEN SET c = c_temp; END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
                IF c > c_temp THEN SET c = c_temp; END IF;
                IF dam THEN
                    IF i>1 AND j>1 AND s1_char = SUBSTRING(s2, j-1, 1) AND s2_char = SUBSTRING(s1, i-1, 1) THEN
                        SET c_temp = CONV(HEX(SUBSTRING(cv2, j-1, 1)), 16, 10) + 1;
                        IF c > c_temp THEN SET c = c_temp; END IF;
                    END IF;
                END IF;
                SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
            END WHILE;
            IF dam THEN SET CV2 = CV1; END IF;
            SET cv1 = cv0, i = i + 1;
        END WHILE;
    END IF;
    RETURN c;
END

Ik had verwacht dat ik met een een extra stukje code binnen één van de loops er zou zijn.

MySQL:

         -- If the limit is reached, abort and save calculations
            IF c = l THEN
                return null;
            END IF;

Maar helaas pindakaas dat lijkt niet het geval te zijn. Het idee achter de functie is dus het verschil tussen twee strings te berekenen. Hoeveel karakters moeten er veranderd worden om het één in het andere te veranderen. Waarbij het omdraaien van letters minder zwaar telt als de dam parameter TRUE is. Aangezien dit een zware berekening is zou ik graag een limiet toe willen voegen (als er meer dan 'l' veranderingen nodig zijn, return null). Ik gebruik het voor een 'fuzzy' search op een enkel woord.

[RobIII]

Laten we even een stap terug doen en eens kijken wat je nou precies probeert te bereiken? Wat bedoel je met "fuzzy" en waarom wil je dat?

[Xthemes.us]

Ik probeer typo's etc af te vangen en een lijst to presenteren met woorden die er op lijken. Ik maak al gebruik van soundex (SOUNDS LIKE) en een gewone 'like' om te zien of de gegeven input een deel is van het woord. Sounds like werkt echter enkel als de eerste letter wel op de juiste plek staat en de resultaten zijn soms twijfelachtig.

levenshtein werkt goed maar i.p.v. het onderstaande te doen zou het een stuk efficienter zijn om in de functie zelf al te beperken.
Hoe het nu werkt (en dus oude code, en andere parameters)

MySQL:

            SELECT NAME
            -- Try to match by mutating string within 3 characters
            FROM `tablename` WHERE levenshtein($escapedName, name) < 3 

Hoe ik het graag zou hebben werken is in plaats van alle mutaties te berekenen en dan resultaten weg te gooien is simpelweg een null te krijgen bij alles dat meer dan 3 mutaties nodig heeft vanuit de functie en dus alle stappen daarna te besparen. Dan kan ik alsnog met een IS NOT NULL de ongewenste resultaten wegfilteren.

Fuzzy verwijst simpelweg naar het matchen van resultaten die er op lijken maar geen exacte match zijn .

[ Voor 4% gewijzigd door Xthemes.us op 16-01-2019 20:18 ]

[RobIII]

Xthemes.us schreef op woensdag 16 januari 2019 @ 20:16:
Fuzzy verwijst simpelweg naar het matchen van resultaten die er op lijken maar geen exacte match zijn .

Ik weet prima wat fuzzy betekent, maar er zijn nogal wat soorten fuzzy, vandaar juist dat ik 't vraag En ik zie je in je post vooral veel uitleggen over je bedachte oplossingsrichting, maar ik mis nog steeds een beetje 't echte probleem. Je probeert typo's af te vangen, dat is de kern?

Waarom zou je dan 1 verkeerd getyped woord tegen (potentieel) miljoenen woorden houden die je allemaal door een functie heen moet sleuren om een 'match-gehalte' te krijgen en bijvoorbeeld niet gewoon trachten het verkeerd getypte woord corrigeren naar 1 (of een paar) best gelijkende woorden en dan een full-text search doen bijvoorbeeld? Dat gaat echt verschillende ordegroottes beter werken in sommige gevallen. Maar we weten te weinig van de daadwerkelijke use-case (hoe ziet de tekst er uit, hoeveel is het, hoeveel daarvan wil je doorzoeken, kun je al op andere manieren een (groot) deel van die records wegsnijden alvorens je ze überhaupt bekijkt enz), gaat 't om een vaste set woorden (bijv. alleen woorden uit de VanDale toegestaan, of willekeurige (al-dan-niet-correcte) tekst? Verschillende talen?) etc. etc. om iets zinnigs erover te kunnen zeggen. En daarom vroeg ik dus naar meer informatie en een stap terug

[ Voor 5% gewijzigd door RobIII op 16-01-2019 20:41 ]

[Kalentum]

Xthemes.us schreef op woensdag 16 januari 2019 @ 19:42:
Ik had verwacht dat ik met een een extra stukje code binnen één van de loops er zou zijn.

En WAAR had je die IF dan precies neergezet?

[Xthemes.us]

Het valt allemaal mee in dit geval, het zijn 548 woorden op het moment, met een groei naar maximaal rond de 1000 in een VARCHAR(255) (welke tevens de primary key van de tabel is) vandaar deze aanpak welke kostbaar is maar wel erge goed resultaten geeft. Even snel wat queries gedraaid en het langste woord is zelfs maar 20 letters met een gemiddelde van ~8 letters.

Een optimalisatie die ik zou overwegen mocht ik iets vergelijkbaars op een andere tabel willen doen waar meer data in zit is eerst een soundex uit te voeren en dan die resultaten door levenhstein te halen. In dit geval is de query in de meeste gevallen van rond een halve seconde uitgevoerd met alle andere stappen daar al bij inbegrepen. De resultaten zijn zoals ik ze wil hebben en de uitvoertijd is in principe ook al prima maar ik zie een relatief simpele stap die het nog een stuk zou kunnen verbeteren.

rutgerw schreef op woensdag 16 januari 2019 @ 20:49:
[...]


En WAAR had je die IF dan precies neergezet?

Zo goed als overal ondertussen haha, aan het begin en einde van beide while loops en meerdere plaatsen ertussen in. Ook een functie gevonden in C++ die het doet voor MySQL maar dat is voor de live omgeving helaas geen optie.

[ Voor 5% gewijzigd door Xthemes.us op 16-01-2019 21:00 ]

[Freeaqingme]

Als het om max een paar duizend rows gaat zou ik vooral de manier pakken waarop je het makkelijkste kan developpen. Ik ken je dataset natuurlijk niet, maar mogelijk ben je er al door gewoon alles te selecteren, en dan daar de levenshtein() functie op aanroepen.

Als performance wel een requirement zou zijn, dan ben ik heel benieuwd hoe je hier een effectieve index voor zou opbouwen, en hoe je op mysql uitgekomen bent (itt tot iets als Lucene of het daarop gebaseerde ElasticSearch)

[Kalentum]

Het is toch wel handig als je de code post met de return NULL erin en hoe je die functie dan aanroept. Een return wordt gewoon uitgevoerd door MySQL dus waarschijnlijk gaat je test conditie een beetje vreemd (bv c wordt nooit gelijk aan het einddoel ouzo)

[Xthemes.us]

Iets meer voeten in aarde dan ik dacht maar m.b.v een andere stackoverflow post en een paar aanpassingen en enige trial and error lijkt dit de truuk te doen.

MySQL:

/* levenshtein + damerau algorithm with limiter for MySQL
 * Can test with:
SELECT levenshtein('godzilla', 'gdozilla', 4, TRUE) AS calculated_value, 1 AS expected_value
UNION ALL
SELECT levenshtein('godzilla', 'gdozilla', 4, FALSE) AS calculated_value, 2 AS expected_value

-- Under the limit, expect 3
UNION ALL 
SELECT levenshtein('godzilla', 'gdzla', 4, TRUE) AS calculate_value, 3 AS expected_value

-- Exactly the limit, expect 3
UNION ALL 
SELECT levenshtein('godzilla', 'gdzla', 3, TRUE) AS calculate_value, 3 AS expected_value

-- Just under the limit, expect 3
UNION ALL 
SELECT levenshtein('godzilla', 'gdzla', 2, TRUE) AS calculate_value, null AS expected_value
 */
CREATE FUNCTION levenshtein(s1 VARCHAR(255), s2 VARCHAR(255), l TINYINT, dam BOOLEAN)
RETURNS TINYINT
DETERMINISTIC
BEGIN
    DECLARE s1_len, s2_len, i, j, c, c_min, c_temp, cost INT;
    DECLARE s1_char, s2_char CHAR;
    -- max strlen=255
    DECLARE cv0, cv1, cv2 VARBINARY(256);
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0, c_min = 0;
    IF s1 = s2 THEN
        RETURN 0;
    ELSEIF s1_len = 0 THEN
        RETURN s2_len;
    ELSEIF s2_len = 0 THEN
        RETURN s1_len;
    ELSE
        WHILE j <= s2_len DO
            SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
        END WHILE;
        WHILE i <= s1_len AND c_min < l DO -- Limit reached, stop computing
            SET s1_char = SUBSTRING(s1, i, 1), c = i, c_min = i, cv0 = UNHEX(HEX(i)), j = 1;
            WHILE j <= s2_len DO
                SET c = c + 1;
                SET s2_char = SUBSTRING(s2, j, 1);
                IF s1_char = s2_char THEN
                    SET cost = 0; ELSE SET cost = 1;
                END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
                IF c > c_temp THEN SET c = c_temp; END IF;
                SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
                IF c > c_temp THEN SET c = c_temp; END IF;
                IF c < c_min THEN SET c_min = c; END IF;
                IF dam THEN
                    IF i>1 AND j>1 AND s1_char = SUBSTRING(s2, j-1, 1) AND s2_char = SUBSTRING(s1, i-1, 1) THEN
                        SET c_temp = CONV(HEX(SUBSTRING(cv2, j-1, 1)), 16, 10) + 1;
                        IF c > c_temp THEN SET c = c_temp; END IF;
                    END IF;
                END IF;
                SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
            END WHILE;
            IF dam THEN SET CV2 = CV1; END IF;
            SET cv1 = cv0, i = i + 1;
        END WHILE;
    END IF;
    IF i < s1_len THEN -- Limit exceeded - null it is    
      return null;
    END IF;
    RETURN c;
END

edit:
En de benodigde tijd voor de uiteindelijk query is nu ~0.35s i.p.v. ~0.5s.