怎么在Java中實(shí)現(xiàn)一個(gè)雙向匹配分詞算法

本篇文章為大家展示了怎么在Java中實(shí)現(xiàn)一個(gè)雙向匹配分詞算法，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。

正向最大匹配分詞：

該算法是基于分詞詞典實(shí)現(xiàn)，從字符串左側(cè)進(jìn)行分割匹配，如果詞典存在則返回分割出來(lái)的詞語(yǔ)并將該詞從之前的字符串中切除，循環(huán)進(jìn)行切割直到字符串大小為0。

例如：str = "我們都是西北農(nóng)林科技大學(xué)信息工程學(xué)院的學(xué)生。",（假設(shè)我們定義最大切割長(zhǎng)度max = 8，也就是八個(gè)漢字）

1.定義分詞長(zhǎng)度len = max，從左邊取出len個(gè)字符word = "我們都是西北農(nóng)林"，并在字典中匹配word；
2.字典中沒(méi)有該詞，那么去掉最后一個(gè)字符賦值給word，len值減1；
3.重復(fù)步驟2，直到在字典中找到該詞或是len = 1，退出循環(huán)；
4.從str中切除掉已分割的詞語(yǔ)，重復(fù)進(jìn)行1、2、3步驟，直到str被分解完。

逆向最大匹配分詞：

和正向分詞算法一樣，只是從字符串的右邊開(kāi)始切分詞語(yǔ)，直到字符串長(zhǎng)度為0,。這里不再贅述。

雙向匹配分詞：

該方法是在正向分詞和逆向分詞的基礎(chǔ)上，對(duì)于分割有歧義的語(yǔ)句進(jìn)行歧義分詞。提出“貪吃蛇算法”實(shí)現(xiàn)。要進(jìn)行分詞的字符串，就是食物。有2個(gè)貪吃蛇，一個(gè)從左向右吃；另一個(gè)從右向左吃。只要左右分詞結(jié)果有歧義，2條蛇就咬下一口。貪吃蛇吃下去的字符串，就變成分詞。 如果左右分詞一直有歧義，兩條蛇就一直吃。兩條蛇吃到字符串中間交匯時(shí)，就肯定不會(huì)有歧義了。這時(shí)候，左邊貪吃蛇肚子里的分詞，中間沒(méi)有歧義的分詞，右邊貪吃蛇肚子里的分詞，3個(gè)一拼，就是最終的分詞結(jié)果。

本文是對(duì)整段話進(jìn)行分詞，首先將這段話根據(jù)標(biāo)點(diǎn)符號(hào)斷句，然后將每句話再進(jìn)行分詞輸出。

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;
/**
 * 基于正逆雙向最大匹配分詞算法實(shí)現(xiàn)
 * @author 劉永浪
 *
 */
public class WordSpilt {
  /**
   * 存儲(chǔ)分詞詞典
   */
  private Map<String, Integer> map = new HashMap<String, Integer>();
  /**
   * 最大切詞長(zhǎng)度,即為五個(gè)漢字
   */
  private int MAX_LENGTH = 5;
  /**
   * 構(gòu)造方法中讀取分詞詞典，并存儲(chǔ)到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è)置最大切詞長(zhǎng)度
   *
   * @param max
   *      最大切詞長(zhǎng)度
   */
  public void setMaxLength(int max) {
    this.MAX_LENGTH = max;
  }
  /**
   * 獲取當(dāng)前最大切詞長(zhǎng)度，默認(rèn)為5（5個(gè)漢字）
   *
   * @return 當(dāng)前最大切詞長(zhǎng)度
   */
  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;
    // 儲(chǔ)存正向匹配分割字符串
    List<String> leftWords = new ArrayList<String>();
    // 儲(chǔ)存負(fù)向匹配分割字符串
    List<String> rightWords = new ArrayList<String>();
    // 用于取切分的字串
    String word = null;
    // 取詞的長(zhǎng)度，初始化設(shè)置為最大值
    int wordLength = MAX_LENGTH;
    // 分詞操作中處于字串當(dāng)前位置
    int position = 0;
    // 已經(jīng)處理字符串的長(zhǎng)度
    int length = 0;
    // 去掉字符串中多余的空格
    spiltStr = spiltStr.trim().replaceAll("\\s+", "");
    // 當(dāng)待切分字符串沒(méi)有被切分完時(shí)循環(huán)切分
    while (length < spiltStr.length()) {
      // 如果還沒(méi)切分的字符串長(zhǎng)度小于最大值，讓取詞詞長(zhǎng)等于該詞本身長(zhǎng)度
      if (spiltStr.length() - length < MAX_LENGTH)
        wordLength = spiltStr.length() - length;
      // 否則取默認(rèn)值
      else
        wordLength = MAX_LENGTH;
      // 如果是正向最大匹配，從spiltStr的position處開(kāi)始切割
      if (leftToRight) {
        position = length;
        word = spiltStr.substring(position, position + wordLength);
      }
      // 如果是逆向最大匹配，從spiltStr末尾開(kāi)始切割
      else {
        position = spiltStr.length() - length;
        word = spiltStr.substring(position - wordLength, position);
      }
      // 從當(dāng)前位置開(kāi)始切割指定長(zhǎng)度的字符串
      // word = spiltStr.substring(position, position + wordLength);
      // 如果分詞詞典里面沒(méi)有切割出來(lái)的字符串，舍去一個(gè)字符
      while (!map.containsKey(word)) {
        // 如果是單字，退出循環(huán)
        if (word.length() == 1) {
          // 如果是字母或是數(shù)字要將連續(xù)的字母或者數(shù)字分在一起
          if (word.matches("[a-zA-z0-9]")) {
            // 如果是正向匹配直接循環(huán)將后續(xù)連續(xù)字符加起來(lái)
            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 {
              // 如果是逆向匹配，從當(dāng)前位置之前的連續(xù)數(shù)字、字母字符加起來(lái)并翻轉(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;
        }
        // 如果是正向最大匹配，舍去最后一個(gè)字符
        if (leftToRight)
          word = word.substring(0, word.length() - 1);
        // 否則舍去第一個(gè)字符
        else
          word = word.substring(1);
      }
      // 將切分出來(lái)的字符串存到指定的表中
      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;
  }
  /**
   * 判斷兩個(gè)集合是否相等
   *
   * @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)在輸入字符串的中間交匯，只要沒(méi)有交匯，就不停循環(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ù)量較少的那個(gè)，不用再循環(huán)
      if (left.size() != right.size()) {
        resultMiddle = left.size() < right.size() ? left : right;
        break;
      }
      // 如果以上條件都不符合，那么實(shí)行“貪吃蛇”算法
      // 讓“左貪吃蛇”吃下正向分詞結(jié)果的第一個(gè)詞
      resultLeft.add(left.get(0));
      // 讓“右貪吃蛇”吃下逆向分詞結(jié)果的最后一個(gè)詞
      resultRight.add(right.get(right.size() - 1));
      // 去掉被“貪吃蛇”吃掉的詞語(yǔ)
      inputStr = inputStr.substring(left.get(0).length());
      inputStr = inputStr.substring(0,
          inputStr.length() - right.get(right.size() - 1).length());
      // 清理之前正逆向分詞結(jié)果，防止造成干擾
      left.clear();
      right.clear();
      // 對(duì)沒(méi)被吃掉的字符串重新開(kāi)始分詞
      left = spilt(inputStr, true);
      right = spilt(inputStr, false);
    }
    // 循環(huán)結(jié)束，說(shuō)明要么分詞沒(méi)有歧義了，要么"貪吃蛇"從兩頭吃到中間交匯了
    // 如果是在中間交匯，交匯時(shí)的分詞結(jié)果，還要進(jìn)行以下判斷：
    // 如果中間交匯有重疊了：
    // 正向第一個(gè)分詞的長(zhǎng)度 + 反向最后一個(gè)分詞的長(zhǎng)度 > 輸入字符串總長(zhǎng)度，就直接取正向的
    if (left.get(0).length() + right.get(right.size() - 1).length() > inputStr
        .length())
      resultMiddle = left;
    // 如果中間交匯，剛好吃完，沒(méi)有重疊：
    // 正向第一個(gè)分詞 + 反向最后一個(gè)分詞的長(zhǎng)度 = 輸入字符串總長(zhǎng)度，那么正反向一拼即可
    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));
    }
    // 將沒(méi)有歧義的分詞結(jié)果添加到最終結(jié)果result中
    for (String string : resultLeft) {
      result.add(string);
    }
    for (String string : resultMiddle) {
      result.add(string);
    }
    // “右貪吃蛇”存儲(chǔ)的分詞要調(diào)整為正向
    for (int i = resultRight.size() - 1; i >= 0; i--) {
      result.add(resultRight.get(i));
    }
    return result;
  }
  /**
   * 將一段話分割成若干句話，分別進(jìn)行分詞
   *
   * @param inputStr
   *      待分割的一段話
   * @return 這段話的分詞結(jié)果
   */
  public List<String> resultSpilt(String inputStr) {
    // 用于存儲(chǔ)最終分詞結(jié)果
    List<String> result = new ArrayList<String>();
    // 如果遇到標(biāo)點(diǎn)就分割成若干句話
    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:過(guò)來(lái)看房?jī)r(jià)貴不貴？乒乓球拍賣完了
    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 + "/");
    }
  }
}

上述內(nèi)容就是怎么在Java中實(shí)現(xiàn)一個(gè)雙向匹配分詞算法，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。