CODEWITHSUNDEEP
python
ExploreData
ExploreData

Reputation: 37

Levenshtein Distance implementation

I am trying to use my Levenshtein algorithm to take one string and compare it to multiple strings in a list or column. The idea is to identify if similar address appear multiple times through out the day. So I would want to pick one address and then run my Levenshtein across multiple strings for the one address. In theory I would rinse and repeat with a different target address.

I've built out a working Levenshtein Model, but am now trying to get it toward my unique situation

import numpy as np
# Define a function that will become the fuzzy match
# I decided to use Levenshtein Distance due to the formulas ability to handle string comparisons of two unique lengths
def string_match(seq1, seq2, ratio_calc = False):
    """ levenshtein_ratio_and_distance:
        Calculates levenshtein distance between two strings.
        If ratio_calc = True, the function computes the
        levenshtein distance ratio of similarity between two strings
        For all i and j, distance[i,j] will contain the Levenshtein
        distance between the first i characters of seq1 and the
        first j characters of seq2
    """
    # Initialize matrix of zeros
    rows = len(seq1)+1
    cols = len(seq2)+1
    distance = np.zeros((rows,cols),dtype = int)

    # Populate matrix of zeros with the indeces of each character of both strings
    for i in range(1, rows):
        for k in range(1,cols):
            distance[i][0] = i
            distance[0][k] = k

    # loop through the matrix to compute the cost of deletions,insertions and/or substitutions    
    for col in range(1, cols):
        for row in range(1, rows):
            if seq1[row-1] == seq2[col-1]:
                cost = 0 # If the characters are the same in the two strings in a given position [i,j] then the cost is 0
            else:
                # In order to align the results with those of the Python Levenshtein package, if we choose to calculate the ratio
                # the cost of a substitution is 2. If we calculate just distance, then the cost of a substitution is 1.
                if ratio_calc == True:
                    cost = 2
                else:
                    cost = 1
            distance[row][col] = min(distance[row-1][col] + 1,      # Cost of deletions
                                 distance[row][col-1] + 1,          # Cost of insertions
                                 distance[row-1][col-1] + cost)     # Cost of substitutions
    if ratio_calc == True:
        # Computation of the Levenshtein Distance Ratio
        Ratio = round(((len(seq1)+len(seq2)) - distance[row][col]) / (len(seq1)+len(seq2)) * 100, 2)
        return "The similarity ratio is {}%".format(Ratio)
    else:
        # print(distance) # Uncomment if you want to see the matrix showing how the algorithm computes the cost of deletions,
        # insertions and/or substitutions
        # This is the minimum number of edits needed to convert seq1 to seq2
        return "The strings are {} edits away".format(distance[row][col]) ```


    seq1 = "8847 N Main St"
    seq2 = "9763 Peachtree blvd"
    Distance = string_match(seq1, seq2)
    ratio = string_match(seq1, seq2, ratio_calc = True)enter code here
    print(Distance)
    print(ratio)
    #Results: the strings are 17 edits away
              The similarity ratio is 24.24%

Upvotes: 0

Views: 1058

Answers (1)

J_H
J_H

Reputation: 20568

Looks like you simply want to loop over them:

prev_addrs = [
    "8847 N Main St",
    "9763 Peachtree blvd",
]
target_addr = '10 Main St.'
for addr in prev_addrs:
    distance = string_match(target_addr, addr)
    # do something with distance...

BTW, you might find it convenient to return a numeric result rather than a string, since you'll likely want to compute max( ... ) or compare to threshold or similar.

And do consider pip installing the package, https://github.com/ztane/python-Levenshtein/wiki, since a C extension will have a speed advantage over python loops.

Upvotes: 1

Related Questions