Re-Pair (сокращение от Recursive Pairing) - это алгоритм сжатия на основе грамматики, который по входному тексту строит прямолинейную программу , то есть неконтекстную грамматику, генерирующую единственную строку: входной текст. Грамматика строится путем рекурсивной замены пары символов, наиболее часто встречающейся в тексте. Как только пара символов не встречается дважды, полученная строка используется как аксиома грамматики. Следовательно, грамматика вывода такова, что все правила, кроме аксиомы, имеют два символа в правой части.
Как это работает
Re-Pair была впервые представлена NJ. Ларссон и А. Моффат [1] в 1999 г.
В их статье алгоритм представлен вместе с подробным описанием структур данных, необходимых для его реализации с линейной временной и пространственной сложностью. Эксперименты показали, что Re-Pair обеспечивает высокую степень сжатия и хорошую производительность при декомпрессии. Однако основным недостатком алгоритма является потребление памяти, которое примерно в 5 раз превышает размер входных данных. Такое использование памяти требуется для выполнения сжатия за линейное время, но делает алгоритм непрактичным для сжатия больших файлов.
Изображение справа показывает, как работает алгоритм сжатия строки .
На первой итерации пара , которое встречается трижды в , заменяется новым символом . На второй итерации самая частая пара в строке, который , заменяется новым символом . Таким образом, в конце второй итерации оставшаяся строка будет. В следующих двух итерациях пары а также заменяются символами а также соответственно. Наконец, строка не содержит повторяющейся пары и поэтому используется как аксиома выходной грамматики.
Структуры данных
Для достижения линейной временной сложности Re-Pair требует следующих структур данных
- Последовательность, представляющая входную строку. Должностьпоследовательности содержит i-й символ входной строки плюс две ссылки на другие позиции в последовательности. Эти ссылки указывают на следующие / предыдущие позиции, например а также , такая, что та же подстрока начинается с , а также и все три вхождения фиксируются одной и той же ссылкой (т. е. в грамматике есть переменная, генерирующая строку).
- Очередь с приоритетом . Каждый элемент очереди - это пара символов (терминалы или ранее определенные пары), которые последовательно встречаются в последовательности. Приоритет пары определяется количеством вхождений пары в оставшейся последовательности. Каждый раз, когда создается новая пара, очередь приоритетов обновляется.
- Хеш-таблица для отслеживания уже определенных пар. Эта таблица обновляется каждый раз, когда создается или удаляется новая пара.
Поскольку хеш-таблица и очередь приоритетов относятся к одним и тем же элементам (парам), они могут быть реализованы с помощью общей структуры данных, называемой PAIR, с указателями для хеш-таблицы (h_next) и очереди приоритетов (p_next и p_prev). Кроме того, каждая PAIR указывает на начало первого (f_pos) и последнего (b_pos) вхождений строки, представленной PAIR в последовательности. На следующем рисунке показан обзор этой структуры данных.
На следующих двух рисунках показан пример того, как эти структуры данных выглядят после инициализации и после применения одного шага процесса сопряжения (указатели на NULL не отображаются):
Кодирование грамматики
После того, как грамматика была построена для данной входной строки, чтобы добиться эффективного сжатия, эта грамматика должна быть эффективно закодирована. Одним из простейших методов кодирования грамматики является неявное кодирование , которое заключается в encodeCFG(X)
последовательном вызове функции , описанной ниже, на всех символах аксиомы. Интуитивно правила кодируются по мере их посещения при обходе грамматики в глубину. При первом посещении правила его правая часть рекурсивно кодируется, и правилу присваивается новый код. С этого момента при достижении правила записывается присвоенное значение.
num_rules_encoded = 256 // По умолчанию расширенная кодировка ASCII является терминалами грамматики.writeSymbol ( символ s ) { bitslen = log ( num_rules_encoded ); // Изначально 8, чтобы описать любой расширенный символ ASCII, записывает s в двоичном формате с использованием битов bitlen }недействительными encodeCFG_rec ( символ s ) { если ( ы это не - терминал , и это является в первый часовом Symbol сек появляется ) { принять правило сек → X Y ; записать бит 1 ; encodeCFG_rec ( X ); encodeCFG_rec ( Y ); назначить для символа сек значения ++ num_rules_encoded ; } else { записываем бит 0 ; writeSymbol ( терминал / присвоенное значение ) } } недействительный encodeCFG ( символ s ) { encodeCFG_rec ( ы ); записать бит 1 ; }
Другая возможность - разделить правила грамматики на поколения так, чтобы правило принадлежит поколению если и только один из или же принадлежит поколению а другой принадлежит поколению с участием . Затем эти поколения кодируются последовательно, начиная с поколения. Это был метод, предложенный первоначально, когда впервые была представлена Re-Pair . Однако в большинстве реализаций Re-Pair используется неявный метод кодирования из-за его простоты и хорошей производительности. Кроме того, он позволяет производить декомпрессию на лету.
Версии
Существует несколько различных реализаций Re-Pair . Каждая из этих версий направлена на улучшение одного конкретного аспекта алгоритма, такого как сокращение времени выполнения, уменьшение занимаемого места или увеличение степени сжатия.
Улучшение | Год | Выполнение | Описание |
---|---|---|---|
Просмотр фраз [2] | 2003 г. | [1] | Вместо того, чтобы манипулировать входной строкой как последовательностью символов, этот инструмент сначала группирует символы в фразы (например, слова). Алгоритм сжатия работает как Re-Pair, но рассматривает идентифицированные фразы как терминалы грамматики. Инструмент принимает различные варианты, чтобы решить, какие фразы следует учитывать, и кодирует полученную грамматику в отдельные файлы: один содержит аксиому, а другой - остальные правила. |
Оригинал | 2011 г. | [2] | Это одна из самых популярных реализаций Re-Pair. Он использует описанные здесь структуры данных (те, которые были предложены при первоначальной публикации [1] ) и кодирует полученную грамматику с использованием метода неявного кодирования. Большинство более поздних версий Re-Pair реализованы, начиная с этой. |
Кодировка [3] | 2013 | [3] | Вместо неявного метода кодирования в этой реализации используется метод от переменной длины до фиксированной длины, в котором каждое правило (представленное строкой переменной длины) кодируется с использованием кода фиксированной длины. |
Использование памяти [4] | 2017 г. | [4] | Алгоритм выполняется в два этапа. На первом этапе он рассматривает высокочастотные пары , то есть те, которые встречаются более чемраз, в то время как пары низких частот рассматриваются во втором. Основное различие между двумя фазами - это реализация соответствующих очередей приоритетов. |
Сжатие [5] | 2017 г. | [5] | Эта версия изменяет способ выбора следующей заменяемой пары. Вместо того, чтобы просто рассматривать наиболее часто встречающуюся пару, он использует эвристику, которая штрафует пары, которые не согласуются с факторизацией Лемпеля-Зива входной строки. |
Сжатие [6] | 2018 г. | [6] | Этот алгоритм уменьшает размер грамматики, сгенерированной Re-Pair, сначала заменяя максимальное количество повторов. Когда пара определяется как наиболее часто встречающаяся пара, то есть та, которая должна быть заменена на текущем шаге алгоритма, MR-repair расширяет пару, чтобы найти самую длинную строку, которая встречается такое же количество раз, как и пара, подлежащая замене. Предоставленная реализация кодирует грамматику, просто перечисляя правила в тексте, поэтому этот инструмент предназначен исключительно для исследовательских целей и не может использоваться для сжатия как таковой. |
Смотрите также
Рекомендации
- ^ а б Ларссон, штат Нью-Джерси, и Моффат, А. (2000). Автономное сжатие на основе словаря. Труды IEEE, 88 (11), 1722-1732.
- ^ Р. Ван. «Просмотр и поиск сжатых документов». Докторская диссертация, Мельбурнский университет, Австралия, декабрь 2003 г.
- ^ Сатоши Ёсида и Такуя Кида, Эффективное кодирование переменной длины в фиксированную длину с помощью алгоритма Re-Pair, In Proc. конференции Data Compression Conference 2013 (DCC 2013), стр. 532, Snowbird, Юта, США, март 2013 г.
- ^ Билле, P., Герц, IL, & Prezza, N. (2017, апрель). Компактное сжатие повторной пары. В 2017 году (DCC) (стр. 171-180). IEEE.
- ^ Gańczorz, М., & JEZ, A. (2017, апрель). Улучшения в компрессоре грамматики Re-Pair. В конференции по сжатию данных (DCC) 2017 г. (стр. 181–190). IEEE.
- ^ Фуруйя, И., Такаги Т., Накашима Ю., Inenaga, С., Баннаи H., & Кида, Т. (2018). MR-RePair: сжатие грамматики на основе максимальных повторов. Препринт arXiv arXiv: 1811.04596.