Ремонт

Re-Pair (сокращение от рекурсивного спаривания ) — это алгоритм сжатия на основе грамматики , который по входному тексту создает прямую программу , то есть контекстно-свободную грамматику, генерирующую одну строку: входной текст. Чтобы выполнить сжатие за линейное время, он потребляет объем памяти, примерно в пять раз превышающий размер входного файла.

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

Как это работает [ править ]

Технология Re-Pair была впервые представлена в штате Нью-Джерси. Ларссон и А. Моффат ^[1] в 1999 году.

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

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

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

Структуры данных [ править ]

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

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

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

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

Кодирование грамматики [ править ]

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

num_rules_encoded = 256 // By default, the extended ASCII charset are the terminals of the grammar.

writeSymbol(symbol s) {
  bitslen = log(num_rules_encoded); // Initially 8, to describe any extended ASCII character
  write s in binary using bitslen bits
}

void encodeCFG_rec(symbol s) {
  if (s is non-terminal and this is the first time symbol s appears) {
  	take rule s → X Y;
    write bit 1;
    encodeCFG_rec(X);
    encodeCFG_rec(Y);
    assign to symbol s value ++num_rules_encoded;
  } else {
    write bit 0;
    writeSymbol(terminal/value assigned)
  }
}

void encodeCFG(symbol s) {
  encodeCFG_rec(s);
  write bit 1;
}

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

Версии [ править ]

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

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

См. также [ править ]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Ларссон, Нью-Джерси, и Моффат, А. (2000). Автономное сжатие на основе словаря. Труды IEEE, 88 (11), 1722–1732.
^ Р. Ван. «Просмотр и поиск сжатых документов». Докторская диссертация, Мельбурнский университет, Австралия, декабрь 2003 г.
^ Сатоши Ёсида и Такуя Кида, Эффективное кодирование от переменной длины к фиксированной длине с помощью алгоритма повторной пары, В Proc. конференции по сжатию данных 2013 г. (DCC 2013), с. 532, Сноуберд, Юта, США, март 2013 г.
^ Билле, П., Горц, Иллинойс, и Прецца, Н. (апрель 2017 г.). Компактное повторное сжатие пар. В 2017 г. (ДКК) (с. 171-180). IEEE.
^ Ганьчорж М. и Еж А. (апрель 2017 г.). Улучшения в компрессоре грамматики Re-Pair. На конференции по сжатию данных (DCC) 2017 г. (стр. 181–190). IEEE.
^ Фуруя И., Такаги Т., Накашима Ю., Иненага С., Баннаи Х. и Кида Т. (2018). MR-RePair: сжатие грамматики на основе максимального количества повторов. Препринт arXiv arXiv:1811.04596.

[Offline-1] Jump up to: Перейти обратно: ^а ^б Ларссон, Нью-Джерси, и Моффат, А. (2000). Автономное сжатие на основе словаря. Труды IEEE, 88 (11), 1722–1732.

[2] Р. Ван. «Просмотр и поиск сжатых документов». Докторская диссертация, Мельбурнский университет, Австралия, декабрь 2003 г.

[3] Сатоши Ёсида и Такуя Кида, Эффективное кодирование от переменной длины к фиксированной длине с помощью алгоритма повторной пары, В Proc. конференции по сжатию данных 2013 г. (DCC 2013), с. 532, Сноуберд, Юта, США, март 2013 г.

[4] Билле, П., Горц, Иллинойс, и Прецца, Н. (апрель 2017 г.). Компактное повторное сжатие пар. В 2017 г. (ДКК) (с. 171-180). IEEE.

[5] Ганьчорж М. и Еж А. (апрель 2017 г.). Улучшения в компрессоре грамматики Re-Pair. На конференции по сжатию данных (DCC) 2017 г. (стр. 181–190). IEEE.

[6] Фуруя И., Такаги Т., Накашима Ю., Иненага С., Баннаи Х. и Кида Т. (2018). MR-RePair: сжатие грамматики на основе максимального количества повторов. Препринт arXiv arXiv:1811.04596.

[1]

[2]

[3]

[4]

[5]

[6]