模糊查詢的思考
現實中經常有這樣的問題,我們要從很多東西里邊找到一個東西,而這些東西有很多別名,例如地點。如
何實現模糊查找呢?
說到查找就要考慮這樣的問題,效率,模糊查找。說到效率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) 編輯 收藏 所屬分類: 基礎