Комментарии 13
Ненавижу форматы с битовым (а не байтовым) выравниванием.
Да. Жестоко) Мне кажется, что лидером по сложности будет арифметическое кодирование с ограниченной разрядностью. Мало того, оно ещё редко где используется - если нужно экстремальное сжатие (алгоритмы с моделированием контекста). А так, да, оптимизированный BWT - это довольно таки хитрая вещь.
Да ладно, 15 строчек реализации самого кодирования. Вот моделирование контекстов - это да, там легко тысячи строк набираются.
Реализация может и да, но чтобы осознать её корректность... А контекстное моделирование довольно таки очевидная вещь, хоть и объёмная по коду.
Подводные камни там есть, конечно. Но и двоичный поиск с нуля обычно с багами выходит :) Нужно не изобретать велосипед просто.
Да, изобретать не надо, но чтобы подробно изучить и понять откуда это получилось, можно потратить много времени, как я собственно и сделал. В итоге, понял, но оставил затею сделать туториал по арифметическому кодированию... Rans куда практичнее, понятнее и быстрее; единственное, он не позволяет делать моделирование контекста, и Rans также можно свести к Хафману, если проквантовать частоты по степеням двойки (проверено).
Занятный факт на тему нишевости BWT — он также лежит в основе bowtie2 (hence the name), одного из стандартных биоинформатических инструментов для выравнивания фрагмента ДНК на геном.
Браво, очень глубокое объяснение! BWT встречается часто, но объясняют его, обычно, плохо. Хотя, возможно, это особо и не требуется - работает и ладно 😁
А объяснение его логики через цепи Маркова вы сами вывели или взяли откуда-то? Я как-то не встречал его даже в тематической литературе - и правда очень редкая тема
BWT - классная вещь!
Помимо более сжимаемого теста, оно позовляет быстро искать подстроки в этом тексте. Будем искать те строки N*N таблицы, которые начинаются на искомую подстроку. Вот хотите вы найти строку "abc". 'c' находится в строках N*N таблицы, которые начинаются на 'c'. Их мы уже по отсортированному первому столбцу нашли. А где будет строка "bc"? Ясно, что первый символ 'b', но какие из b нам подходят? Тут надо посмотреть на двудольный граф, используемый при декодировании. Надо всять те 'b' в первом столбце, которые в последнем столбце выпадют в промежуток, где стоит 'c'. Это можно или бинарным поиском найти, или сохранить таблицу предподсчета, размера |A|*N, где A-алфавит. И не надо даже всю N*N таблицу хранить, нам нужно лишь знать буквы в первом и последнем столбце и перестановку, она же двудольный граф между столбцами.
Именно поэтому оно широко применяется в биоинформатике: Это хорошо сжимаемый формат, с которым можно эффективно работать.
Спасибо, интересная статья!
Насчет сортировки циклических сдвигов - а вы не пробовали стандартный prefix doubling algorithm - он, насколько я помню, довольно просто пишется, и работает за O(N*log N), сильно быстрее наивного, хотя и медленнее линейных. Но и классический алгоритм Укконена по построению суффиксного дерева на питоне занимает всего 50 строк, хотя самому его написать (и, главное, отладить), наверное, сложно.
BWT и MTF на SQL для целей обучения :-)
Как написать bzip2-архиватор на Python: разбираем преобразование Барроуза-Уилера