Book cover

Skip to content
  1. Introduction
  2. Objects and Classes
  3. Finding Duplicate Files
  4. Matching Patterns
  5. Parsing Text
  6. Running Tests
  7. An Interpreter
  8. Functions and Closures
  9. Protocols
  10. A File Archiver
  11. An HTML Validator
  12. A Template Expander
  13. A Code Linter
  14. Page Layout
  15. Performance Profiling
  16. Object Persistence
  17. Binary Data
  18. A Database
  19. A Build Manager
  20. A Package Manager
  21. Transferring Files
  22. Serving Web Pages
  23. A File Viewer
  24. Undo and Redo
  25. A Virtual Machine
  26. A Debugger
  27. Observers
  28. Generating Documentation
  29. Search
  30. File Compression
  31. A File Cache
  32. A Query Builder
  33. Concurrency
  34. Conclusion
  1. Bibliography
  2. Bonus Material
  3. Syllabus
  4. License
  5. Code of Conduct
  6. Contributing
  7. Glossary
  8. Colophon
  9. Index

download examples

GitHub repository

File Compression

  • FIXME

Terms defined: nybble

FIXME: create file compressor

Issue 144

  • First idea: number the tokens in the file and replace each with its number
    • Use blank-nonblank tokenization (which inadvertently captures punctuation)
    • compress.py
    • Test with text of introduction to this book: makes things worse
  • So store as binary
    • binary.py
    • Better, but still larger than the original
    • In fact, our binary compression is worse when tested every chapter
  • Look at statistics
    • frequency.py and frequency.svg
    • Lots of words only occur once (long tail)
    • Single space occurs over 1600 times
  • Use variable-length encoding Chapter 17
    • Use nybbles (half-bytes)
    • Most common seven values are 0000 through 0111
    • Next 49 are (1…, 0…)
    • 343 are (1…, 1…, 0…)
    • Calculate compression before implementing
    • varlen_calc.py tells us we can get the introduction from 13240 bytes to 10281 (approximately 1.3X)
    • But gzip can do 2.3X: how?
  • Lempel-Ziv-Storer-Szymanski