图解字符串相似算法

概念

百度百科
编辑距离（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