CSEP 590Data CompressionAutumn 2007SequiturCSEP 590 - Lecture 5 - Autumn 2007 2Sequitur• Nevill-Manning and Witten, 1996.• Uses a context-free grammar (without recursion) to represent a string.• The grammar is inferred from the string.• If there is structure and repetition in the string then the grammar may be very small compared to the original string.• Clever encoding of the grammar yields impressive compression ratios.• Compression plus structure!CSEP 590 - Lecture 5 - Autumn 2007 3Context-Free Grammars• Invented by Chomsky in 1959 to explain the grammar of natural languages.• Also invented by Backus in 1959 to generate and parse Fortran.• Example:– terminals: b, e– non-terminals: S, A– Production Rules: S → SA, S → A, A → bSe, A → be– S is the start symbolCSEP 590 - Lecture 5 - Autumn 2007 4Context-Free Grammar Example• S → SAS → AA → bSeA → beSAbSebSAebAAebbeAebbebeeExample: b and e matched as parentheses derivation of bbebeeSAb S eS AAb eb ehierarchicalparse treeCSEP 590 - Lecture 5 - Autumn 2007 5Arithmetic Expressions• S → S + T S → TT → T*F T → FF → a F →(S)derivation of a * (a + a) + aSS + TT FT * FF ( S )S + TTFFaaaaSS+TT+TT*F+TF*F+Ta*F+Ta*(S)+Fa*(S+F)+Ta*(T+F)+Ta*(F+F)+Ta*(a+F)+Ta*(a+a)+Ta*(a+a)+Fa*(a+a)+aparse treeCSEP 590 - Lecture 5 - Autumn 2007 6Overview of Grammar CompressionGrammar inferenceString xContext-free grammarGrammar encodingSymbol streamEntropy coderCompressedbit streamGrammar derivationContext-free grammarGrammar decodingSymbol streamEntropy decoderxEncoder DecoderCSEP 590 - Lecture 5 - Autumn 2007 7Sequitur Principles• Digram Uniqueness:– no pair of adjacent symbols (digram) appears more than once in the grammar.• Rule Utility:– Every production rule is used more than once.• These two principles are maintained as an invariant while inferring a grammar for the input string.CSEP 590 - Lecture 5 - Autumn 2007 8Sequitur Example (1)bbebeebebebbebeeS → bCSEP 590 - Lecture 5 - Autumn 2007 9Sequitur Example (2)bbebeebebebbebeeS → bbCSEP 590 - Lecture 5 - Autumn 2007 10Sequitur Example (3)bbebeebebebbebeeS → bbeCSEP 590 - Lecture 5 - Autumn 2007 11Sequitur Example (4)bbebeebebebbebeeS → bbebCSEP 590 - Lecture 5 - Autumn 2007 12Sequitur Example (5)bbebeebebebbebeeS → bbebe Enforce digram uniqueness.be occurs twice.Create new rule A → be.CSEP 590 - Lecture 5 - Autumn 2007 13Sequitur Example (6)bbebeebebebbebeeS → bAAA → beCSEP 590 - Lecture 5 - Autumn 2007 14Sequitur Example (7)bbebeebebebbebeeS → bAAeA → beCSEP 590 - Lecture 5 - Autumn 2007 15Sequitur Example (8)bbebeebebebbebeeS → bAAebA → beCSEP 590 - Lecture 5 - Autumn 2007 16Sequitur Example (9)bbebeebebebbebeeS → bAAebeA → beEnforce digram uniqueness.be occurs twice.Use existing rule A → be.CSEP 590 - Lecture 5 - Autumn 2007 17Sequitur Example (10)bbebeebebebbebeeS → bAAeAA → beCSEP 590 - Lecture 5 - Autumn 2007 18Sequitur Example (11)bbebeebebebbebeeS → bAAeAbA → beCSEP 590 - Lecture 5 - Autumn 2007 19Sequitur Example (12)bbebeebebebbebeeS → bAAeAbeA → beEnforce digram uniqueness.be occurs twice.Use existing rule A → be.CSEP 590 - Lecture 5 - Autumn 2007 20Sequitur Example (13)bbebeebebebbebeeS → bAAeAAA → beEnforce digram uniquenessAA occurs twice.Create new rule B → AA.CSEP 590 - Lecture 5 - Autumn 2007 21Sequitur Example (14)bbebeebebebbebeeS → bBeBA → beB → AACSEP 590 - Lecture 5 - Autumn 2007 22Sequitur Example (15)bbebeebebebbebeeS → bBeBbA → beB → AACSEP 590 - Lecture 5 - Autumn 2007 23Sequitur Example (16)bbebeebebebbebeeS → bBeBbbA → beB → AACSEP 590 - Lecture 5 - Autumn 2007 24Sequitur Example (17)bbebeebebebbebeeS → bBeBbbeA → beB → AAEnforce digram uniqueness.be occurs twice.Use existing rule A → be.CSEP 590 - Lecture 5 - Autumn 2007 25Sequitur Example (18)bbebeebebebbebeeS → bBeBbAA → beB → AACSEP 590 - Lecture 5 - Autumn 2007 26Sequitur Example (19)bbebeebebebbebeeS -> bBeBbAbA -> beB -> AACSEP 590 - Lecture 5 - Autumn 2007 27Sequitur Example (20)bbebeebebebbebeeS → bBeBbAbeA → beB → AAEnforce digram uniqueness.be occurs twice.Use existing rule A → be.CSEP 590 - Lecture 5 - Autumn 2007 28Sequitur Example (21)bbebeebebebbebeeS → bBeBbAAA → beB → AAEnforce digram uniqueness.AA occurs twice.Use existing rule B → AA.CSEP 590 - Lecture 5 - Autumn 2007 29Sequitur Example (22)bbebeebebebbebeeS →bBeBbBA → beB → AAEnforce digram uniqueness.bB occurs twice.Create new rule C → bB.CSEP 590 - Lecture 5 - Autumn 2007 30Sequitur Example (23)bbebeebebebbebeeS → CeBCA → beB → AAC → bBCSEP 590 - Lecture 5 - Autumn 2007 31Sequitur Example (24)bbebeebebebbebeeS → CeBCeA → beB → AAC → bBEnforce digram uniqueness.Ce occurs twice.Create new rule D → Ce.CSEP 590 - Lecture 5 - Autumn 2007 32Sequitur Example (25)bbebeebebebbebeeS → DBDA → beB → AAC → bBD → CeEnforce rule utility.C occurs only once.Remove C → bB.CSEP 590 - Lecture 5 - Autumn 2007 33Sequitur Example (26)bbebeebebebbebeeS → DBDA → beB → AAD → bBeCSEP 590 - Lecture 5 - Autumn 2007 34The HierarchybbebeebebebbebeeS → DBDA → beB → AAD → bBeSD B DA Ab B eb eb B eA A A Ab eb eb e b eb eIs there compression? In this small example, probably not.CSEP 590 - Lecture 5 - Autumn 2007 35Sequitur AlgorithmInput the first symbol s to create the production S → s;repeatmatch an existing rule: create a new rule:remove a rule:input a new symbol:until no symbols leftA → ….XY…B → XYA → ….B….B → XYA → ….XY….B →....XY....A → ….C....B →....C....C → XY A → ….B….B → X1X2…XkA → …. X1X2…Xk….S → X1X2…XkS → X1X2…XksCSEP 590 - Lecture 5 - Autumn 2007 36ExerciseUse Sequitur to construct a grammar for aaaaaaaaaa = a10CSEP 590 - Lecture 5 - Autumn 2007 37Complexity• The number of non-input sequitur operations applied < 2n where n is the input length.• Since each operation takes constant time, sequitur is a linear time algorithmCSEP 590 - Lecture 5 - Autumn 2007 38Amortized Complexity Argument– Let m = # of non-input sequitur operations. Let n = input length. Show m ≤ 2n.– Let s = the sum of the right hand sides of all the production rules. Let r = the number of rules.– We evaluate 2s - r.– Initially 2s - r = 1 because s = 1 and r = 1.– 2s - r > 0 at all times because
View Full Document
Unlocking...