文本相似度算法-Jaro distance

2019-11-14 本文已影响0人 ColdCoder

Jaro distance

给定两个文本串 $s_1$ , $s_2$ ,他们的Joro距离定义为：

其中：
表示两个字符串中match的字符数
表示文本串长度
表示换位(transpositoins)数目()

求match的字符数：
分别来自 $s_1$ , $s_2$ 的字符，当他们相同或者距离小于 $d =\lfloor \frac{max(|x_i|,|x_2|)}{2}\rfloor - 1$ ,则被认为是match的。

比如： $s_1$ =“DIXON”, $s_2$ =“DICKSONX”

距离计算出来等于3,则每一次从max(0,i-d)到min(i+d,xLen)的空间内比较（如果从横轴进行比较，xLen表示长度）。最终得到match数。

$s_1$ 中的每一个字符都会与 $s_2$ 中距离 $d$ 内的字符进行比较。将所有match的字符串，需要替调换顺序才能匹配的总数除以二就是transpositions的大小 $t$ 。这里两个字符串中匹配的分别是："DION"，“DION",所以 $t=0$ 。
另外 $|s_1|$ =4, $|s_2|$ =8,
则：
$d_j=\frac{1}{3}(\frac{4}{5} + \frac{4}{8} + \frac{4-0}{4})$

参考：
https://rosettacode.org/wiki/Jaro_distance#Java

文本相似度算法-Jaro distance

猜你喜欢

热点阅读