Re-Pair

Алгоритм сжатия на основе грамматики

Re-Pair (сокращение от Recursive Pairing) - это алгоритм сжатия на основе грамматики, который по входному тексту строит прямолинейную программу, то есть контекстно-свободную грамматику, генерирующую одну строку : вводимый текст. Грамматика строится путем рекурсивной замены пары символов, наиболее часто встречающейся в тексте. Если нет пары символов, встречающейся дважды, полученная строка используется как аксиома грамматики. Следовательно, грамматика вывода такова, что все правила, кроме аксиомы, имеют два символа в правой части.

• 1 Как это работает
• 2 Структуры данных
  • 2.1 Кодирование грамматики
• 3 Версии
• 4 См. Также
• 5 Ссылки

Строительство программы прямой линии, которая генерирует строку w = "xabcabcy123123zabc" с помощью Re-Pair

Re-Pair была впервые представлена ​​NJ. Ларссон и А. Моффат в 1999 г.

В их статье алгоритм представлен вместе с подробным описанием структур данных, необходимых для его реализации с линейной временной и пространственной сложностью. Эксперименты показали, что Re-Pair достигает высоких степеней сжатия и предлагает хорошие характеристики для декомпрессии. Однако основным недостатком алгоритма является потребление памяти, которое примерно в 5 раз превышает размер входных данных. Такое использование памяти требуется для выполнения сжатия за линейное время, но делает алгоритм непрактичным для сжатия больших файлов.

На изображении справа показано, как работает алгоритм сжимает строку $w\; =\; xabcabcy\; 123123\; zabc\; \{\backslash \; displaystyle\; w\; =\; xabcabcy123123zabc\}$.

Во время первой итерации пара $ab\; \{\backslash \; displaystyle\; ab\}$, который встречается трижды в $w\; \{\backslash \; displaystyle\; w\}$, заменяется новым символом $R\; 1\; \{\backslash \; displaystyle\; R\_\; \{1\}\}$. На второй итерации самая частая пара в строке $w\; =\; x\; R\; 1\; c\; R\; 1\; cy\; 123123\; z\; R\; 1\; c\; \{\backslash \; displaystyle\; w\; =\; xR\_\; \{1\}\; cR\_\; \{1\}\; cy123123zR\_\; \{1\}\; c\}$, то есть $R\; 1\; c\; \{\backslash \; displaystyle\; R\_\; \{1\}\; c\}$, заменяется новым символом $R\; 2\; \{\backslash \; displaystyle\; R\_\; \{2\}\}$. Таким образом, в конце второй итерации оставшаяся строка имеет вид $w\; =\; x\; R\; 2\; R\; 2\; y\; 123123\; z\; R\; 2\; \{\backslash \; displaystyle\; w\; =\; xR\_\; \{2\}\; R\_\; \{2\}\; y123123zR\_\; \{2\}\}$. В следующих двух итерациях пары $12\; \{\backslash \; displaystyle\; 12\}$и $R\; 3\; 3\; \{\backslash \; displaystyle\; R\_\; \{3\}\; 3\}$заменяются символами $R\; 3\; \{\backslash \; displaystyle\; R\_\; \{3\}\}$и $R\; 4\; \{\backslash \; displaystyle\; R\_\; \{4\}\}$соответственно. Наконец, строка $w\; =\; x\; R\; 2\; R\; 2\; y\; R\; 4\; R\; 4\; z\; R\; 2\; \{\backslash \; displaystyle\; w\; =\; xR\_\; \{2\}\; R\_\; \{2\}\; yR\_\; \{4\}\; R\_\; \{4\}\; zR\_\; \{2\}\}$не содержит повторяющейся пары и поэтому используется как аксиома выходной грамматики.

Для достижения линейной временной сложности Re-Pair требует следующих структур данных

• Последовательность, представляющая входную строку. Позиция $i\; \{\backslash \; displaystyle\; i\}$последовательности содержит i-й символ входной строки плюс две ссылки на другие позиции в последовательности. Эти ссылки указывают на следующие / предыдущие позиции, например, $k\; \{\backslash \; displaystyle\; k\}$и $m\; \{\backslash \; displaystyle\; m\}$, так что та же подстрока начинается с $вес\; [я]\; \{\backslash \; displaystyle\; w\; [i]\}$, $w\; [k]\; \{\backslash \; displaystyle\; w\; [k]\}$и $w\; [m]\; \{\backslash \; displaystyle\; w\; [m\; ]\}$и все три вхождения фиксируются одной и той же ссылкой (т. Е. В грамматике есть переменная, генерирующая строку).
• Очередь с приоритетом . Каждый элемент очереди - это пара символов (терминалы или ранее определенные пары), которые встречаются последовательно в последовательности. Приоритет пары определяется количеством вхождений пары в оставшейся последовательности. Каждый раз, когда создается новая пара, очередь приоритетов обновляется.
• Хэш-таблица для отслеживания уже определенных пар. Эта таблица обновляется каждый раз, когда создается или удаляется новая пара.

Поскольку хеш-таблица и приоритетная очередь относятся к одним и тем же элементам (парам), они могут быть реализованы с помощью общей структуры данных, называемой 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 в двоичном формате с использованием битовых битов} void encodeCFG_rec (symbol s) {if (s нетерминальный, и это первый раз, когда появляется символ s) {take rule s → X Y; encodeCFG_rec (X); encodeCFG_rec (Y); присвоить символу значение ++ num_rules_encoded; записать бит 1; } else {записываем бит 0; writeSymbol (терминал / присвоенное значение)}} void encodeCFG (symbol s) {encodeCFG_rec (s); записать бит 1; }

Другая возможность - разделить правила грамматики на поколения так, чтобы правило $X\; \to \; YZ\; \{\backslash \; displaystyle\; X\; \backslash \; to\; YZ\}$принадлежало поколению $i\; \{\backslash \; displaystyle\; i\}$, если хотя бы один из $Y\; \{\backslash \; displaystyle\; Y\}$или $Z\; \{\backslash \; displaystyle\; Z\}$принадлежит к поколению $я\; -\; 1\; \{\backslash \; displaystyle\; i\; \{-\}\; 1\}$, а другой принадлежит поколению $j\; \{\backslash \; displaystyle\; j\}$с $j\; \le \; i\; -\; 1\; \{\backslash \; стиль\; отображения\; j\; \backslash \; leq\; i\; \{-\}\; 1\}$. Затем эти поколения кодируются последовательно, начиная с поколения $0\; \{\backslash \; displaystyle\; 0\}$. Этот метод был предложен изначально, когда впервые было введено Re-Pair . Однако в большинстве реализаций Re-Pair используется неявный метод кодирования из-за его простоты и хорошей производительности. Кроме того, он позволяет производить декомпрессию на лету.

Существует ряд различных реализаций Re-Pair . Каждая из этих версий направлена ​​на улучшение одного конкретного аспекта алгоритма, такого как сокращение времени выполнения, уменьшение занимаемого места или увеличение степени сжатия.

Улучшение	Год	Реализация	Описание
Просмотр фраз	2003	[1]	Вместо того, чтобы манипулировать строка ввода как последовательность символов, этот инструмент сначала группирует символы в фразы (например, слова). Алгоритм сжатия работает как Re-Pair, но рассматривает идентифицированные фразы как терминалы грамматики. Инструмент принимает разные варианты, чтобы решить, какие фразы следует учитывать, и кодирует полученную грамматику в отдельные файлы: один содержит аксиому, а другой - остальные правила.
Оригинал	2011	[2]	Это одна из самых популярных реализаций Re-Pair. Он использует описанные здесь структуры данных (те, что были предложены при первоначальной публикации) и кодирует полученную грамматику с использованием метода неявного кодирования. Большинство более поздних версий Re-Pair реализованы, начиная с этой.
Encoding	2013	[3]	Вместо метода неявного кодирования в этой реализации используется метод переменной длины в метод фиксированной длины, в котором каждое правило (представлено со строкой переменной длины) кодируется с использованием кода фиксированной длины.
Использование памяти	2017	[4]	Алгоритм выполняется в два этапа. На первом этапе он рассматривает высокочастотные пары, то есть те, которые встречаются более $\lceil \; n\; /\; 3\; \rceil \; \{\backslash \; displaystyle\; \backslash \; lceil\; \{\backslash \; sqrt\; \{n\}\}\; /\; 3\; \backslash \; rceil\}$раз, а во втором - пары низких частот. Основное различие между двумя фазами - это реализация соответствующих очередей приоритетов.
Сжатие	2017	[5]	Эта версия изменяет способ выбора следующей пары для замены. Вместо того, чтобы просто рассматривать наиболее часто встречающуюся пару, он использует эвристику, которая штрафует пары, которые не соответствуют факторизации Лемпеля-Зива входной строки.
Compression	2018	[6]	Этот алгоритм уменьшает размер грамматики, сгенерированной Re-Pair, сначала заменяя максимальное количество повторов. Когда пара определяется как наиболее часто встречающаяся пара, то есть та, которая должна быть заменена на текущем шаге алгоритма, MR-repair расширяет пару, чтобы найти самую длинную строку, которая встречается такое же количество раз, как и пара, которую нужно заменить. Предоставленная реализация кодирует грамматику, просто перечисляя правила в тексте, поэтому этот инструмент предназначен исключительно для исследовательских целей и не может использоваться для сжатия как таковой.