Grammar-based code

<p>Grammar-based codes or Grammar-based compression are <a href="/facts/Data_compression/gMFuY4FT">compression</a> algorithms based on the idea of constructing a <a href="/facts/Context-free_grammar/yu1FFdK4">context-free grammar</a> (CFG) for the string to be compressed. Examples include universal <a href="/facts/Lossless_data_compression/LS702KsN">lossless data compression</a> algorithms. To compress a data sequence 
  
    
      
        x
        =
        
          x
          
            1
          
        
        ⋯
        
          x
          
            n
          
        
      
    
    {\displaystyle x=x_{1}\cdots x_{n}}
  
, a grammar-based code transforms 
  
    
      
        x
      
    
    {\displaystyle x}
  
 into a context-free grammar 
  
    
      
        G
      
    
    {\displaystyle G}
  
.
The problem of finding a smallest grammar for an input sequence (<a href="/facts/Smallest_grammar_problem/TXWnBykh">smallest grammar problem</a>) is known to be NP-hard, so many grammar-transform algorithms are proposed from theoretical and practical viewpoints.
Generally, the produced grammar 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is further compressed by statistical encoders like <a href="/facts/Arithmetic_coding/WU0H4oNu">arithmetic coding</a>.
</p>

Grammar-based code open-in-new

Grammar-based code