- 浏览: 278482 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (161)
- 【**计划】 (2)
- 【**Core Java**】 (30)
- 【**JAVA EE】 (6)
- JDBC (3)
- Hibernate专题系列 (0)
- 【**OS】 (14)
- 【**架构设计/设计模式】 (11)
- 【Hadoop】 (3)
- 【**分布式】 (9)
- 模板 (1)
- C (2)
- 常用工具 (1)
- Oracle (2)
- 【Tips】 (3)
- 【数据库】 (2)
- 玩转Ubuntu (0)
- 【计算机网络/网络编程】 (7)
- 【**Search Engine】 (21)
- 【**专题**】 (6)
- 【**Python】 (10)
- XML (1)
- 【**Open Source Framework】 (1)
- 【高级主题】 (1)
- 【存储】 (3)
- 【笔试面试】 (2)
- 【**数据结构与算法设计】 (20)
- 【其他】 (3)
- 【编程练习】 (2)
- 【待完成】 (12)
- 【工作】 (6)
- 【软件研发】 (4)
- 【**多线程多进程编程】 (5)
- 【Web Service】 (1)
- 【表达式解析/JavaCC系列】 (5)
- 【缓存系统:Memcached】 (1)
- 【Java IO/NIO】 (5)
- 【JVM运行机制及内存管理】 (7)
最新评论
-
107x:
...
python list排序 -
yuzhu223:
...
【Python基础】Python的lambda函数与排序 -
Tonyguxu:
分析查询结果的打分小于11.query=1065800715* ...
lucene打分机制的研究 -
Tonyguxu:
query=139320661963.013709 = (MA ...
lucene打分机制的研究 -
Tonyguxu:
query=10658007150.6772446 = (MA ...
lucene打分机制的研究
如何比较两个字符串之间的相似程度(或者差异)?
想要比较两个字符串之间的相似程度,可以看其中一个字符串通过几步操作可以转换为另一个字符串,通过度量转换操作的步数可以来衡量两个串的相似程度,如果转换步数越少,则两者越匹配。这里转换操作的度量就称为:
edit distance。该值越小,则两个字符串越匹配。
但是对edit distance有不同的definition
http://en.wikipedia.org/wiki/Edit_distance写道
edit distance between two strings of characters generally refers to the Levenshtein distance.
However,The term ‘edit distance’ is sometimes used to refer to the distance in which insertions and deletions have equal cost and replacements have twice the cost of an insertion”
There are several different ways to define an edit distance, depending on which edit operations are allowed: replace, delete, insert, transpose, and so on.
However,The term ‘edit distance’ is sometimes used to refer to the distance in which insertions and deletions have equal cost and replacements have twice the cost of an insertion”
There are several different ways to define an edit distance, depending on which edit operations are allowed: replace, delete, insert, transpose, and so on.
相应的也有不同的算法来计算这个值,常见的有Levenshtein distance
Levenshtein distance
http://en.wikipedia.org/wiki/Levenshtein_distance 写道
The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.
算法基本步骤
1 | Set n to be the length of s. Set m to be the length of t. If n = 0, return m and exit. If m = 0, return n and exit. Construct a matrix containing 0..m rows and 0..n columns. |
2 | Initialize the first row to 0..n. Initialize the first column to 0..m. |
3 | Examine each character of s (i from 1 to n). |
4 | Examine each character of t (j from 1 to m). |
5 |
If s[i] equals t[j], the cost is 0. If s[i] doesn't equal t[j], the cost is 1. |
6 | Set cell d[i,j] of the matrix equal to the minimum of: a. The cell immediately above plus 1: d[i-1,j] + 1. b. The cell immediately to the left plus 1: d[i,j-1] + 1. c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost. |
7 | After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m]. |
比较"GUMBO"和"GAMBOL"的相似程度,计算两者的edit distance
参考
1.Levenshtein_distance
http://www.merriampark.com/ld.htm
http://en.wikipedia.org/wiki/Levenshtein_distance
2.Edit_distance
http://en.wikipedia.org/wiki/Edit_distance
发表评论
-
LRU算法介绍
2012-06-05 22:30 3749问题背景 在操作系统的内存管理里,如何节省有限的内存并为尽可 ... -
数据结构之位图bitmap
2012-05-10 23:12 0http://dongxicheng.org/structur ... -
常见数据结构与算法汇总
2012-05-10 23:01 11081、常见数据结构 线性:数组,链表,队列, ... -
数据结构之位图
2012-05-10 18:34 5664介绍 (20120511)位图就是通过将数组下标与应用中 ... -
CRC循环校验
2012-05-10 15:11 1370http://www.360doc.com/content/1 ... -
map3搜索与存储的一道面试题
2012-05-10 15:10 926假设一个mp3搜索引擎收录了2^24首歌曲,并记录了可收听这些 ... -
排序算法
2012-04-21 23:06 690插入排序 shell排序 ... -
【编程珠矶】开篇 千万号码的排序问题
2012-04-21 12:52 941注:学习了《编程珠矶》第一章,将涉及的一些知识点整理如下 ... -
WXXR LRUList的实现
2012-03-01 16:01 777LRUList -
【专题】分治递归+排序算法
2012-03-01 11:47 728123 -
【排序】merge排序
2012-02-28 09:59 892前言 主要学习 http://en.wikipedia.or ... -
【排序】快速排序
2012-02-27 18:40 940前言 快速排序(Quick Sort)算法是 “递归+分治” ... -
算法类博客推荐
2012-02-24 18:17 6461. http://blog.csdn.net/v_J ... -
递归与分治
2012-02-24 18:16 1007分治与递归基本思想 分治:分治强调“分 ... -
Apache LRUMap实现
2012-02-23 13:10 1110源码是 org.apache.commons.collect ... -
WXXR LRUMap的实现
2012-02-22 18:33 1888前言 实现LRU算法,注意观察者模式、并发(读写锁、线程池) ... -
【专题】LRU
2012-02-22 16:21 1530包含如下内容: 一. LRU算法 ht ... -
LRU理论
2012-02-21 18:46 10381.LRU算法介绍 LRU是Least Rec ... -
【排序算法】冒泡排序(bubble sort)
2012-02-19 12:16 0问题描述 将一组乱序的整形按照由小到大排序 算法思路 经 ... -
【Core Java】并发集合
2012-02-02 17:05 1139并发容器与同步容器 ...
相关推荐
BM算法是比KMP更快的字符串匹配算法,它的理论时间复杂度也是O(n+m),但实际上它的平均速度比KMP快很多。BM算法的原理是考虑O(nm)的暴力对比进进行字符串匹配,我们总是希望某次失配后能根据已有信息进行尽可能多的...
带通配符的字符串匹配算法则是这个领域的延伸,它允许在模式字符串中包含特殊字符,如星号(*)或问号(?),以表示任意字符或单个任意字符。这种算法使得搜索更加灵活,可以适应更复杂的查询需求。 **通配符的含义** -...
在并行计算领域,串匹配算法也可以利用MPI(Message Passing Interface)进行分布式处理,将大文本字符串分割成多个部分,每个计算节点独立运行KMP算法,然后汇总结果。这种方法可以极大地提高处理大规模数据的效率...
字符串的模式匹配算法在计算机科学中占据着重要的地位,它主要应用于文本搜索、数据分析和文本处理等领域。KMP(Knuth-Morris-Pratt)算法是其中一种高效的算法,尤其适用于处理具有重复子串的模式匹配问题。接下来...
《多模式字符串匹配算法——AC_BM算法的深度解析与实现》 字符串匹配算法是计算机科学中的一个重要领域,尤其在文本处理、搜索引擎、数据挖掘等领域有着广泛应用。其中,AC_BM算法,即Aho-Corasick算法结合Boyer-...
本篇文章将详细探讨四种常见的字符串匹配算法:平凡算法(SimpleSM)、KMP算法(KMPSM)、BM算法(bmSM)以及RK算法(rkSM),并分析它们的基本原理和C代码实现。 1. **平凡算法(SimpleSM)** 平凡算法是最基础的...
常见的字符串匹配算法及实现
在不匹配时,算法会查找模式串中不匹配字符的位置,从而快速调整模式串的位置。这种方法减少了不必要的移动次数,提高了效率。 4. **Boyer-Moore算法**:Boyer和Moore设计的算法结合了bad-character heuristics和...
一般而言文本就是要编辑的文档,而模式字符串往往由用户来指定,高效的字符串匹配 算法可以提高程序的响应性能,当然字符串匹配算法的应用远远不止于此,例如在生物计算科学中查找特定的DNA序列,也是字符串匹配算法...
本章节将重点介绍字符串匹配的基本概念以及两种重要的算法——简单字符串匹配算法和KMP算法。 #### 一、简单字符串匹配算法 简单字符串匹配算法是最基础的一种方法,其基本思想是从文本串的第一个字符开始,逐个...
首先对三种基本字符串匹配算法进行了详细分析和说明,再编程实现。创新拓展研究了Boyer-Moore算法,进行了分析和编程实现。让四种算法对数据量极大的文本,进行子串的查询处理,并分析算法运行时间效率,并对所有...
在这一篇文章中,我们将详细介绍 C++ 中的字符串匹配算法,主要包括 Brute Force 算法和其他一些常见的字符串匹配算法。 Brute Force 算法 Brute Force 算法是最简单的字符串匹配算法,它的思想是将模式串与主串...
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
本篇文章将深入探讨如何使用C++实现Bad Character Rule(坏字符规则)和Good Suffix Rule(好后缀规则)来优化Boyer-Moore(BM)字符串匹配算法。BM算法以其高效的性能在文本搜索、数据挖掘等多个领域广泛应用。 ...
KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和 Vaughan Pratt三位学者在1970年代提出。该算法在处理字符串匹配问题时,避免了不必要的回溯,极大地提高了...
### 一种改进的字符串匹配算法:KMP算法详解 #### KMP算法简介 KMP算法是一种高效的字符串匹配算法,由D.E.Knuth、V.R.Pratt和J.H.Morris三位计算机科学家共同发现,因此得名为Knuth-Morris-Pratt算法(简称KMP...
KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
BM算法,全称为Boyer-Moore字符串搜索算法,是一种高效的字符串匹配算法。该算法由Robert Boyer和J Strother Moore提出,主要用于在一个主字符串(text)中查找模式字符串(pattern)的出现位置。BM算法的核心思想...
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
字符串模式匹配算法在此过程中扮演了核心角色,因为它可以高效地查找可能的病毒签名或恶意代码序列。本话题将深入探讨如何利用C语言实现基于字符串模式匹配算法的病毒感染检测。 首先,我们需要了解字符串模式匹配...