我有一系列集合,想要放入一个trie中。
普通的trie由元素的字符串组成 - 也就是说,元素的顺序很重要。但是集合没有定义的顺序,因此可能会有更好的压缩效果。
例如,给定字符串
普通的trie由元素的字符串组成 - 也就是说,元素的顺序很重要。但是集合没有定义的顺序,因此可能会有更好的压缩效果。
例如,给定字符串
"abc"
,"bc"
和"c"
,我将创建trie:(*,3) -> ('a',1) -> ('b',1) -> ('c',1)
-> ('b',1) -> ('c',1)
-> ('c',1)
但是,考虑到集合 { 'a', 'b', 'c' }
,{ 'b', 'c' }
,{ 'c' }
,我可以创建上述字典树或其中的任何一个字典树中的十一个:
(*,3) -> ('a',1) -> ('b',1) -> ('c',1)
-> ('c',2) -> ('a',1)
(*,3) -> ('a',1) -> ('c',1) -> ('b',1)
-> ('b',1) -> ('c',1)
-> ('c',1)
(*,3) -> ('a',1) -> ('c',1) -> ('b',1)
-> ('c',2) -> ('a',1)
(*,3) -> ('b',2) -> ('a',1) -> ('c',1)
-> ('c',1)
-> ('c',1)
(*,3) -> ('b',1) -> ('a',1) -> ('c',1)
-> ('c',2) -> ('b',1)
(*,3) -> ('b',2) -> ('c',2) -> ('a',1)
-> ('c',1)
(*,3) -> ('b',1) -> ('c',1) -> ('a',1)
-> ('c',2) -> ('b',1)
(*,3) -> ('c',2) -> ('a',1) -> ('b',1)
-> ('b',1) -> ('c',1)
(*,3) -> ('c',2) -> ('a',1) -> ('b',1)
-> ('b',1)
(*,3) -> ('c',2) -> ('b',1) -> ('a',1)
-> ('b',1) -> ('c',1)
(*,3) -> ('c',3) -> ('b',2) -> ('a',1)
显然可以进行压缩(从7个节点到4个节点)。
我猜测,在每个节点上定义一个本地顺序,该顺序取决于其子节点的相对频率,但我不确定,而且可能过于昂贵。
因此,在我开始自己的压缩算法之前,是否存在现有的算法?它的开销有多大?它是批量处理还是可以针对每个插入/删除操作进行?