R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大。 R语言作为统计学一门语言，一直在小众领域闪耀着光芒。直到大数据的爆发，R语言变成了一门炙手可热的数据分析的利器。随着越来越多的工程背景的人的加入，R语言的社区在迅速扩大成长。现在已不仅仅是统计领域，教育，银行，电商，互联网….都在使用R语言。 要成为有理想的极客，我们不能停留在语法上，要掌握牢固的数学，概率，统计知识，同时还要有创新精神，把R语言发挥到各个领域。让我们一起动起来吧，开始R的极客理想。 关于作者： 张丹，分析师/程序员/Quant: R,Java,Nodejs blog: http://blog.fens.me email: bsspirit@gmail.com 转载请注明出处： http://blog.fens.me/r-levenshtein-distance/ 前言 文字模糊匹配，是在文字处理时，要常用到的一种功能。比如英文，差一个字母，字母的顺序写反了。要实现对文字的模糊匹配，就可以用到莱文斯坦距离的思路，将一个字符串变为另一个字符串需要进行编辑操作最少的次数。 输入法的拼写检查，纠正用户输入的拼写错误，就是使用到了莱文斯坦距离。 目录 莱文斯坦距离介绍 算法原理 R语言代码实现 adist()函数调用 1. 莱文斯坦距离介绍 Levenshtein Distance Levenshtein Distance莱文斯坦距离，属于编辑距离的一种，主要用于衡量两个字符串之间的差异。由苏联数学家Vladimir Levenshtein于1965年提出，被广泛应用于拼写纠错检查、DNA分析、语音识别等领域。 两个字符串之间的Levenshtein Distance莱文斯坦距离指的是，将一个字符串变为另一个字符串需要进行编辑操作最少的次数。其中，允许的编辑操作有以下三种，替换、插入、删除。 「替换」：将一个字符替换成另一个字符 「插入」：插入一个字符 「删除」：删除一个字符 例如，计算 house 到 rose 的莱文斯坦距离。 第一步：house 把第一位 h 替换为 r，得到rouse。 第二步：rouse 把第三位 u 删除，得到rose 即完成了计算，莱文斯坦距离为2. 2. 算法原理 对于两个字符串A、B而言，字符串A的前i个字符和字符串B的前j个字符的莱文斯坦距离符合如下公式。 在数学上，两个字符串a,b的莱文斯坦距离： 计算公式： 表示内容： 2.1 第一种情况：当至少存在一个字符串为空串 若字符串A是一个长度为0的空字符串时，则其变为长度为n的字符串B。只需对字符串A进行n次插入操作即可。 …
Read more →