' Edit distance: Levenshtein, Hamming, Jaccard similarity
#COMPILE EXE
#DIM ALL

FUNCTION LevenshteinDistance(BYVAL s AS STRING, BYVAL t AS STRING) AS LONG
    LOCAL n  AS LONG
    LOCAL m  AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL cost  AS LONG
    LOCAL above  AS LONG
    LOCAL left  AS LONG
    LOCAL diag  AS LONG
    LOCAL result  AS LONG
    n = LEN(s)
    m = LEN(t)
    IF n = 0 THEN FUNCTION = m: EXIT FUNCTION
    IF m = 0 THEN FUNCTION = n: EXIT FUNCTION
    DIM prev(0 TO 100)
    DIM curr(0 TO 100)
    FOR j = 0 TO m
        prev(j) = j
    NEXT j
    FOR i = 1 TO n
        curr(0) = i
        FOR j = 1 TO m
            IF MID$(s, i, 1) = MID$(t, j, 1) THEN cost = 0 ELSE cost = 1
            above = curr(j - 1) + 1
            left = prev(j) + 1
            diag = prev(j - 1) + cost
            curr(j) = above
            IF left < curr(j) THEN curr(j) = left
            IF diag < curr(j) THEN curr(j) = diag
        NEXT j
        FOR j = 0 TO m
            prev(j) = curr(j)
        NEXT j
    NEXT i
    FUNCTION = prev(m)
END FUNCTION

FUNCTION HammingDistance(BYVAL s AS STRING, BYVAL t AS STRING) AS LONG
    LOCAL i  AS LONG
    LOCAL dist  AS LONG
    IF LEN(s) <> LEN(t) THEN FUNCTION = -1: EXIT FUNCTION
    dist = 0
    FOR i = 1 TO LEN(s)
        IF MID$(s, i, 1) <> MID$(t, i, 1) THEN dist = dist + 1
    NEXT i
    FUNCTION = dist
END FUNCTION

FUNCTION JaccardSimilarity(BYVAL s AS STRING, BYVAL t AS STRING) AS DOUBLE
    LOCAL i  AS LONG
    LOCAL inter  AS LONG
    LOCAL uni  AS LONG
    LOCAL inS  AS STRING
    LOCAL inT  AS STRING
    LOCAL ch  AS STRING
    inter = 0
    uni = 0
    FOR i = 1 TO LEN(s)
        ch = MID$(s, i, 1)
        IF INSTR(inS, ch) = 0 THEN
            inS = inS + ch
            IF INSTR(t, ch) > 0 THEN inter = inter + 1
            uni = uni + 1
        END IF
    NEXT i
    FOR i = 1 TO LEN(t)
        ch = MID$(t, i, 1)
        IF INSTR(inT, ch) = 0 THEN
            inT = inT + ch
            IF INSTR(inS, ch) = 0 THEN uni = uni + 1
        END IF
    NEXT i
    IF uni = 0 THEN FUNCTION = 1.0: EXIT FUNCTION
    FUNCTION = inter / uni
END FUNCTION

FUNCTION PBMAIN() AS LONG
    LOCAL s1  AS STRING
    LOCAL s2  AS STRING
    PRINT "=== Edit Distance ==="
    PRINT
    s1 = "kitten"
    s2 = "sitting"
    PRINT "s1: " + s1 + "  s2: " + s2
    PRINT "Levenshtein: " + FORMAT$(LevenshteinDistance(s1, s2))
    PRINT
    s1 = "ABCBDAB"
    s2 = "BDCABA"
    PRINT "s1: " + s1 + "  s2: " + s2
    PRINT "Levenshtein: " + FORMAT$(LevenshteinDistance(s1, s2))
    PRINT
    PRINT "Hamming(""ABCDEF"",""ABCXEF""): " + FORMAT$(HammingDistance("ABCDEF", "ABCXEF"))
    PRINT "Hamming equal: " + FORMAT$(HammingDistance("hello", "hello"))
    PRINT "Hamming unequal: " + FORMAT$(HammingDistance("abc", "abcd"))
    PRINT
    PRINT "Jaccard apple/applet: " + FORMAT$(JaccardSimilarity("apple", "applet") * 100, "##0.0") + "%"
    PRINT
    PRINT "Edit distance tests complete."
    FUNCTION = 0
END FUNCTION
