|
锁定老帖子 主题：正向最大匹配改进算法
该帖已经被评为良好帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-06-06
leon_a 写道 ansjsun 写道 哦是tire树啊... 楼主弄过双数组tire树么???我一直困惑内个呢.你这么分出来效率咋样啊!! 查询时间复杂度o(1),不过这个分词来说实在太过简单了，做文字过滤倒还有那么一丁点参考价值，具体正在完善中（请别期待，我很懒。。。） PS:linliangyi2007兄这么晚还在线 呵呵，正在做IK Analyzer 3.0的版本设计编码。这个版本已经实现了一个不错的词典匹配算法，22w主词典，内存控制在24M，匹配速度大概在300w词每秒以上（没细算，实际值可能更高些）。请让我先买个关子，等IK Analyzer 3.0发布后，跟大家分享哈 
|
| 返回顶楼 | |
|
发表时间：2009-06-06
最后修改：2009-06-06
引用 对于Map的空间使用时需要一定的容易的，在默认情况下，HashMap的冗余参数是0.75，也就是说，当你的Map的空间为10时，实际上只能放入7 个元素，当第八个元素放入时，Map的空间就要翻倍为20了。因此，设置合理的冗余参数，能有效的抑制多余的空间损耗。当然，负面影响是，Map的命中效率会有所下降
就象默认map空间为16一样 虽然在不扩容的情况下只能放16*0.75=12个 但是实际上它还是初始化了一个16个长度的数组 其实最早我是认为这个每必要 因为分枝不会过多 当然现在改这个基本没什么作用...就不讨论这个了 引用 判断一个树节点的子节点，但子节点小于一定数量时，可以简单的使用数组存储，查找时直接遍历数组；但子节点大于一定数量时，改为HashMap存储，提高搜索效率
以你的经验 这个极限值多少适合呢？ |
| 返回顶楼 | |
|
发表时间：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次一定可以完成匹配。 这样可以有效的降低内存消耗。 |
| 返回顶楼 | |
