本文實例講述了Java實現的雙向匹配分詞算法。分享給大家供大家參考,具體如下:
目前比較流行的幾大分詞算法有:基於字符串匹配的分詞方法、基於理解的分詞方法和基於統計的分詞方法。本文采用的是基於字符串匹配法。
正向最大匹配分詞:
該算法是基於分詞詞典實現,從字符串左側進行分割匹配,如果詞典存在則返回分割出來的詞語並將該詞從之前的字符串中切除,循環進行切割直到字符串大小為0。
例如:str = "我們都是西北農林科技大學信息工程學院的學生。",(假設我們定義最大切割長度max = 8,也就是八個漢字)
1.定義分詞長度len = max,從左邊取出len個字符word = "我們都是西北農林",並在字典中匹配word;
2.字典中沒有該詞,那麼去掉最後一個字符賦值給word,len值減1;
3.重複步驟2,直到在字典中找到該詞或是len = 1,退出循環;
4.從str中切除掉已分割的詞語,重複進行1、2、3步驟,直到str被分解完。
逆向最大匹配分詞:
和正向分詞算法一樣,只是從字符串的右邊開始切分詞語,直到字符串長度為0,。這裡不再贅述。
雙向匹配分詞:
該方法是在正向分詞和逆向分詞的基礎上,對於分割有歧義的語句進行歧義分詞。提出“貪吃蛇算法”實現。要進行分詞的字符串,就是食物。有2個貪吃蛇,一個從左向右吃;另一個從右向左吃。只要左右分詞結果有歧義,2條蛇就咬下一口。貪吃蛇吃下去的字符串,就變成分詞。 如果左右分詞一直有歧義,兩條蛇就一直吃。兩條蛇吃到字符串中間交匯時,就肯定不會有歧義了。這時候,左邊貪吃蛇肚子裡的分詞,中間沒有歧義的分詞,右邊貪吃蛇肚子裡的分詞,3個一拼,就是最終的分詞結果。
本文是對整段話進行分詞,首先將這段話根據標點符號斷句,然後將每句話再進行分詞輸出。
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;/** * 基於正逆雙向最大匹配分詞算法實現* @author 劉永浪* */public class WordSpilt { /** * 存儲分詞詞典*/ private Map<String, Integer> map = new HashMap<String, Integer>(); /** * 最大切詞長度,即為五個漢字*/ private int MAX_LENGTH = 5; /** * 構造方法中讀取分詞詞典,並存儲到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(); } /** * 設置最大切詞長度* * @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; // 取詞的長度,初始化設置為最大值int wordLength = MAX_LENGTH; // 分詞操作中處於字串當前位置int position = 0; // 已經處理字符串的長度int length = 0; // 去掉字符串中多餘的空格spiltStr = spiltStr.trim().replaceAll("//s+", ""); // 當待切分字符串沒有被切分完時循環切分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)) { // 如果是單字,退出循環if (word.length() == 1) { // 如果是字母或是數字要將連續的字母或者數字分在一起if (word.matches("[a-zA-z0-9]")) { // 如果是正向匹配直接循環將後續連續字符加起來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 { // 如果是逆向匹配,從當前位置之前的連續數字、字母字符加起來並翻轉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 { // 翻轉操作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(); } // 如果是逆向最大匹配,要把表中的字符串調整為正向if (!leftToRight) { for (int i = rightWords.size() - 1; i >= 0; i--) { leftWords.add(rightWords.get(i)); } } // 返回切分結果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; } /** * 判別分詞歧義函數* * @param inputStr * 待切分字符串* @return 分詞結果*/ public List<String> resultWord(String inputStr) { // 分詞結果List<String> result = new ArrayList<String>(); // “左貪吃蛇”分詞結果List<String> resultLeft = new ArrayList<String>(); // “中貪吃蛇”(分歧部分)分詞結果List<String> resultMiddle = new ArrayList<String>(); // “右貪吃蛇”分詞結果List<String> resultRight = new ArrayList<String>(); // 正向最大匹配分詞結果List<String> left = new ArrayList<String>(); // 逆向最大匹配分詞結果List<String> right = new ArrayList<String>(); left = spilt(inputStr, true); /*System.out.println("正向分詞結果:"); for (String string : left) { System.out.print(string + "/"); } System.out.println("/n逆向分詞結果:");*/ right = spilt(inputStr, false); /*for (String string : right) { System.out.print(string + "/"); } System.out.println("/n雙向分詞結果:");*/ // 判斷兩頭的分詞拼接,是否已經在輸入字符串的中間交匯,只要沒有交匯,就不停循環while (left.get(0).length() + right.get(right.size() - 1).length() < inputStr .length()) { // 如果正逆向分詞結果相等,那麼取正向結果跳出循環if (isEqual(left, right)) { resultMiddle = left; break; } // 如果正反向分詞結果不同,則取分詞數量較少的那個,不用再循環if (left.size() != right.size()) { resultMiddle = left.size() < right.size() ? left : right; break; } // 如果以上條件都不符合,那麼實行“貪吃蛇”算法// 讓“左貪吃蛇”吃下正向分詞結果的第一個詞resultLeft.add(left.get(0)); // 讓“右貪吃蛇”吃下逆向分詞結果的最後一個詞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()); // 清理之前正逆向分詞結果,防止造成乾擾left.clear(); right.clear(); // 對沒被吃掉的字符串重新開始分詞left = spilt(inputStr, true); right = spilt(inputStr, false); } // 循環結束,說明要么分詞沒有歧義了,要么"貪吃蛇"從兩頭吃到中間交匯了// 如果是在中間交匯,交匯時的分詞結果,還要進行以下判斷: // 如果中間交匯有重疊了: // 正向第一個分詞的長度+ 反向最後一個分詞的長度> 輸入字符串總長度,就直接取正向的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)); } // 將沒有歧義的分詞結果添加到最終結果result中for (String string : resultLeft) { result.add(string); } for (String string : resultMiddle) { result.add(string); } // “右貪吃蛇”存儲的分詞要調整為正向for (int i = resultRight.size() - 1; i >= 0; i--) { result.add(resultRight.get(i)); } return result; } /** * 將一段話分割成若干句話,分別進行分詞* * @param inputStr * 待分割的一段話* @return 這段話的分詞結果*/ public List<String> resultSpilt(String inputStr) { // 用於存儲最終分詞結果List<String> result = new ArrayList<String>(); // 如果遇到標點就分割成若干句話String regex = "[,。;!?]"; String[] st = inputStr.split(regex); // 將每一句話的分詞結果添加到最終分詞結果中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為字典文件,這裡設置如下:
歡迎武林網腳本下載腳本教程素材下載
運行結果如下:
更多關於java算法相關內容感興趣的讀者可查看本站專題:《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。