文档章节

JavaScript: 实现简单的中文分词

陈亦
 陈亦
发布于 2014/02/21 01:21
字数 2892
阅读 4249
收藏 16

中文分词在大数据横行的今天是越来越有用武之地了。它不仅被广泛用于专业的中文搜索引擎中,而且在关键词屏蔽、黑白名单以及文本相似度等方面也能大显身手。中文分词最简单也最常用的方式是基于字典查找的方式,通过遍历待分词字符串并在字典中进行查找匹配以达到分词的目的。本文即是采用这种方式。

字典

在本文中,完全依赖于字典,因此需要准备好字典。一般面对不同的领域用不同的字典。比如面向医学的,则字典会添加许多医学术语方面的词。可以很容易的找到常用词的字典,比如搜狗输入法自带的字典等。

停止词

停止词不能用于成词。停止词主要包括无意义的字符(如的、地、得)或词。

常规实现

本文由于只是简单的介绍和实现,所以定义好了简单的字典和停止词,如下代码所示:

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>简单的中文分词</title>
    <meta name="author" content="" />
    <meta http-equiv="X-UA-Compatible" content="IE=7" />
    <meta name="keywords" content="简单的中文分词" />
    <meta name="description" content="简单的中文分词" />
</head>
<body>
<script type="text/javascript">
// 字典
var dict  = {
	"家乡"     : 1,
	"松花"     : 1,
	"松花江"   : 1,
	"那里"     : 1,
	"四季"     : 1,
	"四季迷人" : 1,
	"迷人"     : 1,
	"花香"     : 1
};
// 停止词
var stop  = {
	"的" : 1
};
// 待分词的字符串
var words = "我的家乡在松花江边上,那里有四季迷人的花香。";
</script>
</body>
</html>

dict和stop之所以定义为Object,是因为这样可令查找的时间复杂度为常值O(1)。分词的过程有点像正则表达式的惰性匹配。先从words中读取第一个字符"我"并在dict中和stop中查找,如果是停止词,则丢掉已读取的,然后读取第二个字"的"。如果在dict中,则添加到结果集,然后继续读到下一个,再同样去stop和dict中查找,直到处理完成。代码如下:

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>简单的中文分词</title>
    <meta name="author" content="" />
    <meta http-equiv="X-UA-Compatible" content="IE=7" />
    <meta name="keywords" content="简单的中文分词" />
    <meta name="description" content="简单的中文分词" />
</head>
<body>
<script type="text/javascript">
// 字典
var dict  = {
	"家乡"     : 1,
	"松花"     : 1,
	"松花江"   : 1,
	"那里"     : 1,
	"四季"     : 1,
	"四季迷人" : 1,
	"迷人"     : 1,
	"花香"     : 1
};
// 停止词
var stop  = {
	"的" : 1
};
// 待分词的字符串
var words = "我的家乡在松花江边上,那里有四季迷人的花香。";

function splitWords(words) {
	var start = 0, end = words.length - 1, result = [];
	while (start != end) {
		var str = [];
		for (var i = start; i <= end; i++) {
			var s = words.substring(i, i + 1);
			// 如果是停止词,则跳过
			if (s in stop) {
				break;
			}
			str.push(s);
			// 如果在字典中,则添加到分词结果集
			if (str.join('') in dict) {
				result.push(str.join(''));
			}
		}

		start++;
	}

	return result;
}

console.group("Base 分词: ");
console.log("待分词的字符串: ", words);
console.log("分词结果:       ", splitWords(words));
console.groupEnd();
</script>
</body>
</html>

Trie树实现

但是想一下,在实际应用中,字典可能包含了足够多的词,而且字典中很多词是有共同前缀的。比如上述代码中的"松花"和"松花江"就有共同的前缀"松花",存储重复的前缀将导致字典占用大量的内存,而这部分其实是可以优化的。还记得我之前的一篇介绍Trie树的文章吗?如果您忘了,那请看:Python: Trie树实现字典排序 。事实上还是有不同之处的,因为之前只是针对26个字母的Trie树。对于需要支持中文的Trie树来说,如果直接用一个字符(这个字符可能是ASCII码字符,也可能是中文字符或其它多字节字符)来表示一个节点,则是不可取的。大家知道最常用的汉字有将近一万个,如果每一个节点都要用一个数组来保存将近一万个子节点,那就太吓人了。所以我这里选择Object的方式来保存,这样的好处是查找时间复杂度为O(1)。但即使这样,这个Object还将容纳将近一万个key,所以我这里将结合另外一种方案来实现。

JavaScript的内码是Unicode,它用1~2个字节来存储。如果我们将一个双字节转成UTF8的三个字节(嗯,是的。本文只考虑UTF8的单字节和三字节,因为双字节、四字节、五字节和六字节太少见了),单字节还是不变,以第一个字节为起始节点,那么节点的子节点数就变成了固定的256个,然后我们通过起始字节的大小可以知道这是一个单字节或三字节。这种方式有效的节约了内存。接下来是实现代码:

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>简单的中文分词</title>
    <meta name="author" content="" />
    <meta http-equiv="X-UA-Compatible" content="IE=7" />
    <meta name="keywords" content="简单的中文分词" />
    <meta name="description" content="简单的中文分词" />
</head>
<body>
<script type="text/javascript">
// 字典
var dict  = [
	"家乡",
	"松花",
	"松花江",
	"那里",
	"四季",
	"四季迷人",
	"迷人",
	"花香",
	"hello",
	"kitty",
	"fine"
];
// 停止词
var stop  = {
	"的" : 1
};
// 待分词的字符串
var words = "hello, kitty!我的家乡在松花江边上,那里有四季迷人的花香。fine~";

// Trie树
function Trie() {
	this.root = new Node(null);
}
Trie.prototype = {
	/**
	* 将Unicode转成UTF8的三字节
	*/
	toBytes : function(word) {
		var result = [];
		for (var i = 0; i < word.length; i++) {
			var code = word.charCodeAt(i);
			// 单字节
			if (code < 0x80) {
				result.push(code);
			} else {
				// 三字节
				result = result.concat(this.toUTF8(code));
			}
		}

		return result;
	},
	toUTF8 : function(c) {
		// 1110xxxx 10xxxxxx 10xxxxxx
		// 1110xxxx
		var byte1 = 0xE0 | ((c >> 12) & 0x0F);
		// 10xxxxxx
		var byte2 = 0x80 | ((c >> 6) & 0x3F);
		// 10xxxxxx
		var byte3 = 0x80 | (c & 0x3F);

		return [byte1, byte2, byte3];
	},
	toUTF16 : function(b1, b2, b3) {
		// 1110xxxx 10xxxxxx 10xxxxxx
		var byte1 = (b1 << 4) | ((b2 >> 2) & 0x0F);
		var byte2 = ((b2 & 0x03) << 6) | (b3 & 0x3F);
		var utf16 = ((byte1 & 0x00FF) << 8) | byte2

		return utf16;
	},
	/**
	* 添加每个词到Trie树
	*/
	add : function(word) {
		var node = this.root, bytes = this.toBytes(word), len = bytes.length;
		for (var i = 0; i < len; i++) {
			var c = bytes[i];
			// 如果不存在则添加,否则不需要再保存了,因为共用前缀
			if (!(c in node.childs)) {
				node.childs[c] = new Node(c);
			}
			node = node.childs[c];
		}
		node.asWord(); // 成词边界
	},
	/**
	* 按字节在Trie树中搜索
	*/
	search : function(bytes) {
		var node = this.root, len = bytes.length, result = [];
		var word = [], j = 0;
		for (var i = 0; i < len; i++) {
			var c = bytes[i], childs = node.childs;
			if (!(c in childs)) {
				return result;
			}

			if (c < 0x80) {
				word.push(String.fromCharCode(c));
			} else {
				j++;
				if (j % 3 == 0) {
					var b1 = bytes[i - 2];
					var b2 = bytes[i - 1];
					var b3 = c;
					word.push(String.fromCharCode(this.toUTF16(b1, b2, b3)));
				}
			}
			// 如果是停止词,则退出
			if (word.join('') in stop) {
				return result;
			}

			// 成词
			var cnode = childs[c];
			if (cnode.isWord()) {
				result.push(word.join(''));
			}

			node = cnode;
		}

		return result;
	},
	/**
	* 分词
	*/
	splitWords : function(words) {
		// 转换成单字节进行搜索
		var bytes  = this.toBytes(words);
		var start = 0, end = bytes.length - 1, result = [];

		while (start != end) {
			var word = [];
			for (var i = start; i <= end; i++) {
				var b = bytes[i]; // 逐个取出字节
				word.push(b);
				
				var finds = this.search(word);
				if (finds !== false && finds.length > 0) {
					// 如果在字典中,则添加到分词结果集
					result = result.concat(finds);
					break;
				}
			}

			start++;
		}

		return result;
	},
	/**
	* 词始化整棵Trie树
	*/
	init : function(dict) {
		for (var i = 0; i < dict.length; i++) {
			this.add(dict[i]);
		}
	}
};

// 节点
function Node(_byte) {
	this.childs   = {}; // 子节点集合
	this._byte    = _byte || null; // 此节点上存储的字节
	this._isWord  = false; // 边界保存,表示是否可以组成一个词
}
Node.prototype = {
	isWord : function() {
		return this._isWord;
	},
	asWord : function() {
		this._isWord = true;
	}
};

var trie = new Trie();
trie.init(dict);
var result = trie.splitWords(words);

console.group("Trie 分词: ");
console.log("待分词的字符串: ", words);
console.log("分词结果:       ", result);
console.groupEnd();
</script>
</body>
</html>

各位看了输出结果后就会发现,这个分词是有问题的,因为明显少了"松花江"和"四季迷人"。拿"四季"和"四季迷人"来说,"四季"是"四季迷人"的前缀,在通过trie.isWrod()方法来判断是否成词时,一遇到"四季"就成功了,所以"四季迷人"没有机会得到判断,所以我们需要修改代码,在Node上加一个属性,表示已判断的次数。代码如下:

<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>简单的中文分词</title>
    <meta name="author" content="" />
    <meta http-equiv="X-UA-Compatible" content="IE=7" />
    <meta name="keywords" content="简单的中文分词" />
    <meta name="description" content="简单的中文分词" />
</head>
<body>
<script type="text/javascript">
// 字典
var dict  = [
	"家乡",
	"松花",
	"松花江",
	"那里",
	"四季",
	"四季迷人",
	"迷人",
	"花香",
	"hello",
	"kitty",
	"fine"
];
// 停止词
var stop  = {
	"的" : 1
};
// 待分词的字符串
var words = "hello, kitty!我的家乡在松花江边上,那里有四季迷人的花香。fine~";

// Trie树
function Trie() {
	this.root = new Node(null);
}
Trie.prototype = {
	/**
	* 将Unicode转成UTF8的三字节
	*/
	toBytes : function(word) {
		var result = [];
		for (var i = 0; i < word.length; i++) {
			var code = word.charCodeAt(i);
			// 单字节
			if (code < 0x80) {
				result.push(code);
			} else {
				// 三字节
				result = result.concat(this.toUTF8(code));
			}
		}

		return result;
	},
	toUTF8 : function(c) {
		// 1110xxxx 10xxxxxx 10xxxxxx
		// 1110xxxx
		var byte1 = 0xE0 | ((c >> 12) & 0x0F);
		// 10xxxxxx
		var byte2 = 0x80 | ((c >> 6) & 0x3F);
		// 10xxxxxx
		var byte3 = 0x80 | (c & 0x3F);

		return [byte1, byte2, byte3];
	},
	toUTF16 : function(b1, b2, b3) {
		// 1110xxxx 10xxxxxx 10xxxxxx
		var byte1 = (b1 << 4) | ((b2 >> 2) & 0x0F);
		var byte2 = ((b2 & 0x03) << 6) | (b3 & 0x3F);
		var utf16 = ((byte1 & 0x00FF) << 8) | byte2

		return utf16;
	},
	/**
	* 添加每个词到Trie树
	*/
	add : function(word) {
		var node = this.root, bytes = this.toBytes(word), len = bytes.length;
		for (var i = 0; i < len; i++) {
			var c = bytes[i];
			// 如果不存在则添加,否则不需要再保存了,因为共用前缀
			if (!(c in node.childs)) {
				node.childs[c] = new Node(c);
			}
			node = node.childs[c];
		}
		node.asWord(); // 成词边界
	},
	/**
	* 按字节在Trie树中搜索
	*/
	search : function(bytes) {
		var node = this.root, len = bytes.length, result = [];
		var word = [], j = 0;
		for (var i = 0; i < len; i++) {
			var c = bytes[i], childs = node.childs;
			if (!(c in childs)) {
				return result;
			}

			if (c < 0x80) {
				word.push(String.fromCharCode(c));
			} else {
				j++;
				if (j % 3 == 0) {
					var b1 = bytes[i - 2];
					var b2 = bytes[i - 1];
					var b3 = c;
					word.push(String.fromCharCode(this.toUTF16(b1, b2, b3)));
				}
			}
			// 如果是停止词,则退出
			if (word.join('') in stop) {
				return result;
			}

			// 成词
			var cnode = childs[c];
			if (cnode.isWord()) {
				cnode.addCount(); // 用于计数判断
				result.push(word.join(''));
			}

			node = cnode;
		}

		return result;
	},
	/**
	* 分词
	*/
	splitWords : function(words) {
		// 转换成单字节进行搜索
		var bytes  = this.toBytes(words);
		var start = 0, end = bytes.length - 1, result = [];

		while (start != end) {
			var word = [];
			for (var i = start; i <= end; i++) {
				var b = bytes[i]; // 逐个取出字节
				word.push(b);
				
				var finds = this.search(word);
				if (finds !== false && finds.length > 0) {
					// 如果在字典中,则添加到分词结果集
					result = result.concat(finds);
				}
			}

			start++;
		}

		return result;
	},
	/**
	* 词始化整棵Trie树
	*/
	init : function(dict) {
		for (var i = 0; i < dict.length; i++) {
			this.add(dict[i]);
		}
	}
};

// 节点
function Node(_byte) {
	this.childs   = {}; // 子节点集合
	this._byte    = _byte || null; // 此节点上存储的字节
	this._isWord  = false; // 边界保存,表示是否可以组成一个词
	this._count   = 0;
}
Node.prototype = {
	isWord : function() {
		return (this._isWord && (this._count == 0));
	},
	asWord : function() {
		this._isWord = true;
	},
	addCount : function() {
		this._count++;
	},
	getCount : function() {
		return this._count;
	}
};

var trie = new Trie();
trie.init(dict);
var result = trie.splitWords(words);

console.group("Trie 分词: ");
console.log("待分词的字符串: ", words);
console.log("分词结果:       ", result);
console.groupEnd();
</script>
</body>
</html>

结束语

现在已经能正确的分词了,即使有相同的前缀也没有问题。我上面分词用到的Trie树称为标准Trie树,这种标准Trie树比较直观。对于需要存储中文的Trie树,也有很多是用数组的方式实现的,比如双数组Trie树(Double Array Trie,简称DAT)、三数组Trie树等,有兴趣的朋友可以去了解一下。

本文只是简单的实现了中文分词,还有很多不足的地方。比如没有考虑未登录词的自动成词,人名、岐义等等。但对于一般的如关键词屏蔽和计算文本相似度等应用已经足够了。

© 著作权归作者所有

陈亦
粉丝 241
博文 23
码字总数 53194
作品 0
浦东
高级程序员
私信 提问
加载中

评论(2)

洞悉
洞悉
关注你了
WhiteWater
WhiteWater
79
前端基础-JavaScript

开发工具与关键技术:DW/浏览器 ;简单使用js。 作者:刘佳明 撰写时间:2019年1月 18 日 前面已经随手写过了关于网页编辑的一些基础布局和标签的认识;这篇文章在这里为大家简单的介绍一下关...

没有,
01/18
0
0
25行代码实现一个简单的编译器

起因 《25行JavaScript语句实现一个简单的编译器》实现的是一个简单到不能再简单的玩具的玩具,他的魔法是函数式编程简化了js代码。java 8提供了函数式编程的支持,昨晚脑子抽风突然兴趣jav...

obaniu
2017/11/06
0
0
查询json数据结构的8种方式

你有没有对“在复杂的JSON数据结构中查找匹配内容”而烦恼。这里有8种不同的方式可以做到: JsonSQL JsonSQL实现了使用SQL select语句在json数据结构中查询的功能。 例子: jsonsql.query("s...

KelvinQ
2014/01/13
0
0
《JavaScript实用效果整理》系列分享专栏

整理一些使用的JavaScript效果,在Web开发中遇到的比较好的动态效果,都收藏在这里,对以后的网站开发增加不少的色彩 《JavaScript实用效果整理》已整理成PDF文档,点击可直接下载至本地查阅...

开元中国2015
2018/10/29
0
0
Dart 比 JavaScript 更酷的10个理由

Dart 是 Google发明的一种新的编程语言。在使用JavaScript一年多以后,我对Dart可谓是一见钟情。我以前是做Java的,我在用JS的时候要学习很多新东西。 有人说你必须深入研究JavaScript,否则...

虫虫
2012/01/04
7.3K
13

没有更多内容

加载失败,请刷新页面

加载更多

Linux输入法fcitx的安装问题

Fcitx 总共要安装的包如下 fcitxfcitx-binfcitx-config-commonfcitx-config-gtk | fcitx-config-gtk2fcitx-datafcitx-frontend-allfcitx-frontend-gtk2fcitx-frontend-gtk3......

CHONGCHEN
今天
4
0
网络基础

前言: 最近整理一些以前的学习笔记(有部分缺失,会有些乱,日后再补)。 过去都是存储在本地,此次传到网络留待备用。 计算机网络的功能: 1.数据通信; 2.资源共享; 3.增加数据可靠性; 4....

迷失De挣扎
今天
7
0
spring boot升级到spring cloud

1、先升级spring boot 版本到2.1.3 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-dependencies</artifactId> <version>2.1.3.RELEAS......

moon888
今天
12
0
从蓝鲸视角谈DevOps

DevOps源于Development和Operations的组合 常见的定义 DevOps是一种重视“软件开发人员(Dev)”和“IT运维技术人员(Ops)”之间沟通合作的文化、运动或惯例。透过自动化“软件交付”和“架构变...

嘉为科技
今天
1
0
微服务设计 笔记

微服务设计 一、微服务架构理论 1.六边形架构 1)六边形架构(Hexagonal Architecture),又称为端口和适配器架构风格;使用适配器与外界进行交互,外界通过应用层API与内部进行交互。 2)经典...

啃不动地大坚果
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部