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 閱讀(1219) 評論(0)  編輯  收藏 所屬分類: 基礎

          主站蜘蛛池模板: 天峻县| 柘城县| 彩票| 大城县| 北安市| 图木舒克市| 昭平县| 张家港市| 荥经县| 武强县| 五台县| 孝昌县| 开江县| 合作市| 景东| 固原市| 太仆寺旗| 石狮市| 泰州市| 台湾省| 隆德县| 荆州市| 从化市| 台安县| 宁晋县| 台北市| 湖北省| 宝应县| 富平县| 阳谷县| 平安县| 汉川市| 泾源县| 浮梁县| 石屏县| 台南市| 图木舒克市| 寻乌县| 上饶县| 汕头市| 惠州市|