문법 기반 코드
Grammar-based code
문법 기반 코드 또는 문법 기반 압축은 압축되는 문자열의 Context-Free Grammar(CFG; 문맥 자유 문법)을 구축하는 아이디어에 기초한 압축 알고리즘입니다.예를 들어 범용 무손실 데이터 압축 [1]알고리즘이 있습니다.x데이터 시퀀스를 압축하기 위해 cmx1⋯)n{\displaystyle x=x_{1}\cdots x_{n}},grammar-based 코드는 문맥 자유 문법 G{G\displaystyle}에{\displaystyle)}x. 입력 시퀀스( 작은 문법 문제)을 위한 작은 문법을 찾아야 하는 문제가 되NP-hard,[2] 그렇게 많은 grammar-tran 알려져 있어 전환시키는 것이다.sf옴 알고리즘은 이론적이고 실용적인 관점에서 제안된다.일반적으로 생성된 G(\ G는 산술 부호화 등의 통계 인코더에 의해 더욱 압축된다.
예와 특징
문법에 근거한 코드의 클래스는 매우 넓다.여기에는 블록 코드, Multilevel Pattern Matching(MPM; 멀티레벨 패턴 매칭) 알고리즘,[3] 증분 해석 Lempel-Ziv 코드 [4]변형 및 기타 많은 새로운 범용 무손실 압축 알고리즘이 포함됩니다.문법 기반 코드는 유한한 알파벳으로 고정된 에르고드 소스의 엔트로피 속도를 점근적으로 달성할 수 있다는 점에서 보편적이다.
실용적인 알고리즘
다음 압축 프로그램은 외부 링크에서 사용할 수 있습니다.
- Sequitur는[5] 입력 텍스트를 순차적으로 CFG로 변환하고 생성된 CFG를 산술 코더에 의해 인코딩하는 고전적인 문법 압축 알고리즘입니다.
- Re-Pair는[6] 가장 빈번한 우선 치환 전략을 사용하는 탐욕 알고리즘입니다.압축 성능은 매우 강력하지만, 메인 메모리 공간이 매우 많이 필요합니다.
- GLZA,[7]는 환원할 수 있는 문법, 즉 건설,.(일반적으로,compression-optimal SLG고, 가장 작은 문법 문제가 실제 SLG compres에서 다르다 더 이상 줄일 수 없지 않다가 재방송"철자가"의entropy-coding 비용은 비용 개념 이상이고, 규칙을 entropy-coding 적다 재방송을 포함하고 있습니다.sion 문제).
「 」를 참조해 주세요.
레퍼런스
- ^ Kieffer, J. C.; Yang, E.-H. (2000), "Grammar-based codes: A new class of universal lossless source codes", IEEE Trans. Inf. Theory, 46 (3): 737–754, doi:10.1109/18.841160
- ^ Charikar, M.; Lehman, E.; Liu, D.; Panigrahy, R.; Prabharakan, M.; Sahai, A.; Shelat, A. (2005), "The Smallest Grammar Problem", IEEE Trans. Inf. Theory, 51 (7): 2554–2576, doi:10.1109/tit.2005.850116
- ^ Kieffer, J. C.; Yang, E.-H.; Nelson, G.; Cosman, P. (2000), "Universal lossless compression via multilevel pattern matching", IEEE Trans. Inf. Theory, 46 (4): 1227–1245, doi:10.1109/18.850665
- ^ Ziv, J.; Lempel, A. (1978), "Compression of individual sequences via variable rate coding", IEEE Trans. Inf. Theory, 24 (5): 530–536, doi:10.1109/TIT.1978.1055934, hdl:10338.dmlcz/142945
- ^ Nevill-Manning, C. G.; Witten, I. H. (1997), "Identifying Hierarchical Structure in Sequences: A linear-time algorithm", Journal of Artificial Intelligence Research, 7 (4): 67–82, arXiv:cs/9709102, doi:10.1613/jair.374, hdl:10289/1186
- ^ Larsson, N. J.; Moffat, A. (2000), "Offline Dictionary-Based Compression" (PDF), Proceedings of the IEEE, 88 (11): 1722–1732, doi:10.1109/5.892708
- ^ Conrad, Kennon J.; Wilson, Paul R. (2016), "Grammatical Ziv-Lempel Compression: Achieving PPM-Class Text Compression Ratios with LZ-Class Decompression Speed", IEEE Data Compression Conference: 586, doi:10.1109/DCC.2016.119, ISBN 978-1-5090-1853-6
외부 링크
- GLZA에 관한 토론과
- 예시와 함께 문법 기반 코드에 대한 설명
- 시퀀스 코드
- Re-Pair 코드
- Re-Pair는 Gonzalo Navarro의 버전을 코드합니다.
- GrammarViz 2.0 - Java에서의 Sequitur, Re-Pair 및 Parallel Re-Pair 구현.
