Data Structures and Algorithms in Python

Chapter 13

Text Processing

Contents

13.1 Abundance of Digitized Text

13.1.1 Notations for Strings and the Python str Class

13.2 Pattern-Matching Algorithms

13.2.1 Brute Force

13.2.2 The Boyer-Moore Algorithm

13.2.3 The Knuth-Morris-Pratt Algorithm

13.3 Dynamic Programming

13.3.1 Matrix Chain-Product

13.3.2 DNA and Text Sequence Alignment

13.4 Text Compression and the Greedy Method

13.4.1 The Huffman Coding Algorithm

13.4.2 The GreedyMethod

13.5 Tries

13.5.1 Standard Tries

13.5.2 Compressed Tries

13.5.3 Suffix Tries

13.5.4 Search Engine Indexing

13.6 Exercises

13.1 Abundance of Digitized Text

Despite the wealth of multimedia information, text processing remains one of the dominant functions of computers. Computer are used to edit, store, and display documents, and to transport documents over the Internet. Furthermore, digital systems are used to archive a wide range of textual information, and new data is being generated at a rapidly increasing pace. A large corpus can readily surpass a petabyte of data (which is equivalent to a thousand terabytes, or a million gigabytes). Common examples of digital collections that include textual information are:

• Snapshots of the World Wide Web, as Internet document formats HTML and XML are primarily text formats, with added tags for multimedia content
• All documents stored locally on a user's computer
• Email archives
• Customer reviews
• Compilations ...