本文實例講述了Java實現(xiàn)的雙向匹配分詞算法。分享給大家供大家參考，具體如下：
目前比較流行的幾大分詞算法有：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計的分詞方法。本文采用的是基于字符串匹配法。
正向最大匹配分詞：
該算法是基于分詞詞典實現(xiàn)，從字符串左側(cè)進行分割匹配，如果詞典存在則返回分割出來的詞語并將該詞從之前的字符串中切除，循環(huán)進行切割直到字符串大小為0。
例如：str = "我們都是西北農(nóng)林科技大學信息工程學院的學生。",（假設(shè)我們定義最大切割長度max = 8，也就是八個漢字）
1.定義分詞長度len = max，從左邊取出len個字符word = "我們都是西北農(nóng)林"，并在字典中匹配word；
2.字典中沒有該詞，那么去掉最后一個字符賦值給word，len值減1；
3.重復步驟2，直到在字典中找到該詞或是len = 1，退出循環(huán)；
4.從str中切除掉已分割的詞語，重復進行1、2、3步驟，直到str被分解完。
逆向最大匹配分詞：
和正向分詞算法一樣，只是從字符串的右邊開始切分詞語，直到字符串長度為0,。這里不再贅述。
雙向匹配分詞：
該方法是在正向分詞和逆向分詞的基礎(chǔ)上，對于分割有歧義的語句進行歧義分詞。提出“貪吃蛇算法”實現(xiàn)。要進行分詞的字符串，就是食物。有2個貪吃蛇，一個從左向右吃；另一個從右向左吃。只要左右分詞結(jié)果有歧義，2條蛇就咬下一口。貪吃蛇吃下去的字符串，就變成分詞。 如果左右分詞一直有歧義，兩條蛇就一直吃。兩條蛇吃到字符串中間交匯時，就肯定不會有歧義了。這時候，左邊貪吃蛇肚子里的分詞，中間沒有歧義的分詞，右邊貪吃蛇肚子里的分詞，3個一拼，就是最終的分詞結(jié)果。
本文是對整段話進行分詞，首先將這段話根據(jù)標點符號斷句，然后將每句話再進行分詞輸出。
|
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
|
package cn.nwsuaf.spilt;import java.io.BufferedReader;import java.io.FileReader;import java.io.IOException;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Scanner;/** * 基于正逆雙向最大匹配分詞算法實現(xiàn) * @author 劉永浪 * */public class WordSpilt { /** * 存儲分詞詞典 */ private Map<String, Integer> map = new HashMap<String, Integer>(); /** * 最大切詞長度,即為五個漢字 */ private int MAX_LENGTH = 5; /** * 構(gòu)造方法中讀取分詞詞典，并存儲到map中 * * @throws IOException */ public WordSpilt() throws IOException { BufferedReader br = new BufferedReader(new FileReader("src/dict.txt")); String line = null; while ((line = br.readLine()) != null) { line = line.trim(); map.put(line, 0); } br.close(); } /** * 設(shè)置最大切詞長度 * * @param max * 最大切詞長度 */ public void setMaxLength(int max) { this.MAX_LENGTH = max; } /** * 獲取當前最大切詞長度，默認為5（5個漢字） * * @return 當前最大切詞長度 */ public int getMaxLength() { return this.MAX_LENGTH; } /** * 最大匹配分詞算法 * * @param spiltStr * 待切分的字符串 * @param leftToRight * 切分方向，true為從左向右，false為從右向左 * @return 切分的字符串 */ public List<String> spilt(String spiltStr, boolean leftToRight) { // 如果帶切分字符串為空則返回空 if (spiltStr.isEmpty()) return null; // 儲存正向匹配分割字符串 List<String> leftWords = new ArrayList<String>(); // 儲存負向匹配分割字符串 List<String> rightWords = new ArrayList<String>(); // 用于取切分的字串 String word = null; // 取詞的長度，初始化設(shè)置為最大值 int wordLength = MAX_LENGTH; // 分詞操作中處于字串當前位置 int position = 0; // 已經(jīng)處理字符串的長度 int length = 0; // 去掉字符串中多余的空格 spiltStr = spiltStr.trim().replaceAll("\\s+", ""); // 當待切分字符串沒有被切分完時循環(huán)切分 while (length < spiltStr.length()) { // 如果還沒切分的字符串長度小于最大值，讓取詞詞長等于該詞本身長度 if (spiltStr.length() - length < MAX_LENGTH) wordLength = spiltStr.length() - length; // 否則取默認值 else wordLength = MAX_LENGTH; // 如果是正向最大匹配，從spiltStr的position處開始切割 if (leftToRight) { position = length; word = spiltStr.substring(position, position + wordLength); } // 如果是逆向最大匹配，從spiltStr末尾開始切割 else { position = spiltStr.length() - length; word = spiltStr.substring(position - wordLength, position); } // 從當前位置開始切割指定長度的字符串 // word = spiltStr.substring(position, position + wordLength); // 如果分詞詞典里面沒有切割出來的字符串，舍去一個字符 while (!map.containsKey(word)) { // 如果是單字，退出循環(huán) if (word.length() == 1) { // 如果是字母或是數(shù)字要將連續(xù)的字母或者數(shù)字分在一起 if (word.matches("[a-zA-z0-9]")) { // 如果是正向匹配直接循環(huán)將后續(xù)連續(xù)字符加起來 if (leftToRight) { for (int i = spiltStr.indexOf(word, position) + 1; i < spiltStr .length(); i++) { if ((spiltStr.charAt(i) >= '0' && spiltStr .charAt(i) <= '9') || (spiltStr.charAt(i) >= 'A' && spiltStr .charAt(i) <= 'Z') || (spiltStr.charAt(i) >= 'a' && spiltStr .charAt(i) <= 'z')) { word += spiltStr.charAt(i); } else break; } } else { // 如果是逆向匹配，從當前位置之前的連續(xù)數(shù)字、字母字符加起來并翻轉(zhuǎn) for (int i = spiltStr.indexOf(word, position - 1) - 1; i >= 0; i--) { if ((spiltStr.charAt(i) >= '0' && spiltStr .charAt(i) <= '9') || (spiltStr.charAt(i) >= 'A' && spiltStr .charAt(i) <= 'Z') || (spiltStr.charAt(i) >= 'a' && spiltStr .charAt(i) <= 'z')) { word += spiltStr.charAt(i); if (i == 0) { StringBuffer sb = new StringBuffer(word); word = sb.reverse().toString(); } } else { // 翻轉(zhuǎn)操作 StringBuffer sb = new StringBuffer(word); word = sb.reverse().toString(); break; } } } } break; } // 如果是正向最大匹配，舍去最后一個字符 if (leftToRight) word = word.substring(0, word.length() - 1); // 否則舍去第一個字符 else word = word.substring(1); } // 將切分出來的字符串存到指定的表中 if (leftToRight) leftWords.add(word); else rightWords.add(word); // 已處理字符串增加 length += word.length(); } // 如果是逆向最大匹配，要把表中的字符串調(diào)整為正向 if (!leftToRight) { for (int i = rightWords.size() - 1; i >= 0; i--) { leftWords.add(rightWords.get(i)); } } // 返回切分結(jié)果 return leftWords; } /** * 判斷兩個集合是否相等 * * @param list1 * 集合1 * @param list2 * 集合2 * @return 如果相等則返回true，否則為false */ public boolean isEqual(List<String> list1, List<String> list2) { if (list1.isEmpty() && list2.isEmpty()) return false; if (list1.size() != list2.size()) return false; for (int i = 0; i < list1.size(); i++) { if (!list1.get(i).equals(list2.get(i))) return false; } return true; } /** * 判別分詞歧義函數(shù) * * @param inputStr * 待切分字符串 * @return 分詞結(jié)果 */ public List<String> resultWord(String inputStr) { // 分詞結(jié)果 List<String> result = new ArrayList<String>(); // “左貪吃蛇”分詞結(jié)果 List<String> resultLeft = new ArrayList<String>(); // “中貪吃蛇”（分歧部分）分詞結(jié)果 List<String> resultMiddle = new ArrayList<String>(); // “右貪吃蛇”分詞結(jié)果 List<String> resultRight = new ArrayList<String>(); // 正向最大匹配分詞結(jié)果 List<String> left = new ArrayList<String>(); // 逆向最大匹配分詞結(jié)果 List<String> right = new ArrayList<String>(); left = spilt(inputStr, true); /*System.out.println("正向分詞結(jié)果："); for (String string : left) { System.out.print(string + "/"); } System.out.println("\n逆向分詞結(jié)果：");*/ right = spilt(inputStr, false); /*for (String string : right) { System.out.print(string + "/"); } System.out.println("\n雙向分詞結(jié)果：");*/ // 判斷兩頭的分詞拼接，是否已經(jīng)在輸入字符串的中間交匯，只要沒有交匯，就不停循環(huán) while (left.get(0).length() + right.get(right.size() - 1).length() < inputStr .length()) { // 如果正逆向分詞結(jié)果相等，那么取正向結(jié)果跳出循環(huán) if (isEqual(left, right)) { resultMiddle = left; break; } // 如果正反向分詞結(jié)果不同，則取分詞數(shù)量較少的那個，不用再循環(huán) if (left.size() != right.size()) { resultMiddle = left.size() < right.size() ? left : right; break; } // 如果以上條件都不符合，那么實行“貪吃蛇”算法 // 讓“左貪吃蛇”吃下正向分詞結(jié)果的第一個詞 resultLeft.add(left.get(0)); // 讓“右貪吃蛇”吃下逆向分詞結(jié)果的最后一個詞 resultRight.add(right.get(right.size() - 1)); // 去掉被“貪吃蛇”吃掉的詞語 inputStr = inputStr.substring(left.get(0).length()); inputStr = inputStr.substring(0, inputStr.length() - right.get(right.size() - 1).length()); // 清理之前正逆向分詞結(jié)果，防止造成干擾 left.clear(); right.clear(); // 對沒被吃掉的字符串重新開始分詞 left = spilt(inputStr, true); right = spilt(inputStr, false); } // 循環(huán)結(jié)束，說明要么分詞沒有歧義了，要么"貪吃蛇"從兩頭吃到中間交匯了 // 如果是在中間交匯，交匯時的分詞結(jié)果，還要進行以下判斷： // 如果中間交匯有重疊了： // 正向第一個分詞的長度 + 反向最后一個分詞的長度 > 輸入字符串總長度，就直接取正向的 if (left.get(0).length() + right.get(right.size() - 1).length() > inputStr .length()) resultMiddle = left; // 如果中間交匯，剛好吃完，沒有重疊： // 正向第一個分詞 + 反向最后一個分詞的長度 = 輸入字符串總長度，那么正反向一拼即可 if (left.get(0).length() + right.get(right.size() - 1).length() == inputStr .length()) { resultMiddle.add(left.get(0)); resultMiddle.add(right.get(right.size() - 1)); } // 將沒有歧義的分詞結(jié)果添加到最終結(jié)果result中 for (String string : resultLeft) { result.add(string); } for (String string : resultMiddle) { result.add(string); } // “右貪吃蛇”存儲的分詞要調(diào)整為正向 for (int i = resultRight.size() - 1; i >= 0; i--) { result.add(resultRight.get(i)); } return result; } /** * 將一段話分割成若干句話，分別進行分詞 * * @param inputStr * 待分割的一段話 * @return 這段話的分詞結(jié)果 */ public List<String> resultSpilt(String inputStr) { // 用于存儲最終分詞結(jié)果 List<String> result = new ArrayList<String>(); // 如果遇到標點就分割成若干句話 String regex = "[，。；！？]"; String[] st = inputStr.split(regex); // 將每一句話的分詞結(jié)果添加到最終分詞結(jié)果中 for (String stri : st) { List<String> list = resultWord(stri); result.addAll(list); } return result; } public static void main(String[] args) { // example:過來看房價貴不貴？乒乓球拍賣完了 Scanner input = new Scanner(System.in); String str = input.nextLine(); WordSpilt wordSpilt = null; try { wordSpilt = new WordSpilt(); } catch (IOException e) { e.printStackTrace(); } List<String> list = wordSpilt.resultWord(str); for (String string : list) { System.out.print(string + "/"); } }} |
其中的src/dict.txt為字典文件，這里設(shè)置如下：
|
1
2
3
4
5
6
7
|
歡迎服務器之家腳本下載腳本教程素材下載 |
運行結(jié)果如下：
希望本文所述對大家java程序設(shè)計有所幫助。
原文鏈接：http://blog.csdn.net/lylwanan/article/details/38555929
