Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2012.05.06;
Скачать: CL | DM;

Вниз

Поиск максимального количества равноудалённых битов   Найти похожие ветки 

 
xayam ©   (2011-12-30 12:43) [0]

в битовом поле

http://xayam.livejournal.com/6421.html

посоветуйте чего есть в природе из алгоритмов для реализации такого


 
wl ©   (2011-12-30 13:41) [1]

что-то не увидел сумму


 
xayam ©   (2011-12-30 13:49) [2]


> сумму

сумму?


 
Pavia ©   (2011-12-30 13:53) [3]

AND с маской потом считаешь сумму бит.


 
xayam ©   (2011-12-30 14:09) [4]


> AND с маской потом считаешь сумму бит

трудно представить, что это сработает.
скажем размер файла 1МБ = 1024КБ = 1.048.576 Байт = 8.388.608 бит ~~~ 10 млн. бит
Шаг между битами может быть равен и 1000 спокойно...
Какой комп справится с такой маской?


 
CRLF   (2011-12-30 14:15) [5]

очередной байт нулевой? добавь 8 к расстоянию, перейди к следующему байту...


 
xayam ©   (2011-12-30 14:24) [6]


> очередной байт нулевой? добавь 8 к расстоянию, перейди к
> следующему байту

байты не нужны, их как бы нет, только биты
Для этого конечно всё равно из файла придется читать побайтно, но далее байты, выстроенные в одну большую цепочку, рассматриваются в алгоритме только на уровне битов...


 
CRLF   (2011-12-30 14:32) [7]

на машинном уровне они как бы есть и тебе придётся как бы подстроиться под этот факт.


 
xayam ©   (2011-12-30 14:39) [8]


> тебе придётся как бы подстроиться под этот факт

на самом деле нет.
Сквозная нумерация битов как раз решает эту проблему.
В поле bits.position записано это значение.
Для ускорения конечно нужен движок базы не InnoDB, а Memory, чтобы всё было в оперативке...
Ну и кусок из файла не более 1МБ (в базе это более 8 млн. строк)


 
Pavia ©   (2011-12-30 14:48) [9]


> Шаг между битами может быть равен и 1000 спокойно...

Могут, но проверять такой шаг не нужно. У тебя максимальное сжатие будет на малых расстояниях. Поэтому нет нужды проверять с шагом более 100 (такое сжатие даст менее 1%)


 
Pavia ©   (2011-12-30 15:01) [10]

Кстати аналогичное преобразование будет если использовать DCT или FFT. При этом для них уже разработаны алгоритмы со скоростью N*LOG(n)


 
Mystic ©   (2011-12-30 16:20) [11]

Я даже не понял, что такое равноудаленные биты. Насчитал как минимум три варианта определения :)


 
Jeer ©   (2011-12-30 17:48) [12]


> что такое равноудаленные биты.


От Нового года :)


 
был здесь   (2011-12-30 18:00) [13]


> что такое равноудаленные биты

последовательность однотипных элементов (битов), расположенных на одинаковом расстоянии друг от друга


 
Mystic ©   (2011-12-30 18:08) [14]

Например

1011100110

Тут на расстоянии 2 сколько битов?

2? учитываем только 101, далее единица мешает
3? учитывает 10111
4? учитываем все четыре установленных бита


 
xayam ©   (2011-12-30 18:22) [15]


> 1011100110

2: 1011100110
3: 1011100110
...
чтобы собрать всё число 1011100110 проще так:
1000000000 (триада = 0-0-1)
0011100000 (триада = 2-1-2)
0000000110 (триада = 7-1-1)
------------------------------
1011100110

но на большем отрезке битов такой подход себя не оправдает...


 
xayam ©   (2011-12-30 18:57) [16]


> 1000000000 (триада = 0-0-1)

опс, 0-0-0 правильно

ошибка кстати в терминологии у меня получается - последний элемент триады это не Количество_шагов, а кол-во шагов минус один. Поскольку цикл будет от нуля до этого значения...


 
xayam ©   (2011-12-30 19:20) [17]


> Количество_шагов

блин вообще какое-то плохое слово, лучше уж кол-во уст. битов в рассматрив. последовательности


 
TUser ©   (2011-12-30 22:10) [18]


> Я даже не понял, что такое равноудаленные биты.

+1


 
xayam (from NB)   (2011-12-31 04:46) [19]


> +1

библейский код понятнее? там вместо битов буквы в тексте Библии,
но принцип тот же...


 
Mystic ©   (2011-12-31 13:19) [20]


> чтобы собрать всё число 1011100110 проще так:


Если тебе надо собрать число, то, имхо, интересно использоать метод ветвей и границ + эвристики.


 
xayam ©   (2011-12-31 21:14) [21]


> Если тебе надо собрать число

собрать нужно будет при распаковки :)
разбиение же на последовательность таких триад - это сжатие :)


 
xayam ©   (2012-01-02 03:51) [22]

хотя думаю, что вопрос стартопика поставлен не правильно.
Дело же не в кол-во элементов в одной последовательности,
нужно как раз нечто другое - чтобы каждая последовательность была на своём месте
и в сумме они давали исходное битовое поле...

Сквозная нумерация битов проясняет ситуацию в этом плане.

Имеем последовательность цифр, например:

... 5, 11, 99, 105, 187, 210, 275 ...
где каждое число - это смещение установленного бита от начала файла.

В данном случае исходное битовое поле можно разделить на две последовательности (выделено жирным):

... 5, 11, 99, 105, 187, 210, 275 ...

... 5, 11, 99, 105, 187, 210, 275 ...

и сохранить их, сжав в триады ( Старт-Шаг-Количество ):

5-100-2

11-88-2


 
xayam ©   (2012-01-02 03:52) [23]


> 11-88-2

11-88-3



Страницы: 1 вся ветка

Текущий архив: 2012.05.06;
Скачать: CL | DM;

Наверх




Память: 0.52 MB
Время: 0.007 c
6-1255618941
sloosar
2009-10-15 19:02
2012.05.06
WinInet


4-1256386078
GreyWolf
2009-10-24 16:07
2012.05.06
Аналог GetExceptionInformation в Delphi


2-1325795317
Gu
2012-01-06 00:28
2012.05.06
stdcall


15-1325234614
xayam
2011-12-30 12:43
2012.05.06
Поиск максимального количества равноудалённых битов


15-1325190602
Юрий
2011-12-30 00:30
2012.05.06
С днем рождения ! 30 декабря 2011 пятница