1
回答
双数组字典树关键词查询匹配和替换

大家在进行关键词匹配和替换的时候都是用的什么算法?很多人都可能有这样的需求,比如聊天文本中的敏感词替换、html文本中的关键词加超链接等。不深入技术算法和时刻关注程序性能的人来说,就用个正则替换就行了,但当敏感词(关键词)库有几万甚至更多的时候,用正则哪怕替换几百个文字中的敏感词,运行效率都是极差的,可以说是严重的不合格,那么有什么算法来优化效率呢?答案是肯定的。

在此我跟大家介绍一下现在关键词查找匹配的主流算法都有哪些:

1、DFA算法,效率跟直接用正则比较,简直是一个天上一个地下,不过此算法比较费内存。

2、字典树,给关键词构建一棵字典树,树结构一般是搜索算法里面公认最快的了,比如mysql数据库里面索引查找算法,一种是hash查找,一种就是二叉树查找了。扯远了,字典树相对DFA算法,在理论技术高度上都要优于DFA算法,内存消耗降低,运行效率也相对较好。

3、双数组字典树,这个是字典树的升华版了,不过java开源界有一个DoubleArrayTrie类,此类仅实现了单模匹配,多模匹配就还得自己发挥一下了,在单模匹配的基础上实现多模匹配也挺简单。

4、AC自动机双数组字典树,这个名字比较霸气,也是我在网上查找敏感词替换算法时偶然发现的,也就是在双数组字典树中加入了自动机的概念来优化运行效率,作者是谁我忘记了,不过看那么些一大堆算法理论知识感觉他挺牛逼,专门研究些自然语言方面的算法,比较佩服。

个人测试中,双数组字典树和AC自动机双数组字典树这两者是我个人认为比较优秀的,运行效率AC自动机在处理大量关键词和大量文本的情况下比较好,不过我一般情况就用在聊天文本敏感词替换上,所以我一般选择双数组字典树。

大家会怎么选择呢?

举报
银杏果果
发帖于2年前 1回/164阅
顶部