Можно ли упаковать 11-символьную строчку из цифр в 4 байта?
17.01.03 00:01: Перенесено из 'Алгоритмы'
Здравствуйте Константин Быченков, Вы писали:
КБ>Можно ли упаковать 11-символьную строчку из цифр в 4 байта?
При удачном стечении обстоятельств можно все!
Ты можешь выбрать кодировку для цифр так, чтоб сжатие получилось максимальным, но в 4 байта ты не обязательно уложишься. Я так понимаю, цифры у тебя десятичные? Тогда две наиболее часто встречающиеся цифры закодируй как 00 и 01, а остальные восемь наборами из 4 битов, начинающимеся с единицы(таких как раз 8 штук). Тогда по первому биту ты можешь определять идет набор из двух битов или четырех. В некоторых случаях тебе хватит 4 байтов.
Здравствуйте yogi, Вы писали:
В строке 11 цифр, поэтому в худшем случае одна встретится дважды. Пусть это будет 0.
частоты
0 - 2 --- 2 -+- 4 -------+- 11
| |
1 - 1 -+- 2 -+ |
| |
2 - 1 -+ |
|
3 - 1 -+- 2 -+- 4 -+- 7 -+
| | |
4 - 1 -+ | |
| |
5 - 1 -+- 2 -+ |
| |
6 - 1 -+ |
|
7 - 1 -+- 2 -+- 3 -+
| |
8 - 1 -+ |
|
9 - 1 --- 1 -+
итого код Хаффмана
0 00
1 010
2 011
3 1000
4 1001
5 1010
6 1011
7 1100
8 1101
9 111
00123456789 = 00.010.011.1000.1001.1010.1011.1100.1101.111
байт # 11 111 111 2222 2222 3333 3333 4444 4444
чуть-чуть не хватило.
Здравствуйте Кодт, Вы писали:
К>К>00123456789 = 00.010.011.1000.1001.1010.1011.1100.1101.111
К>байт # 11 111 111 2222 2222 3333 3333 4444 4444
К>
К>чуть-чуть не хватило.
В том-то и дело, что для
произвольной строки не хватит 4 байт, хоть какой сверхплотный код(ну без потери информации, конечно) используй!
2^32 < 10^11
Здравствуйте Курилка, Вы писали:
Кодт>>чуть-чуть не хватило.
Курилка>В том-то и дело, что для
произвольной строки не хватит 4 байт, хоть какой сверхплотный код(ну без потери информации, конечно) используй!
Курилка>2^32 < 10^11
Если две цифры повторяются по 2 раза, или одна — 3 раза, то
1 ------- 2 -------#- 4 -#- 7 -#- 11 | ----------- 3 -------#- 7 -#- 11
| | | | | |
2 ------- 2 -------+ | | | - 1 -#- 2 -----#- 4 -+ |
| | | | | |
3 - 1 -------#- 3 -------+ | | - 1 -+ | |
| | | | |
4 - 1 -#- 2 -+ | | - 1 -#- 2 -----+ |
| | | | |
5 - 1 -+ | | - 1 -+ |
| | |
6 - 1 -#- 2 -------#- 4 -------+ | - 1 -#- 2 -----#- 4 -------+
| | | | |
7 - 1 -+ | | - 1 -+ |
| | |
8 - 1 -#- 2 -------+ | - 1 -#- 2 -----+
| | |
9 - 1 -+ | - 1 -+
|
1: 000 | 00
2: 001 | 0100
3: 010 | 0101
4: 0110 | 0110
4: 0111 | 0111
6: 100 | 100
7: 101 | 101
8: 110 | 110
9: 111 | 111
|
29 бит | 30 бит
Ну и, конечно, еще кодовая таблица должна прилагаться ;)
Здравствуйте Курилка, Вы писали:
К>В том-то и дело, что для произвольной строки не хватит 4 байт, хоть какой сверхплотный код(ну без потери информации, конечно) используй!
К>2^32 < 10^11
Эта да, абсолютно веррррна!!! Нельзя построить инъективную функцию f:A->B, если мощность множетва A больше мощности множества B.
Перекуём баги на фичи!
