概念
百度百科
编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。
应用
- 拼写评测，可以定个规则，空格0.5分，标点0.5分，大小写1分，错误1分等。
- 模糊查询
算法
比如要计算cafe和coffee的编辑距离。cafe→caffe→coffee→coffee
下面看下怎么推算的？
| |c| o | f |f|e|e
-----|----|----|------|----|----|----|----
|0 | 1 | 2 | 3 | 4 |5 |6
c|1 | A=0=min(2,2,0) | E=1=min(1,3,2) |2 | 3 |4 | 5
a|2 | B=1=min(3,1,2) | F=1=min(2,2,1) | 2| 3 | 4| 5
f|3 | C=2=min(4,2,3) | G=2=min(3,2,2)| 1 | 2 | 3| 4
e|4 | D=3=min(5,3,4) |H=3=min(4,3,3)| 2 | 2 |2 |3
A处得值
它的值取决于：左边的1、上边的1、左上角的0.
按照Levenshtein distance的意思：
上面的值和左面的值都要求加1，这样得到1+1=2。
A处 由于是两个a相同，左上角的值加0.这样得到0+0=0。
依次类推，可以得到编辑距离3。
Objects代码
static inline int min(int a, int b) {
return a < b ? a : b;
}
@implementation NSString (GTRScore)
- (float)likePercent:(NSString *)target {
NSInteger n = self.length;
NSInteger m = target.length;
if (0 == m) {
return n;
}
if (0 == n) {
return m;
}
int matrix[n+1][m+1];
memset(&matrix[0], 0, m+1);
for (int i = 1; i <= n; i++) {
memset(&matrix[i], 0, m+1);
matrix[i][0] = i;
}
for (int i = 0; i <= m; i++) {
matrix[0][i] = i;
}
for (int i = 1; i <= n; i++) {
unichar si = [self characterAtIndex:i-1];
for (int j = 1; j <= m; j++) {
unichar dj = [target characterAtIndex:j-1];
int cost;
if (si == dj) {
cost = 0;
} else {
cost = 1;
}
const int above = matrix[i-1][j]+1;
const int left = matrix[i][j-1]+1;
const int diag = matrix[i-1][j-1]+cost;
matrix[i][j] = min(above, min(left, diag));
}
}
return 100.0 - 100.0*matrix[n][m]/self.length;
}
@end
测试代码
#import "NSString+GTRScore.h"
NSString *str = @"cafe";
CGFloat f = [str likePercent:@"coffee"];
NSLog(@"========%f",f);
2016-11-15 17:27:44.643 GTRStringScore[8118:4157093] ========25.000000
