| Вопрос: Интересная проблема:) | Добавлено: 11.05.06 18:48 |
Автор вопроса:  BUG(O)R | Web-сайт: hunger.ru | ICQ: 827887 |
|
Вообщем возникла такая вот интересная проблема, есть некоторый массив данных(символов), например:
0000000000001113333333333333333455555555 Путём долгих манипуляций были найдены БИНАНЫЕ кодыкаждого из этихсимволов, так: 0 -> 11b 1 -> 1001b 3 -> 0b 4 -> 1000b 5 -> 101b Теперь значит задача заменить все эти символы этими кодами, т.е. в итоге должно получиться такое вот число страшное: 11111111111111111111111110011001100100000000000000001000101101101101101101101101b или в шестнадцатиричной системе: FFFFFF99900008B6DB6D Проблема в чём, я сделал с помощью сдвига влево(shl), всё работает, за исключением участков, где например встречается подряд 8 и более символов, чей бинарный код 0. Объясняю дальше, a начинаю формировать байт, если при следующем шаге(сдвиге) он оказывается больше FF, то я отодвигаюьс на шаг назад, записываю этот байт и начинаю формировать следующий байт, т.е. так: 11b 1111b 111111b 11111111b Всё, первый байт сформирован, так я дохожу до участка, где подряд идут 16 троек, их код равен 0, соответственно вместо того, чтобы записать: 90 00 08, получается что все эти нули уходят в пустоту потому как действительно если начать формировать код, то и 0 и 00 и 00000000 будет меньше 255, а мне нужно это учитывать. Так вот как лучше сделать? Писать дополнительный обработчик таких участков? Тогда как? Я понимаю, что наверное трудно понять, что я от вас хочу, спрашивайте я объясню подробнее. |
| Ответы | Всего ответов: 8 |
|
Номер ответа: 1 Автор ответа:  HACKER Разработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #1 | Добавлено: 11.05.06 21:27 |
несрост какой-то, почему именно трояка получилась "0" ? Я конечно не особо в проблему въехал... нет, я читал внимательно, даже несколько раз... просто это что-то такое, которое не поддаётся мозговому штурму без пива, а его щас под рукой нет  чуть позже исправлю ситуацию... а пока расскажи как из 16 нулей (16 троек, код которых "0" надо получить "90 00 08" ?
|
||
|
Номер ответа: 2 Автор ответа: LamerOnLineICQ: 334781088 Вопросов: 108 Ответов: 2822 |
Профиль | | #2 | Добавлено: 12.05.06 11:31 |
|
Ага, объясни следующую фразу
Путём долгих манипуляций были найдены БИНАНЫЕ кодыкаждого из этихсимволов
Возможно после этого и станет понятно остальное... |
||
|
Номер ответа: 3 Автор ответа: Sergey ICQ: 283551900 Вопросов: 1 Ответов: 74 |
Профиль | | #3 | Добавлено: 12.05.06 14:05 |
|
ХМ смахивает на сжатие. Не помню как этот метод называется)
Проблема в чём, я сделал с помощью сдвига влево(shl), всё работает, за исключением участков, где например встречается подряд 8 и более символов, чей бинарный код 0. Объясняю дальше, a начинаю формировать байт, если при следующем шаге(сдвиге) он оказывается больше FF, то я отодвигаюьс на шаг назад, записываю этот байт и начинаю формировать следующий байт, т.е. так:
Немного неверно делай класс Byte который будет содержать сам байт и сколько уже записано. И создавай метод записать бить который будет возвращать true(если байт заполнен) или false (в противном случии) можно другой вариант когда класс отвечает за запись в поток данных. Реализация метода проста. Добавляешь сдвигом 1 бит. Увеличиваешь счетчик на один. Если счетчик 8 то возвращаешь true иначе false. Если метод вернул true то пишешь полученный бит и обнуляешь счетчик. P.S не забудь записать не законченный бит. Если нужно могу выложить работу ‘сжатие файла методом ****забыл каким***’ написанную на С++. |
||
|
Номер ответа: 4 Автор ответа: BUG(O)R ICQ: 827887 Вопросов: 13 Ответов: 142 |
Web-сайт: Профиль | | #4 | Добавлено: 12.05.06 15:18 |
|
Ребята, суть не в том как называется этот метод, и не в реализациях его на других языках, ну если на то пошло, то выполняется сжатие по методу Хаффмана, но мне не надо ссылки на описание алго или реалзации на других языках, я пишу по-своему и с нуля, не смотря ни на чьи сорсы, я просо хочу узнать как мне решить эту проблему, сам алгоритм я понимаю отлично и если бы я писал на ассемблере, скажем, я бы даже не ломал голову над подобной проблемой.
Объясняю подбробнее: Смотрите, первый проход, первый символ "0", его код 11b, я получаю: 11b - это меньше FFh следоваельно формирую дальше это байт, второй проход, второй символ опять "0", его код 11b, получаю: 1111b Опять меньше FFh, значит продолжаю формировать эо байт, так дохожу до 5 символа, на о момент я имею 11111111b, следующий проход нам даёт 1111111111b, это уже больше FFh, значит запсываю 11111111b, обнуляю байт и начинаю формирование нового байта с 5 символа и т.д. Но потом дело доходит до цепи символов "3", а код символа 0b, на момент подхода в этой цепи символов с нулевым кодом я имею 4 сформированных байта: FF FF FF 99h и один ещё недоформированный байт, который равен 9 и в котором закодирован последний из трёх символов "1", его бинарный код 1001b, что в десятичной и есть 9, далее я беру символ "3", его у меня 0, я сдвигаю мой байт таким образом: szByte = szByte * (Bit(j) * Bit(j)) + sootv(j) Где Bit(j) - кол-во бит в коде(у нас код 0, значит bit(j)=0), а sootv(j) и есть сам бинарный код, в результате мы как имели szByte=9, так его и будем иметь, хотя команда shl, коей к моему велкому сожалению нет в басике, вернула бы не 9, а 18, ну этот случай легко обрабатывается таким образом: If sootv(j) > 0 Then szByte = szByte * (Bit(j) * Bit(j)) + sootv(j) Else szByte = szByte * 2 End If Но эо сработает только в случае, когда szByte уже был больше нуля, таким образом участок "1333" мы кодируем так: 10010000, что равно 90h И вот дальше самое интересное, мы имеем 13 троек, бинарный код символ "3" = 0, и мой обработчик который я привёл выше будет на этом сдыхать, хотя должен софрмировать последовательность 00000000b. Вводить дополнельную проверку, как посоветовал Sergey, т.е. проверять закодировалось ли уже больше 8 бит или нет, я не хочу, ибо просто скорость упадёт, хотя судя по всему придётся это сделать. Попробую вообщем переписать, пока кто, что может предлогайте 
|
||
|
Номер ответа: 5 Автор ответа: SergeyICQ: 283551900 Вопросов: 1 Ответов: 74 |
Профиль | | #5 | Добавлено: 12.05.06 17:27 |
|
Где Bit(j) - кол-во бит в коде(у нас код 0, значит bit(j)=0), а sootv(j) и есть сам бинарный код, в результате мы как имели szByte=9, так его и будем иметь, хотя команда shl, коей к моему велкому сожалению нет в басике, вернула бы не 9, а 18, ну этот случай легко обрабатывается таким образом:
If sootv(j) > 0 Then szByte = szByte * (Bit(j) * Bit(j)) + sootv(j) Else szByte = szByte * 2 End If Bit(j) - кол-во бит в коде sootv(j) и есть сам бинарный код что будет если Bit(j) = 2 а sootv(j) = '00' szByte = szByte * 2 // произойдет сдвиг на 1 бит а должно на 2. szByte = szByte * (Bit(j) * Bit(j)) + sootv(j)
что означает Bit(j) * Bit(j)? Bit(j) * Bit(j) – скорей всего хотел сдвинуть на Bit(j) – бит. скорей всего так. szByte = szByte * (2 ^ Bit(j)) + sootv(j)
мой совет работай не с байтами а с long сразу будеш писать 4 байта. Вводить дополнельную проверку, как посоветовал Sergey, т.е. проверять закодировалось ли уже больше 8 бит или нет, я не хочу, ибо просто скорость упадёт
я предложил самый простой метод. я делал так. создавал класс который отвечал за запись в поток. основные его свойства: BufCount - количество бит в буфере, Buffer – сам буфер тип long. И методы: write(Cod as long,Size as long) – записать код(Cod) длины Size privat _write(Cod as Long, Size as Long) – записать код(Cod) длины Size за переполнение буфера отвечает вызвавшая функция. Out() – запись в поток буфера и его обнуление. _write(Cod as long , Size as long) { Buffer= Buffer*(2^ Size) + Cod BufCount = BufCount+ Size } write(long Cod, long Size) { Dim tCount as long - If Size+ BufCount>32 then если будет переполнение tCount = 32-BufCount Считаем сколько бит недостает до заполнение буфера. _write( Cod/(2^( Size – tCount ) ) , tCount ) заполняем буфер Cod/(2^( Size – tCount ) ) выдираем из Cod первые tCount бит. Out() выводим в файл _write( Cod and (2^ (Size – tCount) -1) ) ,Size - tCount ) заполняем буфер оставшейся частью. Cod and (2^ (Size – tCount) -1) выдираем оставшиеся биты. Else Иначе просто пишем в буффер _write( Cod,BufCount) If BufCount= 32 then Out() выводим если заполнили буфер. End if } На С проще можно записать Cod/(2^( Size – tCount ) как Cod>> Size – tCount ) может и в VB так можно.
(2^ (Size – tCount) -1) лучше заранее создать массив M[x] = (2^ (x) -1) |
||
|
Номер ответа: 6 Автор ответа: BUG(O)RICQ: 827887 Вопросов: 13 Ответов: 142 |
Web-сайт: Профиль | | #6 | Добавлено: 12.05.06 17:46 |
|
Sergey, 00 = 0 = 0000000 или = 0000000000000, поэтому сдвиг надо именно на 1 бит
szByte = szByte * (2 ^ Bit(j)) + sootv(j) - не подумал, так правильнее будет
Вот я и говорю, что если бы я писал не на ВБ, я бы вообще с mmx регистрами работал, 64 разрядными, ну было бы даже легче, если бы вб тип long воспринимал подругому, а не как число от -2147483648 до +2147483647 |
||
|
Номер ответа: 7 Автор ответа: SergeyICQ: 283551900 Вопросов: 1 Ответов: 74 |
Профиль | | #7 | Добавлено: 12.05.06 21:39 |
|
Sergey, 00 = 0 = 0000000 или = 0000000000000, поэтому сдвиг надо именно на 1 бит
чтото ты непонимаеш. Пример: 0 -> 11b 1 -> 011b 3 -> 00b 4 -> 010b 5 -> 10b 3 кодируется двумя битами то есть '00' хотя числовое значение 0 но оно теряет длину кода. насчет long используй только первые 3байта(24 бит) |
||
|
Номер ответа: 8 Автор ответа: BUG(O)RICQ: 827887 Вопросов: 13 Ответов: 142 |
Web-сайт: Профиль | | #8 | Добавлено: 13.05.06 09:07 |
|
Sergey, я не знаю о чём ты говоришь, но на основе моего дерева хаффмана у меня 3 кодируется одним 0, поэтому и сдвигаю я на 1 бит.
А работать с 3 младшими байтами числа, когда сам компилятор во всех операциях его представляет как dword более неудобно, чем работать с одним байтом. |
||
Страница: 1 |