COMPSCI 61B Lecture Notes - Lecture 38: Trie, Glossary Of Ancient Roman Religion, General Idea
1 Jun 2017
School
Department
Course
Professor
Document Summary
Done with all major project-relevant information for this class. In a lossless algorithm, we require that no information is lost. Text les often compressible by 70% or more. By default, english text is usually represented by sequences of characters, each. Easy way to compress: use fewer than 8 bits for each letter. Have to decide which bit sequences should go with which letters. More generally, we"d say which codewords go with which symbols. Alternate strategy: avoid ambiguity by making code pre x free. A pre x-free code is one in which no codeword is a pre x of any other. Some pre x-free codes are better for some texts than others. It"d be useful to have a procedure that calculates the best code for a given text. Count relative frequencies of all characters in a text. Split into left" and right halves" of roughly equal frequency. Left half gets a leading zero, right half gets a leading one.
