Java實現的雙向匹配分詞算法示例
更新時間：2017年12月19日 11:44:11 作者：誰將舊詞譯成新曲
這篇文章主要介紹了Java實現的雙向匹配分詞算法,結合完整實例形式詳細分析了雙向匹配分詞算法的原理與java實現技巧,需要的朋友可以參考下
本文實例講述了Java實現的雙向匹配分詞算法。分享給大家供大家參考，具體如下：
目前比較流行的幾大分詞算法有：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計的分詞方法。本文采用的是基于字符串匹配法。
正向最大匹配分詞：
該算法是基于分詞詞典實現，從字符串左側進行分割匹配，如果詞典存在則返回分割出來的詞語并將該詞從之前的字符串中切除，循環(huán)進行切割直到字符串大小為0。
例如：str = "我們都是西北農林科技大學信息工程學院的學生。",（假設我們定義最大切割長度max = 8，也就是八個漢字）
1.定義分詞長度len = max，從左邊取出len個字符word = "我們都是西北農林"，并在字典中匹配word；
2.字典中沒有該詞，那么去掉最后一個字符賦值給word，len值減1；
3.重復步驟2，直到在字典中找到該詞或是len = 1，退出循環(huán)；
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+", "");
// 當待切分字符串沒有被切分完時循環(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) {
// 如果是字母或是數字要將連續(xù)的字母或者數字分在一起
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ù)數字、字母字符加起來并翻轉
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雙向分詞結果：");*/
// 判斷兩頭的分詞拼接，是否已經在輸入字符串的中間交匯，只要沒有交匯，就不停循環(huán)
while (left.get(0).length() + right.get(right.size() - 1).length() < inputStr
.length()) {
// 如果正逆向分詞結果相等，那么取正向結果跳出循環(huán)
if (isEqual(left, right)) {
resultMiddle = left;
break;
}
// 如果正反向分詞結果不同，則取分詞數量較少的那個，不用再循環(huán)
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);
}
// 循環(huán)結束，說明要么分詞沒有歧義了，要么"貪吃蛇"從兩頭吃到中間交匯了
// 如果是在中間交匯，交匯時的分詞結果，還要進行以下判斷：
// 如果中間交匯有重疊了：
// 正向第一個分詞的長度 + 反向最后一個分詞的長度 > 輸入字符串總長度，就直接取正向的
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節(jié)點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
相關文章
這篇文章主要介紹了Kafka 網絡中斷和網絡分區(qū)4種場景分析2007-02-02
這篇文章主要介紹了關于springboot上傳圖片與視頻不顯示問題,最近做畢設時候需要上傳視頻的圖片與視頻,但是每次都需要重啟前端才能展示出此圖片,所以本文給大家介紹了SpringBoot上傳圖片與視頻不顯示問題的解決方案,需要的朋友可以參考下2024-03-03
這篇文章主要介紹了Java進階教程之IO基礎,這里只是對Java IO的基本介紹,包含讀取和寫入等操作,需要的朋友可以參考下2014-09-09
微服務架構已經成為現代應用開發(fā)的熱門趨勢,而Dubbo作為一款強大的分布式服務框架,與Spring?Boot的結合是構建高性能微服務應用的理想選擇,本文將詳細介紹如何在SpringBoot中無縫整合Dubbo,需要的朋友可以參考下2024-01-01
這篇文章主要為大家詳細介紹了Java上傳文件到服務器端的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要給大家介紹了關于java中將一個實體類復制到另一個實體類的3種方法,所謂實體類就是一個擁有Set和Get方法的類,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-07-07
全面解析Spring Security 過濾器鏈的機制和特性
這篇文章主要介紹了Spring Security 過濾器鏈的機制和特性,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
java使用CompletableFuture分批處理任務實現
本文主要介紹了java使用CompletableFuture分批處理任務實現,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-07-07
這篇文章主要介紹了java 如何實現正確的刪除集合中的元素，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
Springboot實現人臉識別與WebSocket長連接的實現代碼
這篇文章主要介紹了Springboot實現人臉識別與WebSocket長連接的實現,本文通過示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2023-11-11