Раскрытие информации: это задание, и я также связался с моим профессором и моим техническим специалистом для ответа. Я проявляю должную осмотрительность и пытаюсь найти наилучшее объяснение проблемы, с которой я борюсь (т.е., пожалуйста, не включайте код). Любая помощь приветствуется!
Я понимаю, что один из простейших подходов к уменьшению следа за таблицей возникновения - это использование контрольных точек. Однако в процессе реализации, с целью декодирования, я заметил, что по мере увеличения размера моего файла (~ 5 КБ) время выполнения начинает значительно замедляться (программа просто зависает на несколько минут перед успешным завершением). Узкое место здесь заключается в том, что после определения контрольной точки в худшем случае нам нужно читать от или до средней точки контрольных точек. Кроме того, как только буферизованная подстрока считывается из входного файла BWT, счетчик для указанного символа также должен быть обновлен, чтобы получить окончательный счет. Мне интересно:
- Если возможно, без дополнительных накладных расходов на память, обновить счетчик, пока буфер считывается из файла?
- Если мое понимание контрольных точек неверно? В настоящее время это понимается следующим образом: определяется размер блока, и каждая последующая контрольная точка отмечает конец предыдущего блока и начало следующего блока.
- Проблема еще проще, и проблема только в поиске частично несортированный массив (т.е. буферизованная часть, считанная из файла)?
Примечание: входной файл BWT не содержит операций RLE или MTF. Выходной файл - это исходная строка. Программа реализуется в C.