根據 LogParser-LLM 的架構設計，前綴樹（Prefix Tree / Prefix Parse Tree）的核心目標是作為高速緩存，攔截 99% 的重複日誌模式，僅在無法“嚴格匹配”時才調用 LLM。以下是基於論文描述的 Java 實現方案。該實現涵蓋了核心數據結構設計、日誌匹配邏輯（Strict Match）以及模版更新機制。

核心設計思路

1. 節點設計 (TreeNode)：

    ◦ 每個節點代表日誌中的一個 Token（單詞）。

    ◦ 節點分為兩種路徑：靜態路徑（精確匹配單詞）和通配符路徑（匹配動態參數，論文中用 <*> 表示）。

    ◦ 非根節點（不僅是葉子節點）都可以指向一個或多個 LogCluster（日誌簇），因為不同長度的日誌可能共享前綴。

2. 工作流程：

    ◦ 插入 (Update)：當 LLM 提取出新模板（例如 User <*> login）後，將模板分詞並插入樹中。

    ◦ 查詢 (Search)：新日誌進來後，逐詞遍歷樹。如果能完全走通某條路徑（靜態詞匹配或對應位置有 <*> 節點），則判定為 Strict Match（嚴格匹配）。

--------------------------------------------------------------------------------

Java 代碼實現

1. 定義基礎類：LogCluster 和 TreeNode

import java.util.*;

// [6] Log Cluster: 存儲日誌模板信息的容器
class LogCluster {
    String template; // LLM 提取出的模板，例如 "Connection from <*>"
    String clusterId;

    public LogCluster(String template, String clusterId) {
        this.template = template;
        this.clusterId = clusterId;
    }

    @Override
    public String toString() {
        return "Cluster[" + clusterId + ": " + template + "]";
    }
}

// [4] Prefix Parse Tree Node
class TreeNode {
    // 靜態Token的子節點映射 (例如 "Connection" -> nextNode)
    Map<String, TreeNode> children = new HashMap<>();
    
    // [4] 通配符節點：用於處理模板中的 <*>，匹配任意動態參數
    TreeNode wildcardChild = null;
    
    // [4] 該節點可能關聯的日誌簇（非葉子節點也可能有簇）
    List<LogCluster> clusters = new ArrayList<>();

    // 獲取或創建普通子節點
    public TreeNode getOrCreateChild(String token) {
        return children.computeIfAbsent(token, k -> new TreeNode());
    }

    // 獲取或創建通配符子節點
    public TreeNode getOrCreateWildcardChild() {
        if (wildcardChild == null) {
            wildcardChild = new TreeNode();
        }
        return wildcardChild;
    }
}

2. 實現前綴樹邏輯：LogPrefixTree

public class LogPrefixTree {
    private final TreeNode root;
    private static final String WILDCARD = "<*>"; // [4] 論文定義的通配符

    public LogPrefixTree() {
        this.root = new TreeNode();
    }

    /**
     * [7] 更新樹 (Update Tree)
     * 當 LLM 返回一個新的模板時，將其解析並存入樹中
     * @param template 例如 "User <*> logged in"
     * @param cluster 對應的日誌簇對象
     */
    public void insertTemplate(String template, LogCluster cluster) {
        // [8] 簡單的分詞，論文中使用空格分割
        String[] tokens = template.trim().split("\\s+");
        TreeNode current = root;

        for (String token : tokens) {
            if (token.equals(WILDCARD)) {
                // 如果模板當前位置是 <*>, 走通配符路徑
                current = current.getOrCreateWildcardChild();
            } else {
                // 否則走精確匹配路徑
                current = current.getOrCreateChild(token);
            }
        }
        // 在路徑末尾綁定簇信息
        current.clusters.add(cluster);
    }

    /**
     * [5, 9] 匹配搜索 (Cluster Matching)
     * 嘗試為新日誌尋找 "Strict Match" (嚴格匹配)
     * @param logMsg 原始日誌消息
     * @return 匹配到的 LogCluster，如果沒有嚴格匹配則返回 null
     */
    public LogCluster search(String logMsg) {
        String[] tokens = logMsg.trim().split("\\s+");
        return searchRecursive(root, tokens, 0);
    }

    // 遞歸搜索以處理可能的路徑分支
    private LogCluster searchRecursive(TreeNode node, String[] tokens, int index) {
        // 1. 終止條件：日誌所有 Token 處理完畢
        if (index == tokens.length) {
            // 檢查當前節點是否有關聯的簇
            if (!node.clusters.isEmpty()) {
                // [5] 嚴格匹配要求 Token 數量一致。
                // 簡單實現中，如果路徑走完且節點有簇，通常即為匹配。
                // 實際可能需要校驗 Cluster 裏的模板長度。
                return node.clusters.get(0); 
            }
            return null;
        }

        String currentLogToken = tokens[index];
        LogCluster result = null;

        // 2. 優先嚐試：精確匹配 (Static Match)
        // [5] 檢查是否存在與當前日誌 Token 完全一致的路徑
        if (node.children.containsKey(currentLogToken)) {
            result = searchRecursive(node.children.get(currentLogToken), tokens, index + 1);
            if (result != null) return result;
        }

        // 3. 備選嘗試：通配符匹配 (Wildcard Match)
        // [5] 如果精確匹配失敗，檢查當前是否有 <*> 路徑
        // 邏輯：模板裏的 <*> 可以匹配日誌裏的任何 Token (如 IP, ID 等)
        if (node.wildcardChild != null) {
            result = searchRecursive(node.wildcardChild, tokens, index + 1);
            if (result != null) return result;
        }

        // 4. 無法匹配 (No Match)
        return null;
    }
}

3. 模擬運行流程

以下代碼展示了系統如何利用前綴樹處理日誌，並在匹配失敗時模擬調用 LLM 的過程。

public class LogParserLLMDemo {
    public static void main(String[] args) {
        LogPrefixTree parser = new LogPrefixTree();

        // 模擬場景：
        // 1. 系統剛啓動，樹是空的
        String log1 = "User 1001 logged in";
        System.out.println("Processing: " + log1);
        
        LogCluster match1 = parser.search(log1);
        if (match1 == null) {
            System.out.println("-> No Match. Calling LLM...");
            // [10] 模擬 LLM 提取模板
            String llmGeneratedTemplate = "User <*> logged in"; 
            LogCluster newCluster = new LogCluster(llmGeneratedTemplate, "C1");
            
            // [7] 更新樹
            parser.insertTemplate(llmGeneratedTemplate, newCluster);
            System.out.println("-> Tree Updated with: " + llmGeneratedTemplate);
        }

        // 2. 相同的模式，但參數不同 (Strict Match)
        String log2 = "User 9999 logged in";
        System.out.println("\nProcessing: " + log2);
        
        LogCluster match2 = parser.search(log2);
        if (match2 != null) {
            // [5] 嚴格匹配成功，無需調用 LLM
            System.out.println("-> Strict Match Found! " + match2); 
        } else {
            System.out.println("-> No Match.");
        }
        
        // 3. 全新的日誌模式
        String log3 = "Connection failed at 10.0.0.1";
        System.out.println("\nProcessing: " + log3);
        LogCluster match3 = parser.search(log3); // 應該返回 null
        if (match3 == null) {
            System.out.println("-> No Match. Calling LLM...");
            // 模擬流程繼續...
        }
    }
}

關鍵實現細節解析

1. Strict Match (嚴格匹配) 的判定：

    ◦ 在 searchRecursive 方法中，代碼邏輯優先尋找 children (精確匹配)。

    ◦ 如果找不到精確匹配，但存在 wildcardChild (即模板中該位置是 <*>)，則代碼會進入通配符分支。

    ◦ 只有當日志的 Token 序列能夠完美對應樹上的一條路徑（靜態詞對應靜態節點，動態參數對應通配符節點），且長度一致（走完路徑到達存有 Cluster 的節點）時，才返回結果。這對應了論文中無需調用 LLM 的場景。

2. Loose Match (寬鬆匹配) 的處理：

    ◦ 上述代碼實現了最核心的樹結構。論文提到的“寬鬆匹配”（Loose Match）是指當嚴格匹配失敗時，系統會嘗試尋找“部分匹配”的簇（例如長度相同但某些靜態詞不匹配）。

    ◦ 在實際工程中，如果 search 返回 null，你可以遍歷所有 Cluster 或基於 Token 長度進行二次篩選（Candidate Selection），如果發現相似度夠高，再交給 LLM 決定是否 Merge（合併）。

3. 分詞策略：

    ◦ LogParser-LLM 明確指出使用簡單的空格分詞（split("\\s+")），不進行復雜的正則預處理（如把 IP 替換成 *），保留原始信息給 LLM 理解。前綴樹也遵循這一原則。

高併發的日誌解析場景

線程安全和迭代搜索，這裏提供一個針對 search 方法的優化思路

// 使用 ConcurrentHashMap 保證併發讀寫的安全性 (基礎保障)
import java.util.concurrent.ConcurrentHashMap;

class TreeNode {
     // 替換為線程安全的 Map
     Map<String, TreeNode> children = new ConcurrentHashMap<>();
     volatile TreeNode wildcardChild = null; // 保證可見性
     // ...
}

// 迭代式搜索 (防止棧溢出，稍微複雜但更健壯)
public LogCluster searchIterative(String logMsg) {
     String[] tokens = logMsg.trim().split("\\s+");
     // 使用棧來保存回溯點：存儲 (當前節點, 當前Token索引)
     Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
    
     stack.push(new Pair<>(root, 0));
    
     while (!stack.isEmpty()) {
         Pair<TreeNode, Integer> current = stack.pop();
         TreeNode node = current.getKey();
         int index = current.getValue();
        
         // 1. 匹配完成
         if (index == tokens.length) {
             if (!node.clusters.isEmpty()) return node.clusters.get(0);
             continue; // 路徑走通但沒有簇（可能是中間節點），回溯
         }
        
         String token = tokens[index];
        
         // 2. 壓入通配符路徑 (作為後備選項，先入棧後出)
         // 注意：棧是後進先出，所以如果我們希望“靜態優先”，應該先壓入通配符，再壓入靜態
         if (node.wildcardChild != null) {
             stack.push(new Pair<>(node.wildcardChild, index + 1));
         }
        
         // 3. 壓入靜態路徑 (優先處理)
         if (node.children.containsKey(token)) {
             stack.push(new Pair<>(node.children.get(token), index + 1));
         }
     }
     return null;
}

如有想了解更多軟件設計與架構, 系統IT,企業信息化, 團隊管理 資訊，請關注我的微信訂閲號：

作者：Petter Liu
出處：http://www.cnblogs.com/wintersun/
本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。 該文章也同時發佈在我的獨立博客中-Petter Liu Blog。