DANCE WITH JAVA

开发出高质量的系统

常用链接

统计

积分与排名

好友之家

最新评论

模糊查询的思考

现实中经常有这样的问题,我们要从很多东西里边找到一个东西,而这些东西有很多别名,例如地点。如

何实现模糊查找呢?

说到查找就要考虑这样的问题,效率,模糊查找。说到效率hash表肯定是一种很好的解决方案。
但是如何实现模糊查找呢?一种最简单的方法是这样。利用hashmap提高效率
方法一:
构造一棵树,每个节点包含一个map,每个map中放着的是很多个节点
因为别名是汉字,我们使用汉字的unicode(唯一)作为key,value就是包含这个字的节点。比如
中国人->A
中华人民共和国->B
构造这样一个树 ,rootMap(key=中 value=node1)-->

                              |-(key=国 value=node2)-->node2包含map2(key=人 value=A) 
node1包含map1-- |
                              |-(key=华 value=node3)-->node3包含map3(key=人 value=node4)-->node4


包含map4(key=民 value=node5)-->node5包含map5以此类推,这样就建立了一个树型结构

输入“中”,直接把属于中的一支拿出来
输入“中华”把属于中华的一支拿出来。
但是事实证明这个方案是个不好的办法,因为存在以下问题。
1,当别名达到50000多个的时候占用内存100m也就是说,空间消耗大
2,当第一个字不准确的时候,模糊查询失效
虽然有改进方法,但是改进空间不大

方法二:
方法二来源于选举的思想,所以用人来代替地名更合适,比如说有10个人,每个人都有很多的名字,
姓名,字,乳名,曾用名等等

虽然别名是多的,但是真是地点确是比较少的,建立一个10长度的数组,把这些人编号,
你输入一些字例如“舒庆春舍于”,来投票,我把你输入的字一个一个去查找,
先查找别名包含“舒”的所有人,每人投一票,
再查找别名包含“庆”的所有人,每人投一票,
再查找别名包含“春”的所有人,每人投一票,
依此类推,最后我在10个人中找出票数最多的人

这个的优点:
模糊查询更有效,占用内存更少,减少交互(用户可以多输入一些相关信息),一定能查到结果(相对是)
注:为什么要减少交互呢,因为有些情况下交互越少越好(例如短信,因为收费和录入麻烦的原因)
缺点:
1,因为操作多,查询多,效率低下
2,当实际的“人”变的非常多的时候,出现空间不足。

但是这个方法的可优化性很强,因为人们取名字是有规律的,用到的字可能很多,常用字却很少,
所以我们可以把一些常用字对应的人先查出来,在查询的时候直接使用这些结果。这样缺点1就能得到优化
对于缺点2,我们可以实现这样的方法,默认不建立任何数组,建立一个空map,当这个人被第一次投票的时候他进入map,这样,那些被投0票的人就不会进入,大大减少了空间浪费,但是如果被投票的人很多呢可以模仿内存的实现方式,实现部分存到硬盘,采取换入换出的方式,因为每个人都得到平均票数的机会很少,大部分时候是某些人得到大多数的票,所以换入换出应该不是很频繁,问题二也得到了一定程度的解决。

 

posted on 2006-09-22 01:15 dreamstone 阅读(1198) 评论(0)  编辑  收藏 所属分类: 基础


只有注册用户登录后才能发表评论。


网站导航: