每日算法 — 使用java实现基数树：Patricia Trie的压缩路径与最长前缀匹配

引言

基数树（Radix Tree），又称压缩前缀树（Compressed Prefix Tree）或Patricia Trie（Practical Algorithm To Retrieve Information Coded In Alphanumeric），是一种对标准字典树（Trie）的空间优化结构。它通过将只有单个子节点的链压缩为一条边，显著减少了树的深度和节点数量。

在路由表查找、IP地址最长前缀匹配、自动补全系统、DNA序列分析等领域，基数树因其 O(m) 的查找效率（m为键长）和出色的空间利用率而被广泛采用。Linux内核的路由表、Nginx的location匹配等底层实现都使用了基数树的变种。

核心思想

标准Trie的问题

标准Trie中，每个节点存储一个字符，从根到叶子的路径构成一个完整的字符串。当键之间没有公共前缀时，这种结构没有问题。但当存储 "smart"、"smash"、"smile" 等具有长公共前缀的字符串时，会产生大量只有单个子节点的中间节点，造成严重的空间浪费。

基数树的压缩策略

基数树的核心优化是路径压缩：

1. 合并单边链：如果一个节点只有一个子节点，将两者合并，边上存储合并后的字符串片段
2. 边标签存储子串：每条边不再只存一个字符，而是存一个字符串片段
3. 分叉时分裂：当插入的新字符串与某条边的标签有公共前缀但不完全匹配时，在该位置分裂边

例如存储 "romane"、"romulus"、"rubens"、"ruber"、"rubicon"、"rubicundus"：
– 标准Trie需要约 30+ 个节点
– 基数树仅需约 10 个节点

算法实现

import java.util.ArrayList;
import java.util.List;

/**
 * 基数树（Patricia Trie / Radix Tree）实现
 * 核心思想：压缩单分支路径，边存储字符串片段而非单个字符
 */
public class RadixTree {

    /**
     * 基数树节点
     */
    private static class Node {
        // 子节点列表，每条边隐含在子节点中
        List<Node> children;
        // 从父节点到当前节点的边标签（字符串片段）
        String edgeLabel;
        // 是否为完整键的结束节点
        boolean isEnd;
        // 存储与该键关联的值（可选）
        Object value;

        Node(String edgeLabel) {
            this.edgeLabel = edgeLabel;
            this.children = new ArrayList<>();
            this.isEnd = false;
        }
    }

    private final Node root;
    private int size;

    public RadixTree() {
        this.root = new Node("");
        this.size = 0;
    }

    /**
     * 查找最长公共前缀长度
     */
    private int longestCommonPrefix(String s1, String s2) {
        int len = Math.min(s1.length(), s2.length());
        int i = 0;
        while (i < len && s1.charAt(i) == s2.charAt(i)) {
            i++;
        }
        return i;
    }

    /**
     * 插入键值对
     * @param key 键字符串
     * @param value 关联值
     */
    public void insert(String key, Object value) {
        if (key == null || key.isEmpty()) return;

        Node current = root;
        int index = 0;

        while (index < key.length()) {
            String remaining = key.substring(index);
            Node matchedChild = null;
            int matchLen = 0;

            // 在当前节点的子节点中寻找匹配边
            for (Node child : current.children) {
                int lcp = longestCommonPrefix(child.edgeLabel, remaining);
                if (lcp > 0) {
                    matchedChild = child;
                    matchLen = lcp;
                    break;
                }
            }

            if (matchedChild == null) {
                // 无匹配子节点，直接添加新子节点
                Node newNode = new Node(remaining);
                newNode.isEnd = true;
                newNode.value = value;
                current.children.add(newNode);
                size++;
                return;
            }

            if (matchLen == matchedChild.edgeLabel.length()) {
                // 边标签完全匹配，继续向下
                if (matchLen == remaining.length()) {
                    // 键已存在，更新值
                    matchedChild.isEnd = true;
                    matchedChild.value = value;
                    return;
                }
                current = matchedChild;
                index += matchLen;
            } else {
                // 部分匹配，需要分裂边
                String commonPrefix = matchedChild.edgeLabel.substring(0, matchLen);
                String childSuffix = matchedChild.edgeLabel.substring(matchLen);
                String newSuffix = remaining.substring(matchLen);

                // 创建中间节点，承载公共前缀
                Node intermediate = new Node(commonPrefix);
                current.children.remove(matchedChild);
                current.children.add(intermediate);

                // 原子节点作为中间节点的子节点
                matchedChild.edgeLabel = childSuffix;
                intermediate.children.add(matchedChild);

                // 新插入的键作为中间节点的另一个子节点
                Node newNode = new Node(newSuffix);
                newNode.isEnd = true;
                newNode.value = value;
                intermediate.children.add(newNode);
                size++;
                return;
            }
        }
    }

    /**
     * 查找键是否存在
     * @param key 键字符串
     * @return 是否存在
     */
    public boolean search(String key) {
        Node node = findNode(key);
        return node != null && node.isEnd;
    }

    /**
     * 查找键对应的值
     * @param key 键字符串
     * @return 值，不存在返回null
     */
    public Object get(String key) {
        Node node = findNode(key);
        return (node != null && node.isEnd) ? node.value : null;
    }

    /**
     * 找到对应键的节点（内部辅助方法）
     */
    private Node findNode(String key) {
        if (key == null || key.isEmpty()) return null;

        Node current = root;
        int index = 0;

        while (index < key.length()) {
            String remaining = key.substring(index);
            Node matchedChild = null;
            int matchLen = 0;

            for (Node child : current.children) {
                int lcp = longestCommonPrefix(child.edgeLabel, remaining);
                if (lcp > 0) {
                    matchedChild = child;
                    matchLen = lcp;
                    break;
                }
            }

            if (matchedChild == null || matchLen != matchedChild.edgeLabel.length()) {
                return null; // 无匹配或部分匹配
            }

            current = matchedChild;
            index += matchLen;
        }

        return current;
    }

    /**
     * 最长前缀匹配：找到与给定字符串具有最长公共前缀的键
     * @param prefix 前缀字符串
     * @return 最长匹配的键
     */
    public String longestPrefixMatch(String prefix) {
        if (prefix == null || prefix.isEmpty()) return "";

        Node current = root;
        int index = 0;
        StringBuilder matchedKey = new StringBuilder();
        String lastEndKey = "";

        while (index < prefix.length()) {
            String remaining = prefix.substring(index);
            Node matchedChild = null;
            int matchLen = 0;

            for (Node child : current.children) {
                int lcp = longestCommonPrefix(child.edgeLabel, remaining);
                if (lcp > 0) {
                    matchedChild = child;
                    matchLen = lcp;
                    break;
                }
            }

            if (matchedChild == null) break;

            matchedKey.append(matchedChild.edgeLabel.substring(0, matchLen));

            if (matchedChild.isEnd && matchLen == matchedChild.edgeLabel.length()) {
                lastEndKey = matchedKey.toString();
            }

            if (matchLen < matchedChild.edgeLabel.length()) {
                break; // 部分匹配
            }

            current = matchedChild;
            index += matchLen;
        }

        return lastEndKey;
    }

    /**
     * 查找所有以给定前缀开头的键
     * @param prefix 前缀
     * @return 匹配的键列表
     */
    public List<String> keysWithPrefix(String prefix) {
        List<String> result = new ArrayList<>();
        if (prefix == null) return result;

        Node prefixNode;
        String prefixPath;

        if (prefix.isEmpty()) {
            prefixNode = root;
            prefixPath = "";
        } else {
            prefixNode = findNode(prefix);
            if (prefixNode == null) return result;
            prefixPath = prefix;
            if (!prefixNode.isEnd) {
                // 继续收集子树中的键
            } else {
                result.add(prefix);
            }
        }

        collectKeys(prefixNode, prefixPath, result);
        return result;
    }

    /**
     * 递归收集子树中的所有键
     */
    private void collectKeys(Node node, String prefix, List<String> result) {
        for (Node child : node.children) {
            String newPrefix = prefix + child.edgeLabel;
            if (child.isEnd) {
                result.add(newPrefix);
            }
            collectKeys(child, newPrefix, result);
        }
    }

    /**
     * 打印树的结构，用于调试
     */
    public void printTree() {
        System.out.println("=== Radix Tree Structure ===");
        printNode(root, 0, "");
    }

    private void printNode(Node node, int depth, String prefix) {
        String indent = "  ".repeat(depth);
        if (depth > 0) {
            System.out.println(indent + "Edge: '" + node.edgeLabel + "' " + 
                (node.isEnd ? "[END value=" + node.value + "]" : ""));
        }
        for (Node child : node.children) {
            printNode(child, depth + 1, prefix + child.edgeLabel);
        }
    }

    /**
     * 主程序：演示基数树的核心操作
     */
    public static void main(String[] args) {
        RadixTree tree = new RadixTree();

        // 插入示例数据（模拟路由表场景）
        System.out.println("=== 插入键值对 ===");
        String[][] entries = {
            {"romane", "1"},
            {"romanus", "2"},
            {"romulus", "3"},
            {"rubens", "4"},
            {"ruber", "5"},
            {"rubicon", "6"},
            {"rubicundus", "7"},
        };

        for (String[] entry : entries) {
            tree.insert(entry[0], entry[1]);
            System.out.println("插入: " + entry[0] + " -> " + entry[1]);
        }

        tree.printTree();

        // 查找测试
        System.out.println("\n=== 查找测试 ===");
        for (String key : new String[]{"romane", "roman", "rubicon", "rubic", "xyz"}) {
            System.out.println("search(\"" + key + "\") = " + tree.search(key));
        }

        // 最长前缀匹配测试
        System.out.println("\n=== 最长前缀匹配测试 ===");
        for (String query : new String[]{"romanesque", "ruberize", "rubiconquest", "romx"}) {
            System.out.println("longestPrefixMatch(\"" + query + "\") = \"" + tree.longestPrefixMatch(query) + "\"");
        }

        // 前缀搜索测试
        System.out.println("\n=== 前缀搜索测试 ===");
        for (String prefix : new String[]{"rom", "rub", "r"}) {
            System.out.println("keysWithPrefix(\"" + prefix + "\") = " + tree.keysWithPrefix(prefix));
        }

        // IP路由场景模拟
        System.out.println("\n=== IP路由最长前缀匹配模拟 ===");
        RadixTree ipTree = new RadixTree();
        ipTree.insert("192.168.1", "LAN-1");
        ipTree.insert("192.168", "LAN");
        ipTree.insert("192.168.1.100", "Server-A");
        ipTree.insert("10.0.0", "VPN");
        ipTree.insert("10.0", "Internal");

        for (String ip : new String[]{"192.168.1.50", "192.168.2.1", "192.168.1.100", "10.0.0.5", "8.8.8.8"}) {
            System.out.println("IP " + ip + " -> 最长前缀匹配: \"" + ipTree.longestPrefixMatch(ip) + "\"");
        }
    }
}

算法详解

插入操作的三种情况

基数树的插入需要根据新键与现有边的匹配程度分三种情况处理：

情况1：无匹配子节点
直接在当前节点下添加新子节点，边上标记完整的新键后缀。

情况2：完全匹配
边的标签与新键的剩余部分完全一致。如果已到达键的末尾，标记该节点为结束节点；否则继续向下遍历。

情况3：部分匹配（分裂）
这是最关键的情况。例如已有边 "romane"，要插入 "roman"：
1. 公共前缀为 "roman"（5个字符）
2. 原边分裂为公共前缀 "roman" 和剩余后缀 "e"
3. 新键 "roman" 作为另一个子节点（或标记中间节点为结束）

最长前缀匹配

最长前缀匹配是基数树在路由查找中的核心应用。算法逻辑为：
1. 沿着树向下遍历，尽可能匹配输入字符串
2. 记录遍历过程中遇到的最后一个结束节点
3. 当无法继续匹配时，返回记录的结束节点对应的键

这使得基数树可以在 O(m) 时间内找到与目标字符串最长匹配的已知前缀，远优于线性扫描。

复杂度分析

与标准Trie的对比

实际应用场景

基数树在以下领域有广泛应用：

1. IP路由表查找：Linux内核的 fib_trie 使用基数树实现最长前缀匹配
2. Nginx location匹配：高效匹配URL前缀
3. 自动补全系统：基于前缀快速检索候选词
4. DNA序列分析：处理具有大量公共前缀的基因序列
5. 版本控制系统：Git的tree对象使用类似结构存储路径

总结

基数树通过对单分支路径的压缩，在保持Trie O(m) 查找效率的同时，大幅降低了空间开销。本文的Java实现展示了插入、查找、最长前缀匹配等核心操作，以及边分裂这一关键机制。

理解基数树的关键在于掌握路径压缩的思想：不要为了形式上的统一而浪费空间，当信息可以被合并时就应该合并。这一思想不仅适用于字符串检索，也能启发我们在其他数据结构设计中追求更紧凑的表示。