Alpha DevCon 2018
Results 1 to 2 of 2

Thread: Levenshtein Distance

  1. #1
    Member
    Real Name
    Sparticuz
    Join Date
    Jun 2009
    Location
    Clearwater, FL
    Posts
    499

    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.
    from https://en.wikipedia.org/wiki/Levenshtein_distance

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

    Code:
    FUNCTION LevenshteinDistance AS N (string_1 AS C, string_2 AS C )
        
        ' Degenerate Cases
        if strequal(string_1,string_2) then
            LevenshteinDistance = 0
            end
        end if
        if len(string_1) == 0 then
            LevenshteinDistance = len(string_2)
            end
        end if
        if len(string_2) == 0 then
            LevenshteinDistance = len(string_1)
            end
        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
        next
        
        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
                else
                    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
        
    END FUNCTION
    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
    Location
    New Orleans, LA
    Posts
    1,871

    Default Re: Levenshtein Distance

    I prefer taxicab geometry - because no matter what it will take me forever to figure out complex math...in it's simplest form
    NWCOPRO Nuisance Wildlife Control Software-My Application: http://www.nwcopro.com "I am not discouraged, because every wrong attempt discarded is another step forward."

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

Bookmarks

Posting Permissions

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