記得java老師曾經說過百度的一個面試題目，大概意思是“有1W條無序的記錄，如何從其中快速的查找到自己想要的記錄”。這個就相當于一個簡單的搜索引擎。最近在整理這一年的工作中，自己竟然已經把這個實現了，今天對其進一步的抽象，和大家分享下。
先寫具體的實現代碼，具體的實現思路和邏輯寫在代碼之后。
搜索時用于排序的Bean
/** *@Description: */ package cn.lulei.search.engine.model; public class SortBean { private String id; private int times; public String getId() { return id; } public void setId(String id) { this.id = id; } public int getTimes() { return times; } public void setTimes(int times) { this.times = times; } } 構造的搜索數據結構以及簡單的搜索算法
/** *@Description: */ package cn.lulei.search.engine; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.List; import cn.lulei.search.engine.model.SortBean; public class SerachBase { //details 存儲搜素對象的詳細信息，其中key作為區分Object的唯一標識 private HashMap<String, Object> details = new HashMap<String, Object>(); //對于參與搜索的關鍵詞，這里采用的稀疏數組存儲，也可以采用HashMap來存儲，定義格式如下 //private static HashMap<Integer, HashSet<String>> keySearch = new HashMap<Integer, HashSet<String>>(); //HashMap中額key值相當于稀疏數組中的下標，value相當于稀疏數組在該位置的值 private final static int maxLength = Character.MAX_VALUE; @SuppressWarnings("unchecked") private HashSet<String>[] keySearch = new HashSet[maxLength]; /** *@Description: 實現單例模式，采用Initialization on Demand Holder加載 *@Version:1.1.0 */ private static class lazyLoadSerachBase { private static final SerachBase serachBase = new SerachBase(); } /** * 這里把構造方法設置成私有為的是單例模式 */ private SerachBase() { } /** * @return * @Description: 獲取單例 */ public static SerachBase getSerachBase() { return lazyLoadSerachBase.serachBase; } /** * @param id * @return * @Description: 根據id獲取詳細 */ public Object getObject(String id) { return details.get(id); } /** * @param ids * @return * @Description: 根據ids獲取詳細，id之間用","隔開 */ public List<Object> getObjects(String ids) { if (ids == null || "".equals(ids)) { return null; } List<Object> objs = new ArrayList<Object>(); String[] idArray = ids.split(","); for (String id : idArray) { objs.add(getObject(id)); } return objs; } /** * @param key * @return * @Description: 根據搜索詞查找對應的id，id之間用","分割 */ public String getIds(String key) { if (key == null || "".equals(key)) { return null; } //查找 //idTimes存儲搜索詞每個字符在id中是否出現 HashMap<String, Integer> idTimes = new HashMap<String, Integer>(); //ids存儲出現搜索詞中的字符的id HashSet<String> ids = new HashSet<String>(); //從搜索庫中去查找 for (int i = 0; i < key.length(); i++) { int at = key.charAt(i); //搜索詞庫中沒有對應的字符，則進行下一個字符的匹配 if (keySearch[at] == null) { continue; } for (Object obj : keySearch[at].toArray()) { String id = (String) obj; int times = 1; if (ids.contains(id)) { times += idTimes.get(id); idTimes.put(id, times); } else { ids.add(id); idTimes.put(id, times); } } } //使用數組排序 List<SortBean> sortBeans = new ArrayList<SortBean>(); for (String id : ids) { SortBean sortBean = new SortBean(); sortBeans.add(sortBean); sortBean.setId(id); sortBean.setTimes(idTimes.get(id)); } Collections.sort(sortBeans, new Comparator<SortBean>(){ public int compare(SortBean o1, SortBean o2){ return o2.getTimes() - o1.getTimes(); } }); //構建返回字符串 StringBuffer sb = new StringBuffer(); for (SortBean sortBean : sortBeans) { sb.append(sortBean.getId()); sb.append(","); } //釋放資源 idTimes.clear(); idTimes = null; ids.clear(); ids = null; sortBeans.clear(); sortBeans = null; //返回 return sb.toString(); } /** * @param id * @param searchKey * @param obj * @Description: 添加搜索記錄 */ public void add(String id, String searchKey, Object obj) { //參數有部分為空，不加載 if (id == null || searchKey == null || obj == null) { return; } //保存對象 details.put(id, obj); //保存搜索詞 addSearchKey(id, searchKey); } /** * @param id * @param searchKey * @Description: 將搜索詞加入到搜索域中 */ private void addSearchKey(String id, String searchKey) { //參數有部分為空，不加載 //這里是私有方法，可以不做如下判斷，但為了設計規范，還是加上 if (id == null || searchKey == null) { return; } //下面采用的是字符分詞，這里也可以使用現在成熟的其他分詞器 for (int i = 0; i < searchKey.length(); i++) { //at值相當于是數組的下標，id組成的HashSet相當于數組的值 int at = searchKey.charAt(i); if (keySearch[at] == null) { HashSet<String> value = new HashSet<String>(); keySearch[at] = value; } keySearch[at].add(id); } } } 測試用例：
/** *@Description: */ package cn.lulei.search.engine.test; import java.util.List; import cn.lulei.search.engine.SerachBase; public class Test { public static void main(String[] args) { // TODO Auto-generated method stub SerachBase serachBase = SerachBase.getSerachBase(); serachBase.add("1", "你好！", "你好！"); serachBase.add("2", "你好！我是張三。", "你好！我是張三。"); serachBase.add("3", "今天的天氣挺好的。", "今天的天氣挺好的。"); serachBase.add("4", "你是誰？", "你是誰？"); serachBase.add("5", "高數這門學科很難", "高數確實很難。"); serachBase.add("6", "測試", "上面的只是測試"); String ids = serachBase.getIds("你的高數"); System.out.println(ids); List<Object> objs = serachBase.getObjects(ids); if (objs != null) { for (Object obj : objs) { System.out.println((String) obj); } } } } 測試輸出結果如下：
5,3,2,1,4,高數確實很難。今天的天氣挺好的。你好！我是張三。你好！你是誰？
這樣一個簡單的搜索引擎也就算是完成了。
問題一：這里面的分詞采用的是字符分詞，對漢語的處理還是挺不錯的，但是對英文的處理就很弱。
改進方法：采用現在成熟的分詞方法，比如IKAnalyzer、StandardAnalyzer等，這樣修改，keySearch的數據結構就需要做下修改，可以修改為 private HashMap<String, String>[] keySearch = new HashMap[maxLength]; 其中key存儲分的詞元，value存儲唯一標識id。
問題二：本文實現的搜索引擎對詞元并沒有像lucene設置權重，只是簡單的判斷詞元是否在對象中出現。
改進方法：暫無。添加權重處理，使數據結構更加復雜，所以暫時沒有對其做處理，在今后的文章中會實現權重的處理。
下面就簡單的介紹一下搜索引擎的實現思路。
在SerachBase類中設置details和keySearch兩個屬性，details用于存儲Object的詳細信息，keySearch用于對搜索域做索引。details數據格式為HashMap，keySearch的數據格式為稀疏數組（也可以為HashMap，HashMap中額key值相當于稀疏數組中的下標，value相當于稀疏數組在該位置的值）。
對于details我就不做太多的介紹。
keySearch中數組下標（如用HashMap就是key）的計算方法是獲取詞元的第一個字符int值（因為本文的分詞采用的是字符分詞，所以一個字符就是一個詞元），該int值就是數組的下標，相應的數組值就是Object的唯一標識。這樣keySearch的數據結構就如下圖
因此想添加新紀錄的時候只需要調用add方法即可。
對于搜索的實現邏輯和上面的keySearch類似。對于id的搜索直接使用HashMap的get方法即可。對于搜索詞的一個搜索，整體的過程也是采用先分詞、其次查詢、最后排序。當然這里面的分詞要和創建采用的分詞要一致（即創建的時候采用字符分詞，查找的時候也采用字符分詞）。
在getIds方法中，HashMap<String, Integer> idTimes = new HashMap<String, Integer>();idTimes 變量用來存儲搜索詞中的詞元有多少個在keySearch中出現，key值為唯一標識id，value為出現的詞元個數。HashSet<String> ids = new HashSet<String>(); ids變量用來存儲出現的詞元的ids。這樣搜索的復雜度就是搜索詞的詞元個數n。獲得包含詞元的ids，構造SortBean數組，對其排序，排序規則是出現詞元個數的降序排列。最后返回ids字符串，每個id用"，"分割。如要獲取詳細信息
再使用getObjects方法即可。
上述的只是一個簡單的搜索引擎，并沒有設計太多的計算方法，希望對大家的學習有所啟發。
新聞熱點
疑難解答
