Я ищу алгоритм, который может идентифицировать и сжимать последовательные повторы данных, а не повторы более ранних данных; думайте, как LZ, но вместо использования пар длина / смещение, используя пары длина / счет, где источник всегда непосредственно предшествует копиям, позволяя распаковывать при потреблении с помощью простого счетчика l oop. Это обычный механизм в двигателях Retro Musi c, но обычно его делали вручную в течение дня. В идеале он должен генерировать минимально возможное сжатие, когда для исходных данных возможно несколько разных сжатий.
Некоторые размышления, сделанные двумя днями позже: LZ почти полезен для этой цели, но не совсем. Я думаю, что 3 его модификации заставят его работать.
Префикс соответствует только в скользящем окне, если конец совпадения будет концом скользящего окна. Это гарантирует, что он создает циклы, а не ссылки на произвольные местоположения в скользящем окне.
Когда совпадение найдено, оно читает во входных данных вперед, чтобы определить, сколько раз совпадение повторяется ( Механизм LZ RLE c, но квантованный до полных циклов).
Создается дерево решений. Каждый раз, когда обнаруживается al oop, создаются ветви для l oop и no l oop, и обработка продолжается по обоим путям до тех пор, пока все не будут завершены, после чего в качестве кодирования используется кратчайшая общая ветвь. Это делает его не жадным и не позволяет ему всегда брать первый l oop, который может быть меньше, чем последующий l oop, поскольку в отличие от LZ он не может обрабатывать совпадения, содержащиеся в совпадениях.
Итак, для буквенно-цифровых c токенов 0001 2223 2223 2223 2223 24 5656 5678 9999 222A первым кандидатом будет 3x0, который должен быть зациклен. Но 3x0 1 3x2 3 было бы жадной ошибкой; ему нужно дождаться 3x0 1 4x2223, что стало возможным благодаря дереву решений (в отличие от отказа от 3x0 l oop, это создаст бесполезную ветвь).
Я посмотрю, как это реализовать. Есть комментарии?