24小时热门版块排行榜

返回列表

rachel429429

新虫 (初入文坛)

应助: 0 (幼儿园)
帖子: 1
在线: 52分钟
虫号: 3640843
注册: 2015-01-12

[交流] 排序问题求有效算法已有1人参与

问题：一个布尔矩阵，把矩阵行进行排序，之后基于列进行RLE压缩，也就是连续的0或者1可以用（0，重复次数），（1，重复次数）来表示，每个重复的0或者1字段定义为一个run。

下表是一个排序前和排序后的对比，
 排序前：行顺序为t1 t2 t3 t4 t5，第一列为5个run，第二列为4个run因为有两个连续的1排列在一起，第三列为5个run，第四列是4个run，总run数=18；
 排序后：行顺序为 t2 t4 t1 t3 t5，总run数变为6个。

问题是：怎样进行排序使得压缩性能最好，性能度量可以是run数，也可以是用压缩率（压缩之后的数据大小/未压缩的数据大小），求算法的启发？

排序前          排序后
t1 1001       t2 0110
t2 0110       t4 0110
t3 1001       t1 1001
t4 0110       t3 1001
t5 1100       t5 1100
runs 5454    runs 2223

total runs=18 total runs=6

回复此楼