르페어

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 기사의 리드 섹션은 기사의 길이에 비해 너무 길 수도 있다. 기사의 본문으로 일부 자료를 옮겨서 도움을 주십시요. 레이아웃 가이드 및 리드 섹션 지침을 읽고 섹션에 모든 필수 세부 정보가 포함되도록 하십시오. 기사의 토크 페이지에서 이 문제를 논의하십시오.(1919년 9월) 이 기사의 외부 링크 사용은 위키피디아의 정책이나 지침을 따르지 않을 수 있다. 너무 많거나 부적절한 외부 링크를 제거하고 적절한 경우 유용한 링크를 각주 참조로 변환하여 이 문서를 개선하십시오.(2019년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

Re-Pair(재귀적 페어링의 줄임말)는 문법 기반의 압축 알고리즘으로, 입력 텍스트가 주어지면 직선 프로그램, 즉 단일 문자열을 생성하는 문맥 없는 문법: 입력 텍스트가 생성된다.문법은 본문에서 발생하는 가장 빈번한 한 쌍의 문자를 재귀적으로 대체함으로써 만들어진다.일단 한 쌍의 문자가 두 번 발생하지 않으면, 그 결과 문자열이 문법의 공리로 사용된다.따라서 출력 문법은 공리를 제외한 모든 규칙에는 오른쪽에는 두 개의 기호가 있을 정도로 되어 있다.

작동 방식

Re-Pair를 사용하여 w="xabcabcy123zabc" 문자열을 생성하는 직선 프로그램의 구축

Re-Pair는 NJ. Larsson과 A에 의해 처음 소개되었다.1999년 모팻^[1].

그들의 논문에는 알고리즘이 선형적인 시간과 공간 복잡성으로 구현하는 데 필요한 데이터 구조에 대한 상세한 설명과 함께 제시되어 있다.실험 결과, Re-Pair는 높은 압축률을 달성하고 감압에 좋은 성능을 제공하는 것으로 나타났다.그러나 알고리즘의 주요 단점은 입력 크기의 약 5배에 달하는 메모리 소비량이다.이러한 메모리 사용은 압축을 선형 시간 내에 수행하기 위해 필요하지만 알고리즘을 큰 파일을 압축하는 데 비현실적으로 만든다.

오른쪽 이미지는 알고리즘이 어떻게 $작동$하는지 문자열${\displaystyle w}$ = ${\displaystyle x}$ ${\displaystyle a}$ c ${\displaystyle a}$ b ${\displaystyle c}$ y ${\displaystyle 123123}$ ${\displaystyle z}$ a ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle w=xabcy123zc}$을(를) 압축하는 방법을 보여준다$.$

During the first iteration, the pair ${\displaystyle ab}$, which occurs three times in ${\displaystyle w}$, is replaced by a new symbol ${\displaystyle R_{1}}$. On the second iteration, the most frequent pair in the string ${\displaystyle w=xR_{1}cR_{1}cy123123zR_{1$$}c}$, which is ${\displaystyle R_{1}c}$, is replaced by a new symbol ${\displaystyle R_{2}}$. Thus, at the end of the second iteration, the remaining string is ${\displaystyle w=xR_{2}R_{2}y123123zR_{2}}$. In the next two iterations, the pairs ${\displaystyle 12}$$$ 및 $R{\displaystyle {}_{}}$ ${\displaystyle {}_{}\mathrm{}}$ ${\displaystyle R_{3}3}$은(는) 각각$$ 기호 ${\displaystyle {R\mathrm{}}_{}}$ 3 ${\$과(와) $R{\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\$로 대체된다$$.마지막으로 $w{\displaystyle }$= ${\displaystyle x}$ ${\displaystyle {}_{}}$ 2 ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ R 4 ${\displaystyle {R\mathrm{}}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {R\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\$2}}개 문자열은 반복된 쌍을 포함하지$$ 않으므로 출력 문법의 공리로 사용된다.

데이터 구조

선형 시간 복잡성을 달성하기 위해 Re-Pair는 다음과 같은 데이터 구조를 필요로 한다.

• 입력 문자열을 나타내는 시퀀스.시퀀스의 위치$$ $i{\displaystyle }$ ${\displaystyle i}$에는 입력 문자열의 i번째 기호와 시퀀스의 다른 위치에 대한 두 개의 참조가 포함되어 있다.이러한 참조는 $다음{\displaystyle /}$이전$$$(예$: k {\$displaystyle$ $k}$ 및 m {\$displaystyle$ $w$$[i$ $w{\displaystyle }$[ ${\displaystyle k}$ ], $w{\displaystyle }$ [ k ${\displaystyle ]}$ ${\$$displaystyle w[k]]$ 및$$ w${\displaystyle }$[ ${\displaystyle m}$에서 동일한 하위 문자열이 시작되고$$ 세 가지 발생 모두 동일한 참조에 의해 캡처된다$($예: i$).$s 문자열을 생성하는 문법의 변수).
• 우선 순위 대기열.큐의 각 요소는 순서대로 연속적으로 발생하는 기호 쌍(단말 또는 이전에 정의된 쌍)이다.쌍의 우선 순위는 나머지 순서에서 쌍의 발생 횟수로 주어진다.새 쌍이 생성될 때마다 우선 순위 대기열이 업데이트된다.
• 이미 정의된 쌍을 추적하기 위한 해시 테이블.이 테이블은 새 쌍이 생성되거나 제거될 때마다 업데이트된다.

해시 테이블과 우선 순위 대기열은 동일한 요소(페어)를 가리키기 때문에, 해시 테이블(h_next)과 우선 순위 대기열(p_next, p_p_prev)에 대한 포인터가 있는 PALE이라는 공통 데이터 구조로 구현할 수 있다.또한 각 PARE는 시퀀스에서 PARE로 대표되는 문자열의 첫 번째(f_pos)와 마지막(b_pos) 발생을 가리킨다.다음 그림은 이 데이터 구조의 개요를 보여준다.

다음 두 그림은 이러한 데이터 구조가 초기화 후와 페어링 프로세스의 한 단계(NULL에 대한 포인터는 표시되지 않음)를 적용한 후 어떻게 보이는지 예를 보여준다.

문법 인코딩

일단 주어진 입력 문자열을 위해 문법이 만들어지면, 효과적인 압축을 이루기 위해서, 이 문법은 효율적으로 암호화되어야 한다.문법을 인코딩하는 가장 간단한 방법 중 하나는 암묵적인 인코딩인데, 이 인코딩은 호출 함수에 의해 구성되어 있다.encodeCFG(X)아래에 설명된 대로 모든 공리의 기호에 순차적으로 표시하십시오.직관적으로 규칙은 문법의 깊이 첫 번째 통과에서 방문될 때 암호화된다.규칙을 처음 방문할 때 규칙의 오른쪽은 재귀적으로 인코딩되고 새 코드가 규칙에 할당된다.그 시점부터 규칙에 도달할 때마다 할당된 값이 기록된다.

num_message_message = 256 // 기본적으로 확장 ASCII 문자 집합은 문법의 단자다.  writeSymbol(심볼 s) {   비트의 = 통나무를 하다(num_message_message); // 초기 8: 확장 ASCII 문자를 설명   글씨를 쓰다 s 에 이진의 사용. 비트의 조각들 }  공허하게 하다 encodeCFG_rec(심볼 s) {   만일 (s 이다 논외의-종말의 그리고 이 이다 그 맨 처음의 시간 심볼 s 등장하다) {    받아들이다 통치를 하다 s → X Y;     글씨를 쓰다 물다 1;     encodeCFG_rec(X);     encodeCFG_rec(Y);     할당하다 로 심볼 s 가치를 매기다 ++num_message_message;   } 다른 {     글씨를 쓰다 물다 0;     writeSymbol(종말의/가치를 매기다 맡겨진)   } }  공허하게 하다 인코드CFG(심볼 s) {   encodeCFG_rec(s);   글씨를 쓰다 물다 1; } 

$또$ 다른 가능성은 규칙 $X{\displaystyle }$→ ${\displaystyle Y}$ Z ${\displaystyle$ X$\to YZ$$}$이(가) 적어도 Y ${\displaystyle Y}$ 또는$$ $Z{\displaystyle }$ ${\displaystyle Z}$이(가) $i{\displaystyle }$- ${\displaystyle 1\mathrm{}}$ ${\displaystystyle i-}$에 속하고$$ 다른 하나는 ge에 속하도록 문법 규칙을 세대로 구분하는 것이다.neration $j{\displaystyle }$ ${\displaystyle j}$과${\displaystyle (}와{\displaystyle }$) j${\displaystyle 1\mathrm{}}$ i$-$ 1 {\$displaystyle$j$\leq$ i${-1}.$ 그런 다음 이 세대는 $이후{\displaystyle \mathrm{}}$ 0$${\$displaystyle 0}$세대로 인코딩된다$.$이것은 원래 르페어가 처음 도입되었을 때 제안된 방식이었다.그러나 대부분의 Re-Pair 구현에서는 단순성과 우수한 성능 때문에 암시적 인코딩 방식을 사용한다.게다가, 그것은 즉각적인 감압을 허용한다.

버전

Re-Pair의 구현에는 여러 가지가 있다.이러한 각 버전은 런타임 감소, 공간 소비 감소 또는 압축 비율 증가와 같은 알고리즘의 특정 측면을 개선하는 것을 목표로 한다.

개선	연도	실행	설명
구[2] 검색	2003	[1]	입력 문자열을 일련의 문자로 조작하는 대신, 이 도구는 먼저 문자들을 구(예: 단어)로 분류한다.압축 알고리즘은 Re-Pair로 작동하지만 식별된 구문을 문법의 단자로 간주한다.도구는 어떤 종류의 구문을 고려할지 결정하기 위해 다양한 옵션을 수용하고 결과 문법을 공리를 포함하는 문법과 나머지 규칙과 함께 구분된 파일로 인코딩한다.
오리지	2011	[2]	이것은 Re-Pair의 가장 인기 있는 구현 중 하나이다.여기에 기술된 데이터 구조(처음 출판되었을[1] 때 제안된 것)를 사용하고 암묵적 인코딩 방식으로 결과 문법을 인코딩한다.대부분의 후기 버전의 Re-Pair는 이 버전부터 구현된다.
인코딩[3]	2013	[3]	이 구현에서는 암묵적 인코딩 방식 대신 각 규칙(변수 길이 문자열로 표시됨)을 고정 길이 코드로 인코딩하는 가변 길이 대 고정 길이 방법을 사용한다.
메모리 사용량[4]	2017	[4]	알고리즘은 두 단계로 수행된다.1단계에서는 고주파 쌍, 즉 ${\displaystyle frequencyn\sqrt{}}{\displaystyle }$/${\displaystyle }$3 ${\displaystyle \lceil {\sqrt{n}/3\rceil }$회 이상 발생하는$$ 쌍을 고려하며, 2단계에서는 저주파 쌍을 고려한다.두 단계 사이의 주요 차이점은 해당 우선순위 대기열의 구현이다.
압축[5]	2017	[5]	이 버전은 교체할 다음 쌍을 선택하는 방법을 수정한다.단순히 가장 빈번한 쌍을 고려하는 대신에, 그것은 입력 문자열의 Lempel-Ziv 인수화와 일관성이 없는 쌍을 처벌하는 경험적 접근법을 채택한다.
압축[6]	2018	[6]	이 알고리즘은 최대 반복을 먼저 대체해 Re-Pair에서 생성되는 문법 크기를 줄인다.쌍이 알고리즘의 현재 단계에서 가장 빈번한 쌍으로 식별되면, MR-repair는 쌍을 확장하여 교체할 쌍과 동일한 횟수로 발생하는 가장 긴 문자열을 찾는다.제공된 구현은 단순히 텍스트에 규칙을 나열함으로써 문법을 암호화하므로, 이 도구는 순수하게 연구 목적을 위한 것이며, 압축에는 그대로 사용할 수 없다.

참고 항목

• 바이트 쌍 인코딩
• 세키투르 알고리즘

참조