列文施泰因距离实现

Question

我正在尝试使用我的Levenshtein算法来获取一个字符串并将其与列表或列中的多个字符串进行比较。这个想法是确定类似的地址是否在一天中多次出现。所以我想选择一个地址，然后在多个字符串中为一个地址运行我的 Levenshtein。理论上，我会冲洗并使用不同的目标地址重复。

我已经建立了一个有效的Levenshtein模型，但现在正试图让它达到我的独特情况

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%

Answer 1

看起来你只是想循环它们：

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...

顺便说一句，您可能会发现返回数字结果而不是字符串很方便，因为您可能希望计算max( ... )或与阈值或类似值进行比较。

并考虑pip安装软件包，https://github.com/ztane/python-Levenshtein/wiki，因为 C 扩展将比 python 循环具有速度优势。