字符串纠错

故这样的,之前在 Leetcode 遇到一道题:『Edit Distance』, 当时做的时候并没有太多的思考,原因也很简单,不知道这道题的算法什么时候可以用得到。

直到,最近在看搜索引擎部分的算法,在处理用户的拼写异常的时候,比如,当用户搜索 『苏州大雪』的时候,怎么能进行纠错为『苏州大学』。

亦或者,在进行爬虫数据筛选的时候,比如在 B 站进行动漫数据抓取的时候,有很多的 UP 主会对动漫的名字做一定的修改,比如『(xx 字幕组)小林家的龙女仆』或者『小林家的龙女仆(高清)』。按照我之前的处理方式,还是很简单的 KV 存储,所以在计算弹幕和播放量的时候,并没有统计合并这样的数据。而从实际情况上来看的话,这两个的数据是应该统计在一起的。

所以,发现这个算法也是可以用的。而且,这个算法确实挺有意思。

using namespace std;

class Solution {
    public:
        int minDistance(string source, string target) {
            int m = source.length(), n = target.length();
            vector<vector<int> > DP(m + 1, vector<int> (n + 1, 0));
            for (int i = 1; i <= m; i++)
                DP[i][0] = i;
            for (int j = 1; j <= n; j++)
                DP[0][j] = j;

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (source[i - 1] == target[j - 1]) {
                        DP[i][j] = DP[i - 1][j - 1];
                    } else {
                        DP[i][j] = min(DP[i - 1][j - 1] + 1, min(DP[i][j - 1] + 1, DP[i - 1][j] + 1));
                    }
                }
            }
            return DP[m][n];
        }
}; 

核心算法也就是这么一点,而且时间复杂度来看的话,也只有 O(n^2),相对于 B 站动漫的数据(万级别),也是可以接受的。 同时,考虑到简单的写法空间复杂度为 O(MN),不过实际使用中,只会使用到两排的数据,其实也可以对 DP 数组进行压缩。不过,并没有那么急切。

算法确实很有意思。

但是,业界上,还有其他挺多的有趣的算法。比如非常工程化的字典,规则等等。这些通常是基于实践结果,而后进行的统计算法。 算法的准确度通常也需要人工介入。

说了这么多,其实也只是停留在拼写异常的纠错上。并没有加入同义词替换。比如说:『笔记本 内存8G』 和『笔记本电脑 大内存』这样的 query 串的合并。有个很好的办法就是对其商品进行加 tag,然后对关键词进行分类,将其转换成不同的 tag,然后根据 tag 进行数据的筛选。

当然,如果再要引入业务上的排序,这些,就会出现这样的一个架构设计:

搜索

最后的纠错,其实还是落在了字典的充实度上。爬取 B 站的动漫名,这样的集合还是非常容易获得的。可以从对应的网站,比如『豆瓣』,『IMDB』 等电影评论网站上获得所有的动漫的名字,然后更具相似度进行分类。

就目前的可控使用的搜索三方库来看的话,比如说 Lucene,他也并没有提供这么一个搜索串纠错的功能。同时参考其他公司的架构实现:

蘑菇街:

搜索

可以发现,很多的都是基于 Solr,或者 ELK。而对于 solr 而言,它提供了纠错的组件,比如,而仔细看下来,他的源码实现也是基于最短编辑路径的算法。

同时网上大量充斥着效果不好的言论,其实也很好理解。毕竟这个是基于文本匹配的算法。并没有做任何的优化。比如有 N 个名词的字典,词长度平均为 M,那么时间复杂度就可以达到 O(M*N^2) 这样一个恐怖的数据。所以会有各种定制化的纠错手段出现。同时,也会更具业务进行划分。

比如根据当前的地理位置,缩小字典库之类的。所以,那些个工程化很浓的解决手段,比如规则匹配,易错词表都有了用武之地。

同时,除了这些死算法之后,当下的热门机器学习似乎也是有参与其中,不过这一块的知识有待补充。

搜索这块,还是挺有意思的。

版权所有:《Mike's Blog》 => 《字符串纠错
本文地址:https://mikecoder.cn/post/178
除非注明,文章均为 《Mike's Blog》 原创,欢迎转载!转载请注明本文地址,谢谢。

发表评论

*