支持翻译传递推导与O(1)查询的哈希表-图混合数据结构咨询

核心逻辑 #

不用每次查询都跑BFS/DFS做图遍历，用三层结构把传递关系的计算前置到录入环节，查询直接走哈希索引拿结果，做到O(1)时间复杂度，同时天然满足双向查询、传递推导的需求，扩展成本极低。 #

结构定义 #

一共三个核心哈希表，无复杂依赖：

• node_map：节点索引，键为(语言标识, 词汇文本)元组，值为词汇节点的全局唯一ID，解决不同语言下相同拼写词汇的冲突问题
• adj_list：无向邻接表，存储词汇节点之间的直接翻译边，录入的每一组映射对都会存双向边，是双向查询的基础
• component_cache：连通分量结果缓存，每个互相可达的词汇连通分量对应一个缓存项，存储分量内所有语言词汇的跨语言对应关系，是O(1)查询的核心
• 辅助索引node_to_component：记录每个节点属于哪个连通分量，用来快速定位缓存

操作流程 #

录入翻译映射 #

以录入(lang1, word1, lang2, word2)为例：

1. 先检查两个词汇是否在node_map中存在，不存在就创建新节点，给新节点初始化独立的连通分量缓存
2. 在adj_list中给两个节点加双向边
3. 检查两个节点所属连通分量：
   • 如果同属一个分量，直接在缓存里补双向映射即可，不需要其他操作
   • 如果分属两个不同分量，按「小分量合并进大分量」的原则合并两个连通分量的缓存：遍历小分量里的所有词汇，和大分量里的所有词汇双向补全跨语言映射，更新小分量所有节点的分量归属，删除冗余的小分量缓存

合并操作仅在两个原本不连通的翻译网络被新映射打通时触发，按大小合并的策略可以把均摊操作压到接近O(1)，不会因为数据量变大出现明显性能滑坡

查询翻译 #

接口签名：get_translation(word: str, source_lang: str, target_lang: str) -> str | None

1. 拼源词汇key (source_lang, word)，如果不在node_map里直接返回None
2. 通过node_to_component找到该词汇所属连通分量
3. 直接从component_cache里拿对应目标语言的翻译结果返回，全程无遍历，时间复杂度O(1)

需求匹配说明 #

• 双向查询：邻接表存无向边，缓存写入时自动补全双向映射，哪怕只录了English到German的映射，查German到English也直接命中缓存
• 传递推导：只要两个词汇在同一个连通分量里，不管中间隔了多少层映射关系，合并连通分量的时候就已经把跨语言的对应关系补全了，不需要查询时临时遍历找路径
• 可扩展性：后续如果要支持词性标注、歧义词汇分组、方言映射等能力，只需要调整node_map的键组成、修改连通分量合并时的匹配规则即可，整体框架不需要改动

最简参考实现（Python） #

class TranslationStore:
    def __init__(self):
        self.node_map = dict()
        self.node_to_component = dict()
        self.adj_list = dict()
        self.component_cache = dict()
        self._next_node_id = 0
        self._next_component_id = 0

    def add_translation_pair(self, lang_a: str, word_a: str, lang_b: str, word_b: str):
        # 初始化不存在的词汇节点
        def get_or_create(lang: str, word: str) -> int:
            node_key = (lang, word)
            if node_key not in self.node_map:
                nid = self._next_node_id
                self._next_node_id += 1
                self.node_map[node_key] = nid
                self.adj_list[nid] = []
                # 新节点初始化为独立连通分量
                cid = self._next_component_id
                self._next_component_id += 1
                self.node_to_component[nid] = cid
                self.component_cache[cid] = {lang: {word: {lang: word}}}
            return self.node_map[node_key]
        
        nid_a = get_or_create(lang_a, word_a)
        nid_b = get_or_create(lang_b, word_b)
        # 补双向邻接边
        self.adj_list[nid_a].append(nid_b)
        self.adj_list[nid_b].append(nid_a)

        cid_a = self.node_to_component[nid_a]
        cid_b = self.node_to_component[nid_b]
        # 同分量直接补缓存映射
        if cid_a == cid_b:
            self.component_cache[cid_a][lang_a][word_a][lang_b] = word_b
            self.component_cache[cid_a][lang_b][word_b][lang_a] = word_a
            return
        
        # 小分量合并进大分量，减少遍历开销
        if len(self.component_cache[cid_a]) < len(self.component_cache[cid_b]):
            cid_a, cid_b = cid_b, cid_a
        cache_large = self.component_cache[cid_a]
        cache_small = self.component_cache.pop(cid_b)

        # 合并缓存，补全跨分量的所有翻译映射
        for lang_s, word_map_s in cache_small.items():
            if lang_s not in cache_large:
                cache_large[lang_s] = dict()
            for word_s, trans_map_s in word_map_s.items():
                cache_large[lang_s][word_s] = trans_map_s
                for lang_l, word_map_l in cache_large.items():
                    if lang_l == lang_s:
                        continue
                    for word_l in word_map_l:
                        cache_large[lang_s][word_s][lang_l] = word_l
                        cache_large[lang_l][word_l][lang_s] = word_s
        
        # 更新小分量所有节点的归属
        for nid in self.adj_list:
            if self.node_to_component[nid] == cid_b:
                self.node_to_component[nid] = cid_a

    def get_translation(self, word: str, source_lang: str, target_lang: str) -> str | None:
        source_key = (source_lang, word)
        if source_key not in self.node_map:
            return None
        cid = self.node_to_component[self.node_map[source_key]]
        return self.component_cache[cid][source_lang][word].get(target_lang)

内容的提问来源于stack exchange，提问作者Juan Mendoza