Python中的Jaro和Jaro-Winkler相似度

2025年1月5日 | 阅读6分钟

Jaro 相似度

两个字符串之间的 Jaro 相似度是衡量它们相似程度的指标。Jaro 距离的值介于 0 和 1 之间，其中 1 表示字符串相等，0 表示字符串不相似。

示例

Input: s1 = "CRATE", s2 = "TRACE"; 
Output: Jaro Similarity = 0.733333
Input: s1 = "DwAyNE", s2 = "DuANE"; 
Output: Jaro Similarity = 0.822222

算法

以下公式用于计算 Jaro 相似度

Jaro and Jaro-Winkler Similarity in Python

其中

m 是匹配字符的数量
t 是换位的数量的一半
其中 |s1| 和 |s2| 分别是字符串 s1 和 s2 的长度。

当字符相同且字符之间的距离不超过 { max(|s1|, |s2|) / 2 } - 1 时，则称这些字符为匹配字符。

两个字符串中顺序不同的匹配字符数量的一半即为换位。

计算

假设 s1="arnab" 和 s2="raanb"，任何字符可以匹配的最大距离为 1。
很明显，两个字符串都包含五个匹配的字符，但由于字符顺序不同，有四个字符的顺序不正确，导致两次换位。
因此，可以使用以下公式确定 Jaro 相似度

Jaro 相似度 = ( 1 / 3 ) * { ( 5 / 5 ) + ( 5 / 5 ) + ( 5 - 2 ) / 5 } = 0.86667

Python 中 Jaro 相似度的实现

上述方法的实现如下。

代码

# Python3 implementation of Jaro Similarity
# Function to calculate the Jaro Similarity of two strings
def jaro_distance(s1, s2):	
	# If the strings are equal, return the maximum similarity
	if (s1 == s2):
		return 1.0
	# Length of two strings
	len1 = len(s1)
	len2 = len(s2)
	# Maximum distance up to which matching is allowed
	max_dist = (max(len1, len2) // 2) - 1
	# Count of matches
	match = 0
	# Hash for matches
	hash_s1 = [0] * len(s1)
	hash_s2 = [0] * len(s2)
	# Traverse through the first string
	for i in range(len1):
           # Check if there is any match
		for j in range(max(0, i - max_dist), 
					min(len2, i + max_dist + 1)):		
			# If there is a match
			if (s1[i] == s2[j] and hash_s2[j] == 0):
				hash_s1[i] = 1
				hash_s2[j] = 1
				match += 1
				break
	# If there is no match, return 0 similarity
	if (match == 0):
		return 0.0
	# Number of transpositions
	t = 0
	point = 0
	# Count the number of occurrences where two characters match
	# but there is a third matched character in between the indices
	for i in range(len1):
		if (hash_s1[i]):
			# Find the next matched character in second string
			while (hash_s2[point] == 0):
				point += 1
			if (s1[i] != s2[point]):
				t += 1
			point += 1
	# Number of transpositions divided by 2
	t = t // 2
	# Return the Jaro Similarity
	return (match / len1 + match / len2 +
			(match - t) / match) / 3.0
# Driver code
s1 = "CRATE"
s2 = "TRACE"
# Print Jaro Similarity of two strings
print(round(jaro_distance(s1, s2), 6))

程序说明

此 Python 程序用于计算两个输入字符串 (s1 和 s2) 之间的 Jaro 相似度。Jaro 相似度是一种相似度指标，其值介于 0 和 1 之间，1 表示两个字符串完全匹配。程序首先验证输入字符串是否等效，然后返回最大的相似度 1.0。接着确定字符串的长度，指定允许的最大匹配距离，并初始化计数器。为了在给定距离内找到第二个字符串中的匹配项，程序会遍历第一个字符串中的字符。哈希数组用于跟踪匹配项，并计算换位数。

输出

0.733333

时间复杂度： O(N * M)，其中 N 和 M 分别是 s1 和 s2 的字符串长度。
辅助空间： O(N + M)

Jaro-Winkler 相似度

Jaro-Winkler 相似度是一种字符串度量，用于计算两个字符串之间的编辑距离。Winkler-Jaro 相似度和 Jaro 相似度非常相似。当两个字符串的前缀匹配时，它们会产生分歧。Jaro-Winkler 相似度使用前缀因子“p”来在字符串共享特定最大长度 (l) 的前缀时提供更精确的结果。

示例

Input: s1 = "DwAyNE", s2 = "DuANE"; 
Output: Jaro-Winkler Similarity = 0.84
Input: s1 = "TRATE", s2 = "TRACE"; 

计算

Jaro-Winkler 相似度定义如下

其中

Sj 是 Jaro 相似度。
Sw 是 Jaro-Winkler 相似度。
P 是比例因子（默认为 0.1）。
L 是匹配前缀的长度，最多为四个字符。
假设 s1="arnab" 和 s2="aranb"。两个字符串的 Jaro 相似度为 0.933333。（基于上述计算。）
我们假设比例因子为 0.1，匹配前缀的长度为 2。
更改公式中的一个值

Jaro-Winkler 相似度= 0.9333333 + 0.1 * 2 * (1-0.9333333) = 0.946667

Python 中 Jaro-Winkler 相似度的实现

以上方法的实现如下：

代码

# Python3 implementation of Jaro Similarity
# Function to calculate the Jaro Similarity of two strings
def jaro_distance(s1, s2):
    # If the strings are equal, return the maximum similarity
    if s1 == s2:
        return 1.0
    # Length of two strings
    len1, len2 = len(s1), len(s2)
    # If either string is empty, return 0 similarity
    if len1 == 0 or len2 == 0:
        return 0.0
    # Maximum distance up to which matching is allowed
    max_dist = (max(len(s1), len(s2)) // 2) - 1
    # Count of matches
    match = 0
    # Hash for matches
    hash_s1 = [0] * len(s1)
    hash_s2 = [0] * len(s2)
    # Traverse through the first string
    for i in range(len1):
        # Check if there is any match
        for j in range(max(0, i - max_dist), min(len2, i + max_dist + 1)):
            # If there is a match
            if s1[i] == s2[j] and hash_s2[j] == 0:
                hash_s1[i] = 1
                hash_s2[j] = 1
                match += 1
                break
    # If there is no match, return 0 similarity
    if match == 0:
        return 0.0
    # Number of transpositions
    t = 0
    point = 0
    # Count the number of occurrences where two characters match
    # but there is a third matched character in between the indices
    for i in range(len1):
        if hash_s1[i]:
            # Find the next matched character in the second string
            while hash_s2[point] == 0:
                point += 1
            if s1[i] != s2[point]:
                point += 1
                t += 1
            else:
                point += 1
    # Number of transpositions divided by 2
    t = t // 2
    # Return the Jaro Similarity
    return ((match / len1 + match / len2 + (match - t) / match) / 3.0)
# Jaro Winkler Similarity
def jaro_Winkler(s1, s2):
    # Calculate Jaro Similarity
    jaro_dist = jaro_distance(s1, s2)
    # If the Jaro Similarity is above a threshold
    if jaro_dist > 0.7:
        # Find the length of the common prefix
        prefix = 0
        for i in range(min(len(s1), len(s2))):
            # If the characters match
            if s1[i] == s2[i]:
                prefix += 1
            else:
                # If characters don't match, break
                break
        # A maximum of 4 characters are allowed in the prefix
        prefix = min(4, prefix)
        # Calculate Jaro Winkler Similarity
        jaro_dist += 0.1 * prefix * (1 - jaro_dist)
    return jaro_dist
# Driver code
if __name__ == "__main__":
    s1 = "TRATE"
    s2 = "TRACE"
    # Print Jaro-Winkler Similarity of two strings
    print("Jaro-Winkler Similarity =", jaro_Winkler(s1, s2))

程序说明

此 Python 程序实现了用于比较两个字符串的 Jaro 相似度和 Jaro-Winkler 相似度度量。jaro_distance 函数在确定 Jaro 相似度时会考虑字符串的长度、允许的最大匹配距离以及具有潜在换位的匹配次数。通过添加公共前缀并根据前缀的长度修改相似度分数，jaro_Winkler 函数进一步提高了相似度。对于两个示例字符串（“TRATE”和“TRACE”），驱动代码演示了如何使用 Jaro-Winkler 相似度并输出分数。拼写检查和记录链接是使用这些相似度度量的两个常见字符串匹配应用。

输出

Jaro-Winkler Similarity = 0.9066666666666667

时间复杂度： O(N * M)，其中 N 和 M 分别是 s1 和 s2 的字符串长度。
辅助空间： O(N + M)。

下一个主题Python 中的 Kaprekar 常量

← 上一个下一个 →

Python中的Jaro和Jaro-Winkler相似度

Jaro 相似度

算法

计算

Python 中 Jaro 相似度的实现

Jaro-Winkler 相似度

计算

Python 中 Jaro-Winkler 相似度的实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

其他

Python中的Jaro和Jaro-Winkler相似度

Jaro 相似度

算法

计算

Python 中 Jaro 相似度的实现

Jaro-Winkler 相似度

计算

Python 中 Jaro-Winkler 相似度的实现

相关帖子

如何在Python中使用星号表达式解包

如何在Python中捕获SystemExit异常

如何在Python中获取左侧用零填充的字符串

如何使用Python创建一个编程语言

Python中的无头Chrome

Python中的朴素时间序列预测

Python中的numpy.tile()

Python的缺点

Python - Bigrams

词嵌入：探索、解释和利用（含Python代码）

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器