2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Простой архиватор
Сообщение14.10.2010, 20:04 
Задача
Реализовать архиватор файлов, состоящих только из строчных латинских букв('a'-'z')
..........
..........

Последовательность из n одинаковых символов(байтов) заменяется на один байт, содержащий два значения: n и код строчной латинской буквы. Учесть ограничение на длину последовательности повторяющихся букв - 32 шт. ...........

У меня проблема: как уместить два числа в одном байте? Ведь $2<=n<=32$.

 
 
 
 Re: Простой архиватор
Сообщение14.10.2010, 20:09 
Никак. Скорее всего, в задании ошибка. Ваша задача - определить реальный предел длины последовательности, которую можно закодировать.
Может быть, конечно, что байт у Вас не 8-ми битовый, но это уж слишком маловероятно.

 
 
 
 Re: Простой архиватор
Сообщение15.10.2010, 07:03 
Вариант для меньшего ограничения на длину последовательности (5 символов).
Т.к. словарь состоит из 26 символов, можно использовать не коды ASCII, а последовательный номер ('a'->0, 'b'->1, ..., 'z'->25) и следующую схему кодирования:
Код:
fnnccccc
f = 0/1 (признак - код ASCII/закодированная последовательность);
nn = Длина_Последовательности-2;
ccccc = Номер_Символа.

0x80 -> "aa"
0xf9 -> "zzzzz"

 
 
 
 
Сообщение15.10.2010, 13:35 
lim0n в сообщении #362187 писал(а):
Вариант для меньшего ограничения на длину последовательности (5 символов).

Только почему 5-то, когда 8?... (флажок вреден, тут вам не там, тут не *.PCX)

 
 
 
 Re: Простой архиватор
Сообщение15.10.2010, 13:59 
А в чем проблема-то? Маленьких латинских букв всего лишь 26 < 32 - имеем 4, к примеру, младших, бита. Оставшиеся 4, к примеру, старших бита - количество символов в последовательности + 1 (т.к. бессмыссленно кодировать 0 символов). Т.е. максимальное кол-во повторяющихся символов, закодированных одним байтом у вас будет равно 32.

Т.е. если c - код данного символа, N - кол-во повторов, cc - код, получим:
Код:
cc = ((N-1)<<4) | (c - 'a');

 
 
 
 Re: Простой архиватор
Сообщение15.10.2010, 14:21 
ewert в сообщении #362256 писал(а):
флажок вреден, тут вам не там, тут не *.PCX)
Как в упакованном тексте различить просто символ с кодом ASCII и байт, кодирующий последовательность одинаковых символов?

Ed_Em в сообщении #362268 писал(а):
Маленьких латинских букв всего лишь 26 < 32 - имеем 4, к примеру, младших, бита.
Да, но $26>16$, так что 4 бита не хватит.

 
 
 
 Re: Простой архиватор
Сообщение15.10.2010, 14:34 
lim0n в сообщении #362283 писал(а):
Как в упакованном тексте различить просто символ с кодом ASCII и байт, кодирующий последовательность одинаковых символов?

Что значит "как"? Когда часть битов заранее отведена под длину. Просто кодируем отдельный символ как цепочку единичной длины -- и всё тут.

В формате *.PCX -- совсем другая история, там кодировать приходится все символы, а не только 26 избранных, поэтому без флажков, конечно, и не обойтись. Но это -- там.

 
 
 
 Re: Простой архиватор
Сообщение15.10.2010, 14:42 
ewert в сообщении #362287 писал(а):
Просто кодируем отдельный символ как цепочку единичной длины -- и всё тут.
Т.е.
Код:
0x0 -> "a"
0x20 -> "aa"
...
0xe0 -> "aaaaaaaa"
Похоже на то... :-)

 
 
 
 Re: Простой архиватор
Сообщение15.10.2010, 14:56 
Ed_Em в сообщении #362268 писал(а):
Маленьких латинских букв всего лишь 26 < 32 - имеем 4, к примеру, младших, бита.
Да, но $26>16$, так что 4 бита не хватит.[/quote]
Тьфу ты, извиняюсь, обсчитался...
Мда. Тогда ограничиваемся маскимальной длиной в 8 символов... Либо используем флаги, и более длинные последовательности кодируем двумя байтами.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group