文本相似度算法-Jaro distance

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

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 4,435评论 0 5
  • http://python.jobbole.com/85231/ 关于专业技能写完项目接着写写一名3年工作经验的J...
    燕京博士阅读 7,615评论 1 118
  • 介绍 本节内容将介绍在 Python 里处理字符串的基本概念,以及正则表达式的使用,以及介绍几种常见的字符串处理算...
    寒冰卿阅读 726评论 0 0
  • 我是谁,我是父母定下的概念?还是学校?还是社会?孩子在不同的家庭,会成为不同的人。这些年的我是真正的我吗?不是,我...
  • 与一座城市的伤感告别 2017.08.13 朦胧的雨,昏暗...
    巴山_c3cb阅读 521评论 1 0