Data Structures and Algorithms in Java, 6th Edition

Chapter 13

Text Processing

Contents

13.1 Abundance of Digitized Text

13.1.1 Notations for Character Strings

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 Tries

13.3.1 Standard Tries

13.3.2 Compressed Tries

13.3.3 Suffix Tries

13.3.4 Search Engine Indexing

13.4 Text Compression and the Greedy Method

13.4.1 The Huffman Coding Algorithm

13.4.2 The Greedy Method

13.5 Dynamic Programming

13.5.1 Matrix Chain-Product

13.5.2 DNA and Text Sequence Alignment

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. Computers are used to edit, store, and display documents, and to transport files 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
• Compilations of status updates on social networking ...