java - 前缀最优匹配算法代码实现？？

Question

前缀最优匹配算法代码实现

1. 通过跟编码字符串进行匹配, 从一个已经建立好的编码对照表里面找出最优的编码ID
2. 编码对照表定义如下:
    1. 编码字符串(长度最大为6): 1~6位的小写字母字符串
    2. 编码ID: 整数
    3. 编码字符串和编码ID都是唯一值, 没有重复
    4. 编码对照表已经按<编码字符串>排好序(升序)
    5. 编码对照表记录数: 2万左右
    6. 编码表样例: (以JSON形式来描述)
        {"a":1, "aa":2, "aab":3, "aba":4, "b", ... , "xyzabc":19800, "zab":19801, "zz":19802}
3. 前缀最优匹配算法:
        1. 从字符串的第一位开始匹配, 匹配长度最长优先
        2. 待匹配字符串的长度最短为6位
        3. 以上面的编码表为例进行匹配:
            1. "aiabcdef" 匹配记录为"a":1
            2. "aabchjhk" 匹配记录为"aab":3
            3. "aacxylm"  匹配记录为"aa":2
            4. "abcdhkd" 匹配记录为"a":1
            5. "zaaihl" 没有匹配记录:-1
        3. 匹配算法函数定义: 
            function BestFind(2万条记录的编码对照表, 需要匹配的编码字符串)
            按上面的编码表样例, BestFind($CodeMap, "aabchgl") 应该返回 3
            
4. 题目本意是设计一个高效<查找算法>, 查找执行前的数据准备时间不归入算法开销里面
5. 在2万个充分随机产生的编码表里面进行查找, 效率应该在每秒10万次以上才算合格

Answer 1

可以试试一下字典树 (Trie)

Answer 2

以下是前缀最优匹配算法的高效实现，使用二分查找优化性能，满足每秒10万次查询的要求。算法基于已排序的编码表，从最长前缀（6位）开始尝试，逐步缩短长度，直到找到匹配或遍历完所有可能前缀。

import bisect

def best_find(keys, values, s):
    """
    前缀最优匹配算法实现
    :param keys: 已排序的编码字符串列表（升序）
    :param values: 对应的编码ID列表
    :param s: 待匹配的字符串（长度至少6位）
    :return: 匹配的编码ID（未找到返回-1）
    """
    n = len(keys)
    if n == 0 or len(s) < 1:
        return -1
    
    # 只检查前6个字符
    max_len = min(6, len(s))
    
    # 从最长前缀开始尝试（6 → 1）
    for L in range(max_len, 0, -1):
        prefix = s[:L]
        # 二分查找定位位置
        idx = bisect.bisect_left(keys, prefix)
        # 检查是否匹配
        if idx < n and keys[idx] == prefix:
            return values[idx]
    return -1

算法说明

1. 核心逻辑：

   • 从最长可能前缀（6位）向最短（1位）遍历。
   • 对每个前缀长度 L，用 bisect_left 在有序列表中二分查找。
   • 若找到完全匹配的编码字符串，立即返回对应编码ID。

2. 时间复杂度：

   • 最多尝试6次（前缀长度6→1）。
   • 每次二分查找复杂度为 $O(\log N)$，$N=20000$ 时约15次比较。
   • 总复杂度 $O(6 \times \log N) \approx O(90)$ 次操作/查询，满足每秒10万次性能要求。
3. 空间复杂度：$O(1)$，无额外空间占用。

测试用例验证

# 编码表（keys已排序）
keys = ['a', 'aa', 'aab', 'aba', 'b', 'xyzabc', 'zab', 'zz']
values = [1, 2, 3, 4, 5, 19800, 19801, 19802]

# 测试案例
print(best_find(keys, values, "aiabcdef"))   # 输出: 1（匹配"a"）
print(best_find(keys, values, "aabchjhk"))   # 输出: 3（匹配"aab"）
print(best_find(keys, values, "aacxylm"))    # 输出: 2（匹配"aa"）
print(best_find(keys, values, "abcdhkd"))    # 输出: 1（匹配"a"）
print(best_find(keys, values, "zaaihl"))     # 输出: -1（无匹配）

性能优化关键

1. 有序数组二分查找：利用 bisect_left 快速定位（比遍历快 $O(N/\log N)$ 倍）。
2. 从长前缀开始匹配：优先匹配最长前缀，找到后立即返回，避免冗余检查。
3. 最小化字符串操作：仅截取待匹配前缀，不处理超长字符串。

此实现严格满足题目要求，在2万条随机编码表下可轻松达到每秒10万次以上查询。