New call-to-action
Results 1 to 2 of 2

Thread: Levenshtein Distance

  1. #1
    Real Name
    Join Date
    Jun 2009
    Clearwater, FL

    Default Levenshtein Distance

    Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.

    The following is based on the pseudocode for the 'Iterative with two matrix rows' version

    FUNCTION LevenshteinDistance AS N (string_1 AS C, string_2 AS C )
        ' Degenerate Cases
        if strequal(string_1,string_2) then
            LevenshteinDistance = 0
        end if
        if len(string_1) == 0 then
            LevenshteinDistance = len(string_2)
        end if
        if len(string_2) == 0 then
            LevenshteinDistance = len(string_1)
        end if
        dim v0[0..len(string_2)+1] as n
        dim v1[0..len(string_2)+1] as n
        'initialize v0 (the previous row of distances)
        'this row is A[0][i]: edit distance for an empty string_1
        'the distance is just the number of characters to delete from string_2
        for i = 0 to v0.size()-1
            v0[i] = i
        for i = 0 to len(string_1)
            'calculate v1 (current row distances) from the previous row v0
            'first element of v1 is A[i+1][0]
            'edit distance is delete (i+1) chars from string_1 to match empty string_2
            v1[0] = i + 1
            'use formula to fill in the rest of the row
            for j = 0 to len(string_2)
                if substr(string_1,i,1) == substr(string_2,j,1) then
                    dim cost as n = 0
                    dim cost as n = 1
                end if
                dim minList as c
                minList = alltrim(str(v1[j]+1)) + crlf() + alltrim(str(v0[j+1]+1)) + crlf() + alltrim(str(v0[j]+cost))
                v1[j+1] = *min(minList)
            next j
            'copy v1 (current row) to v0 (previous row) for next iteration
            for j = 0 to v0.size()-1
                v0[j] = v1[j];
            next j
        next i
        LevenshteinDistance = v1[len(string_2)]+1
    Last edited by Sparticuz; 06-14-2016 at 01:26 PM.

  2. #2
    "Certified" Alphaholic CharlesParker's Avatar
    Real Name
    Charles Parker
    Join Date
    Dec 2012
    New Orleans, LA

    Default Re: Levenshtein Distance

    I prefer taxicab geometry - because no matter what it will take me forever to figure out complex it's simplest form
    NWCOPRO: Nuisance Wildlife Control Software My Application: "Without forgetting, we would have no memory at what was I saying?"

Similar Threads

  1. Distance calculation function
    By Bill Parker in forum Alpha Five Version 11 - Desktop Applications
    Replies: 9
    Last Post: 03-28-2012, 08:40 AM
  2. Would like to search by distance
    By Marilyn Wallace in forum Alpha Five Version 6
    Replies: 2
    Last Post: 10-03-2005, 04:57 PM
  3. Zipcode & distance
    By richarddsmith in forum Alpha Five Version 5
    Replies: 17
    Last Post: 07-13-2003, 09:11 AM
  4. Vertical distance
    By Janet Seber in forum Alpha Five Version 5
    Replies: 2
    Last Post: 02-12-2003, 09:35 AM
  5. Zip Code distance finder
    By John Magno in forum Alpha Five Version 5
    Replies: 1
    Last Post: 11-22-2002, 08:38 AM


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts