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

← →
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 правильно

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

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

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

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

+1

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

> +1

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

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

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

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

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

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

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

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

... 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

> 11-88-2

11-88-3

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