您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

中文分詞核心算法：逆向最大匹配（RMM）原理與 IK Analyzer 源碼深度解析

編輯：Java 綜合教學

中文分詞核心算法：逆向最大匹配（RMM）原理與 IK Analyzer 實現解析

中文分詞是自然語言處理的基石。本文深入剖析逆向最大匹配（Reverse Maximum Matching, RMM）算法原理，並結合開源項目 IK Analyzer 核心源碼（AnalyzeContext、CJKSegmenter）進行逐行解讀。

一、逆向最大匹配算法原理

加載詞典：將詞典構建為 Trie 樹或 Hash 表，支持 O(1) 前綴查找。
從文本末尾向前掃描：每次取最大長度（如 7 個字符）作為候選詞。
詞典查找：若命中，輸出該詞，指針前移詞長；未命中，長度 -1 重試，直到長度為 1（單字成詞）。
重複直至文本開頭。

特點：適合中文「後綴豐富」特性（如「的、了、著」），切分精度通常優於正向最大匹配（MM）。

二、IK Analyzer 核心類結構

1. AnalyzeContext：分詞上下文環境

封裝分詞過程所需的所有狀態：

segmentBuff：字符緩衝區（4096 char）
charTypes：字符類型數組（數字、字母、中文、分隔符等）
cursor：當前掃描指針（從末尾向前）
buffOffset：緩衝區在原文中的偏移量
orgLexemes：原始詞元集合（QuickSortSet，按起始位置/長度排序）
pathMap：詞元路徑映射（位置 → LexemePath，用於最優路徑選擇）
results：最終輸出詞元鏈表
buffLocker：緩衝區鎖（多分詞器協同時防止緩衝區被覆蓋）

關鍵方法

fillBuffer(Reader)：分塊讀取，支持大文本流式分詞，處理緩衝區滑動與字符規范化。
initCursor()：初始化指針到緩衝區末尾，完成字符規范化與類型識別。
moveCursor()：指針前移 moveIndex+1 位，配合 RMM 回退邏輯。
outputToResult()：根據 pathMap 輸出最優路徑詞元，單字符兜底輸出。
getNextLexeme()：輸出迭代器，攔截停用詞，賦值詞元文本。

2. CJKSegmenter：中日韓字符逆向最大匹配分詞器

實現 ISegmenter 接口，核心邏輯在 analyze(AnalyzeContext)：


public void analyze(AnalyzeContext context) {
    // 動態調整最大匹配長度（邊界處理）
    if (context.getCursor() < moveIndex) {
        moveIndex = context.getCursor();
        MATCH_LEN = context.getCursor() + 1;
    }
    // 詞典查找：從 cursor-moveIndex 開始，長度 MATCH_LEN
    Hit hit = Dictionary.getSingleton().matchInMainDict(
        context.getSegmentBuff(), context.getCursor() - moveIndex, MATCH_LEN
    );
    if (hit.isMatch() || MATCH_LEN == 1) {
        // 命中或已退避到單字：產出詞元
        Lexeme lexeme = new Lexeme(context.getBufferOffset(),
            context.getCursor() - moveIndex, MATCH_LEN, Lexeme.TYPE_CJK);
        context.addLexeme(lexeme);
        context.setMoveIndex(moveIndex);
        init(); // 重置移動索引
    } else {
        // 未命中：回退一位繼續嘗試（遞歸）
        if (!hit.isUnmatch() || hit.isUnmatch()) { // 邏輯簡化：未完全不匹配則繼續
            --moveIndex;
            --MATCH_LEN;
            analyze(context); // 遞歸回退
        }
    }
}
private void init() { moveIndex = 6; MATCH_LEN = 7; } // 默認最大詞長 7

三、關鍵設計細節解讀

設計點	實現細節	作用
緩衝區滑動	`fillBuffer` 中 `System.arraycopy` 移動未處理數據到頭部	支持任意大文本流式處理，內存恆定
字符規范化	`CharacterUtil.regularize()`	全半角轉換、大小寫統一、特殊字符處理
字符類型識別	`CharacterUtil.identifyCharType()`	區分中文、英文、數字、分隔符，支持子分詞器分工
緩衝區鎖	`buffLocker` Set	多分詞器（如 CJK、英文、數字）串行處理同一緩衝區時防衝突
最優路徑選擇	`pathMap` + `QuickSortSet`	詞元按起始位置排序，動態規劃選擇詞數最少/詞長最大路徑
數量詞合併	`compound()` 中 TYPE_NUM + TYPE_QUANTIFIER → TYPE_NUM_QUAN	「三個」合併為一詞，提升語義完整性
停用詞過濾	`Dictionary.isStopWord()` 在 `getNextLexeme` 中攔截	輸出階段過濾「的、是、在」等無語義詞

四、算法複雜度與優化方向

時間複雜度：O(N × L) ，N 為文本長度，L 為最大詞長（常數 7），實際接近 O(N)。
空間複雜度：O(BufferSize + DictSize) ，緩衝區固定 4K，詞典常駐內存。
優化點：
- 詞典用 DoubleArrayTrie（DAT）替代 HashMap，極大降低內存並提升查找速度。
- 引入 HMM/CRF 統計模型解決歧義（如「結婚的和尚未結婚的」）。
- 並行分詞：文本按句子切分後多線程處理，合併結果。