Форум: "Прочее";
Текущий архив: 2012.05.06;
Скачать: [xml.tar.bz2];
ВнизПоиск максимального количества равноудалённых битов Найти похожие ветки
← →
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;
Скачать: [xml.tar.bz2];
Память: 0.5 MB
Время: 0.003 c