版块导航: 正在加载中...

登录注册

应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

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

回复此楼

» 猜你喜欢

1楼 2016-09-12 15:38:41

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

feixiaolin

荣誉版主 (文坛精英)

专家经验: +518
信息EPI: 3
应助: 942 (博后)
贵宾: 1.275
金币: 3430
散金: 58785
红花: 532
沙发: 11
帖子: 24215
在线: 2601.8小时
虫号: 2139575
注册: 2012-11-21
专业: 光学信息获取与处理
管辖: 数学

★
小木虫: 金币+0.5, 给个红包，谢谢回帖

看看线性代数，也许有启发。

赞一下(1人)