首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

计算字符串相似算法——Levenshtein

0.这个算法实现起来很简单 1.百百科介绍: Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需最少编辑操作次数。...许可编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。 编辑距离算法是首先由俄国科学家Levenshtein提出,故又叫Levenshtein Distance。...g.计算相似 先取两个字符串长度最大值maxLen,用1-(需要操作数除maxLen),得到相似。 例如abc 和abe 一个操作,长度为3,所以相似为1-1/3=0.666。...("差异步骤:"+dif[len1][len2]); 52 //计算相似 53 float similarity =1 - (float) dif[len1][...3.还是没弄懂 6.结束 算法优化空间很大。 最后也没弄懂为什么这样算能算出相似

6.9K10

字符串相似算法-莱文斯坦距离算法

莱文斯坦(Levenshtein)距离 莱文斯坦距离可以解决字符串相似问题。...在莱文斯坦距离中,对每一个字符都有三种操作:删除、添加、替换 例如有s1和s2两个字符串,a和b是与之对应保存s1和s2全部字符数组,i/j是数组下标。...举个例子,字符串"kitten" 与“sitting” 莱文斯坦距离是3,因为将kitten变为sitting,最少需要三次变换: 第一步 kitten -> sitten (字符k变成s) sitten...0.12.0‑cp36‑cp36m‑win_amd64.whl linux安装 pip 安装Levenshtein模块 pip install python-Levenshtein 计算两个字符串相似...list相似 import Levenshtein import jieba autohome='2009款 1.6L 自动G特别版' #current='花冠 2009款 1.6L 自动G特别版

2.9K20
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    文本相似计算_文本相似分析算法

    大家好,又见面了,我是你们朋友全栈君。 这篇文档简单介绍一下Simhash算法 一....Simhash 计算文档相似算法, 比如用在搜索引擎爬虫系统中,收录重复网页是毫无意义,只会造成存储和计算资源浪费。...有时候我们需要处理类似的文档,比如新闻,很多不同新闻网新闻内容十分相近,标题略有相似。如此问题,便可以应用Simhash 文档相似算法,查看两篇文档相似程度,删去相似web文档。 二....Google就是基于此算法实现网页文件查重。...但是,使用上述方法产生simhash用来比较两个文本之间相似,将其扩展到海量数据近重复检测中去,时间复杂和空间复杂都太大。

    1.3K20

    图片相似识别:aHash算法

    aHash、pHash、dHash是常用图像相似识别算法,原理简单,实现方便,个人把这三个算法作为学习图片相似识别的入门算法。本次起,从aHash开始,对三个算法基本原理和实践代码进行梳理。...1 aHash算法 Hash算法进行图片相似识别的本质,就是将图片进行Hash转化,生成一组二进制数字,然后通过比较不同图片Hash值距离找出相似图片。...距离越近,越相似。当图片缩小为8*8时,通常认为汉明距离小于10一组图片为相似图片。...2 Python实现 本例中将计算以下两张图片相似: (image1) (image2) 图像处理库 图像处理可以用opencv包或者PIL包。...hash1 = aHash(image1) hash2 = aHash(image2) dist = Hamming_distance(hash1, hash2) #将距离转化为相似

    4.7K30

    图片相似识别:pHash算法

    前面已经整理了aHash和dHash算法原理和python代码(戳:图片相似识别:aHash算法,图片相似识别:dHash算法),今天来介绍hash三兄弟最后一个——pHash。...DCT变换是对称,因此可以对经过DCT变换图片进行还原操作。 3 Python实现 本例中依然计算以下两张图片相似: ? (image1) ?...(image2) 完整算法 这里同步给出三种hash完整代码,便于进行效果比较。...下面通过PIL进行算法实现(此部分DCT变换为自己写,如有错误欢迎指出): from PIL import Image import os import numpy as np import time...从上述例子也可以看出,用不同方法最后相似度数值不同,因此在实际应用中还需结合实际效果不断调整确定阈值。

    7K10

    文本相似算法小结

    分词 + 杰卡德系数 首先是最简单粗暴算法。为了对比两个东西相似,我们很容易就想到可以看他们之间有多少相似的内容,又有多少不同内容,再进一步可以想到集合交并集概念。...假设有两个集合A,B;如果我们想要知道这两个集合相似究竟有多少,我们可以进行如下计算: [hq9gt0ogba.jpeg] 这个结果称为杰卡德相似系数,越大表明两个集合相似越高。...值得一提是,空间向量+余弦相似这个算法也被广泛地应用于推荐系统中(据说网易云推荐就是基于这个算法),这里也展开一下对应思路。...基于相似推荐算法,其实就是根据已有的用户行为数据去推断一个新用户可能做出下一个行为。具体举个例子,比如网易云电台推荐。...这样做好处是,我们向量从词维度下降到文本主题维度,维度更少,计算更快。 其他 简要提一下其他相似/距离公式和算法,在某些场景下也会是不错选择。 1.

    5K100

    用C#实现字符串相似算法(编辑距离算法 Levenshtein Distance)

    在搞验证码识别的时候需要比较字符代码相似用到“编辑距离算法”,关于原理和C#实现做个记录。...计算相似公式:1-它们距离/两个字符串长度最大值。 为了直观表现,我将两个字符串分别写到行和列中,实际计算中不需要。...要实现此算法,首先需要明确“字符串近似”概念。     计算字符串相似通常使用是动态规划(DP)算法。     常用算法是 Levenshtein Distance。...一个一个涂画之后,偶然发现另一种字符串相关算法完全可以适用。那就是 Longest common subsequence(LCS,最长公共字串)。为什么这个算法可以用来计算两个字符串相关?...这样处理目的是为了避免得到较长匹配结果(类似正则表达式贪婪、懒惰模式)。     以上只是描述了怎么计算两个字符串相似程度。除此之外还需要:①剔除相似较低结果;②对结果进行排序。

    6K61

    相似计算——余弦相似

    余弦相似介绍 余弦相似是利用两个向量之间夹角余弦值来衡量两个向量之间相似,这个值范围在-1到1之间。...两个向量夹角示例图如下: 余弦相似计算公式 向量余弦相似计算公式 余弦相似计算示例代码 用Python实现余弦相似计算时,我们可以使用NumPy库来计算余弦相似,示例代码如下: import...(norm_x) 余弦相似应用 余弦相似相似计算中被广泛应用在文本相似、推荐系统、图像处理等领域。...如在文本相似计算中,可以使用余弦相似来比较两个文档向量表示,从而判断它们相似程度。 又如在推荐系统中,可以利用余弦相似来计算用户对不同商品喜好程度,进而进行商品推荐。...如果两篇文章余弦相似接近1,那么它们在内容上是相似的; 如果余弦相似接近0,则它们在内容上是不相似的。 这样相似计算方法可以在信息检索、自然语言处理等领域得到广泛应用。

    21610

    字符串相似匹配算法_java逻辑表达式解析

    阅读博客朋友可以参看视频: 如何进入google,算法面试技能全面提升指南 什么叫有限状态自动机 先看一个图: 上面这个图描述就叫一个有限状态自动机,图中两个圆圈,也叫节点,用于表示状态...在每一个步骤中,我们都需要从P第一个字符开始,看看最多能连续读取几个字符,使得他们能成为S后缀,假设P字符个数为m, 那么这个读取过程最多需要读取m个字符,于是复杂为O(m)....K, 使得P[1…k] 是字符串 Pq P_q后缀,该调用有两层循环,所以复杂是O( m2 m^2), makeJumpTable有两层循环,循环次数为O(m*| ∑ \sum|), 所以makeJumpTable...总时间复杂为O( m3 m^3| ∑ \sum|), 也就是说,构建跳转表复杂是:O( m3 m^3| ∑ \sum|)。...我们只给出了算法实现流程,算法数学原理比较复杂,我们将在下一节详解。

    1.2K40

    文本相似——自己实现文本相似算法(余弦定理)

    于是我决定把它用到项目中,来判断两个文本相似。...,所以每两个章节之间都要比较,若一本书书有x章的话,这 里需对比x(x-1)/2次;而此算法采用矩阵方式,计算两个字符串之间变化步骤,会遍历两个文本中每一个字符两两比较,可以推断出时间复杂至少...想到Lucene中评分机制,也是算一个相似问题,不过它采用是计算向量间夹角(余弦公式),在google黑板报中:数学之美(余弦定理和新闻分类) 也有说明,可以通过余弦定理来判断相似;于是决定自己动手试试...,        最后我们相似可以这么计算: ?        ...最后写了个测试,根据两种不同算法对比下时间,下面是测试结果:        余弦定理算法:doc1 与 doc2 相似为:0.9954971, 耗时:22mm        距离编辑算法:doc1

    1.1K31

    均值哈希算法计算图片相似

    均值哈希算法一张图片就是一个二维信号,它包含了不同频率成分。亮度变化小区域是低频成分,它描述大范围信息。而亮度变化剧烈区域(比如物体边缘)就是高频成分,它描述具体细节。...所以我们平时下采样,也就是缩小图片过程,实际上是损失高频信息过程。均值哈希算法就是利用图片低频信息。具体步骤:(1)缩小尺寸:将图片缩小到8x8尺寸,总共64个像素。...最后得到两张图片指纹信息后,计算两组64位数据汉明距离,即对比数据不同位数,不同位数越少,表明图片相似越大。...分析: 均值哈希算法计算速度快,不受图片尺寸大小影响,但是缺点就是对均值敏感,例如对图像进行伽马校正或直方图均衡就会影响均值,从而影响最终hash值。...#均值哈希算法def aHash(image): #缩放为8*8 image=cv2.resize(image,(8,8),interpolation=cv2.INTER_CUBIC)

    1.2K10

    相似与距离算法种类总结

    6、海明距离(Hamming distance) 定义:在信息论中,两个等长字符串之间汉明距离是两个字符串对应位置不同字符个数。...场景:在海量物品相似计算中可用simHash对物品压缩成字符串,然后使用海明距离计算物品间距离 二、相似度度量(9种) 相似度度量(Similarity),即计算个体间相似程度,与距离度量相反...,相似度度量值越小,说明个体间相似越小,差异越大 1、余弦相似(Cosine Similarity) 2、调整余弦相似(Adjusted Cosine Similarity) 3、皮尔森相关系数...6、对数似然相似率 7、互信息/信息增益,相对熵/KL散 8、信息检索–词频-逆文档频率(TF-IDF) 9、词对相似–点间互信息 三、距离度量与相似度度量区别 欧氏距离是最常见距离度量,而余弦相似则是最常见相似度度量...; 而余弦相似更多是从方向上区分差异,而对绝对数值不敏感, 更多用于使用用户对内容评分来区分用户兴趣相似和差异,同时修正了用户间可能存在度量标准不统一问题(因为余弦相似对绝对数值不敏感

    1.2K40

    【机器学习】几种相似算法分析

    大家好,又见面了,我是你们朋友全栈君。 最近开始研究推荐系统,其中常见相似算法有以下几种: 1....适用范围 适用于A评价普遍高于B评价 3. 余弦相似 余弦距离,也称为余弦相似,是用向量空间中两个向量夹角余弦值作为衡量两个个体间差异大小度量。...那么是否可以在(用户-商品-行为数值)矩阵基础上使用调整余弦相似计算呢?从算法原理分析,复杂虽然增加了,但是应该比普通余弦夹角算法要强。...“判断两段文本语义相似事情,实验中用doc2vec做文本向量化,用余弦值衡量文本相似。 为什么选用余弦?...那么如果用欧式距离计算相似,a和b相似就比a和c相似高,而如果用余弦计算,则答案反之。 那么欧式距离和余弦相似区别是什么呢?

    1.7K30

    Spark实现推荐系统中相似算法

    在推荐系统中,协同过滤算法是应用较多,具体又主要划分为基于用户和基于物品协同过滤算法,核心点就是基于"一个人"或"一件物品",根据这个人或物品所具有的属性,比如对于人就是性别、年龄、工作、收入、喜好等...,找出与这个人或物品相似的人或物,当然实际处理中参考因子会复杂多。...本篇文章不介绍相关数学概念,主要给出常用相似算法代码实现,并且同一算法有多种实现方式。...denominator == 0) Double.NaN else member / (denominator * 1.0) } 大家如果在实际业务处理中有相关需求,可以根据实际场景对上述代码进行优化或改造,当然很多算法框架提供一些算法是对这些相似算法封装...比如Spark MLlib在KMeans算法实现中,底层对欧几里得距离计算实现。

    91810

    文本相似 | 余弦相似思想

    计算文本相似有什么用?...推荐系统 在微博和各大BBS上,每一篇文章/帖子下面都有一个推荐阅读,那就是根据一定算法计算出来相似文章。...冗余过滤 我们每天接触过量信息,信息之间存在大量重复,相似可以帮我们删除这些重复内容,比如,大量相似新闻过滤筛选。 这里有一个在线计算程序,你们可以感受一下 ?...余弦相似思想 余弦相似,就是用空间中两个向量夹角,来判断这两个向量相似程度: ?...相似,个么侬就好好弄一个相似程度好伐?比如99%相似、10%相似,更关键是,夹角这个东西—— 我不会算! 谁来跟我说说两个空间向量角度怎么计算?哪本书有?

    2.8K70
    领券