- 浏览: 277776 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (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 3745问题背景 在操作系统的内存管理里,如何节省有限的内存并为尽可 ... -
数据结构之位图bitmap
2012-05-10 23:12 0http://dongxicheng.org/structur ... -
常见数据结构与算法汇总
2012-05-10 23:01 11051、常见数据结构 线性:数组,链表,队列, ... -
数据结构之位图
2012-05-10 18:34 5661介绍 (20120511)位图就是通过将数组下标与应用中 ... -
CRC循环校验
2012-05-10 15:11 1366http://www.360doc.com/content/1 ... -
map3搜索与存储的一道面试题
2012-05-10 15:10 922假设一个mp3搜索引擎收录了2^24首歌曲,并记录了可收听这些 ... -
排序算法
2012-04-21 23:06 675插入排序 shell排序 ... -
【编程珠矶】开篇 千万号码的排序问题
2012-04-21 12:52 939注:学习了《编程珠矶》第一章,将涉及的一些知识点整理如下 ... -
WXXR LRUList的实现
2012-03-01 16:01 777LRUList -
【专题】分治递归+排序算法
2012-03-01 11:47 717123 -
【排序】merge排序
2012-02-28 09:59 881前言 主要学习 http://en.wikipedia.or ... -
【排序】快速排序
2012-02-27 18:40 938前言 快速排序(Quick Sort)算法是 “递归+分治” ... -
算法类博客推荐
2012-02-24 18:17 6331. http://blog.csdn.net/v_J ... -
递归与分治
2012-02-24 18:16 1005分治与递归基本思想 分治:分治强调“分 ... -
Apache LRUMap实现
2012-02-23 13:10 1099源码是 org.apache.commons.collect ... -
WXXR LRUMap的实现
2012-02-22 18:33 1887前言 实现LRU算法,注意观察者模式、并发(读写锁、线程池) ... -
【专题】LRU
2012-02-22 16:21 1529包含如下内容: 一. LRU算法 ht ... -
LRU理论
2012-02-21 18:46 10321.LRU算法介绍 LRU是Least Rec ... -
【排序算法】冒泡排序(bubble sort)
2012-02-19 12:16 0问题描述 将一组乱序的整形按照由小到大排序 算法思路 经 ... -
【Core Java】并发集合
2012-02-02 17:05 1136并发容器与同步容器 ...
相关推荐
BM算法是比KMP更快的字符串匹配算法,它的理论时间复杂度也是O(n+m),但实际上它的平均速度比KMP快很多。BM算法的原理是考虑O(nm)的暴力对比进进行字符串匹配,我们总是希望某次失配后能根据已有信息进行尽可能多的...
字符串的模式匹配算法在计算机科学中占据着重要的地位,它主要应用于文本搜索、数据分析和文本处理等领域。KMP(Knuth-Morris-Pratt)算法是其中一种高效的算法,尤其适用于处理具有重复子串的模式匹配问题。接下来...
在此背景下,Boyer和Moore于1977年提出了一种革命性的字符串匹配算法——Boyer-Moore算法,该算法不仅在理论上具有线性时间复杂度的优势,在实际应用中也展现出极高的效率,尤其是在处理长文本和模式时。随后,R....
在这个主题中,我们将探讨三种经典的字符串匹配算法:穷举法、KMP(Knuth-Morris-Pratt)算法和BM(Boyer-Moore)算法。 1. **穷举法**:也称为朴素匹配算法,是最直观的字符串匹配方法。它通过比较主串中的每个...
### 字符串匹配算法小集解析 #### 一、引言 本文档提供了一系列共35种不同的字符串匹配算法,这些算法在英文环境下被广泛讨论和应用。通过对这些算法进行详细的解析,我们可以更好地理解每种算法的特点、应用场景...
根据提供的信息,《PDF电子书《柔性字符串匹配》》主要探讨了与字符串匹配相关的算法知识。字符串匹配是计算机科学中的一个核心问题,在文本处理、搜索引擎、生物信息学等多个领域都有着广泛的应用。下面将从不同的...
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、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的...
字符串模式匹配算法在此过程中扮演了核心角色,因为它可以高效地查找可能的病毒签名或恶意代码序列。本话题将深入探讨如何利用C语言实现基于字符串模式匹配算法的病毒感染检测。 首先,我们需要了解字符串模式匹配...
BM算法,全称为Boyer-Moore字符串搜索算法,是一种高效的字符串匹配算法。该算法由Robert Boyer和J Strother Moore提出,主要用于在一个主字符串(text)中查找模式字符串(pattern)的出现位置。BM算法的核心思想...
字符串匹配算法是计算机科学中一个经典而基础的问题,几乎存在于所有需要处理文本的领域。随着互联网和信息技术的快速发展,人们处理的数据量呈爆炸式增长,这导致了对高效字符串匹配算法的需求日益迫切。传统的串行...
在这个话题中,我们将深入探讨几种经典的字符串匹配算法,包括Bad Character Heuristic(BM算法)和Knuth-Morris-Pratt(KMP算法)。 **Bad Character Heuristic (BM算法)** BM算法是由Sunday和Sunday在1977年提出...
在IT领域,字符串匹配算法是计算机科学中一个基础且重要的概念,特别是在文本处理、搜索引擎和数据挖掘等应用中。本项目关注的是一个C语言实现的文件中字符串匹配算法,其核心目标是读取名为"input.txt"的文件,根据...
本文将详细解析三种常见的字符串匹配算法:Brute Force(暴力搜索)、KMP(Knuth-Morris-Pratt)以及BM(Boyer-Moore)。这些算法在文本处理、数据搜索、生物信息学等多个领域有着广泛的应用。 首先,让我们来了解...
**Sunday字符串匹配算法详解** Sunday算法,全称为Sunday's Simple String Matching Algorithm,是由E. W. Dijkstra在1976年提出的一种高效字符串匹配算法。这个算法在单字符串匹配领域具有较高的性能,其主要特点...
KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法。它的主要思想是在发生不匹配时,能知道部分已经匹配的字符序列的后缀和模式串的前缀存在重复,因此可以利用这些信息避免...
### 字符串匹配算法概述 #### 1. 引言 在信息学竞赛与实际应用领域中,字符串处理占据着极其重要的地位。虽然表面上看似简单的字符串处理问题,却蕴含着丰富的算法思想和技术挑战。本篇文章将详细介绍由ACM金牌...