Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 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
2-1325856082
Gu
2012-01-06 17:21
2012.05.06
messagebox


2-1325799180
Gu
2012-01-06 01:33
2012.05.06
опции компилятора


2-1326089711
Псарь
2012-01-09 10:15
2012.05.06
Свой Event Log.


15-1325337132
Кто б сомневался
2011-12-31 17:12
2012.05.06
Что означает жест


15-1324526689
И. Павел
2011-12-22 08:04
2012.05.06
Сайт, сделанный на ucoz.ru





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский