何种数据结构可助力JSON patches压缩？含Trie与基数排序探讨

压缩核心逻辑 #

JSON补丁压缩的核心是移除冗余补丁——这类补丁会被后续同路径或更短前缀的补丁完全覆盖，遵循「最后写入者获胜且优先最高祖先」规则：

• 后执行的补丁优先级高于先执行的
• 路径前缀更短的祖先补丁，优先级高于其后代路径的补丁

压缩示例 #

• 示例一：如果补丁列表里有多次replace操作，最后跟着一个remove操作，且remove的路径是前面所有补丁路径的前缀，那么前面的所有replace都可以删掉，只保留最终的remove操作。
• 示例二：如果补丁列表先有add操作，之后是多次针对同路径的replace，那么所有replace都可以去掉，只保留带最终值的add操作。

可行的数据结构方案 #

1. Trie（前缀树）

把JSON补丁的路径拆分为独立的路径段（比如/user/profile/name拆成user、profile、name），将这些路径段作为Trie的节点构建树结构。遍历补丁列表时，按顺序把每个路径插入Trie，同时记录每个节点对应的补丁操作和执行顺序索引：

• 当插入一个新路径时，如果Trie中已经存在该路径的祖先节点（且对应补丁的执行顺序更晚），则当前补丁属于冗余项，直接丢弃
• 如果当前路径的后代节点已经存在于Trie中，说明后代路径的补丁被当前祖先补丁覆盖，需要把这些后代节点对应的补丁全部标记为冗余并移除

这种结构能高效追踪路径的层级依赖，快速判断补丁是否被覆盖，适合处理路径结构复杂的补丁集合。

2. 基于路径段+补丁索引的基数排序

这种方案的核心是通过排序过滤冗余补丁，步骤如下：

1. 两次排序：
   • 第一优先级：按补丁的执行索引降序排列，保证后执行的补丁先被处理
   • 第二优先级：按路径的段数升序排列，让祖先路径的补丁优先于后代路径
2. 遍历去重：维护一个已保留的路径前缀集合，遍历排序后的补丁：
   • 如果当前路径的任意前缀已经在集合中，说明该补丁被优先级更高的祖先补丁覆盖，直接跳过
   • 否则，保留该补丁，并将当前路径加入集合

这种方式逻辑简单直观，排序后遍历的时间复杂度低，适合处理大规模的补丁列表。

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