如何计算模糊字符串匹配中的分数？
How to calculate score in fuzzy string matching?
我想知道计算两个字符串之间的模糊匹配分数背后的数学逻辑和公式。
假设我有两个字符串 s1 和 s2，我想在 python 中使用模糊匹配。我知道像 fuzzywuzzy 这样的 python 库可以做到这一点。但我想知道模糊匹配方法和比率计算背后的确切数学和逻辑。
名字的模糊字符串匹配由一个字母和三个数字组成：字母是名字的第一个字母，数字编码其余的辅音。发音位置相似的辅音使用相同的数字，例如，唇辅音 B、F、P 和 V 均编码为数字 1。
可以找到正确的值如下：
保留姓名的第一个字母并删除所有其他出现的 a、e、i、o、u、y、h、w。
用数字替换辅音如下（第一个字母后）：
b, f, p, v → 1
c, g, j, k, q, s, x, z → 2
d, t → 3
l → 4
m, n → 5
r → 6
如果原名中有两个或多个相同编号的字母相邻（步骤1之前），则只保留第一个字母；由 'h' 或 'w' 分隔的相同数字的两个字母也被编码为单个数字，而由元音分隔的此类字母被编码两次。此规则也适用于第一个字母。
如果您的单词中的字母太少而无法分配三个数字，请附加零直到出现三个数字。如果您有四个或更多数字，则只保留前三个。
使用此算法，“Robert”和“Rupert”return 生成相同的字符串“R163”，而“Rubin”生成“R150”。 “Ashcraft”和“Ashcroft”都产生“A261”。 “Tymczak”产生“T522”而不是“T520”（名称中的字符 'z' 和 'k' 被编码为 2 两次，因为元音位于它们之间）。 “Pfister”产生“P236”而不是“P123”（前两个字母具有相同的数字并且编码一次为 'P'），而“Honeyman”产生“H555”。
您可以在此处找到详细信息：
https://en.wikipedia.org/wiki/Soundex#:~:text=Soundex%20is%20a%20phonetic%20algorithm,despite%20minor%20differences%20in%20spelling.
模糊字符串匹配，也称为 近似字符串匹配 ，是查找与给定模式近似匹配的字符串的过程。
匹配的接近程度通常根据编辑距离来衡量，编辑距离是将字符串转换为精确匹配所需的原始操作的数量。
原始操作通常是：insertion（在给定位置插入一个新字符），deletion（删除特定字符）和substitution（用新字符替换一个字符）。
模糊搜索通过使用计算两个词之间的距离（或相似度）的数学公式来工作。一种常用的方法称为 Levenshtein distance.
Here你可以找到公式。
Levenshtein 距离的替代方法是使用余弦相似度。 余弦距离的真正优点是可以进行降维。这使您可以高效且模糊地处理非常大的文档。它还允许您创建高效的数据结构来查找相似的字符串等等。
Here你可以找到公式。
以上回答对两种常用的模糊字符串匹配算法，即Levenshtein距离和Soundex算法进行了深入的解释。我将尝试解释余弦相似度在模糊字符串匹配中的使用。
两个非零向量之间的余弦相似度就是这些向量之间夹角的余弦值。核心思想是找到每个字符串对应的向量表示。这可以通过使用词袋特征提取器或 TF-IDF 特征提取器来完成。字符串之间的相似性与余弦相似性度量成正比。
例如：考虑以下名称：
姓名 1 : athaarv
姓名 2：atharv
步骤 1) 这些字符串的 2gram 表示是
Name1_2gram = ["at","th","ha","aa","ar","rv"]
Name2_2gram = ["at","th","ha","ar","rv"]
Step2) Bag of Words Representation:
Name1_BOW = [1,1,1,1,1,1]
Name2_BOW = [1,1,1,0,1,1]
Step3) 计算余弦相似度：
余弦相似度 = ([1 1 1 1 1 1].[1 1 1 0 1 1])/(sqrt(5)*sqrt(6)) = 0.91
注意：使用 TF-IDF 的字符串表示通常比 BOW.Also Nanonets 博客有一些关于这个特定主题的资源可能会有帮助。
我想知道计算两个字符串之间的模糊匹配分数背后的数学逻辑和公式。
假设我有两个字符串 s1 和 s2，我想在 python 中使用模糊匹配。我知道像 fuzzywuzzy 这样的 python 库可以做到这一点。但我想知道模糊匹配方法和比率计算背后的确切数学和逻辑。
名字的模糊字符串匹配由一个字母和三个数字组成：字母是名字的第一个字母，数字编码其余的辅音。发音位置相似的辅音使用相同的数字，例如，唇辅音 B、F、P 和 V 均编码为数字 1。
可以找到正确的值如下：
保留姓名的第一个字母并删除所有其他出现的 a、e、i、o、u、y、h、w。 用数字替换辅音如下（第一个字母后）：
b, f, p, v → 1
c, g, j, k, q, s, x, z → 2
d, t → 3
l → 4
m, n → 5
r → 6
如果原名中有两个或多个相同编号的字母相邻（步骤1之前），则只保留第一个字母；由 'h' 或 'w' 分隔的相同数字的两个字母也被编码为单个数字，而由元音分隔的此类字母被编码两次。此规则也适用于第一个字母。 如果您的单词中的字母太少而无法分配三个数字，请附加零直到出现三个数字。如果您有四个或更多数字，则只保留前三个。
使用此算法，“Robert”和“Rupert”return 生成相同的字符串“R163”，而“Rubin”生成“R150”。 “Ashcraft”和“Ashcroft”都产生“A261”。 “Tymczak”产生“T522”而不是“T520”（名称中的字符 'z' 和 'k' 被编码为 2 两次，因为元音位于它们之间）。 “Pfister”产生“P236”而不是“P123”（前两个字母具有相同的数字并且编码一次为 'P'），而“Honeyman”产生“H555”。
您可以在此处找到详细信息： https://en.wikipedia.org/wiki/Soundex#:~:text=Soundex%20is%20a%20phonetic%20algorithm,despite%20minor%20differences%20in%20spelling.
模糊字符串匹配，也称为 近似字符串匹配 ，是查找与给定模式近似匹配的字符串的过程。 匹配的接近程度通常根据编辑距离来衡量，编辑距离是将字符串转换为精确匹配所需的原始操作的数量。 原始操作通常是：insertion（在给定位置插入一个新字符），deletion（删除特定字符）和substitution（用新字符替换一个字符）。
模糊搜索通过使用计算两个词之间的距离（或相似度）的数学公式来工作。一种常用的方法称为 Levenshtein distance.
Here你可以找到公式。
Levenshtein 距离的替代方法是使用余弦相似度。 余弦距离的真正优点是可以进行降维。这使您可以高效且模糊地处理非常大的文档。它还允许您创建高效的数据结构来查找相似的字符串等等。
Here你可以找到公式。
以上回答对两种常用的模糊字符串匹配算法，即Levenshtein距离和Soundex算法进行了深入的解释。我将尝试解释余弦相似度在模糊字符串匹配中的使用。
两个非零向量之间的余弦相似度就是这些向量之间夹角的余弦值。核心思想是找到每个字符串对应的向量表示。这可以通过使用词袋特征提取器或 TF-IDF 特征提取器来完成。字符串之间的相似性与余弦相似性度量成正比。
例如：考虑以下名称： 姓名 1 : athaarv 姓名 2：atharv
步骤 1) 这些字符串的 2gram 表示是
Name1_2gram = ["at","th","ha","aa","ar","rv"]
Name2_2gram = ["at","th","ha","ar","rv"]
Step2) Bag of Words Representation:
Name1_BOW = [1,1,1,1,1,1]
Name2_BOW = [1,1,1,0,1,1]
Step3) 计算余弦相似度：
余弦相似度 = ([1 1 1 1 1 1].[1 1 1 0 1 1])/(sqrt(5)*sqrt(6)) = 0.91
注意：使用 TF-IDF 的字符串表示通常比 BOW.Also Nanonets 博客有一些关于这个特定主题的资源可能会有帮助。