직선 문법
Straight-line grammar직선 문법(때로는 SLG라고 줄여 부르기도 한다)은 정확히 하나의 문자열을 생성하는 형식 문법이다.[1]따라서 분기되지 않고(모든 비터미널에는 관련 생산 규칙이 하나만 있음), 루프(비터미널 A가 B의 파생에 나타나는 경우, B는 A의 파생에 나타나지 않는다)도 없다.[1]
유용성 영역
직선 그래머는 압축 구조에서 (사전 감압 없이) 직접 실행하는 알고리즘 개발에 널리 사용된다.[2]: 212
SLG는 Kolmogorov 복잡성, 무손실 데이터 압축, Structure discovery 및 Compressed data structure와 같은 분야에 관심이 많다.[clarification needed]
주어진 문자열을 생성하는 최소한의 크기의 문맥이 없는 문법(동등하게: SLG)을 찾는 문제를 가장 작은 문법문제라고 한다.[citation needed]
직선 문법(더 정확히 말하면: 직선 문맥 없는 문자열 문법)은 직선 문맥 없는 트리 문법으로 일반화할 수 있다.후자는 나무를 압축하는 데 편리하게 사용할 수 있다.[2]: 212
형식 정의
1. 모든 비단어 N에 대해 N을 왼쪽 측면으로 하는 생산 규칙이 하나 이상 있으며,
2. V에서 정의한 지시 그래프 G=<V,E>는 비종말의 집합이며 (A,B) ∈ E는 A에 대한 생산 규칙의 오른쪽에 B가 나타날 때마다 반복된다.
직선 문맥 없는 나무 그래머의 보다 일반적인 형식주의에 대한 수학적 정의는 로레이 외 연구진에서 찾을 수 있다.[2]: 215
촘스키 정상 형태의 SLG는 직선 프로그램과 동등하다.[citation needed]
SLG를 사용한 알고리즘 목록
- Sequitur 알고리즘은 주어진 문자열의 직선 문법을 구성한다.
- 렘펠-지브-웰치 알고리즘은 문법이 생성되는 시작 규칙만 저장할 필요가 있을 정도로 결정론적인 방식으로 문맥 없는 문법을 만든다.
- 바이트 쌍 인코딩
참고 항목
참조
- ^ a b Florian Benz and Timo Kötzing, "최소 문법 문제에 대한 효과적인 휴리스틱", Genetic and 진화 연산 컨퍼런스에 대한 제15차 연례 회의의 진행 - GECCO '13, 2013. ISBN978-1-4503-1963-8doi:10.1145/2463372.2463441, 페이지 488
- ^ a b c Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Parameter Reduction in Grammar-Compressed Trees". Proc. FOSSACS (PDF). LNCS. Vol. 5504. Springer. pp. 212–226.