Алгоритмическое
Экспериментирую с архиваторами, алгоритмами сжатия данных, с ориентированными на сжатие текста.
Есть моя реализация PPM, которая сжимает тексты лучше WinRar и 7zip. Написана она just for fun, на практике не применима, работает в 20 раз медленнее, чем те же WinRar и 7zip. Внутри использует полу-байтовое суффиксное дерево (suffix tree), оно просто быстрее байтового суффиксного дерева. Это основной вариант, он рабочий, его можно пощупать, протестировать, запаковать что-то и распаковать.
Я захотел написать вариант, использующий битовый разбор, строится битовое суффиксное дерево.
Написал.
Оно работает, и даже быстрее, чем в основном варианте, но... узлов очень много.
Оказалось, что суффиксное дерево для битового разбора требует намного больше узлов, чем для полу-байтового, которое у меня в основном алгоритме. Чудовищно много узлов.
А в это время существует мой старый алгоритм битового разбора в Patricia Tree, которое требует намного меньше узлов, чем даже в основном алгоритме. Намного, в десятки раз меньше.
При этом, просасывание файла через парсер для разбора на полную глубину (для контекстов длиной 1000+ битов) выполняется в три раза быстрее, чем в битовом суффиксном дереве на глубину 128 битов. То есть, и узлов меньше, оперативной памяти для разбора текста требует меньше, ещё и работает очень быстро.
Надо их как-то скрестить между собой.
Есть два тестовых файла, enwik8 на 10^8 байтов дампа википедии, и enwik9 на 10^9 байтов дампа википедии. То есть, на 100 Mb и 1000 Mb. В Patricia Tree каждый бит имеет индекс, и у меня не реализован скользящий буфер битов для Patricia Tree, так что хочется засосать весь большой файл в буфер целиком. Оказалось, что Int32 не хватает, чтобы индексировать биты такого большого буфера, нужно использовать int64.
Возникают любопытные проблемы, когда ворочаешь такими большими объёмами данных!
Есть моя реализация PPM, которая сжимает тексты лучше WinRar и 7zip. Написана она just for fun, на практике не применима, работает в 20 раз медленнее, чем те же WinRar и 7zip. Внутри использует полу-байтовое суффиксное дерево (suffix tree), оно просто быстрее байтового суффиксного дерева. Это основной вариант, он рабочий, его можно пощупать, протестировать, запаковать что-то и распаковать.
Я захотел написать вариант, использующий битовый разбор, строится битовое суффиксное дерево.
Написал.
Оно работает, и даже быстрее, чем в основном варианте, но... узлов очень много.
Оказалось, что суффиксное дерево для битового разбора требует намного больше узлов, чем для полу-байтового, которое у меня в основном алгоритме. Чудовищно много узлов.
А в это время существует мой старый алгоритм битового разбора в Patricia Tree, которое требует намного меньше узлов, чем даже в основном алгоритме. Намного, в десятки раз меньше.
При этом, просасывание файла через парсер для разбора на полную глубину (для контекстов длиной 1000+ битов) выполняется в три раза быстрее, чем в битовом суффиксном дереве на глубину 128 битов. То есть, и узлов меньше, оперативной памяти для разбора текста требует меньше, ещё и работает очень быстро.
Надо их как-то скрестить между собой.
Есть два тестовых файла, enwik8 на 10^8 байтов дампа википедии, и enwik9 на 10^9 байтов дампа википедии. То есть, на 100 Mb и 1000 Mb. В Patricia Tree каждый бит имеет индекс, и у меня не реализован скользящий буфер битов для Patricia Tree, так что хочется засосать весь большой файл в буфер целиком. Оказалось, что Int32 не хватает, чтобы индексировать биты такого большого буфера, нужно использовать int64.
Возникают любопытные проблемы, когда ворочаешь такими большими объёмами данных!