Извините за путаницу, в статье забыл написать про унарный префикс, который обозначает число блоков кодирования. Но в бенчмарке он учтен. Т. е. у вас все правильно, но терминатор не нужен, а нужно перед кодом 1110 = 3 написать, число блоков кода: 110 01 001 1111 111111111111111 Псевдокод:
decode(stream):
read unary -> num_blocks
read 2 bits -> current_val
repeat num_blocks times:
ones_needed = current_val
value = 0
pos = 0
while ones_counted < ones_needed:
bit = read 1 bit
if bit == 1:
value |= (1 << pos)
ones_counted += 1
pos += 1
while true:
bit = read 1 bit
if bit == 1:
value |= (1 << pos)
break
pos += 1
current_val = value
return current_val
Первые два бита переворачивать не надо, так как декодер и так знает что ему читать ровно два бита.
Второй уровень(и любые следующие, кроме данных) всегда начинается на 1, так как должны быть строго больше прошлого (иначе нет смысла от нового уровня).
Таким образом единица в начале каждого уровня очевидна и хранить ее не обязательно, но нам нужен терминатор.
Поэтому мы переворачиваем коды каждого уровня кроме первого и самих данных, чтобы эта единица была в конце и декодер читал все до нее.
Прогонял, собственно и ссылка на репозиторий есть.
Код рекурсивный, данные разворачивать не надо - после них и так терминатор, разворот происходит только у кодов, сделать я это могу потому что последовательность чисел монотонно возрастает, и начинаются потому все числа всегда на единицу - которую я и использую как терминатор
Хэши поломают поиск подстрок, и оставят только exact мэтчи. Если брать какой то хэш который сохраняет информацию, а не возвращает рандом - тогда еще можно попробовать.
Про размер блока, он привязан к размеру того что вы ищете, если длинный поиск и короткие блоки - будет много false positives просто и все. Размер блоков самих данных не особо важен.
Сегодня поиграюсь с этим, возьму и конкурента пожестче, и свой алгоритм пожестче сделаю
Поправил примерчики, опечаток не было - просто неочевидные формулировки.
Читаем мы не до одной единицы, а до следующей после закодированной, иначе все нули не учитывались бы. Если бы мы заранее знали что все данные, которые мы кодируем заканчиваются на 1 - могли бы сэкономить бит на терминаторе.
Я так понял ты про упаковать несколько чисел в один u32/u64/u128? Когда ты знаешь заранее что и как кладешь и тебе все считать на видеокарте - то так и надо
Но суть моего кода в том, что ты пишешь биты не по фиксированной раскладке фиксированной длины, а сколько надо - столько и пишешь, отсюда и появляется проблема неоднозначности декодирования, которую решают универсальные коды типа моего.
00 - 0 единиц, можно кодировать сколько угодно нулей, если не нужно - всегда можно сдвинуть все числа и назначить на 00 одну единицу или что то другое вообще
Насчет оценки сколько попкаунтов. Верхняя оценка - столько же сколько и у омеги, а точно без попкаунтов посчитать и не выйдет
Если надо выбирать из нескольких стратегий то надо их как то кодировать по идее log2(число стратегий) битами, или заранее выбрать одну - смотря какие числа чаще будут встречаться, на 16к-2кк vbyte самый вкусный потому что паддинг нули почти пропадают в процентном соотношении а сумма битовых флагов еще более менее сравнима с омегой
По факту для маленьких штучек лучше писать фиксированные кастомные структуры исходя из статистического распределения данных которые через нее будут проходить и желаемой точности, универсальные коды тут и по длине и по вычислениям могут быть не оптимальны
Upd: если мы знаем еще что это вдобавок и число то можно еще бит сэкономить не тратя память на очевидную первую единицу
На счет отрицательных я сейчас подумал и можно 1 бит флаг писать в конец перед терминатором, но вообще это зависит от того как вы отрицательные числа кодируете, флагом в начале или по стандарту который сейчас везде
lrzip части рядом располагает и жмет их, мой убирает дубликаты полностью и у lrzip ограничение - окно zstd, то есть соотношение сжатия упрется в плато - собственно как и сам zstd
Извините за путаницу, в статье забыл написать про унарный префикс, который обозначает число блоков кодирования. Но в бенчмарке он учтен. Т. е. у вас все правильно, но терминатор не нужен, а нужно перед кодом 1110 = 3 написать, число блоков кода: 110 01 001 1111 111111111111111 Псевдокод:
Сегодня-завтра выложу сравнение с ними.
Суффиксное дерево как минимум весит немало в сравнении. Bwt пока не тестил.
Но вообще я не для каких то своих задач ищу структуры данных, я просто исследую в свободное время и делюсь наработками.
В обратном порядке:
0101 0110 - исходные данные, 4 единицы
100 - 4, означает число единиц у верхнего уровня
01 - 1, число единиц верхнего уровня
Первые два бита переворачивать не надо, так как декодер и так знает что ему читать ровно два бита.
Второй уровень(и любые следующие, кроме данных) всегда начинается на 1, так как должны быть строго больше прошлого (иначе нет смысла от нового уровня).
Таким образом единица в начале каждого уровня очевидна и хранить ее не обязательно, но нам нужен терминатор.
Поэтому мы переворачиваем коды каждого уровня кроме первого и самих данных, чтобы эта единица была в конце и декодер читал все до нее.
Итого имеем 01 001 01010110 1
Многоразовая проверка membership
Частая
Прогонял, собственно и ссылка на репозиторий есть.
Код рекурсивный, данные разворачивать не надо - после них и так терминатор, разворот происходит только у кодов, сделать я это могу потому что последовательность чисел монотонно возрастает, и начинаются потому все числа всегда на единицу - которую я и использую как терминатор
Ну если устраивает O(N) то в целом можно просто лечь и расслабиться
Если я правильно понял
Оба захлебнутся в false positive
Хэши поломают поиск подстрок, и оставят только exact мэтчи. Если брать какой то хэш который сохраняет информацию, а не возвращает рандом - тогда еще можно попробовать.
Про размер блока, он привязан к размеру того что вы ищете, если длинный поиск и короткие блоки - будет много false positives просто и все. Размер блоков самих данных не особо важен.
Сегодня поиграюсь с этим, возьму и конкурента пожестче, и свой алгоритм пожестче сделаю
Поправил примерчики, опечаток не было - просто неочевидные формулировки.
Читаем мы не до одной единицы, а до следующей после закодированной, иначе все нули не учитывались бы. Если бы мы заранее знали что все данные, которые мы кодируем заканчиваются на 1 - могли бы сэкономить бит на терминаторе.
Я почитал в интернете, да есть BinaryFuse8, завтра сравню, да и пара идей по доработке моего алгоритма появилась - и выложу еще статейку с числами
Размер ядра можно ограничить увеличив агрессивность сжатия, т. е. Уменьшив размер минимального коллапса, но подрастает число false positives немного
А скелет в целом напрямую зависит не от количества данных, а от их общей энтропии, так что при линейном росте данных ядро может вообще не расти
Черт возьми да!) Буду благодарен если найдешь ошибки в алгоритме, тогда сдамся и пойду работать в макдональдс где мне и место?
Я так понял ты про упаковать несколько чисел в один u32/u64/u128? Когда ты знаешь заранее что и как кладешь и тебе все считать на видеокарте - то так и надо
Но суть моего кода в том, что ты пишешь биты не по фиксированной раскладке фиксированной длины, а сколько надо - столько и пишешь, отсюда и появляется проблема неоднозначности декодирования, которую решают универсальные коды типа моего.
00 - 0 единиц, можно кодировать сколько угодно нулей, если не нужно - всегда можно сдвинуть все числа и назначить на 00 одну единицу или что то другое вообще
Насчет оценки сколько попкаунтов. Верхняя оценка - столько же сколько и у омеги, а точно без попкаунтов посчитать и не выйдет
Если надо выбирать из нескольких стратегий то надо их как то кодировать по идее log2(число стратегий) битами, или заранее выбрать одну - смотря какие числа чаще будут встречаться, на 16к-2кк vbyte самый вкусный потому что паддинг нули почти пропадают в процентном соотношении а сумма битовых флагов еще более менее сравнима с омегой
По факту для маленьких штучек лучше писать фиксированные кастомные структуры исходя из статистического распределения данных которые через нее будут проходить и желаемой точности, универсальные коды тут и по длине и по вычислениям могут быть не оптимальны
Так я же про хранение написал. О сжатии и передаче даже не заикался!
При чем тут Хаффман и Соломон то…
но тема действительно интересная)
Upd: на счет микроконтроллеров - есть no_std, но если очень хочется переписать на C, 400 строк по образцу написать нынче дело очень простое
Биты они и есть биты) универсальный же код!
Upd: если мы знаем еще что это вдобавок и число то можно еще бит сэкономить не тратя память на очевидную первую единицу
На счет отрицательных я сейчас подумал и можно 1 бит флаг писать в конец перед терминатором, но вообще это зависит от того как вы отрицательные числа кодируете, флагом в начале или по стандарту который сейчас везде
lrzip части рядом располагает и жмет их, мой убирает дубликаты полностью и у lrzip ограничение - окно zstd, то есть соотношение сжатия упрется в плато - собственно как и сам zstd