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

徐大白
2个月前 阅读 21 点赞 1

前言

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

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


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;
	}


| 1
评论 ( {{ comments.total }} )

还没有人发表评论...

{{ o.content }}
赞 {{ o.likes_count ? o.likes_count : '' }} 回复 {{ o.created_at }}
相关推荐