|
锁定老帖子 主题：正向最大匹配改进算法
该帖已经被评为良好帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-05-26
最后修改：2009-05-29
AD.： 2年J2EE经验，熟悉常用数据结构算法，熟悉常用开发框架。 手机：15940949592，欢迎骚扰及内部推荐 题外话：为什么用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("欢迎光临上海浦东发展银行主页！");
}
其结果为 上海浦东发展银行 完整代码见附件 由于时间仓促，难免有疏漏之处，望指正并见谅 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2009-05-29
太牛了楼主我一直在想办法实现这个...你的字典是怎么构建的啊
|
| 返回顶楼 | |
|
发表时间：2009-05-30
ansjsun 写道 太牛了楼主我一直在想办法实现这个...你的字典是怎么构建的啊
字典当然是Trie树了 不过普通的Trie树会产生很多冗余节点 所以我采用的是
public class TrieTreeNode {
public TrieTreeNode parent;
public Map<Character, TrieTreeNode> childs = new HashMap<Character, TrieTreeNode>();
public char value = 0;
public int state = 0;
public int count = 0;
}
这种结构 另原来的程序有点小错误，修正了，修正版本在这个回复的附件 |
| 返回顶楼 | |
|
发表时间：2009-06-01
哦是tire树啊...
楼主弄过双数组tire树么???我一直困惑内个呢.你这么分出来效率咋样啊!! |
| 返回顶楼 | |
|
发表时间：2009-06-02
LZ这个有点问题
你试试这个
tt.insertTrieTree("python");
tt.insertTrieTree("py");
tt.insertTrieTree("pyt");
tt.insertTrieTree("thon");
tt.searchTrieTree("python");
得到的结果是 python |
| 返回顶楼 | |
|
发表时间：2009-06-02
最后修改：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 |
| 返回顶楼 | |
|
发表时间：2009-06-02
多谢楼主提供
|
| 返回顶楼 | |
|
发表时间：2009-06-02
jenlp520 写道 LZ这个有点问题
你试试这个
tt.insertTrieTree("python");
tt.insertTrieTree("py");
tt.insertTrieTree("pyt");
tt.insertTrieTree("thon");
tt.searchTrieTree("python");
得到的结果是 python 得到这个结果是正常的，在我的算法中，只进行了最大匹配，没有记录过程词与分支处理 |
| 返回顶楼 | |
|
发表时间：2009-06-02
最后修改：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("中国人走了");
输出：中国人
|
| 返回顶楼 | |
|
发表时间：2009-06-02
最后修改：2009-06-02
我的情况里只进行了最大匹配的情况，中国人走了。正确应该被拆分成，
中国/国人/中国人/走了 处理这种，一个词头是另一个词的尾以及记录过程词 只需要在我的算法中稍加改动就可以了，比如 可以在任意搜寻到状态1的时候记录此词 以及每个字都进行最大正向匹配就可以解决词头词尾的问题（不过这样匹配速度就降下来了，寻找更好的方法，希望共同探讨） 其算法正在写（写出个烂效率的匹配最多词，将就着看吧，见附件） 另:本文只是抛块转头，希望勾引好玉出来 |
| 返回顶楼 | |
