精华内容
下载资源
问答
  • 本文将从字符串模糊匹配的角度介绍一下搜索引擎。一般的搜索,要分为两个步骤:搜索和排序。搜索的方法有很多,为了高效一般进行字符串或关键词匹配,而用户提供的一些关键词可能不是数据库中保存的,例如使用倒...

    之前笔者写过一篇文章关于如何做搜索,但那篇文章的角度是从文本相似度角度写的。那种方式是目前发展的趋势,但是真正的搜索特别是网页搜索不可能在大范围的文本之间两两算相似度的。那样搜索引擎的效率会变得特别低下。本文将从字符串模糊匹配的角度介绍一下搜索引擎。

    一般的搜索,要分为两个步骤:搜索和排序。搜索的方法有很多,为了高效一般进行字符串或关键词匹配,而用户提供的一些关键词可能不是数据库中保存的,例如使用倒排的方法很难找到Head节点,此处需要使用模糊匹配的方式。这里简单列举一下Learning-to-Rank排序的方法:BM25算法、TF-IDF算相似度、SVD奇异值分解(主题模型)得到向量表示算相似度、再就是之前介绍的文本相似度计算的方法。如果是网页的排序,可能会涉及到网址质量好坏需要使用PageRank排序算法等。

    本文主要从模糊匹配的角度,简单介绍下搜索。主要解决的问题类似,“刘得华演过的电影”与“刘德华演过的电影”表示的是同一个意思。

    1. 编辑距离

    首先给大家介绍一下编辑距离,编辑距离就是用于衡量两个字符串之间的差异。具体描述为:string1通过多少次最少操作(增添字符、删除字符、替换字符)得到string2,最少操作的次数就定义为编辑距离。例如句子刘得华演过的电影”与“刘德华演过的电影”只需要一次替换“得”为“德”,所以二者之间的距离为1。如果两个字符串S1和S2,长度分别为i,j。那么二者之间的距离D(i,j)可以表示为:

    (1)min(i,j)==0,即S1,S2中存在空字符串

    D(i,j)=max(i,j)

    (2)min(i,j) != 0,

    去掉S1或S2的最后一个字符进行比较,分别得到距离

    D(i,j-1), D(i-1,j),D(i-1,j-1)

    由动态规划的思想可以得到:

    D(i,j) = min{D(i,j-1), D(i-1,j),D(i-1,j-1)+sigma(i,j)} 其中sigma(i,j)取值为0或 1,1表示S1和S2最后一个字符不相同,0表示相同。具体实现如下:

    intLevenshteinDistance(constchar*s,intlen_s,constchar*t,intlen_t){intcost;if(len_s==)returnlen_t;if(len_t==)returnlen_s;if(s[len_s-1]==t[len_t-1])cost=;elsecost=1;returnminimum(LevenshteinDistance(s,len_s-1,t,len_t)+1,LevenshteinDistance(s,len_s,t,len_t-1)+1,LevenshteinDistance(s,len_s-1,t,len_t-1)+cost);}

    2. fuzzywuzzy

    Python提供fuzzywuzzy模块,不仅可用于计算两个字符串之间的相似度,而且还提供排序接口能从大量候选集中找到最相似的句子。

    (1)安装

    需要安装python-Levenshtein库用于计算上述讲解的编辑距离。

    pip install python-Levenshtein

    pip install fuzzywuzzy

    (2)接口说明

    两个模块:fuzz, process,fuzz主要用于两字符串之间匹配,process主要用于搜索排序。

    fuzz.ratio(s1,s2)直接计算s2和s2之间的相似度,返回值为0-100,100表示完全相同;

    fuzz.partial_ratio(S1,S2)部分匹配,如果S1是S2的子串依然返回100;

    fuzz.token_sort_ratio(S1,S2)只比较S1,S2单词是否相同,不考虑词语之间的顺序;

    fuzz.token_set_ratio(S1,S2)相比fuzz.token_sort_ratio不考虑词语出现的次数;

    process.extract(S1, ListS,limit=n),表示从列表ListS中找出Top n与S1最相似的句子;

    process.extractOne(S1,ListS),返回最相似的一个

    (3)使用

    运行结果:

    说明str1和str2之间相似度是对称的。

    展开全文
  • I'm checking if there are similar results (fuzzy match) in 4 same dataframe columns, and I have the following code, as an example. When I apply it to the real 40.000 rows x 4 columns dataset, keeps ru...

    I'm checking if there are similar results (fuzzy match) in 4 same dataframe columns, and I have the following code, as an example. When I apply it to the real 40.000 rows x 4 columns dataset, keeps running in eternum. The issue is that the code is too slow. For example, if I limite the dataset to 10 users, it takes 8 minutes to compute, while for 20, 19 minutes. Is there anything I am missing? I do not know why this take that long. I expect to have all results, maximum in 2 hours or less. Any hint or help would be greatly appreciated.

    from fuzzywuzzy import process

    dataframecolumn = ["apple","tb"]

    compare = ["adfad","apple","asple","tab"]

    Ratios = [process.extract(x,compare) for x in dataframecolumn]

    result = list()

    for ratio in Ratios:

    for match in ratio:

    if match[1] != 100:

    result.append(match)

    break

    print (result)

    Output:

    [('asple', 80), ('tab', 80)]

    解决方案Major speed improvements come by writing vectorized operations and avoiding loops

    Importing necessary package

    from fuzzywuzzy import fuzz

    import pandas as pd

    import numpy as np

    Creating dataframe from first list

    dataframecolumn = pd.DataFrame(["apple","tb"])

    dataframecolumn.columns = ['Match']

    Creating dataframe from second list

    compare = pd.DataFrame(["adfad","apple","asple","tab"])

    compare.columns = ['compare']

    Merge - Cartesian product by introducing key(self join)

    dataframecolumn['Key'] = 1

    compare['Key'] = 1

    combined_dataframe = dataframecolumn.merge(compare,on="Key",how="left")

    combined_dataframe = combined_dataframe[~(combined_dataframe.Match==combined_dataframe.compare)]

    Vectorization

    def partial_match(x,y):

    return(fuzz.ratio(x,y))

    partial_match_vector = np.vectorize(partial_match)

    Using vectorization and getting desired result by putting threshold on score

    combined_dataframe['score']=partial_match_vector(combined_dataframe['Match'],combined_dataframe['compare'])

    combined_dataframe = combined_dataframe[combined_dataframe.score>=80]

    Results

    +--------+-----+--------+------+

    | Match | Key | compare | score

    +--------+-----+--------+------+

    | apple | 1 | asple | 80

    | tb | 1 | tab | 80

    +--------+-----+--------+------+

    展开全文
  • Python字符串模糊匹配库FuzzyWuzzy 在计算机科学中,字符串模糊匹配(fuzzy string matching)是一种近似地(而不是精确地)查找与模式匹配的字符串的技术。换句话说,字符串模糊匹配是一种搜索,即使用户拼错...

    Python字符串模糊匹配库FuzzyWuzzy

    在计算机科学中,字符串模糊匹配(fuzzy string matching)是一种近似地(而不是精确地)查找与模式匹配的字符串的技术。换句话说,字符串模糊匹配是一种搜索,即使用户拼错单词或只输入部分单词进行搜索,也能够找到匹配项。因此,它也被称为字符串近似匹配。

    字符串模糊搜索可用于各种应用程序,例如:

    • 拼写检查和拼写错误纠正程序。例如,用户在Google中键入“Missisaga”,将返回文字为“Showing results for mississauga”的点击列表。也就是说,即使用户输入缺少字符、有多余的字符或者有其他类型的拼写错误,搜索查询也会返回结果。
    • 重复记录检查。例如,由于名称拼写不同(例如Abigail Martin和Abigail Martinez)在数据库中被多次列出。

    这篇文章将解释字符串模糊匹配及其用例,并使用Python中Fuzzywuzzy库给出示例。

    使用FuzzyWuzzy合并酒店房型

    每个酒店都有自己的命名方法来命名它的房间,在线旅行社(OTA)也是如此。例如,同一家酒店的一间客房Expedia将之称为“Studio, 1 King Bed with Sofa Bed, Corner”,Booking.com(缤客)则简单地将其显示为“Corner King Studio”。不能说有谁错了,但是当我们想要比较OTA之间的房价时,或者一个OTA希望确保另一个OTA遵循费率平价协议时(rate parity agreement),这可能会导致混乱。换句话说,为了能够比较价格,我们必须确保我们进行比较的东西是同一类型的。对于价格比较网站和应用程序来说,最令人头条的问题之一就是试图弄清楚两个项目(比如酒店房间)是否是同一事物。

    Fuzzywuzzy是一个Python库,使用编辑距离(Levenshtein Distance)来计算序列之间的差异。为了演示,我创建了自己的数据集,也就是说,对于同一酒店物业,我从Expedia拿一个房间类型,比如说“Suite, 1 King Bed (Parlor)”,然后我将它与Booking.com中的同类型房间匹配,即“King Parlor Suite”。只要有一点经验,大多数人都会知道他们是一样的。按照这种方法,我创建了一个包含100多对房间类型的小数据集,可以访问Github下载

    我们使用这个数据集测试Fuzzywuzzy的做法。换句话说,我们使用Fuzzywuzzy来匹配两个数据源之间的记录。

    import pandas as pd
    df = pd.read_csv('../input/room_type.csv')
    df.head(10)
    import pandas as pd

    df = pd.read_csv(’…/input/room_type.csv’)
    df.head(10)

    import pandas as pd

    df = pd.read_csv(’…/input/room_type.csv’)
    df.head(10)

    有几种方法可以比较Fuzzywuzzy中的两个字符串,让我们一个一个地进行尝试。

    ratio ,按顺序比较整个字符串的相似度

    from fuzzywuzzy import fuzz
    fuzz.ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')
    from fuzzywuzzy import fuzz

    fuzz.ratio(‘Deluxe Room, 1 King Bed’, ‘Deluxe King Room’)

    from fuzzywuzzy import fuzz

    fuzz.ratio(‘Deluxe Room, 1 King Bed’, ‘Deluxe King Room’)

    返回结果时62,它告诉我们“Deluxe Room, 1 King Bed”和“Deluxe King Room”的相似度约62%。

    fuzz.ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds') fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')

    “Traditional Double Room, 2 Double Beds”和“Double Room with Two Double Beds”的相似度约69%。“Room, 2 Double Beds (19th to 25th Floors)”和“Two Double Beds — Location Room (19th to 25th Floors)”相似度约74%。显然效果不怎么样。事实证明,简单的方法对于词序,缺失或多余词语以及其他类似问题的微小差异太过敏感。

    partial_ratio,比较部分字符串的相似度

    我们仍在使用相同的数据对:

    fuzz.partial_ratio('Deluxe Room, 1 King Bed','Deluxe King Room')
    fuzz.partial_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.partial_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.partial_ratio('Deluxe Room, 1 King Bed','Deluxe King Room') fuzz.partial_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds') fuzz.partial_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.partial_ratio('Deluxe Room, 1 King Bed','Deluxe King Room')
    fuzz.partial_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.partial_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')

    返回依次69、83、63。对于我的数据集来说,比较部分字符串并不能带来更好的整体效果。让我们尝试下一个。

    token_sort_ratio,忽略单词顺序

    fuzz.token_sort_ratio('Deluxe Room, 1 King Bed','Deluxe King Room')
    fuzz.token_sort_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.token_sort_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.token_sort_ratio('Deluxe Room, 1 King Bed','Deluxe King Room') fuzz.token_sort_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds') fuzz.token_sort_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.token_sort_ratio('Deluxe Room, 1 King Bed','Deluxe King Room')
    fuzz.token_sort_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.token_sort_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')

    返回依次84、78、83。这是迄今为止最好的。

    token_set_ratio,去重子集匹配

    它与token_sort_ratio类似,但更加灵活。

    fuzz.token_set_ratio('Deluxe Room, 1 King Bed','Deluxe King Room')
    fuzz.token_set_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.token_set_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.token_set_ratio('Deluxe Room, 1 King Bed','Deluxe King Room') fuzz.token_set_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds') fuzz.token_set_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')
    fuzz.token_set_ratio('Deluxe Room, 1 King Bed','Deluxe King Room')
    fuzz.token_set_ratio('Traditional Double Room, 2 Double Beds','Double Room with Two Double Beds')
    fuzz.token_set_ratio('Room, 2 Double Beds (19th to 25th Floors)','Two Double Beds - Location Room (19th to 25th Floors)')

    返回依次100、78、97。看来token_set_ratio最适合我的数据。根据这一发现,将token_set_ratio应用到整个数据集。

    def get_ratio(row):
    name1 = row['Expedia']
    name2 = row['Booking.com']
    return fuzz.token_set_ratio(name1, name2)
    rated = df.apply(get_ratio, axis=1)
    rated.head(10)
    greater_than_70_percent = df[rated > 70]
    greater_than_70_percent.count()
    len(greater_than_70_percent) / len(df)
    def get_ratio(row): name1 = row['Expedia'] name2 = row['Booking.com'] return fuzz.token_set_ratio(name1, name2)

    rated = df.apply(get_ratio, axis=1)
    rated.head(10)

    greater_than_70_percent = df[rated > 70]
    greater_than_70_percent.count()
    len(greater_than_70_percent) / len(df)

    def get_ratio(row):
    name1 = row[‘Expedia’]
    name2 = row[‘Booking.com’]
    return fuzz.token_set_ratio(name1, name2)

    rated = df.apply(get_ratio, axis=1)
    rated.head(10)

    greater_than_70_percent = df[rated > 70]
    greater_than_70_percent.count()
    len(greater_than_70_percent) / len(df)

    当设定相似度> 70时,超过90%的房间对超过这个匹配分数。还很不错!上面只是做了2个文本间的相似度比较,如果存在多个如何处理?可以使用库中提供的 Process类:

    用来返回模糊匹配的字符串和相似度。

    >>> choices = ["Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"]
    >>> process.extract("new york jets", choices, limit=2)
    [('New York Jets', 100), ('New York Giants', 78)]
    >>> process.extractOne("cowboys", choices)
    ("Dallas Cowboys", 90)
    >>> choices = ["Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"] >>> process.extract("new york jets", choices, limit=2) [('New York Jets', 100), ('New York Giants', 78)] >>> process.extractOne("cowboys", choices) ("Dallas Cowboys", 90)
    >>> choices = ["Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"]
        >>> process.extract("new york jets", choices, limit=2)
            [('New York Jets', 100), ('New York Giants', 78)]
        >>> process.extractOne("cowboys", choices)
            ("Dallas Cowboys", 90)
    

    FuzzyWuzzy在中文场景下的使用

    FuzzyWuzzy支持对中文进行比较:

    from fuzzywuzzy import fuzz
    from fuzzywuzzy import process
    print(fuzz.ratio("数据挖掘", "数据挖掘工程师"))
    title_list = ["数据分析师", "数据挖掘工程师", "大数据开发工程师", "机器学习工程师",
    "算法工程师", "数据库管理", "商业分析师", "数据科学家", "首席数据官",
    "数据产品经理", "数据运营", "大数据架构师"]
    print(process.extractOne("数据挖掘", title_list))
    from fuzzywuzzy import fuzz from fuzzywuzzy import process

    print(fuzz.ratio(“数据挖掘”, “数据挖掘工程师”))

    title_list = [“数据分析师”, “数据挖掘工程师”, “大数据开发工程师”, “机器学习工程师”,
    “算法工程师”, “数据库管理”, “商业分析师”, “数据科学家”, “首席数据官”,
    “数据产品经理”, “数据运营”, “大数据架构师”]

    print(process.extractOne(“数据挖掘”, title_list))

    from fuzzywuzzy import fuzz
    from fuzzywuzzy import process

    print(fuzz.ratio(“数据挖掘”, “数据挖掘工程师”))

    title_list = [“数据分析师”, “数据挖掘工程师”, “大数据开发工程师”, “机器学习工程师”,
    “算法工程师”, “数据库管理”, “商业分析师”, “数据科学家”, “首席数据官”,
    “数据产品经理”, “数据运营”, “大数据架构师”]

    print(process.extractOne(“数据挖掘”, title_list))

    仔细查看代码,还是存在的问题:

    • FuzzWuzzy并不会针对中文进行分词
    • 也没有对中文的一些停用词进行过滤

    改进方案,处理前进行中文处理:

    • 繁简转换
    • 中文分词
    • 去除停用词

    参考链接:

    展开全文
  • 使用Levenshtein距离的Python和C ++快速模糊字符串匹配 ••• 描述 RapidFuzz是适用于Python和C ++的快速字符串匹配库,它使用的字符串相似度计算。 但是,有两个方面使RapidFuzz与FuzzyWuzzy脱颖而出: 它已...
  • 使用Levenshtein距离说明在Python和C ++中进行快速模糊字符串匹配•安装•使用•许可证说明RapidFuzz是一个快速字符串匹配库,用于使用Levenshtein距离说明在Python和C ++中进行快速模糊字符串匹配•安装•使用•...
  • stuList = [ (‘201758709’,‘官方’,‘男’), (‘201750743’,‘公会’,‘男’), (‘201752322’,‘愚人节’,‘男’)] ... 谁知道这个要怎么做才能实现模糊字符串匹配,例如输入官字,就会输出官方,求大神帮忙啊!

    stuList = [
    (‘201758709’,‘官方’,‘男’),
    (‘201750743’,‘公会’,‘男’),
    (‘201752322’,‘愚人节’,‘男’)]

    class Student():

    def __init__(self,xh):
    
        self.xh = xh;
    
        for s in stuList:
            if s[0] == xh:
                self.xm = s[1]
                self.xb = s[2]
    
                self.myTuple = s;
    
                break;
    
    @classmethod
    def findByName(cls,xm):
        resList = []
        for a in stuList:
            if a[1]xxxx:
                resList.append(a);
    
        return resList;
    

    !
    谁知道这个要怎么做才能实现模糊的字符串匹配,例如输入官字,就会输出官方,求大神帮忙啊!

    展开全文
  • fuzzywuzzy:Python中的字符串模糊匹配
  • 要求Python 2.7或更高版本difflib python-Leven FuzzyWuzzy模糊字符串匹配,像老板。 它使用Levenshtein距离来计算简单易用的程序包中序列之间的差异。 要求Python 2.7或更高版本difflib python-Levenshtein(可选,...
  • python 字符串模糊匹配 Fuzzywuzzy

    千次阅读 2019-05-17 20:37:14
    Python提供fuzzywuzzy模块,不仅可用于计算两个字符串之间的相似度,而且还提供排序接口能从大量候选集中找到最相似的句子。 (1)安装 pip install fuzzywuzzy (2)接口说明 两个模块:fuzz, process,fuzz主要...
  • github主页 导入: >>> from fuzzywuzzy import fuzz >>> from fuzzywuzzy import process 1) >>> fuzz.ratio(this is a test, ...fuzz.partial_ratio()对位置敏感,搜索匹配。 2) >>> fuzz._process_and_sort(s,
  • FuzzyWuzzy:Python中的模糊字符串匹配

    千次阅读 2019-03-13 16:25:07
    模糊字符串匹配是大致(而不是精确地)查找与给定模糊匹配字符串的过程,就像字面意思一样,它也被称为近似字符串匹配。通常,这些字符串普哦诶的模式另一个字符串。 使用Levenshtein Distance计算两个字符串之间...
  • 模糊字符串匹配像老板。 它使用来计算简单易用的程序包中序列之间的差异。 要求 Python 2.7或更高版本 difflib (可选,在字符串匹配中提供4-10倍的加速,尽管在可能导致) 供测试用 pycodestyle 假设 pytest 安装...
  • Fuzzyset-用于python模糊字符串集。 Fuzzyset是一种数据结构,对数据执行类似于全文搜索的操作,以确定可能的拼写错误和近似的字符串匹配。 用法 用法很简单。 只需将一个字符串添加到集合中,然后使用.get或[]...
  • fuzzywuzzy, 在 python 中,模糊字符串匹配 FuzzyWuzzy像老板一样的模糊字符串匹配。 它使用 Levenshtein距离来计算simple-to-use包中序列之间的差异。要求python 2.4或者更高版本diffliblevenshtein ( 可选
  • 我有2组数据,它们具有共同的功能集,但ID名称的标签不同.我想看看是否有一个最佳分类器可以帮助我选择哪些名称匹配是基于这些功能的最佳选择.第1组看起来像:Name ID1 code1 move1 yearHighland 1 nc st 2002Highl...
  • Python编程:fuzzywuzzy字符串模糊匹配

    千次阅读 2019-03-26 13:00:51
    fuzzywuzzy使用编辑距离(Levenshtein Distance)来计算序列之间的差异 github: https://github.com/seatgeek/fuzzywuzzy 安装 pip install fuzzywuzzy ...python: fuzzywuzzy学习笔记
  • 用Shell通配符匹配字符串 问题 你想使用Unix Shell中常用的通配符(比如*.py,Dat[0-9]*.csv等)去匹配文本字符串 解决方案 fnmatch模块提供了两个函数——fnmatch()和fnmatchcase(),可以用来实现这样的匹配。用法...
  • 利用FuzzyWuzzy库匹配字符串1. 背景前言2. FuzzyWuzzy库介绍2.1 安装2.1 fuzz模块2.1.1 简单匹配(Ratio)2.1.2 非完全匹配(Partial Ratio)2.1.3 忽略顺序匹配(Token Sort Ratio)2.1.4 去重子集匹配(Token Set ...
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 输出为数组,元素为元组,元祖第一个匹配到的字符串,第二个为int型,为score。对输出按照score排序。 >>> process.extractWithoutOrder(query, choices, processor = default_processor, scorer=default_...
  • Python实现字符串匹配算法

    千次阅读 2015-01-04 16:17:15
    字符串匹配是一个经典的问题,即如何在一个给定的z字符串中查找一个给定的值。这里给出了最原始的蛮力字符串匹配算法以及Horspool算法的实现,后者是利用时空权衡中输入增强技术对原始的蛮力算法进行改进。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,286
精华内容 4,114
关键字:

python模糊匹配字符串

python 订阅