确定一个企业名称是否与另一个名称非常相似 - Python

Question

我正在处理一个大型的企业数据库。

我想比较两个企业名称的相似度，以查看它们是否可能是重复的。

以下是一些企业名称列表，应该测试出具有高重复概率的名称，如何进行比较呢？

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

- Chris Dutrow

---

http://en.wikipedia.org/wiki/Levenshtein_distance - Mitch Wheat

这与App Engine有什么关系？ - Wooble

请查看此链接：https://github.com/Cheukting/fuzzy-match-company-name/blob/master/Fuzzy-match-company-names.ipynb - Saurabh Gokhale

Answer 1

我最近完成了一项类似的任务, 尽管我是在将新数据与数据库中现有名称进行匹配，而不是在一个集合内查找重复项。名称匹配实际上是一个经过深入研究的任务，除了匹配通用字符串外，还考虑了许多因素。

首先，我建议参考一篇论文，"How to play the “Names Game”: Patent retrieval comparing different heuristics", 作者是Raffo和Lhuillery。发表版可在这里找到，PDF版本可在这里免费获取。作者提供了一个很好的摘要，比较了许多不同的匹配策略。他们考虑了三个阶段，称为解析、匹配和过滤。

解析包括应用各种清理技术。一些例子:

• 标准化字母大小写(例如，全部小写)
• 标准化标点符号(例如，逗号必须跟随空格)
• 标准化空格(例如，将所有连续的空格转换为单个空格)
• 标准化重音和特殊字符(例如，将重音字母转换为ASCII等效项)
• 标准化法律控制术语(例如，将“Co.” 转换为“Company”)

在我的情况下, 我将所有字母都转换为小写, 用空格替换所有标点符号, 用非变音的字符替换变音字符, 去除所有其他特殊字符，并在一个列表后删除名称开头和结尾的法律控制术语。

匹配是对解析后的名称进行比较。这可以是简单的字符串匹配、编辑距离、Soundex或Metaphone，也可以是对组成名称的单词集合或字母集合进行比较，或者对长度为n的字母序列（n-grams）的集合进行比较。实际上，采用n-gram方法进行名称匹配非常好，因为它忽略了单词顺序，对于像“examples department”和“department of examples”这样的情况有很大帮助。事实上，使用一些简单的东西，如Jaccard指数比较双字节字符（2-grams, character pairs）是非常有效的。与其他一些建议相比，当涉及到名称匹配时，Levenshtein距离是较差的方法之一。

在我的情况下，我分两步进行匹配，首先通过比较解析后的名称是否相等来进行匹配，然后使用Jaccard指数对其余的双字节字符集合进行匹配。与其实际计算所有名称对之间的Jaccard指数值相比，我首先限制了给定大小的两个集合的Jaccard指数的最大可能值，并且仅在上限足够高以潜在地对匹配有用时才计算Jaccard指数。大多数名称对仍然不相似，它们不是匹配项，但它显著减少了所做的比较数量。

过滤是使用辅助数据从解析和匹配阶段拒绝错误的正例。简单版本可以看是否匹配的名称对应于不同城市中的企业，因此为不同企业。该示例可以在匹配之前作为一种预过滤应用。更复杂或耗时的检查可以在之后应用。

我没有进行太多的过滤。我检查了公司所在的国家是否相同，就这样了。在数据中实际上没有太多可能性，一些时间限制排除了对附加过滤数据进行广泛搜索的可能性，而且还计划进行手动检查。

- Michael J. Barber

---

Cleanco是一个很好的库，可用于从公司名称中删除组织类型术语（如LLC、Inc.、Corp.）。 - Renato Byrro

Answer 2

解析

让我们以这个奇怪的名字作为例子。

我想在这个优秀的被接受答案上添加一些例子。在Python 2.7中测试。

name = "THE |  big,- Pharma: LLC"  # example of a company name

我们可以从删除法律控制术语开始（这里是LLC）。为了做到这一点，有一个非常棒的Python库cleanco，它能够准确实现此功能。

from cleanco import cleanco
name = cleanco(name).clean_name()  # 'THE | big,- Pharma'

去掉所有标点符号：

name = name.translate(None, string.punctuation)  # 'THE  big Pharma'

< p >（对于Unicode字符串，可以使用以下代码代替（源自此处，正则表达式库）：

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 Mars这样的公司被错误地匹配为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），并使用一些标记数据来训练一个二元分类模型，该模型将在给定一组分数的情况下输出候选人对是否匹配。有关此内容的更多信息可以在同一篇博客文章中找到。

- Dennis Golomazov

---

Unicode字符可以通过将它们转换为ASCII中的类似字符来处理，例如unidecode.unidecode(name)。 - rinspy

Answer 3

有一个很棒的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，它也支持模糊搜索。

- grundic

---

太棒了，答案非常出色，简直就像魔法一样有效！非常感谢你的帮助！ - undefined

Answer 4

你可以使用Levenshtein距离来衡量两个序列之间的差异（基本上是编辑距离）。

Python中的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])

- Neal

Answer 5

这是对丹尼斯评论的更新。他提供的答案和链接非常有帮助，但我一开始无法正确使用它们。在尝试了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中运行。

- jmatthew007

Answer 6

我搜索了“python编辑距离”，这个库是第一个结果：http://www.mindrot.org/projects/py-editdist/

另一个做同样工作的Python库在这里：http://pypi.python.org/pypi/python-Levenshtein/

编辑距离表示您需要执行的工作量，通过仅遵循简单的（通常是基于字符的）编辑操作将一个字符串转换为另一个字符串。每个操作（替换、删除、插入；有时是交换）都有一个相关成本，两个字符串之间的最小编辑距离是它们有多不相似的度量。

在您的特定情况下，您可能希望对字符串进行排序，以便从较长的字符串到较短的字符串，并且惩罚字符删除较少（因为我看到在许多情况下，其中一个字符串几乎是另一个字符串的子字符串）。因此，删除不应受到很大惩罚。

你可以使用这个示例代码：http://norvig.com/spell-correct.html

- Ruggiero Spearman

Answer 7

考虑使用Diff-Match-Patch库。你会对Diff过程感兴趣——在文本上应用差异可以给你一个很好的区别概念，以及它们的编程表示形式。

- Sudhir Jonathan

Answer 8

你可以通过空格、逗号等方式将单词分开，然后计算它与另一个名称有多少个共同单词，并在达到一定数量的阈值之前将其视为“相似”。

另一种方法是做同样的事情，但是将单词拆分为每个字符。然后对于每个单词，您需要比较是否按相同顺序（从两侧）找到了x个字符（或百分比），然后可以说该单词也是相似的。

例如：您有sqre和square 然后您通过字符检查并发现sqre都在square中且顺序相同，则它是一个相似的单词。

- maaudet

Answer 9

基于莱文斯坦距离的算法是好的（但不完美），但它们的主要缺点是每次比较非常慢，考虑到您需要比较每个可能的组合。

另一种解决问题的方法是使用嵌入或词袋模型将每个公司名称（经过清理和预处理）转换为数字向量。然后根据可用的情况应用无监督或监督机器学习方法。

- George Sotiropoulos

Answer 10

我创建了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")
 

- user3643160

---

这个问题已经有了解决方案，请考虑留下评论，以便在一个非常老的问题上添加一些内容。 - Alessandro