递归后缀链分解算法性能优化需求

def find_suffix_chain(word: str, start_pos: str, root: str,
                      current_chain: List = None, visited: Set = None,
                      shared_cache: dict = None) -> List:
    """
    带跨词根共享缓存的递归后缀链查找器。
    缓存键：(剩余文本, 起始词性, 最后一个后缀组)
    这么设计是安全的，因为is_valid_transition仅依赖最后一个后缀的组。
    """

    if current_chain is None: current_chain = []
    if visited is None: visited = set()
    if shared_cache is None: shared_cache = {}

    # --- 单次调用内的备忘（避免在同一调用树内重复访问）---
    chain_signature = tuple(s.name for s in current_chain)
    state_key = (len(root), start_pos, chain_signature)
    if state_key in visited: return []
    visited.add(state_key)

    root_len = len(root)
    rest = word[root_len:]

    # 基准情况
    if not rest:
        return [([], start_pos)]

    if start_pos not in SUFFIX_TRANSITIONS:
        return []

    # --- 跨词根共享缓存 ---
    # 键：剩余文本、当前词性、最后一个后缀组
    # （组为None表示处于词根阶段，暂无层级限制）
    last_group = current_chain[-1].group if current_chain else None
    cache_key = (rest, start_pos, last_group)

    if cache_key in shared_cache:
        return shared_cache[cache_key]

    results = []

    # --- 选择迭代策略：索引式或暴力式 ---
    if _SUFFIX_INDEX is not None:
        _iter = _indexed_suffix_iter(start_pos, rest, root)
    else:
        _iter = _bruteforce_suffix_iter(start_pos, root)

    for target_pos, suffix_obj, suffix_forms in _iter:

            # --- 层级验证 ---
            if current_chain:
                last_suffix = current_chain[-1]
                if not is_valid_transition(last_suffix, suffix_obj):
                    continue

            # --- 唯一性检查 ---
            if suffix_obj.is_unique:
                if any(s.name == suffix_obj.name for s in current_chain):
                    continue

            # --- 形式匹配 ---
            for suffix_form in suffix_forms:
                sf_len = len(suffix_form)
                if sf_len > len(rest):
                    continue

                # --- 匹配类型1：标准匹配 ---
                if rest.startswith(suffix_form):
                    subchains = find_suffix_chain(
                        word, target_pos,
                        word[:root_len + sf_len],
                        current_chain + [suffix_obj],
                        visited,
                        shared_cache
                    )
                    for chain, final_pos in subchains:
                        results.append(([suffix_obj] + chain, final_pos))

                # --- 匹配类型2：元音窄化 ---
                elif sf_len > 0 and suffix_form[-1] in ('a', 'e'):
                    narrowed_form = suffix_form[:-1]
                    if rest.startswith(narrowed_form):
                        rest_after = rest[len(narrowed_form):]
                        if any(rest_after.startswith(v) for v in IYOR_VARIATIONS):
                            subchains = find_suffix_chain(
                                root + suffix_form + rest_after,
                                target_pos,
                                root + suffix_form,
                                current_chain + [suffix_obj],
                                visited,
                                shared_cache
                            )
                            for chain, final_pos in subchains:
                                results.append(([suffix_obj] + chain, final_pos))

    # 返回前存入共享缓存
    # 注意：仅当当前链中无唯一后缀时才缓存，
    # 因为唯一性约束会导致结果依赖于链的历史。
    has_unique_in_chain = any(s.is_unique for s in current_chain)
    if not has_unique_in_chain:
        shared_cache[cache_key] = results

    return results

该递归函数find_suffix_chain用于根据给定后缀集合，找出单词的所有可能后缀链分解方式（需保留所有可能结果，部分后缀组合可能产生相同结果）。每个后缀具备返回其所有形式的方法，后缀仅可作用于名词或动词，并将其转换为对应词性（名词/动词二选一）。当前该函数性能开销极大，需全方位优化。

核心优化方向 #

• 缓存逻辑扩展：当前仅在无唯一后缀时缓存，可将已使用的唯一后缀名称加入缓存键，让含唯一后缀的状态也能被缓存；同时精简state_key，用rest替代len(root)，减少冗余计算。
• 递归转迭代：将递归实现改为深度优先/广度优先的迭代模式，用栈或队列存储状态（当前链、剩余文本、词性、已用唯一后缀等），消除递归栈的性能损耗。
• 匹配逻辑加速：提前将后缀按词性、长度降序预处理；用切片比较替代startswith提升匹配速度；将IYOR_VARIATIONS转为集合或构建前缀树，加速变体匹配。
• 循环分支优化：在迭代器中提前过滤不符合层级规则的后缀；将当前链中的唯一后缀存入集合，把唯一性检查的时间复杂度从O(n)降为O(1)。
• 减少状态复制：用临时添加+回溯移除的方式替代current_chain + [suffix_obj]的列表复制；优化visited集合的存储形式，降低内存占用和查找耗时。

内容的提问来源于stack exchange，提问作者LeBron James