正向最大匹配改进算法

AD.：
2年J2EE经验，熟悉常用数据结构算法，熟悉常用开发框架。
手机：[phone]，欢迎骚扰及内部推荐

题外话：为什么用java来写呢，因为可以写的又臭又长

   

正文：
传送门，引用ahuaxuan大牛的帖子，使用DFA实现文字过滤

在ahuaxuan的帖子中，实际上也引入了一个基于Trie字典树中文分词的问题。

图1：一个典型的Trie树结构

其中图1 state为1时表示从根结点到state=1的结点成一个词
图1由三个词组成：“上海”，“上海浦东”，“上海浦东发展银行”

将“上海浦东发展银行”进行词语切分，在不使用正向最大匹配及逆向最大匹配的情况下，有可能切分结果如下：“上海/浦东/发展/银行”，而我们实际想要的结果是“上海浦东发展银行”整句的专有名词。如果想进行这样的切分，就需要使用正向最大匹配或逆向最大匹配算法
单介绍正向最大匹配

正向最大匹配是在已经匹配到state=1的词时，继续向Trie树下遍历有限深度（其深度由参数给出）。如果此时落在state=0的Trie树结点上，向上回溯直到state=1，将词输出。如果直接落在state=1结点，那么直接输出此词。

图2：正向最大匹配示意图

图2中，其继续遍历深度=5
当遍历到state=1的“海”字时，继续向下遍历5次，到“银”字，因其state=0，回溯到“东”字
输出“上海浦东”
其直接限制是受到参数遍历深度的限制。那有的朋友可能会说，把参数改大不就解决问题了。不过这样就引入了效率问题，很多词只需要向下遍历2，3次就可以最大化匹配

改进
图3：正向最大匹配改进

图3中，其继续遍历深度也=5
但是当回溯到词“上海浦东”时，以“东”字结点继续遍历，直到其下面5个结点的state都=0时结束，很明显，这是一个递归的过程
代码如下

	/**
	 * 
	 * 最大正向匹配改进
	 * 
	 * @param node
	 * @param textChar
	 * @param index
	 * @return
	 */
	private int searchMaxWord(TrieTreeNode node, char[] textChar, int index) {
		if (terminateCondition(node, textChar, index)) {
			return --index;
		}
		TrieTreeNode tempNode = node;
		for (int i = index; i < index + RECURSION_TIME; i++) {
			if (tempNode.childs.get(textChar[i]).state != 1) {
				WORD_LEN++;
				tempNode = tempNode.childs.get(textChar[i]);
			} else {
				WORD_LEN++;
				return searchMaxWord(tempNode.childs.get(textChar[i]),
						textChar, i + 1);
			}
		}
		return -1;
	}

	/**
	 * 改进算法递归终止条件
	 * 
	 * @param node
	 * @param textChar
	 * @param index
	 * @return
	 */
	private boolean terminateCondition(TrieTreeNode node, char[] textChar,
			int index) {
		TrieTreeNode tempNode = node;
		for (int i = index; i < index + RECURSION_TIME; i++) {
			if (i > textChar.length - 1) {
				return true;
			}
			if (tempNode.childs.get(textChar[i]) == null) {
				return true;
			}
			if (tempNode.childs.get(textChar[i]).state != 1) {
				tempNode = tempNode.childs.get(textChar[i]);
			} else {
				return false;
			}
		}
		return true;
	}

依据此方法改进

	public static void main(String[] args) {
		TrieTree tt = new TrieTree();
		tt.insertTrieTree("上海");
		tt.insertTrieTree("上海浦东");
		tt.insertTrieTree("上海浦东发展银行");
		tt.searchTrieTree("欢迎光临上海浦东发展银行主页！");
	}

其结果为

上海浦东发展银行

完整代码见附件

由于时间仓促，难免有疏漏之处，望指正并见谅

评论

24 楼 linliangyi2007 2009-06-06  

jenlp520 写道

引用

对于Map的空间使用时需要一定的容易的，在默认情况下，HashMap的冗余参数是0.75，也就是说，当你的Map的空间为10时，实际上只能放入7 个元素，当第八个元素放入时，Map的空间就要翻倍为20了。因此，设置合理的冗余参数，能有效的抑制多余的空间损耗。当然，负面影响是，Map的命中效率会有所下降

就象默认map空间为16一样 虽然在不扩容的情况下只能放16*0.75=12个 但是实际上它还是初始化了一个16个长度的数组
其实最早我是认为这个每必要 因为分枝不会过多 当然现在改这个基本没什么作用...就不讨论这个了

引用

判断一个树节点的子节点，但子节点小于一定数量时，可以简单的使用数组存储，查找时直接遍历数组；但子节点大于一定数量时，改为HashMap存储，提高搜索效率

以你的经验 这个极限值多少适合呢？

我目前设置的数组大小为4。这样如果使用简单的遍历，最多4次，平均2次命中，如果使用2分法，可以将数组扩大到8，这样3次一定可以完成匹配。
这样可以有效的降低内存消耗。

23 楼 jenlp520 2009-06-06  

引用

对于Map的空间使用时需要一定的容易的，在默认情况下，HashMap的冗余参数是0.75，也就是说，当你的Map的空间为10时，实际上只能放入7 个元素，当第八个元素放入时，Map的空间就要翻倍为20了。因此，设置合理的冗余参数，能有效的抑制多余的空间损耗。当然，负面影响是，Map的命中效率会有所下降

就象默认map空间为16一样 虽然在不扩容的情况下只能放16*0.75=12个 但是实际上它还是初始化了一个16个长度的数组
其实最早我是认为这个每必要 因为分枝不会过多 当然现在改这个基本没什么作用...就不讨论这个了

引用

判断一个树节点的子节点，但子节点小于一定数量时，可以简单的使用数组存储，查找时直接遍历数组；但子节点大于一定数量时，改为HashMap存储，提高搜索效率

以你的经验 这个极限值多少适合呢？

22 楼 linliangyi2007 2009-06-06  

leon_a 写道

ansjsun 写道

哦是tire树啊...
楼主弄过双数组tire树么???我一直困惑内个呢.你这么分出来效率咋样啊!!

查询时间复杂度o(1),不过这个分词来说实在太过简单了，做文字过滤倒还有那么一丁点参考价值，具体正在完善中（请别期待，我很懒。。。）

PS:linliangyi2007兄这么晚还在线

呵呵，正在做IK Analyzer 3.0的版本设计编码。这个版本已经实现了一个不错的词典匹配算法，22w主词典，内存控制在24M，匹配速度大概在300w词每秒以上（没细算，实际值可能更高些）。请让我先买个关子，等IK Analyzer 3.0发布后，跟大家分享哈

21 楼 leon_a 2009-06-06  

ansjsun 写道

哦是tire树啊...
楼主弄过双数组tire树么???我一直困惑内个呢.你这么分出来效率咋样啊!!

查询时间复杂度o(1),不过这个分词来说实在太过简单了，做文字过滤倒还有那么一丁点参考价值，具体正在完善中（请别期待，我很懒。。。）

PS:linliangyi2007兄这么晚还在线

20 楼 leon_a 2009-06-06  

jenlp520 写道

ps:请原谅我没学过数据结构...看双数组trie看了半天还是弄清楚怎么去创建数组
ps:附上我没看懂的双数组trie文档

双数组trie树在存储空间上确实做到了最小，不过在其树结构有变化时，比如增加与删除节点，其解决冲突的时间复杂度很高在比较大的字典中，并不适合

19 楼 linliangyi2007 2009-06-06  

jenlp520 写道

感谢你的建议..
我字典的词是转成char[]后保存的每个char的
我改DEFAULT_INITIAL_CAPACITY的原因是 我认为大部分节点下的分支不会超过10个 所以我认为Map内的Entry数组不需要默认的16这么大

对于Map的空间使用时需要一定的容易的，在默认情况下，HashMap的冗余参数是0.75，也就是说，当你的Map的空间为10时，实际上只能放入7个元素，当第八个元素放入时，Map的空间就要翻倍为20了。因此，设置合理的冗余参数，能有效的抑制多余的空间损耗。当然，负面影响是，Map的命中效率会有所下降

引用

3.尝试动态的结合map和数组。
这个能否举个例 我现在对用数组实现多分支trie树很困扰

判断一个树节点的子节点，但子节点小于一定数量时，可以简单的使用数组存储，查找时直接遍历数组；但子节点大于一定数量时，改为HashMap存储，提高搜索效率

18 楼 jenlp520 2009-06-05  

linliangyi2007 写道

jenlp520 写道

现在我很郁闷啊 用之前的做法 2000个关键字消耗内存在15-18M左右 这个大小很恐怖啊

我估计是每个节点一个hashmap太占内存了 然后自己改了下map把原来DEFAULT_INITIAL_CAPACITY = 16改成了
DEFAULT_INITIAL_CAPACITY = 5结果在测试2000个关键字还是用了15M内存左右
后来我又试试不在每个节点里面放一个hashmap而是用个全局的...结果还是用了15M左右

难道一定要用双数组trie才能把内存降下来么...

ps:请原谅我没学过数据结构...看双数组trie看了半天还是弄清楚怎么去创建数组
ps:附上我没看懂的双数组trie文档

提示你，
1.不要简单的使用String来记录词典的词，那样太占内存
2.有效的设置hashmap的参数loadFactor，建议是0.8（DEFAULT_INITIAL_CAPACITY 只是默认的容量，当不够是，HashMap照样翻倍增加，你的设计基本是没有用的，关键是loadFactor这个参数）；
3.尝试动态的结合map和数组。

感谢你的建议..
我字典的词是转成char[]后保存的每个char的
我改DEFAULT_INITIAL_CAPACITY的原因是 我认为大部分节点下的分支不会超过10个 所以我认为Map内的Entry数组不需要默认的16这么大

引用

3.尝试动态的结合map和数组。

这个能否举个例 我现在对用数组实现多分支trie树很困扰

17 楼 linliangyi2007 2009-06-05  

jenlp520 写道

现在我很郁闷啊 用之前的做法 2000个关键字消耗内存在15-18M左右 这个大小很恐怖啊

我估计是每个节点一个hashmap太占内存了 然后自己改了下map把原来DEFAULT_INITIAL_CAPACITY = 16改成了
DEFAULT_INITIAL_CAPACITY = 5结果在测试2000个关键字还是用了15M内存左右
后来我又试试不在每个节点里面放一个hashmap而是用个全局的...结果还是用了15M左右

难道一定要用双数组trie才能把内存降下来么...

ps:请原谅我没学过数据结构...看双数组trie看了半天还是弄清楚怎么去创建数组
ps:附上我没看懂的双数组trie文档

提示你，
1.不要简单的使用String来记录词典的词，那样太占内存
2.有效的设置hashmap的参数loadFactor，建议是0.8（DEFAULT_INITIAL_CAPACITY 只是默认的容量，当不够是，HashMap照样翻倍增加，你的设计基本是没有用的，关键是loadFactor这个参数）；
3.尝试动态的结合map和数组。

16 楼 linliangyi2007 2009-06-05  

Programmer2.x 写道

中文分词，效果最好的是隐马尔科夫模型。

楼上这个回答文不对题！隐码模型跟楼主说的字串匹配没直接关系。

在中文分词中，隐码模型适合做语法分析，但不见的是效果最好的分词方式。用过中科院的分词器你就知道了。


另外，楼主的想法很好。
给楼主一个提示，
1.在路径上标注匹配的最长词语（这个楼主已经实现）
2.在词典的分支上注明是否还有后续的叶节点（这样可以最快的终止匹配失败）
有了上面的数据结构，不需要使用固定深度递归来试探，能有效的提高效率，而且不会漏掉比递归深度还长的词汇

15 楼 Programmer2.x 2009-06-04  

中文分词，效果最好的是隐马尔科夫模型。

14 楼 jenlp520 2009-06-04  

现在我很郁闷啊 用之前的做法 2000个关键字消耗内存在15-18M左右 这个大小很恐怖啊

我估计是每个节点一个hashmap太占内存了 然后自己改了下map把原来DEFAULT_INITIAL_CAPACITY = 16改成了
DEFAULT_INITIAL_CAPACITY = 5结果在测试2000个关键字还是用了15M内存左右
后来我又试试不在每个节点里面放一个hashmap而是用个全局的...结果还是用了15M左右

难道一定要用双数组trie才能把内存降下来么...

ps:请原谅我没学过数据结构...看双数组trie看了半天还是弄清楚怎么去创建数组
ps:附上我没看懂的双数组trie文档

13 楼 leon_a 2009-06-02  

jenlp520 写道

我写的一个跟现在这个差不多 我发现我们都被满屏的if else困扰啊

ps:银河英雄传好看么...我就只知道杨威利这个角色

等我抽出时间重构一下。
PS:银英很好看，老动画

12 楼 jenlp520 2009-06-02  

我写的一个跟现在这个差不多 我发现我们都被满屏的if else困扰啊

ps:银河英雄传好看么...我就只知道杨威利这个角色

11 楼 leon_a 2009-06-02  

我的情况里只进行了最大匹配的情况，中国人走了。正确应该被拆分成，
中国/国人/中国人/走了
处理这种，一个词头是另一个词的尾以及记录过程词
只需要在我的算法中稍加改动就可以了，比如
可以在任意搜寻到状态1的时候记录此词
以及每个字都进行最大正向匹配就可以解决词头词尾的问题（不过这样匹配速度就降下来了，寻找更好的方法，希望共同探讨）

其算法正在写（写出个烂效率的匹配最多词，将就着看吧，见附件）

另:本文只是抛块转头，希望勾引好玉出来

10 楼 jenlp520 2009-06-02  

leon_a 写道

jenlp520 写道

LZ这个有点问题
你试试这个

		tt.insertTrieTree("python");
		tt.insertTrieTree("py");
		tt.insertTrieTree("pyt");
		tt.insertTrieTree("thon");
		tt.searchTrieTree("python");

得到的结果是

python

得到这个结果是正常的，在我的算法中，只进行了最大匹配，没有记录过程词与分支处理

原来是这样挖 我误会拉````

不过这样的不算分支吧 一个词的头是另一个词的尾

		tt.insertTrieTree("中国人");
		tt.insertTrieTree("人走了");
		tt.searchTrieTree("中国人走了");

               输出：中国人

9 楼 leon_a 2009-06-02  

jenlp520 写道

LZ这个有点问题
你试试这个

		tt.insertTrieTree("python");
		tt.insertTrieTree("py");
		tt.insertTrieTree("pyt");
		tt.insertTrieTree("thon");
		tt.searchTrieTree("python");

得到的结果是

python

得到这个结果是正常的，在我的算法中，只进行了最大匹配，没有记录过程词与分支处理

8 楼 sanliyer 2009-06-02  

多谢楼主提供

7 楼 jenlp520 2009-06-02  

还有多谢LZ``借用你的思想 写了个

                DFATree dfaTree = new DFATree();
		dfaTree.addWords("python");
		dfaTree.addWords("py");
		dfaTree.addWords("pyt");
		dfaTree.addWords("thon");
		List list =  dfaTree.searchWord("python");

得到结果是：

py : 1
pyt : 1
python : 1
thon : 1

6 楼 jenlp520 2009-06-02  

LZ这个有点问题
你试试这个

		tt.insertTrieTree("python");
		tt.insertTrieTree("py");
		tt.insertTrieTree("pyt");
		tt.insertTrieTree("thon");
		tt.searchTrieTree("python");

得到的结果是

python

5 楼 ansjsun 2009-06-01  

哦是tire树啊...
楼主弄过双数组tire树么???我一直困惑内个呢.你这么分出来效率咋样啊!!