Краткое содержание

arXiv:2512.17217v1 Тип объявления: новое Аннотация: Факторизация Лемпеля-Зива 78 (LZ78) является хорошо изученной техникой сжатия данных. Она и ее производные используются в форматах сжатия, таких как "compress" или "gif". Хотя большинство исследований сосредоточено на факторизации обычных данных, мало внимания уделяется индексации данных для быстрой факторизации LZ78. Здесь мы изучаем факторизацию LZ78 и ее производные в модели сжатия подстрок, где разрешается индексировать данные и возвращать факторизацию указанной подстроки при запросе. В этой модели мы предлагаем алгоритм, работающий в сжатом пространстве, который вычисляет факторизацию с логарифмическим замедлением по сравнению с оптимальной временной сложностью.