Работа с большим потоком бит

Модераторы: Hawk, Romeo, Absurd, DeeJayC, WinMain

Ответить
DeviceIK
Сообщения: 5
Зарегистрирован: 21 мар 2007, 12:50

Работа с большим потоком бит

Сообщение DeviceIK » 06 дек 2007, 09:31

Исследую файл в битовом виде. Ищу совпадение комбинаций внутри потока.
Размер блока для исследования - от 2 до 4096. Т.е. например, 100 бит. Если
первые 100 бит и 5е 100 бит совпадают, то увеличиваю счетчик для такой
комбинации.
Задача отобразить на графике все комбинации для блока данной длины. Т.е. и
встречающиеся, и все отсутствующие. Т.е. если блок 2 бита, комбинация 01
встречается 3 раза и все, то на графике:
00 - 0,
01 - 3,
10 - 0,
11 - 0.
Вопрос: как сделать то же самое для блока 4096? Поскольку комбинаций
2^4096, то обрабатывать все это довольно долго. Может по частям или еще
как-нибудь. При этом при выводе еще надо проверять было ли совпадение
такой комбинации в файле, чтобы на оси "У" отобразилось нужное значение.

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: Работа с большим потоком бит

Сообщение somewhere » 06 дек 2007, 12:06

1. Думаю не стоит отображать комбинации, которые не встретились. Сами подумайте, 2^4096 - какое это число!!!
2. Предложу другой способ поиска, на примере:
пусть дана последовательность бит, длиной скажем, 16 бит, ну или N
0101011100101001
и пусть размер блока 5 бит, тогда можно составить список из всех встречающихся комбинаций, предварительно перед добавлением проверять - есть ли такой в списке
например:
1. 01010
2. 10101
3. 01011
4. 10111
....
10. 01010 - такая есть уже, не добавляем, счетчик этой + 1
ну и т.д., т.е. не искать перебором всех комбинаций с нуля, потому как с увеличением
длины блока шанс встретить искомую комбинацию будет очччень быстро уменьшаться.
Таким образом ищем исходя из того, что имеем
It's a long way to the top if you wanna rock'n'roll

DeviceIK
Сообщения: 5
Зарегистрирован: 21 мар 2007, 12:50

Re: Работа с большим потоком бит

Сообщение DeviceIK » 06 дек 2007, 12:23

Все совпадения я нашел и могу их отобразить на графике. Нужно все остальные отобразить!

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: Работа с большим потоком бит

Сообщение somewhere » 06 дек 2007, 12:27

Тогда обьясняй, как ищешь? полным перебором? с нуля?
И еще вопрос, КАК ты отобразишь 2^4096 значений? Говоря откровенно, на графике
ты сможешь отобразить кол-во совпадений до длины блока 10-14 бит. При длине блока свыше 14 бит тебе
будет трудно с этим графиком работать.
При длине блока хотя бы 32 бита время хотя бы на формирование графика будет очень велико и измерятся в часах
При длине блока в 64 бита даже просто на перебор значений от 0 до 2^64 потребуется 290 лет, при частоте процессора в 2ГГц - делайте выводы
It's a long way to the top if you wanna rock'n'roll

Ответить