• Archive by category "程序算法"

Blog Archives

用R语言实现点积相似度Dot Product Similarity

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-dot-product-similarity/

前言

在文字处理时,我们经常需要判断两段文字是否相似,计算文本相似度有很多度种方法,文本将介绍最简单,也是计算最高效的一种方法点积相似度,与余弦相似度很像,与欧式距离相似度也很像。

目录

  1. 点积相似度介绍
  2. R语言实现点积计算
  3. 点积相似度应用

1. 点积相似度介绍

点积在数学中,又称数量积(dot product 或者 scalar product),是指接受在实数R上的两个向量并计算它们对应元素的乘机之和,也是欧几里得空间的标准内积。当两个向量进行点积操作时,结果的大小可以反映两个向量的相似性。这是因为点积操作考虑了向量的方向和大小。

点积计算

点积有两种定义方式:代数方式和几何方式。通过在欧氏空间中引入笛卡尔坐标系,向量之间的点积既可以由向量坐标的代数运算得出,也可以通过引入两个向量的长度和角度等几何概念来求解。

代数方式:

两个向量a = [a1, a2,…, an]和b = [b1, b2,…, bn]的点积定义为:

几何方式:

点积相似度

点积相似度,是一种计算两个向量之间相似性的方法,对于两个向量a和b,它们的点积相似度为它们对应元素的乘机之和。

假设我们有两个向量 A 和 B,它们的点积定义为:

A . B = |A| * |B| * cos(θ)
其中,|A| 和 |B| 分别是 A 和 B 的长度,θ 是 A 和 B 之间的夹角。
  • 当 A 和 B 的方向相同时(即它们的夹角接近0),cos(θ) 接近 1,所以 A . B 较大。这表明 A 和 B 很相似。
  • 当 A 和 B 的方向相反时(即它们的夹角接近180度),cos(θ) 接近 -1,所以 A . B 较小,甚至为负。这表明 A 和 B 不相似。
  • 当 A 和 B 互相垂直时(即它们的夹角为90度),cos(θ) 为 0,所以 A . B 为 0。这表明 A 和 B 没有相似性。

因此,通过计算向量的点积,我们可以得到一个衡量两个向量相似性的标量值。在深度学习中,尤其是在自然语言处理和推荐系统中,我们经常需要衡量和比较向量(例如,单词嵌入或用户和物品的嵌入)的相似性。在这些情况下,点积是一种简单且有效的方法。

2. R语言实现点积计算

根据公式计算点积是很简单的,用R语言的基本函数,就可以完成点积的计算。

首先,定义2个向量a和b。


> a <- c(2, 5, 6)
> b <- c(4, 3, 2)

代数方式实现


> fun1<-function(a,b){
+   sum(a*b)
+ }
> 
> fun1(a,b)
[1] 35

几何方式实现


> fun2<-function(a,b){
+   a %*% b  
+ }
> 
> fun2(a,b)
     [,1]
[1,]   35

3. 点积相似度应用

接下来,我们设置一个场景,用点积相似度计算,计算不同人的简历的相似度。

假设有三个求职者A,B,C,从简历中提取了5个属性,分别是:性别、学历、籍贯、编程语言、职位。

姓名性别学历籍贯编程语言职位
A本科浙江JAVA开发工程师
B硕士北京R算法工程师
C本科上海JAVA开发工程师

那么,我们可以把上面的表格转换为一个矩阵:


[
[男	本科	浙江	JAVA	开发工程师],
[女	硕士	北京	R	算法工程师],
[男	本科	上海	JAVA	开发工程师],
]

然后,我们把这个矩阵转置:


[
[男, 女, 男]
[本科, 硕士, 本科],
[浙江, 北京, 上海],
[JAVA, R, JAVA],
[开发工程师, 算法工程师, 开发工程师]
]

计算上面2个矩阵的点积,计算过程为:


[
[男 * 男 + 本科 * 本科 + 浙江 * 浙江 + JAVA * JAVA + 开发工程师*开发工程师,
男 * 女 + 本科 * 硕士 + 浙江 * 北京 + JAVA * R + 开发工程师*算法工程师,
男 * 男 + 本科 * 本科 + 浙江 * 上海 + JAVA * JAVA + 开发工程师*开发工程师],
[女 * 男 + 硕士 * 本科 + 北京 * 浙江 + R * JAVA + 算法工程师*开发工程师,
女 * 女 + 硕士 * 硕士 + 硕士 * 硕士 + R * R + 算法工程师*算法工程师,
女 * 男 + 硕士 * 本科 + 北京 * 上海 + R * JAVA + 算法工程师*开发工程师],
[男 * 男 + 本科 * 本科 + 上海 * 浙江 + JAVA * JAVA + 开发工程师*开发工程师,
男 * 女 + 本科 * 硕士 + 上海 * 北京 + JAVA * R + 开发工程师*算法工程师,
男 * 男 + 本科 * 本科 + 上海 * 上海 + JAVA * JAVA + 开发工程师*开发工程师],
]

这里为了便于计算,我们假设将值相等的点积值设为1,不相等设为0,计算结果为一个3*3的矩阵,得到计算结果为:


[
[5, 0, 4]
[0, 5, 0]
[4, 0, 5]
]

我们可以认为这个矩阵代表了,三个人之间两两的关联度,数值越大越相似。

ABC
A504
B050
C405

于是,这样我们再比较简历的时候,就可以判断谁和谁比较相似了。词向量计算,和这个计算过程是类似的。因此,在文本的的匹配过程中,每个词都可以找到与之相似度分数最高的一个关联词。

最后,我们用R语言来模拟上面的手动计算过程。

首先,用R语言来构建数据集resume。


> resume<-data.frame(
+   `姓名`=c('A','B','C'),
+   `性别`=c('男','女','男'),
+   `学历`=c('本科','硕士','本科'),
+   `籍贯`=c('浙江','北京','上海'),
+   `编程语言`=c('JAVA','R','JAVA'),
+   `职位`=c('开发工程师','算法工程师','开发工程师')
+ )

> resume
  姓名 性别 学历 籍贯 编程语言       职位
1    A   男 本科 浙江     JAVA 开发工程师
2    B   女 硕士 北京        R 算法工程师
3    C   男 本科 上海     JAVA 开发工程师

把data.frame矩阵化,同时建立转置矩阵


> m1<-resume[,-1];m1
  性别 学历 籍贯 编程语言       职位
1   男 本科 浙江     JAVA 开发工程师
2   女 硕士 北京        R 算法工程师
3   男 本科 上海     JAVA 开发工程师
> m2<-t(m1);m2
         [,1]         [,2]         [,3]        
性别     "男"         "女"         "男"        
学历     "本科"       "硕士"       "本科"      
籍贯     "浙江"       "北京"       "上海"      
编程语言 "JAVA"       "R"          "JAVA"      
职位     "开发工程师" "算法工程师" "开发工程师"

建立函数dot_similary(),完成点积的计算,得到点积相似度矩阵。本文的代码实现过程,没有使用矩阵的方法来实现,因此这里主要是介绍计算思路。


> dot_similary<-function(df){
+   m1<-df[,-1];m1
+   m2<-t(m1);m2
+   
+   n<-nrow(m1)
+   mm<-matrix(0,nrow=n,ncol=n)
+   for(i in 1:n){
+     for(j in 1:n){
+       v<-length(which(m1[i,]==m2[,j]))    
+       mm[i,j]<-v
+     }
+   }
+   
+   colnames(mm)<-df[,1]
+   rownames(mm)<-df[,1] + mm + } # 运行函数,获得结果 

> dot_similary(resume)
  A B C
A 5 0 4
B 0 5 0
C 4 0 5

如果看看计算过程,可以打印矩阵点积计算的过程。


> row1<-paste(
+   paste(paste(m1[1,],m2[,1], sep='*'),collapse = "+"),
+   paste(paste(m1[1,],m2[,2], sep='*'),collapse = "+"),
+   paste(paste(m1[1,],m2[,3], sep='*'),collapse = "+"),
+   sep=","
+ )
> row1
[1] "男*男+本科*本科+浙江*浙江+JAVA*JAVA+开发工程师*开发工程师,男*女+本科*硕士+浙江*北京+JAVA*R+开发工程师*算法工程师,男*男+本科*本科+浙江*上海+JAVA*JAVA+开发工程师*开发工程师"
 
> row2<-paste(
+   paste(paste(m1[2,],m2[,1], sep='*'),collapse = "+"),
+   paste(paste(m1[2,],m2[,2], sep='*'),collapse = "+"),
+   paste(paste(m1[2,],m2[,3], sep='*'),collapse = "+"),
+   sep=","
+ )
> row2
[1] "女*男+硕士*本科+北京*浙江+R*JAVA+算法工程师*开发工程师,女*女+硕士*硕士+北京*北京+R*R+算法工程师*算法工程师,女*男+硕士*本科+北京*上海+R*JAVA+算法工程师*开发工程师"
 
> row3<-paste(
+   paste(paste(m1[3,],m2[,1], sep='*'),collapse = "+"),
+   paste(paste(m1[3,],m2[,2], sep='*'),collapse = "+"),
+   paste(paste(m1[3,],m2[,3], sep='*'),collapse = "+"),
+   sep=","
+ )
> row3
[1] "男*男+本科*本科+上海*浙江+JAVA*JAVA+开发工程师*开发工程师,男*女+本科*硕士+上海*北京+JAVA*R+开发工程师*算法工程师,男*男+本科*本科+上海*上海+JAVA*JAVA+开发工程师*开发工程师"

本文我们了解点积相似度的原理和实现,并且应用了点积似度,对简历中的人进行了相似度的计算,从而可以判断两个人之间的相似程度,让我们进行文本匹配时又多了一种方法。本文代码:https://github.com/bsspirit/r-string-match/blob/main/dotproduct.r

转载请注明出处:
http://blog.fens.me/r-dot-product-similarity/

打赏作者

用R语言实现余弦相似度Cosine Similarity

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-cosine-similarity/

前言

在文字处理时,我们经常需要判断两段文字是否相似,如果这两段文字的用词越相似,它们的内容就应该越相似。这个场景下,我们就可以考虑先把文字转换成词频向量,然后用余弦相似度来判断是否相似。

目录

  1. 余弦相似度介绍
  2. R语言实现余弦相似度
  3. 计算2个文本的相似度

1. 余弦相似度介绍

余弦相似度,通过测量两个向量的夹角的余弦值来度量它们之间的相似性。例如,将两篇文章向量化,余弦距离可以避免因为文章的长度不同而导致距离偏大,余弦距离只考虑两篇文章生成的向量的夹角。

余弦相似度被大量用于对比:如人脸对比、声音对比,来快速判断两个图片或者两段声音的相似度,进而判断是不是来自同一个人。当一个图像或者声音样本具有n维的特征,我们就可以把他认为是n维向量,两个样本使用余弦相似度比对时,就是对两个n维向量的夹角余弦值,其大小进行衡量。

余弦相似度的取值范围是[-1,1],相同两个向量的之间的相似度为1。余弦距离的取值范围是[0,2]。

  • 当夹角为0,两个向量同向,相当于相似度最高,余弦值为1,表示完全正相关。
  • 当夹角90°,两个向量垂直,余弦为0,表示不相关。
  • 当夹角180°,两个向量反向,余弦为-1,表示完全负相关。

计算公式:

相比其他的距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上。

欧式距离与余弦距离的对比:

  1. 欧式距离的数值受到维度的影响,余弦相似度在高维的情况下也依然保持低维完全相同时相似度为1等性质。
  2. 欧式距离体现的是距离上的绝对差异,余弦距离体现的是方向上的相对差异。

不同情况不同选择:

  1. 两个人分别取了蓝球(1,0)与红球(0,1),这两个向量的欧式距离较小,可是事实是这两个球是不同的,而余弦距离为2表示的是完全不同的意思。所以在这种情况下选择余弦距离更具合理性。
  2. 两个人对APP的使用次数与使用时长分别表示为(1,10),(10,100),可知余弦相似度较小,说明这两个人的行为时相同的,可是,事实是不同的,两个人的活跃度有着极大的差异,第二个人的活跃度更高。

2. R语言实现余弦相似度

我们可以安装lsa包,使用cosine()函数,计算2个向量的余弦相似度。

lsa(Latent Semantic Analysis 潜在语义分析)包基本思想是,文本确实具有高阶(=潜在语义)结构,但这种结构会被词语用法(如通过使用同义词或多义词)所掩盖。通过对给定的文档-术语矩阵进行截断奇异值分解(双模式因子分析),以统计方式得出概念指数,从而克服了这一可变性问题。

lsa包的安装过程比较简单。


> install.packages(lsa)
> library(lsa>

计算2个向量的余弦相似度。


> vec1 = c( 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 )
> vec2 = c( 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0 )
> cosine(vec1,vec2) 
          [,1]
[1,] 0.2357023

3. 计算2个文本的相似度

有了计算余弦相似度的工具后,那么接下来,我们就可以尝试计算文本的相似度了。

使用余弦相似度,计算文本相似的具体步骤:

  1. 定义两个文本内容
  2. 对两个文本内容进行分词
  3. 列出所有的词,并计算词频
  4. 整理词频为词向量
  5. 用余弦相似度计算词向量

第一步,我们定义两段文本内容,分别是

  • 句子1:”我买了一个手机,又配了一个手机壳”
  • 句子2:”我有3年没有换新手机了,还是原来的手机壳”

> txt1<-"我买了一个手机,又配了一个手机壳"
> txt2<-"我有3年没有换新手机了,还是原来的手机壳"

第二步,对上面2个句子进行分词,这里我们使用jiebaR包进行分词,关于jiebaR包的具体用法,请参考文章R语言中文分词包jiebaR


# 加载jiabaR包
> library(jiebaR)

# 定义分词引擎
> wk<-worker()

# 分别对两个文本进行分词
> w1<-wk[txt1]
> w2<-wk[txt2]

第三步,进出所有的词,并查看词频


> w1
 [1] "我"   "买"   "了"   "一个" "手机" "又"   "配"   "了"   "一个" "手机" "壳"  
> w2
 [1] "我"     "有"     "3"      "年"     "没有"   "换"     "新手机" "了"     "还是"   "原来"   "的"    
[12] "手机"   "壳" 

# 查看词频
> table(w1)
w1
  壳   了   买   配 手机   我 一个   又 
   1    2    1    1    2    1    2    1 

> table(w2)
w2
     3     的   还是     换     壳     了   没有     年   手机     我 新手机     有   原来 
     1      1      1      1      1      1      1      1      1      1      1      1      1 

第四步,整理词频为词向量,这里我把生成词向量过程,封装成一个函数叫dfm(),形成单词矩阵。


# 加载工具包
> library(plyr)
> library(magrittr)

# 封装词向量函数
> dfm<-function(w1,w2){
+     t1<-table(w1) %>% ldply
+     t2<-table(w2) %>% ldply
+     names(t1)<-c("seg","cnt1")
+     names(t2)<-c("seg","cnt2")
+     mm<-merge(t1,t2,by="seg",all=TRUE)
+     mm$cnt1[which(is.na(mm$cnt1))]<-0
+     mm$cnt2[which(is.na(mm$cnt2))]<-0
+     list(dat=t(mm[,-1]),seg=mm$seg)
+ }

# 查看词向量的输出结果
> m<-dfm(w1,w2);m
$dat
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17]
cnt1    0    0    0    0    1    2    1    0    0     1     2     1     0     2     0     1     0
cnt2    1    1    1    1    1    1    0    1    1     0     1     1     1     0     1     0     1

$seg
 [1] "3"      "的"     "还是"   "换"     "壳"     "了"     "买"     "没有"   "年"     "配"     "手机"  
[12] "我"     "新手机" "一个"   "有"     "又"     "原来"  

第五步,用余弦相似度计算词向量的相似度,即两段文本的余弦相似度。结果是0.4,表示不是太相似。


> library(lsa)
> cosine(m$dat[1,],m$dat[2,]) 
          [,1]
[1,] 0.4036037

那我们换一组句子再试试,比如

  • 句子1:如果这两句话的用词越相似,它们的内容就应该越相似。
  • 句子2:如果这两句话的内容越相似,它们的用词也应该越相似。

用R语言计算上面2个句子的余弦相似度,得0.95,表示非常相似了。


> txt1<-"如果这两句话的用词越相似,它们的内容就应该越相似"
> txt2<-"如果这两句话的内容越相似,它们的用词也应该越相似"
> w1<-wk[txt1]
> w2<-wk[txt2]
> m<-dfm(w1,w2);m
$dat
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
cnt1    2    1    1    1    1    1    2    0    1     1     2     1
cnt2    2    0    1    1    1    1    2    1    1     1     2     1

$seg
 [1] "的"     "就"     "两句话" "内容"   "如果"   "它们"   "相似"   "也"     "应该"   "用词"   "越"    
[12] "这"    

> cosine(m$dat[1,],m$dat[2,]) 
     [,1]
[1,] 0.95

本文我们了解余弦相似度的原理和实现,并且应用了余弦相似度计算,从而可以判断两个文本之间的相似程度,让我们进行文本匹配时又多了一种方法。本文代码:https://github.com/bsspirit/r-string-match/blob/main/cosine.r

转载请注明出处:
http://blog.fens.me/r-cosine-similarity/

打赏作者

用R语言实现汉明距离算法Hamming Distance

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-hamming-distance/

前言

在文字处理时,经常会用到编码方式,把文字和数字进行编码转换,从而计算文本的相似性。比如英文,差一个字母,字母的顺序写反了。要实现对文字的模糊匹配,就可以用到汉明距离的思路,计算将一个字符串变换成另外一个字符串所需要替换的字符个数。

目录

  1. 汉明距离介绍
  2. 算法原理
  3. R语言代码实现

1. 汉明距离介绍 Hamming Distance

Hamming Distance汉明距离,是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。汉明距离的计算思路与莱文斯坦距离算法有类似之处,参考文章R语言莱文斯坦距离算法Levenshtein Distance

汉明距离计算,例如:

  • 二进制 1011101 与 1001001 之间的汉明距离是 2。
  • 字符串 2143896 与 2233796 之间的汉明距离是 3。
  • 字符串 toned 与 roses 之间的汉明距离是 3。

汉明重量,是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 1110001 的汉明重量是 4。

2. 算法原理

我们以d(x,y)表示两个数字x,y之间的汉明距离。

  • 对于两个等长字符串,可直接进行两个字符串对应位置的不同字符的个数。
  • 对于两个数字,可先转为二进制,然后进行异或运算,并统计结果为1的个数。

两个二进制组(00)与(01)的距离是1,(110)和(101)的距离是2。在一个码组集合中,任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。最小汉明距离越大,码组越具有抗干扰能力。

例如,2个数字93和73,93的二进制为10001001,73的二进制为10110001,然后进行xor异或运算,结果为10100,对结果统计1的个数,即得到汉明距离为2。

3. R语言实现

3.1 字符串类型

针对字符串的建立汉明距离算法,计算汉明距离。


> haming_string<-function(txt1,txt2){
+   len1<-nchar(txt1)
+   len2<-nchar(txt2)
+   
+   if(len1!=len2){
+     stop(paste("length is not equal"))
+   }
+   
+   n<-0
+   for(i in 1:len1){
+     t1<-substring(txt1,i,i)
+     t2<-substring(txt2,i,i)
+     if(t1!=t2){
+       n<-n+1
+     }
+   }
+   return(n)
+ }

汉明距离测试。


> haming_string("1011101","1101001")
[1] 3
> haming_string("2143896","2233796")
[1] 3
> haming_string("toned","roses")
[1] 3

3.2 数字类型
针对数字的建立汉明距离算法,先转换为二进制,再进行异或计算,计算汉明距离。


> haming_int<-function(num1,num2){
+   b1<-intToBits(num1)
+   b2<-intToBits(num2)
+   x<-xor(b1,b2);x
+   length(which(x==1))
+ }

汉明距离测试。


> haming_int(93,73)
[1] 2
> haming_int(137,177)
[1] 3

本文我们了解汉明距离的原理和实现,后面我们就可以利用汉明距离的特性,对字符串和数字进行相似度的距离计算,从而实现文本的模糊匹配。本文代码:https://github.com/bsspirit/r-string-match/blob/main/hanmming.r

转载请注明出处:
http://blog.fens.me/r-hamming-distance/

打赏作者

R语言莱文斯坦距离算法Levenshtein Distance

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/

前言

文字模糊匹配,是在文字处理时,要常用到的一种功能。比如英文,差一个字母,字母的顺序写反了。要实现对文字的模糊匹配,就可以用到莱文斯坦距离的思路,将一个字符串变为另一个字符串需要进行编辑操作最少的次数。

输入法的拼写检查,纠正用户输入的拼写错误,就是使用到了莱文斯坦距离。

目录

  1. 莱文斯坦距离介绍
  2. 算法原理
  3. R语言代码实现
  4. 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次插入操作即可。

例如:


A="",B="abc"时
lev距离 = max(length(A),length(B)) = max(0,3) = 3

同理,若字符串A是一个长度为n的字符串时,则其变为长度为0的空字符串B。则只需对字符串A进行n次删除操作即可。

例如:


A="abcd",B=""时
lev距离 = max(length(A),length(B)) = max(4,0) = 4

故在上述公式中,可将这两种情况统一为: 当两个字符串的长度最小值为0时,则说明有一个字符串为空串。则这二者之间的莱文斯坦距离为两个字符串长度的最大值。

2.2 第二种情况:两个字符串均不为空串

当两个字符串均不为空串时,这里假设字符串A为horse、字符串B为ros。由于替换/插入/删除,三种操作不会改变字符串中各字符的相对顺序。因此,可以每次仅对字符串A进行操作,即只考虑
字符串A的前i个字符 和 字符串B的前j个字符 的莱文斯坦距离,让i和j都从1开始计数。字符串A的前5个字符 和 字符串B的前3个字符 的莱文斯坦距离lev(5,3),就是最终我们所求的字符串A、字符串B之间的莱文斯坦距离3。

【插入】假设我们把 horse 变为 ro 的莱文斯坦距离记为u,即:


# 字符串A的前5个字符 和 字符串B的前3个字符 的莱文斯坦距离为 u
lev(5,2) = u

则 horse 期望变为 ros,其所需的编辑次数不会超过 u+1。因为 horse 只需先经过u次编辑操作变为 ro,然后在尾部插入s字符即可变为 ros

【删除】假设我们把 hors 变为 ros 的莱文斯坦距离记为v,即:


# 字符串A的前4个字符 和 字符串B的前3个字符 的莱文斯坦距离为 v
lev(4,3) = v

则 horse 期望变为 ros,其所需的编辑次数不会超过 v+1。因为 horse 只需先进行一次删除操作变为 hors,再经过v次编辑操作即可变为 ros

【替换】假设我们把 hors 变为 ro 的莱文斯坦距离记为w,即


# 字符串A的前4个字符 和 字符串B的前2个字符 的莱文斯坦距离为 w
lev(4,2) = w

则 horse 期望变为 ros,其所需的编辑次数不会超过 w+1。因为 horse 只经过w次编辑操作即可变为 roe,然后通过一次替换操作,将尾部的e字符替换为s字符即可。

得出莱文斯坦距离满足如下的递推公式


lev(horse, ros) = lev(5,3)
= min( lev(5,2)+1, lev(4,3)+1, lev(4,2)+1 )
= min(u+1, v+1, w+1)

如果 某字符串A的第i个字符 与 某字符串B的第j个字符 完全相同,则其所需的编辑次数肯定不会超过 lev(i-1, j-1)。因为无需进行替换,可跳过该步骤。

通过上面的分析过程,我们其实不难看出。如果期望 字符串A的前i个字符 与 字符串B的前j个字符 完全相同。可以有如下三种途径操作方式进行实现。而最终的莱文斯坦距离就是下面三种实现方式中次数最小的一个。

  1. 在 字符串A的前i个字符 与 字符串B的前j-1个字符 完全相同的基础上,进行一次「插入」操作
  2. 在 字符串A的前i-1个字符 与 字符串B的前j个字符 完全相同的基础上,进行一次「删除」操作
  3. 在 字符串A的前i-1个字符 与 字符串B的前j-1个字符 完全相同的基础上,如果字符串A的第i个字符与字符串B的第j个字符不同,则需要进行一次「替换」操作;如果字符串A的第i个字符与字符串B的第j个字符相同,则无需进行任何操作。

参考文章:https://zhuanlan.zhihu.com/p/507830576

3. R语言代码实现

构建lev_dist()函数,实现莱文斯坦距离,使用递归方法进行实现。想了一种简单的实现方法,但效率太低,看看就好,千万不要用到实际的算法中。等有时间,我再换个思路实现一下。


#######################################
# Levenshtein 莱文斯坦距离,递归实现(效率很低)
######################################
> lev_dist<-function(txt1,txt2){
+   len1<-nchar(txt1)
+   len2<-nchar(txt2)
+   
+   if(len1==0) return(len2)
+   if(len2==0) return(len1)
+   
+   # 插入消耗
+   insert_cost <- lev_dist(txt1, substring(txt2,1,len2-1)) + 1;
+   
+   # 删除消耗
+   delete_cost <- lev_dist(substring(txt1,1,len1-1), txt2) + 1;
+   
+   # 替换消耗
+   cost<-ifelse(substring(txt1,len1,len1) == substring(txt2,len2,len2),0,1)
+   replaces_cost <- lev_dist(substring(txt1,1,len1-1), substring(txt2,1,len2-1)) + cost;
+   
+   rs<-min(insert_cost,delete_cost,replaces_cost)
+   print(paste("txt1:",txt1,"txt2:",txt2,"insert:",insert_cost,"delete:",delete_cost,"replaces:",replaces_cost))
+   return(rs)
+ }

对结果进行测试


# 测试ab和a的情况
> lev_dist("ab","a")
[1] "txt1: a txt2: a insert: 2 delete: 2 replaces: 0"
[1] "txt1: ab txt2: a insert: 3 delete: 1 replaces: 2"
[1] 1

# 测试ab和abc的情况
> lev_dist("ab","abc")
[1] "txt1: a txt2: a insert: 2 delete: 2 replaces: 0"
[1] "txt1: ab txt2: a insert: 3 delete: 1 replaces: 2"
[1] "txt1: a txt2: a insert: 2 delete: 2 replaces: 0"
[1] "txt1: a txt2: ab insert: 1 delete: 3 replaces: 2"
[1] "txt1: a txt2: a insert: 2 delete: 2 replaces: 0"
[1] "txt1: ab txt2: ab insert: 2 delete: 2 replaces: 0"
[1] "txt1: a txt2: a insert: 2 delete: 2 replaces: 0"
[1] "txt1: a txt2: ab insert: 1 delete: 3 replaces: 2"
[1] "txt1: a txt2: abc insert: 2 delete: 4 replaces: 3"
[1] "txt1: a txt2: a insert: 2 delete: 2 replaces: 0"
[1] "txt1: a txt2: ab insert: 1 delete: 3 replaces: 2"
[1] "txt1: ab txt2: abc insert: 1 delete: 3 replaces: 2"
[1] 1

让单词变长,虽然莱文斯坦距离并不大,但是计算次数是相当的多,效率非常低。


> lev_dist("kitten","sitting")
....
....
// 省略
3

用递归的方式,虽然比较容易实现,但是效率太低,没有办法是应用中使用。

4. adist()函数

在R的基础包utils中,找到了 adist()函数,就实现了莱文斯坦距离,我们可以直接使用adist()来完成,莱文斯坦距离的计算。还是R语言原生的程序效率高!!

分别测试 house 到 rose,horse 到 ros的 莱文斯坦距离。


# 
> adist("house","rose")
     [,1]
[1,]    2
> adist("horse","ros")
     [,1]
[1,]    3

查看替换sub 、插入ins 、删除del ,分别使用了几次。


> drop(attr(adist("horse", "rose", counts = TRUE), "counts"))
ins del sub 
  0   1   1 

按顺序查看替换、插入、删除的操作步骤,S=替换,M为跳过,D为删除,I为插入
> attr(adist("horse", "rosxeee", counts = TRUE), "trafos")
     [,1]      
[1,] "SMDMIIIM"

本文我们了解了莱文斯坦距离的原理和实现,后面我们就可以利用莱文斯坦距离的特性,对文字进行相似度的距离计算,从而实现文本的模糊匹配。本文代码:https://github.com/bsspirit/r-string-match/blob/main/levenshtein.r

转载请注明出处:
http://blog.fens.me/r-levenshtein-distance/

打赏作者

用R语言实现字符串快速匹配算法KMP

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-kmp/

前言

文字匹配是字符符处理操作时,最常用到的一种方法。比如我们想从一段长文本中,找到是否有我想要的词,可以用于在图书中用关键词进行搜索,这样就可以定位到具体的位置。当文本长度巨大,且匹配字符串长度过长时,这种匹配就会有效率问题,很变的很慢。

那么我们可以用KMP的算法思路,在提升文字精确匹配的效率。本文代码:https://github.com/bsspirit/r-string-match

目录

  1. 字符串匹配:暴力破解法
  2. KMP算法解释和实现
  3. KMP和暴力破解算法对比

1. 字符串匹配:暴力破解法

一般的字符串匹配算法,是将 2个字符串每个字符挨个进行比较,相当于是把每个字符都比较了一遍,做了对所有字符的组合,这样操作导致的时间复杂度是O(m*n),也就是 2 个字符串长度的积,俗称暴力解法。

我们设定原始字符串为:ABDABDZ ABCED,匹配字符串为:ABC。直接使用暴力法进行字符串匹配。

首先,建立暴力破解的字符串匹配函数bad_match(),包括4个参数。

  • txt,原始文本的字符串
  • pattern,匹配的字符串
  • n,用于取匹配前几个,默认为0,表示全匹配
  • LOGGER,用于显示日志

# 清空环境变量
> rm(list=ls())

# 设置运行目录
> setwd("C:/work/R/text")

# 建立字符串匹配函数:暴力破解法
> # 暴力破解法
> baoli_match<-function(txt,pattern,n=0,LOGGER=FALSE){
+   rs<-data.frame(start=0,end=0)  # 默认返回值
+   start<-0                       # 命中后在原始字符串的开始位置
+   
+   n1<-nchar(txt)                 # 原始字符串长度
+   n2<-nchar(pattern)             # 匹配的字符串长度
+   
+   # 如果匹配的字符串为空,则返回
+   if(n2==0) return(r2)          
+   
+   # 初始化变量索引,i用于原始字符串,j用于匹配字符串
+   i<-j<-1
+   # 用于计数,循环了多少次
+   k<-0
+   
+   # 循环计算
+   while(i < n1){
+     
+     # 打印日志
+     if(LOGGER){  
+       print(paste(i,j,substr(txt, i, i),substr(pattern, j, j),sep=","))  
+       k<-k+1
+     }
+     
+     # 匹配成功,同时移动
+     if(substr(txt,i,i) == substr(pattern,j,j)){ 
+       i<-i+1
+       j<-j+1
+     } else { # 匹配不成功,回到开始匹配的位置,重置i,j的索引
+       i<-i-(j-1)  
+       i<-i+1
+       j<-1
+     }
+     
+     # 把匹配到的,所有结果存到变量
+     if(j==(n2+1)) {
+       start<-append(start,i-n2)
+       j<-1
+       
+       # 只取前面n个结果返回
+       if(n > 0 && n==length(start)-1){
+         break;
+       }
+     }
+   }
+   
+   # 打印日志,输出循环了多少次
+   if(LOGGER){
+     print(paste("k",k,sep="="))
+   }
+   
+   # 拼接返回值,为data.frame
+   if(length(start) > 1) {
+     start<-start[-1]
+     rs<-data.frame(start=start,end=start+n2-1)
+   }
+   return(rs)
+ }

输出字符串,运行结果。


# 原始字符串
> txt<-"ABCCADZABCCABBC"

# 匹配字符串
> pattern<-"ABCCABB"

# 暴力匹配
> baoli_match(txt,pattern,LOGGER=TRUE)
[1] "1,1,A,A"
[1] "2,2,B,B"
[1] "3,3,C,C"
[1] "4,4,C,C"
[1] "5,5,A,A"
[1] "6,6,D,B"
[1] "2,1,B,A"
[1] "3,1,C,A"
[1] "4,1,C,A"
[1] "5,1,A,A"
[1] "6,2,D,B"
[1] "6,1,D,A"
[1] "7,1,Z,A"
[1] "8,1,A,A"
[1] "9,2,B,B"
[1] "10,3,C,C"
[1] "11,4,C,C"
[1] "12,5,A,A"
[1] "13,6,B,B"
[1] "14,7,B,B"

# 循环共20次
[1] "k=20"
     
# 匹配到1个结果,对应用到原始字符串的开始位置和结束位置
  start end
1     8  14

2. KMP算法介绍

KMP 算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 提出的,因此人们称它为 Knuth-Morris-Pratt算法(简称KMP)。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 kmp_next () 函数实现,函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度O(m+n)。

建立kmp_next() 函数,匹配字符串的最长公串。


# 建立匹配字符串的最长公串
> kmp_next <- function(patten,LOGGER=FALSE) {
+   n <- nchar(patten)
+   nxt <- rep(0, n)
+   i <- 2
+   j <- 1
+   while (i < n) {
+     if(LOGGER){
+       print(paste(i,j,substr(patten, i, i),substr(patten, j, j),sep=","))  
+     }
+     if (substr(patten, i, i) == substr(patten, j, j)) {
+       nxt[i] <- j
+       i = i + 1
+       j = j + 1
+     } else{
+       if (j > 1) {
+         j = nxt[j - 1]
+       }
+       else{
+         nxt[i] = 0
+         i = i + 1
+       }
+     }
+   }
+   nxt
+ }

运行计算结果,ABC的最长公串为0,ABCCABB最长公串,为1和2。


> kmp_next("ABC")
[1] 0 0 0

> kmp_next("ABCCABB")
[1] 0 0 0 0 1 2 0

建立KMP算法函数,使用kmp_next()最长公串的结果,减少循环的次数。


> kmp_match<-function(txt, patten, n=0, LOGGER=FALSE) {
+   rs<-data.frame(start=0,end=0)  # 默认返回值
+   start<-0                       # 命中后在原始字符串的开始位置
+   n1<-nchar(txt)                 # 原始字符串长度
+   n2<-nchar(pattern)             # 匹配的字符串长度
+   
+   # 如果匹配的字符串为空,则返回
+   if(n2==0) return(rs)
+   
+   nxt<-kmp_next(patten)       #获取next最长公串
+ 
+   # 初始化变量索引,i用于原始字符串,j用于匹配字符串
+   i<-j<-1
+   # 用于计数,循环了多少次
+   k<-0
+   
+   # 循环计算
+   while(i1) j<-nxt[j-1]+1
+       else i<-i+1
+     }
+     
+     if(j==(n2+1)) {
+       start<-append(start,i-n2)
+       j<-1
+       
+       if(n>0 && n==length(start)-1){
+         break;
+       }
+     }
+   }
+   
+   # 打印日志,输出循环了多少次
+   if(LOGGER){
+     print(paste("k",k,sep="="))
+   }
+   
+   # 拼接返回值,为data.frame
+   if(length(start)>1) {
+     start<-start[-1]
+     rs<-data.frame(start=start,end=start+n2-1)
+   }
+   return(rs)
+ }

运行KMP算法,使用暴力破解法同样的参数,发现循环计算只运行了14次,比暴力破解法少了2次。


> txt<-"ABCCADZABCCABBC"
> pattern<-"ABCCABB"

> kmp_match(txt,pattern,LOGGER=TRUE)
[1] "pattern:ABCCABB,next:0000120"
[1] "1,1,A,A"
[1] "2,2,B,B"
[1] "3,3,C,C"
[1] "4,4,C,C"
[1] "5,5,A,A"
[1] "6,6,D,B"
[1] "6,2,D,B"
[1] "6,1,D,A"
[1] "7,1,Z,A"
[1] "8,1,A,A"
[1] "9,2,B,B"
[1] "10,3,C,C"
[1] "11,4,C,C"
[1] "12,5,A,A"
[1] "13,6,B,B"
[1] "14,7,B,B"

# 循环共16次
[1] "k=16"

# 匹配到1个结果,对应用到原始字符串的开始位置和结束位置
  start end
1     8  14

3. KMP和暴力破解算法对比

我们对比一下暴力破解法 和 KMP算法,具体的差异在什么问题,为什么能少算4次。

从下面循环对比的图中,我们可以明确的看到KMP算法,少的原因在于出现的匹配不一致时,暴力匹配是让匹配字符串回到1重新开始匹配,而KMP算法则是利用了next的最大公共串,找到上一个公共串的位置,这样就可以大幅提升遍历的效率。

KMP算法的原理的参考文献:阮一峰:字符串匹配的KMP算法

虽然R语言不擅长写算法,且while循环的性能也不高,但是如果能大幅减少循环的计算次数,也是一种不错的解决方案。自己写了一套字符串匹配的代码已经放到了github:https://github.com/bsspirit/r-string-match

一点一点的优化,从算法层搞起。

转载请注明出处:
http://blog.fens.me/r-kmp/

打赏作者