python - 字符串匹配 - 使用的最佳距离算法

Question

我有两个数据框，df1并且df2，其中包含有关投票站的信息。数据帧具有不同的长度。两个数据框都有一个名为 的列ps_name，这是投票站的名称，还有一个名为 的列district，表示投票站位于哪个区。

我试图在ps_name列上阻塞的同时匹配列上的字符串，因此我可以将匹配项上的（纬度和经度）列从district复制到。geolocationsdf1df2

到目前为止，我已经尝试在阈值处使用jaro-winkler0.88来比较字符串。

# Matched:
**df1:** AGRICULTURAL OFFICE ATTOCK (MALE) I (P)
**df2:** AGRICULTURAL OFFICE ATTOCK (MALE) (P)

# Did not match:
**df1:** govt girls high school peoples colony attock ii
**df2:** high school peoples colony attock ii

我应该使用什么字符串距离算法？我试过jaro-winkler并且也在考虑smith-waterman。

Answer 1

一种选择是使用在fuzzywuzzy（或此处）包中实现的Levenshtein距离，该算法在O（n + d^2）中运行，其中n是较长字符串的长度，d是编辑距离。

例子：

from fuzzywuzzy import fuzz
fuzz.ratio('govt girls high school peoples colony attock ii','high school peoples colony attock ii') 
#87
fuzz.ratio('AGRICULTURAL OFFICE ATTOCK (MALE) I (P)', 'AGRICULTURAL OFFICE ATTOCK (MALE) (P)')
#97