阅读 188

一个简单的关键词检测(DFA)

前言

关键词检测是现在几乎所有网站系统都必须要有的东西。往复杂了做会牵扯到NLP之类的“高级技术”,这个就不在本篇里瞎扯了。这里教大家一个简单的算法:DFA。

DFA是啥

DFA:Deterministic Finite Automaton,也就是确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。

这个描述有点难懂,我用一段白话来说明一下:你有一个集合,集合内的每一个元素都标明了自己的状态,通过你已知的某些事件,你可以从当前元素的状态得到下一个状态,从而知道下一个元素是啥,即event + state = next state。而且毕竟集合是有限的,一定能从一个节点找到最终的节点。

上图比较清楚的展示了这种集合间元素的关系,状态S通过事件a可以找到U,可以通过事件b找到V。那么怎么把这个有穷自动机用到关键词检测里呢,下面举个例子。

举个例子

现在有几个关键词:妙蛙种子,妙蛙草,妙蛙花,皮卡丘,皮丘。我们现在对这些关键词进行一些操作,构造出一个有穷自动机出来。

如果我们将这些词整理成这样一个树状结构,我们就可以根据第一个字,去对他所属的树去进行检索,这将大大提高搜索的效率。

以妙蛙花为例:

  1. 先通过“妙”字去搜索,看看存不存在以“妙”为根节点的树。若不存在,则这个词不在我们的关键词中。
  2. 若存在这个树,则我们去匹配第二个字“蛙”,看看这个字是不是在当前这个树的第二个节点上。若不存在话,则这个词不在我们的关键词中。然后依次类推下去。
  3. 如何判断这棵树已经到最末尾了,即到了关键字最后一个字。我们在生成这颗树的时候,给最后的节点加上一个属性(isEnd=true),标明这个关键词已经结束了。

下面给出这个自动机的HashSet实例:

妙 = { 
    isEnd = 0 
    蛙 = {
        isEnd = 0
        种 = {
            isEnd = 0 
            子 = {
                isEnd = 1
            } 
        } 
        草 = {
            isEnd = 1
        }
        花 = {
            isEnd = 1
        }
    }
}

皮 = {
    isEnd = 0
    卡 = {
        isEnd = 0
        丘 = {
            isEnd = 1
        }
    }
    丘 = {
        isEnd = 1
    }
}

复制代码

代码实现

class DFA
{
    private $tree = [];

    public function build($strWord)
    {

        $len = mb_strlen($strWord, 'UTF-8');
        $tree = &$this->tree;

        for ($i = 0; $i < $len; $i++) {

            $word = mb_substr($strWord, $i, 1, 'UTF-8');

            if (isset($tree[$word])) {

                if ($i == ($len - 1)) {
                    $tree[$word]['end'] = 1;
                }

            } else {

                if ($i == ($len - 1)) {
                    $tree[$word] = [];
                    $tree[$word]['end'] = 1;
                } else {
                    $tree[$word] = [];
                    $tree[$word]['end'] = 0;
                }

            }

            $tree = &$tree[$word];
        }
    }

    public function search($strWord)
    {
        $len = mb_strlen($strWord, 'UTF-8');

        $arrHashMap = $this->tree;

        for ($i = 0; $i < $len; $i++) {

            $word = mb_substr($strWord, $i, 1, 'UTF-8');

            if (!isset($arrHashMap[$word])) {
                $arrHashMap = $this->tree;
                continue;
            }

            if ($arrHashMap[$word]['end']) {
                return true;
            }

            $arrHashMap = $arrHashMap[$word];
        }
        
        return false;
    }
}

$obj = new DFA();
$obj->build('妙蛙种子');
$obj->build('妙蛙草');
$obj->build('皮卡丘');
$obj->build('皮丘');

var_dump($obj->search('迷唇姐'));
var_dump($obj->search('妙蛙种子'));

复制代码

一些问题

  1. 这个检测关键词也是依赖于词库本身,词库本身需要人维护。
  2. 词库若很大的话,会占用很多内存。
  3. 无意义字符会影响查询,需要提前进行过滤。

综上

以上就是使用DFA进行关键词检测的一个简单应用,在一些简单的应用场景里面还是挺实用的。当然,真正的关键词检测还需要用到深度学习和自然语言分析等相关技术,这些等以后有机会了再研究吧。

PS

附上仓库

github.com/Devil0023/p…

关注下面的标签,发现更多相似文章
评论