Ремонт - Re-Pair

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья ведущий раздел может быть слишком длинным для статьи. Помогите, переместив какой-нибудь материал из него в основную часть статьи. Пожалуйста, прочтите руководство по макету и руководящие принципы ведущего раздела чтобы раздел по-прежнему содержал все важные детали. Пожалуйста, обсудите этот вопрос в статье страница обсуждения. (Сентябрь 2019) Эта статья использование внешняя ссылка может не следовать политикам или рекомендациям Википедии. Пожалуйста улучшить эту статью путем удаления излишний или же неприличный внешние ссылки и преобразование полезных ссылок, где это необходимо, в ссылки на сноски. (Сентябрь 2019) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Как это устроено

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

Ремонт был впервые представлен NJ. Ларссон и А. Моффат^[1] в 1999 году.

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

Изображение справа показывает, как работает алгоритм сжатия строки ${ displaystyle w = xabcabcy123123zabc}$.

На первой итерации пара ${ displaystyle ab}$, которое встречается трижды в ${ displaystyle w}$, заменяется новым символом ${ displaystyle R_ {1}}$.На второй итерации самая частая пара в строке ${ displaystyle w = xR_ {1} cR_ {1} cy123123zR_ {1} c}$, который ${ displaystyle R_ {1} c}$, заменяется новым символом ${ displaystyle R_ {2}}$Таким образом, в конце второй итерации оставшаяся строка будет ${ displaystyle w = xR_ {2} R_ {2} y123123zR_ {2}}$.В следующих двух итерациях пары ${ displaystyle 12}$ и ${ displaystyle R_ {3} 3}$ заменяются символами ${ displaystyle R_ {3}}$ и ${ displaystyle R_ {4}}$ соответственно. Наконец, строка ${ displaystyle w = xR_ {2} R_ {2} yR_ {4} R_ {4} zR_ {2}}$ не содержит повторяющейся пары и поэтому используется как аксиома выходной грамматики.

Структуры данных

Чтобы достичь линейной временной сложности, Ремонт требует следующих структур данных

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

Поскольку хеш-таблица и приоритетная очередь относятся к одним и тем же элементам (парам), они могут быть реализованы с помощью общей структуры данных, называемой PAIR, с указателями на хеш-таблицу (h_next) и приоритетную очередь (p_next и p_prev). Кроме того, каждая PAIR указывает на начало первого (f_pos) и последнего (b_pos) вхождений строки, представленной PAIR в последовательности. На следующем рисунке показан обзор этой структуры данных.

На следующих двух рисунках показан пример того, как эти структуры данных выглядят после инициализации и после применения одного шага процесса сопряжения (указатели на NULL не отображаются):

Кодирование грамматики

После того, как грамматика была построена для данной входной строки, чтобы добиться эффективного сжатия, эта грамматика должна быть эффективно закодирована. Одним из простейших методов кодирования грамматики является неявное кодирование, который заключается в вызове функции encodeCFG (X), описанные ниже, последовательно на всех символах аксиомы. Интуитивно правила кодируются по мере их посещения при обходе грамматики в глубину. При первом посещении правила его правая часть рекурсивно кодируется, и правилу присваивается новый код. С этого момента, когда правило достигается, записывается присвоенное значение.

num_rules_encoded = 256 // По умолчанию расширенная кодировка ASCII - это терминалы грамматики.writeSymbol(символ s) {  Bitslen = бревно(num_rules_encoded); // Изначально 8 для описания любого расширенного символа ASCII  записывать s в двоичный с помощью Bitslen биты}пустота encodeCFG_rec(символ s) {  если (s является не-Терминал и это является то первый время символ s появляется) {  	брать правило s → Икс Y;    encodeCFG_rec(Икс);    encodeCFG_rec(Y);    назначать к символ s ценить ++num_rules_encoded;    записывать кусочек 1;  } еще {    записывать кусочек 0;    writeSymbol(Терминал/ценить назначенный)  }}пустота encodeCFG(символ s) {  encodeCFG_rec(s);  записывать кусочек 1;}

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

Версии

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

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

Смотрите также

• Кодирование пар байтов
• Алгоритм Sequitur

Рекомендации