記得java老師曾經說過百度的一個面試題目，大概意思是“有1W條無序的記錄，如何從其中快速的查找到自己想要的記錄”。這個就相當于一個簡單的搜索引擎。最近在整理這一年的工作中，自己竟然已經把這個實現了，今天對其進一步的抽象，和大家分享下。
先寫具體的實現代碼，具體的實現思路和邏輯寫在代碼之后。
搜索時用于排序的Bean
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/** *@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; } } |
構造的搜索數據結構以及簡單的搜索算法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
/** *@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); } } } |
測試用例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/** *@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); } } } } |
測試輸出結果如下：
|
1
2
3
4
5
6
|
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方法即可。
上述的只是一個簡單的搜索引擎，并沒有設計太多的計算方法，希望對大家的學習有所啟發。
