怎样实现基于Trie树和字典的分词功能

前言

目前做分词比较流行的是用深度学习来做,比如用循环神经网络和条件随机场,也有直接用条件随机场或隐马尔科夫模型的。前面也实现过上面几种,效果挺不错,基于隐马尔科夫模型的差一点,条件随机场的效果较好,而加入深度学习的效果最好。

而最最传统的分词做法很多都是基于字典的,然后通过最大匹配法匹配,效果比较一般。效果虽然一般,但我们还是看下怎么实现的吧。

Trie树结构

Trie 是一种搜索树,它的 key 都为字符串,通过 key 可以找到 value。能做到高效查询和插入,时间复杂度为O(k),缺点是耗内存。它的核心思想就是减少没必要的字符比较,使查询高效率,即用空间换时间,再利用共同前缀来提高查询效率。

Trie树的根节点不包含字符,根节点到某节点的路径连起来的字符串为该节点对应的字符串,每个节点只包含一个字符,此外,任意节点的所有子节点的字符都不相同。

比如如下,将五个词语添加到Trie树中,最后的结构如图所示。

TrieTree tree = new TrieTree();
tree.put("美利坚");
tree.put("美丽");
tree.put("金币");
tree.put("金子");
tree.put("帝王");

这里写图片描述

Github

https://github.com/sea-boat/TextAnalyzer/blob/master/src/main/java/com/seaboat/text/analyzer/segment/

效果

可以看到基于字典的分词效果是存在缺点的,需要用机器学习进一步优化。

DictSegment segment = new DictSegment();
System.out.println(segment.seg("我是中国人"));
System.out.println(segment.seg("人工智能是什么"));
System.out.println(segment.seg("北京互联网违法和不良信息举报中心"));
[我, 是, 中国人]
[人工智能, 是, 什么]
[北京, 互联网, 违法, 和不, 良, 信息, 举报中心]

简易实现

定义一个节点类代表Trie树节点,包含若干子节点、值和删除标记。getChild方法用于遍历该节点下的指定字符的子节点,allChildrenDeleted方法用于检测节点下的子节点是否已被删除了,setChild方法用于将子节点设置到某个节点上。

public class TrieNode {

    private TrieNode[] children;
    private String value;
    private boolean deleted = false;

    public TrieNode(String value) {
        this.value = value == null ? null : value.intern();
    }

    public boolean isEmpty() {
        return this.value == null && this.children == null;
    }

    public TrieNode[] getChildren() {
        return children;
    }

    public TrieNode getChild(String word) {
        if (children == null)
            return null;
        for (TrieNode c : children) {
            if (c.getValue() == word.intern() && !c.deleted)
                return c;
        }
        return null;
    }

    public boolean allChildrenDeleted() {
        if (children == null)
            return true;
        for (TrieNode c : children) {
            if (!c.deleted)
                return false;
        }
        return true;
    }

    public void setChild(TrieNode child) {
        if (children == null) {
            children = new TrieNode[1];
            children[0] = child;
        } else {
            TrieNode[] temp = children;
            children = new TrieNode[temp.length + 1];
            System.arraycopy(temp, 0, children, 0, temp.length);
            children[children.length - 1] = child;
        }
    }

}

定义一个 TrieTree 类代表树对象,包含了树的根节点。put方法用于将字符串放到树结构中,需要先遍历检测是否已经有字符串前缀,没有则要创建对应的节点,然后添加到对应节点的子节点中。getremove操作都需要针对树结构做处理,最终完成查询和删除,删除操作为了方便仅仅是设置下指定节点的删除标识。

public class TrieTree {

    protected TrieNode root;

    public TrieTree() {
        this.root = new TrieNode(null);
    }

    public void put(String word) throws IllegalArgumentException {
        if (word == null) {
            throw new IllegalArgumentException();
        }
        TrieNode current = this.root;
        for (String s : word.split("")) {
            TrieNode child = current.getChild(s);
            if (child == null) {
                child = new TrieNode(s);
                current.setChild(child);
            }
            current = child;
        }
    }

    public TrieNode get(String word) throws IllegalArgumentException {
        if (word == null) {
            throw new IllegalArgumentException();
        }
        TrieNode current = this.root;
        for (String s : word.split("")) {
            TrieNode child = current.getChild(s);
            if (child == null)
                return null;
            current = child;
        }
        return current;
    }

    public void remove(String word) {
        if (word == null || word.length() <= 0) {
            return;
        }
        for (int i = 0; i < word.length(); i++) {
            String sub_word = word.substring(0, word.length() - i);
            TrieNode current = this.root;
            for (String s : sub_word.split("")) {
                TrieNode child = current.getChild(s);
                if (child != null && (child.getChildren() == null || child.allChildrenDeleted()))
                    child.setDeleted(true);
                current = child;
            }
        }
    }

}

seg为分词方法,它主要就是尝试进行最大字符串匹配,尽量匹配字典中最长词,其中查找是否存在字符串在teri树中查找。

public List<String> seg(String text) {
        int flag = 0;
        int delta = 1;
        List<String> words = new ArrayList<String>();
        while (flag + delta <= text.length()) {
            String temp = text.substring(flag, flag + delta);
            if (tree.get(temp) != null) {
                if ((flag + delta) == text.length()) {
                    words.add(temp);
                    break;
                }
                delta++;
                continue;
            }
            words.add(temp.substring(0, temp.length() - 1));
            flag = flag + delta - 1;
            delta = 1;
        }
 return words;
    }

————-推荐阅读————

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇


跟我交流,向我提问:

这里写图片描述

公众号的菜单已分为“读书总结”、“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。

为什么写《Tomcat内核设计剖析》

欢迎关注:

这里写图片描述

相关文章
相关标签/搜索