自然语言处理hanlp------6-2字典树的实现_扫描“自然语言处理”,如果“自然”这条路径不存在于字典树中,则可以断定一切以“

---

前言

本章节为原书的
2.4.4首字散列其余二分的字典树
2.4.5前缀树的妙用
主要作为叙述了解即可

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、首字散列其余二分

首先需要了解散列函数，其实一般也就说的是哈希函数，这个大家就不陌生了。将某个字符输出为对应的散列值，也就说一串整数
例如：

$ python3
>>> hash('池')-hash('江')
2668313623312284569
1
2
3

这是Python的散列，采用Unicode，显然结果 很不友好

再例如：

System.out.println(new Character('池').hashcode() - new Character('江').hashcode())
>输出结果
1
1
2
3

java的散列值明显友好一些，采用utf-16（池江二字已知字符相邻）

java的散列函数输出是[0,65535]，用来索引子节点很合适
做法如下：
1.创建一个65535大小的数组
2.将子节点按对应的字符整型值作为下标放入数组中
这样做，每次访问只需要访问对应的下标即可，考虑到汉语中二字词最多，所以结合二分的策略，诞生了本节的字典树，仅在根节点实施散列，其余二分。举例如下图（引用hankcs的原图）：

引用上节的效率测评代码之后，首字散列其余二分的算法比二叉树相比而言，最长匹配中文分词速度又得到了一些提升，特别是在逆向和双向，优势更明显。

二、前缀树的妙用

上一节用字典树代替了TreeMap,利用containsKey做分词，速度加快了近一倍，但并没有达到字典树的潜力。

利用字典树的概念，我们可以做的更快，发挥前缀的作用

这种性质如何加速诃典分词呢？在扫描“自然语言处理”这句话的时候，朴素实现会依次查询“自”“自然”“自然语”“自然语言”是否在可典中。但事实上，如果“自然”这条路径不存在于前缀树中，则可以断定一切以“自然”开头的词语都不可能存在。也就是说，在状态转移失败时（由根节点向“自”、由“自”向“自然”的转移)，我们就可以提前终止对以“自”开头的扫描，从而节省相当多的时间。

全切分核心代码如下（示例）：

public void parseText(String text, AhoCorasickDoubleArrayTrie.IHit<V> processor)
    {
        int length = text.length();
        int begin = 0;
        BaseNode<V> state = this;

        for (int i = begin; i < length; ++i)
        {
            state = state.transition(text.charAt(i));
            if (state != null)
            {
                V value = state.getValue();
                if (value != null)
                {
                    processor.hit(begin, i + 1, value);
                }
            }
            else
            {
                i = begin;
                ++begin;
                state = this;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

最长匹配核心代码如下（示例）：

public void parseLongestText(String text, AhoCorasickDoubleArrayTrie.IHit<V> processor)
    {
        int length = text.length();
        for (int i = 0; i < length; ++i)
        {
            BaseNode<V> state = transition(text.charAt(i));
            if (state != null)
            {
                int to = i + 1;
                int end = to;
                V value = state.getValue();
                for (; to < length; ++to)
                {
                    state = state.transition(text.charAt(to));
                    if (state == null) break;
                    if (state.getValue() != null)
                    {
                        value = state.getValue();
                        end = to + 1;
                    }
                }
                if (value != null)
                {
                    processor.hit(i, end, value);
                    i = end - 1;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

其实我们不必深究代码怎么去写，但一定要去了解每段代码是什么原理，为什么这样写，可能说起来有些矛盾，懂得都懂。

---

测试

利用状态转移的技巧，前缀树的作用就发挥出来了，同样进行上节的测试，速度差异就明显了，同样用原书展示：

over！

此外：本人创建了QQ交流群，希望大家来交流学习