自适应令牌字典（Adaptive Token Dictionary）入门指南：从原理到实战

1次阅读

没有评论

共计 1595 个字符，预计需要花费 4 分钟才能阅读完成。

在文本处理任务中，字典是最基础的数据结构之一。传统的静态字典在构建时需要预先确定所有可能的词汇，这在处理动态变化的文本时会遇到诸多问题。

内存占用高 ：静态字典需要为所有可能的词汇分配空间，即使某些词汇从未被使用
查询效率低 ：随着字典规模增大，查询时间也会线性增长
灵活性差 ：无法动态添加新词汇，必须重新构建整个字典

这些问题在处理用户生成内容、实时日志等动态文本时尤为明显。

在处理动态文本时，我们通常有以下几种选择：

静态字典 ：预先定义所有词汇，简单但不够灵活
哈希表 ：支持动态插入，但无法保留词汇顺序信息
自适应令牌字典 ：结合了静态字典和哈希表的优点

自适应令牌字典的主要优势在于：

支持动态词汇添加
保持词汇的顺序性
查询效率接近 O(1)
内存使用更加高效

自适应令牌字典通常采用以下数据结构设计：

哈希映射 ：用于快速查询词汇是否存在
动态数组 ：按添加顺序存储词汇
位图索引 ：高效标记词汇状态

关键算法包括：

动态扩容机制 ：当容量不足时自动扩展存储空间
惰性删除 ：标记删除而非立即释放空间
压缩算法 ：定期整理碎片化空间

以下是 Python 实现的简化版本：

class AdaptiveTokenDictionary:
    def __init__(self):
        self.token_to_id = {}  # 哈希映射
        self.id_to_token = []  # 动态数组
        self.free_ids = set()  # 空闲 ID 集合

    def add_token(self, token):
        """添加新令牌"""
        if token not in self.token_to_id:
            if self.free_ids:
                # 重用空闲 ID
                new_id = self.free_ids.pop()
                self.id_to_token[new_id] = token
            else:
                # 分配新 ID
                new_id = len(self.id_to_token)
                self.id_to_token.append(token)
            self.token_to_id[token] = new_id
            return new_id
        return self.token_to_id[token]

    def remove_token(self, token):
        """移除令牌（惰性删除）"""
        if token in self.token_to_id:
            token_id = self.token_to_id[token]
            del self.token_to_id[token]
            self.free_ids.add(token_id)
            return True
        return False

    def get_id(self, token):
        """获取令牌 ID"""
        return self.token_to_id.get(token, -1)

    def get_token(self, token_id):
        """根据 ID 获取令牌"""
        if 0 <= token_id < len(self.id_to_token) and token_id not in self.free_ids:
            return self.id_to_token[token_id]
        return None

自适应令牌字典的性能特点如下：