有关20个'0'至'9'的数字的压缩问题（编码类高手请进哦）(300分)

B

brokensun

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-29

• #1

请教最小的存储空间（字节单位）
10个字节的话就别来灌水了，谢谢

 

T

tulipfan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-29

• #2

找找RLE算法吧

 

P

Pearl.

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-29

• #3

最小？
最小当然是1字节啦, 嘻嘻。
针对20个'1'或20个'2'....或20个'9'等特例(可以预定义多达256种组合)

 

B

brokensun

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #4

to:tulipfan
是要定长的，用RLE，我还用得着到处发贴子
to: Pearl.
你丫的分是不是灌水灌出来的？无聊！

 

W

wql

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #5

直接存储位置:
var _sbufacked array [1..20] of char;
// 假设你已经输入
_dbufacked array [1..20*10] of char;
// 输出结果: (字符:下个索引,位置...位置)...(字符:下个索引,位置...位置)...
_dnum:integer;//压缩长度
{
例如:
Source: 0 1 0 5 9 1 5 5 6 6 7 1 0 5 7 8 1 0 1 8
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
结果:_DBuf中的结构
#7为下个索引的位置
'0': 偏移1到6: #48#7#1#3#13#18
#48为'0', #1,#3,#13,#18为位置
#15为下个索引的位置
'1': 偏移7到14: #49#15#2#6#12#17#19
#49为'1', #2,#6,#12,#17为位置
}
procedure Compress;
var
i,j,k:integer;
begin
_dnum:=1;//压缩长度计数
for i:=0 to 9do
// 仅仅"0".."9"
begin
_dbuf[_dnum]:=chr($30+i);
k:=0;//该数字的个数
for j:=1 to 20do
//仅仅20个数字
begin
if _sbuf[j]=chr($30+i) then
begin
inc(k);
_dbuf[_dnum+1+k]:=chr(j);//存储位置
end;
end;
if (k<>0) then
//该数值存在,写入个数,不存在的不压缩存储
begin
_dbuf[_dnum+1]:=chr(_dnum+1+k+1);//下个位置的索引
_dnum:=_dnum+1+k;//压缩长度
end;
end;
if (_dnum>20) then
begin
showmessage('编码压缩失败 !');
end;
end;

end;

 

I

iie

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #6

1)骂人不好
2)需要67位，字节也就是9个了

 

J

jsxjd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #7

同意9个字节：
9999999999的十六进制表示是 2540BE3FF ,每两位是一个字节。
2540BE3FF 的平方，应该需要 9 个字节。

 

B

brokensun

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #8

to:wql
谢谢您的源码，您这是压缩？惭愧，看了没理解您的意思，您仔细看了我的题么？
to:iie
呵呵，主要是现在坛上太不严肃，您这67位至90位，可是有13位的冗余
to:jsxjd
您看，10个“9”转，为什么不20个“9”一起转，这样就只有8位字节就够了
---- 不好意思，写上面这行时，其实是溢出了，我还美呢，自己也在奇怪，本来有15位的冗佘，
怎么能靠转换进制这简单就解决了呢，呵呵，sorry的很啊，留在这里以臭自己

 

B

brokensun

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #9

大家有考虑用算术编码呢，有没有更好的呢

 

I

iie

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #10

怎么还不明白呵，20/lg2=67，就是这么算出来的。
我不明白你说的90位是什么意思，9个字节是72位，有5位空闲。

 

I

iie

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #11

要是我来编算法，就会按10bitsBase1K编码，这样70bits就可以编到21位十进制，
算法可以简单一点。

 

B

brokensun

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #12

iie和jsxjd是同一意思，90是9*10来的，呵呵，10是哪来的呢，是我一时昏，把8当10了。
20个“0”~“9”的数据量呢，你的67位已经是近似的（1024做1K），况且就是67对72也有
5位的冗余，所以我想是不是还有更好的办法，而且不是大家上述的位到字节这样思路

 

I

iie

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #13

你错误的地方很多
1）67位不是base1K的结果
2）我说了base1K要用到70bits表示21位10进制
3）因为是字节单位，空闲位是不可避免的，除非你的编码位正好是8的倍数
4）67位是编码极限，这是没有疑问的
5）空闲位跟冗余是两码事
6）至于编码方式，要求简单的话BCD是最适宜的，可是你又说10字节免谈，呵呵
7）再多我也懒得说了，看来你没开过基础课，呵

 

B

beyondair

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-30

• #14

想想

 

B

brokensun

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-08

• #15

编码压缩有利用冗余和熵两种方式
67位是编码是极限想是从冗余角度出发的吧，我想处理一个问题，经验确实重要，但原理
也该是很重要，不然就不会从根本上所提高
好了，希望有兴趣的朋友的继续，我呢，开基础课去了~~~~~

 

I

iie

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-19

• #16

:-(
看来我的回答不见得比pearl更准确……

 

A

ana

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-19

• #17

我也不同意什么67就是极限的（井底之蛙），但是如果用熵压缩的话恐怕不能定长吧

 

I

iie

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-19

• #18

OMG

 

G

GGCAT

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-19

• #19

67bit是最坏情况 最好情况不好说
最好还是要和数据的统计相关针对

 

J

jsxjd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-19

• #20

因为你给的信息 只是 20 个 0-9 ，那有 10^20 种情况。每一种情况必须有不同的编码。
这和压缩程序对特定文件的压缩处理是不一样的。
归根到底是 10^20 是 256 的多少次方的问题。