我正在使用大型企业数据库。
我希望能够比较两个企业名称的相似性，看看它们是否可能是重复的。
以下是应测试为很可能重复的企业名称列表，有什么好的方法可以解决这个问题？
乔治华盛顿中学 乔治华盛顿学校 圣达菲东公司 圣达菲东 Chop't 创意沙拉公司 Chop't创意沙拉公司 曼尼和奥尔加的披萨 曼尼和奥尔加的披萨 雷的地狱汉堡太 雷的地狱汉堡 埃尔索尔 索尔德美洲 奥尔尼剧院艺术中心 奥尔尼剧院 21 M 休息室 21M 休息室 华盛顿假日酒店 华盛顿乔治敦假日酒店 华盛顿特区/杜邦环岛原住客栈 杜邦环岛万豪居家酒店 吉米约翰的美食三明治 吉米约翰的 华盛顿特区奥尼肖勒姆酒店 欧尼肖勒姆酒店
我最近完成了一项类似的任务，尽管我正在将新数据与数据库中的现有名称进行匹配，而不是在一组中查找重复项。名称匹配实际上是一项经过充分研究的任务，其中有许多因素超出了您在匹配通用字符串时所考虑的范围。
首先，我建议看一下Raffo 和 Lhuillery的论文，如何玩“名字游戏”：专利检索比较不同的启发式方法。已发布的版本在此处，PDF 可在此处免费获得。作者提供了一个很好的总结，比较了许多不同的匹配策略。他们考虑了三个阶段，他们称之为解析、匹配和过滤。
解析包括应用各种清洁技术。一些例子：
在我的例子中，我将所有字母折叠成小写，用空格替换所有标点符号，用不带重音的对应字符替换重音字符，删除所有其他特殊字符，并从列表后面的名称的开头和结尾删除合法控制术语。
匹配是解析名称的比较。这可以是简单的字符串匹配、编辑距离、Soundex 或 Metaphone、组成名称的单词集的比较，或字母集或n元组（长度为n的字母序列）的比较。n -gram 方法实际上对名称非常好，因为它忽略了词序，对“示例部门”与“示例部门”之类的事情有很大帮助。事实上，使用像Jaccard 索引这样简单的东西来比较二元组（2 元组，字符对）非常有效。与其他几个建议相比，在名称匹配方面，Levenshtein 距离是较差的方法之一。
在我的例子中，我分两步进行匹配，首先比较解析后的名称是否相等，然后将 Jaccard 索引用于剩余的二元组。我没有实际计算所有名称对的所有 Jaccard 索引值，而是首先对两组给定大小的 Jaccard 索引的最大可能值设置一个界限，并且仅在该上限足够高时才计算 Jaccard 索引可能有用。大多数名称对仍然不同，以至于它们不匹配，但它大大减少了比较的次数。
过滤是使用辅助数据来拒绝来自解析和匹配阶段的误报。一个简单的版本是查看匹配的名称是否对应于不同城市的企业，从而对应不同的企业。该示例可以在匹配之前应用，作为一种预过滤。之后可能会应用更复杂或更耗时的检查。
我没有做太多过滤。我检查了这些国家的公司，看看它们是否相同，就是这样。数据中并没有太多的可能性，一些时间限制排除了对额外数据的任何广泛搜索以增强过滤，并且无论如何计划进行手动检查。
我想为出色的公认答案添加一些示例。在 Python 2.7 中测试。
让我们以这个奇怪的名字为例。
name = "THE | big,- Pharma: LLC" # example of a company name
我们可以从删除法律控制条款开始（这里是 LLC）。为此，有一个很棒的cleanco Python 库，它可以做到这一点：
from cleanco import cleanco
name = cleanco(name).clean_name() # 'THE | big,- Pharma'
删除所有标点符号：
name = name.translate(None, string.punctuation) # 'THE big Pharma'
（对于 unicode 字符串，以下代码可以代替（source，regex）：
import regex
name = regex.sub(ur"[[:punct:]]+", "", name) # u'THE big Pharma'
使用NLTK将名称拆分为标记：
import nltk
tokens = nltk.word_tokenize(name) # ['THE', 'big', 'Pharma']
小写所有标记：
tokens = [t.lower() for t in tokens] # ['the', 'big', 'pharma']
删除停用词。请注意，它可能会导致公司出现问题，例如On Marswill be wrongly match to Mars，因为On是一个停用词。
from nltk.corpus import stopwords
tokens = [t for t in tokens if t not in stopwords.words('english')] # ['big', 'pharma']
我在这里不介绍重音字符和特殊字符（欢迎改进）。
现在，当我们将所有公司名称映射到令牌时，我们想要找到匹配的对。可以说，Jaccard（或 Jaro-Winkler）的相似性在这项任务中优于 Levenstein，但仍然不够好。原因是它没有考虑名称中单词的重要性（就像 TF-IDF 一样）。因此，像“公司”这样的常用词对分数的影响与可能唯一标识公司名称的词一样大。
为了改进这一点，您可以使用这个很棒的系列文章（不是我的）中建议的名称相似性技巧。这是其中的一个代码示例：
# token2frequency is just a word counter of all words in all names
# in the dataset
def sequence_uniqueness(seq, token2frequency):
return sum(1/token2frequency(t)**0.5 for t in seq)
def name_similarity(a, b, token2frequency):
a_tokens = set(a.split())
b_tokens = set(b.split())
a_uniq = sequence_uniqueness(a_tokens)
b_uniq = sequence_uniqueness(b_tokens)
return sequence_uniqueness(a.intersection(b))/(a_uniq * b_uniq) ** 0.5
使用它，您可以匹配相似度超过某个阈值的名称。作为一种更复杂的方法，您还可以获取多个分数（例如，这个唯一性分数，Jaccard 和 Jaro-Winkler）并使用一些标记数据训练一个二元分类模型，如果给定多个分数，它将输出候选对是否匹配。更多信息可以在同一篇博客文章中找到。
您可以使用 Levenshtein 距离，它可用于测量两个序列之间的差异（基本上是编辑距离）。
def levenshtein_distance(a,b):
n, m = len(a), len(b)
if n > m:
# Make sure n <= m, to use O(min(n,m)) space
a,b = b,a
n,m = m,n
current = range(n+1)
for i in range(1,m+1):
previous, current = current, [i]+[0]*n
for j in range(1,n+1):
add, delete = previous[j]+1, current[j-1]+1
change = previous[j-1]
if a[j-1] != b[i-1]:
change = change + 1
current[j] = min(add, delete, change)
return current[n]
if __name__=="__main__":
from sys import argv
print levenshtein_distance(argv[1],argv[2])
有一个很棒的库可以为 python 搜索类似/模糊的字符串：fuzzywuzzy。在提到 Levenshtein 距离测量时，它是一个很好的包装库。在这里如何分析你的名字：
#!/usr/bin/env python
from fuzzywuzzy import fuzz
names = [
("George Washington Middle Schl",
"George Washington School"),
("Santa Fe East Inc",
"Santa Fe East"),
("Chop't Creative Salad Co",
"Chop't Creative Salad Company"),
("Manny and Olga's Pizza",
"Manny's & Olga's Pizza"),
("Ray's Hell Burger Too",
"Ray's Hell Burgers"),
("El Sol",
"El Sol de America"),
("Olney Theatre Center for the Arts",
"Olney Theatre"),
("21 M Lounge",
"21M Lounge"),
("Holiday Inn Hotel Washington",
"Holiday Inn Washington-Georgetown"),
("Residence Inn Washington,DC/Dupont Circle",
"Residence Inn Marriott Dupont Circle"),
("Jimmy John's Gourmet Sandwiches",
"Jimmy John's"),
("Omni Shoreham Hotel at Washington D.C.",
"Omni Shoreham Hotel"),
]
if __name__ == '__main__':
for pair in names:
print "{:>3} :: {}".format(fuzz.partial_ratio(*pair), pair)
>>> 79 :: ('George Washington Middle Schl', 'George Washington School')
>>> 100 :: ('Santa Fe East Inc', 'Santa Fe East')
>>> 100 :: ("Chop't Creative Salad Co", "Chop't Creative Salad Company")
>>> 86 :: ("Manny and Olga's Pizza", "Manny's & Olga's Pizza")
>>> 94 :: ("Ray's Hell Burger Too", "Ray's Hell Burgers")
>>> 100 :: ('El Sol', 'El Sol de America')
>>> 100 :: ('Olney Theatre Center for the Arts', 'Olney Theatre')
>>> 90 :: ('21 M Lounge', '21M Lounge')
>>> 79 :: ('Holiday Inn Hotel Washington', 'Holiday Inn Washington-Georgetown')
>>> 69 :: ('Residence Inn Washington,DC/Dupont Circle', 'Residence Inn Marriott Dupont Circle')
>>> 100 :: ("Jimmy John's Gourmet Sandwiches", "Jimmy John's")
>>> 100 :: ('Omni Shoreham Hotel at Washington D.C.', 'Omni Shoreham Hotel')
解决此类问题的另一种方法可能是Elasticsearch，它也支持模糊搜索。
这是对丹尼斯评论的一点更新。这个答案真的很有帮助，他发布的链接也是如此，但我无法让它们立即工作。在尝试了 Fuzzy Wuzzy 搜索后，我发现这给了我一堆更好的答案。我有很多商家，我只想将它们组合在一起。最终我会有一张桌子，我可以用它来尝试一些机器学习来玩，但现在这需要付出很多努力。
我只需要稍微更新他的代码并添加一个函数来创建 tokens2frequency 字典。原始文章也没有，然后函数没有正确引用它。
import pandas as pd
from collections import Counter
from cleanco import cleanco
import regex
import nltk
from nltk.corpus import stopwords
nltk.download('stopwords')
# token2frequency is just a Counter of all words in all names
# in the dataset
def sequence_uniqueness(seq, token2frequency):
return sum(1/token2frequency[t]**0.5 for t in seq)
def name_similarity(a, b, token2frequency):
a_tokens = set(a)
b_tokens = set(b)
a_uniq = sequence_uniqueness(a, token2frequency)
b_uniq = sequence_uniqueness(b, token2frequency)
if a_uniq==0 or b_uniq == 0:
return 0
else:
return sequence_uniqueness(a_tokens.intersection(b_tokens), token2frequency)/(a_uniq * b_uniq) ** 0.5
def parse_name(name):
name = cleanco(name).clean_name()
#name = name.translate(None, string.punctuation)
name = regex.sub(r"[[:punct:]]+", "", name)
tokens = nltk.word_tokenize(name)
tokens = [t.lower() for t in tokens]
tokens = [t for t in tokens if t not in stopwords.words('english')]
return tokens
def build_token2frequency(names):
alltokens = []
for tokens in names.values():
alltokens += tokens
return Counter(alltokens)
with open('marchants.json') as merchantfile:
merchants = pd.read_json(merchantfile)
merchants = merchants.unique()
parsed_names = {merchant:parse_name(merchant) for merchant in merchants}
token2frequency = build_token2frequency(parsed_names)
grouping = {}
for merchant, tokens in parsed_names.items():
grouping[merchant] = {merchant2: name_similarity(tokens, tokens2, token2frequency) for merchant2, tokens2 in parsed_names.items()}
filtered_matches = {}
for merchant in pcard_merchants:
filtered_matches[merchant] = {merchant1: ratio for merchant1, ratio in grouping[merchant].items() if ratio >0.3 }
这将为您提供最终过滤的名称列表以及它们匹配的其他名称。它与其他帖子的基本代码相同，只是填充了一些缺失的部分。这也在 Python 3.8 中运行
我搜索了“python 编辑距离”，这个库是第一个结果： http: //www.mindrot.org/projects/py-editdist/
另一个做同样工作的 Python 库在这里： http: //pypi.python.org/pypi/python-Levenshtein/
编辑距离表示您只需遵循简单的（通常是基于字符的）编辑操作将一个字符串转换为另一个字符串所需执行的工作量。每个操作（替换、删除、插入；有时是转置）都有相关的成本，两个字符串之间的最小编辑距离是衡量这两个字符串的不同程度的指标。
在您的特定情况下，您可能希望对字符串进行排序，以便找到从较长到较短的距离并减少对字符删除的惩罚（因为我看到在许多情况下，其中一个字符串几乎是另一个字符串的子字符串） . 所以删除不应该受到很多惩罚。
您还可以使用此示例代码： http: //norvig.com/spell-correct.html
考虑使用Diff-Match-Patch 库。您会对 Diff 过程感兴趣 - 在您的文本上应用差异可以让您很好地了解差异以及它们的编程表示。
你可以做的是用空格、逗号等分隔单词，然后你计算它与另一个名字共有的单词数量，然后在它被认为是“相似”之前添加一些 thresold 单词。
另一种方法是做同样的事情，但取单词并为每个字符拼接它们。然后对于每个单词，如果字母以相同的顺序（从两侧）找到 x 个字符（或百分比），那么您可以说这个词也相似。
例如：你有 sqre 和 square
然后你按字符检查，发现sqre都是正方形，顺序相同，那么它是一个相似的词。
基于 Levenshtein 距离的算法很好（不完美），但它们的主要缺点是每次比较都非常慢，而且您必须比较每个可能的组合。
解决问题的另一种方法是，使用嵌入或词袋将每个公司名称（经过一些清理和预处理）转换为数字向量。之后，您根据可用的方法应用无监督或有监督的 ML 方法。
我创建了 matchkraft ( https://github.com/MatchKraft/matchkraft-python )。它在fuzzy-wuzzy 之上工作，您可以在一个列表中模糊匹配公司名称。
这是非常容易使用。这是python中的一个例子：
from matchkraft import MatchKraft
mk = MatchKraft('<YOUR API TOKEN HERE>')
job_id = mk.highlight_duplicates(name='Stackoverflow Job',
primary_list=[
'George Washington Middle Schl',
'George Washington School',
'Santa Fe East Inc',
'Santa Fe East',
'Rays Hell Burger Too',
'El Sol de America',
'microsoft',
'Olney Theatre',
'El Sol'
]
)
print (job_id)
mk.execute_job(job_id=job_id)
job = mk.get_job_information(job_id=job_id)
print (job.status)
while (job.status!='Completed'):
print (job.status)
time.sleep(10)
job = mk.get_job_information(job_id=job_id)
results = mk.get_results_information(job_id=job_id)
if isinstance(results, list):
for r in results:
print(r.master_record + ' --> ' + r.match_record)
else:
print("No Results Found")