book

Data Structures and Algorithms in Python

by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

March 2013

Intermediate to advanced

748 pages

21h 42m

English

Wiley

Read now

Unlock full access

Book FeaturesOnline ResourcesContents and OrganizationPrerequisitesRelation to Computer Science CurriculumAbout the AuthorsAdditional Books by These AuthorsAcknowledgments
1.1 Python Overview1.2 Objects in Python1.3 Expressions, Operators, and Precedence1.4 Control Flow1.5 Functions1.5.1 Information Passing1.6 Simple Input and Output1.7 Exception Handling1.8 Iterators and Generators1.9 Additional Python Conveniences1.10 Scopes and Namespaces1.11 Modules and the Import Statement1.12 Exercises
2.1 Goals, Principles, and Patterns2.2 Software Development2.3 Class Definitions2.4 Inheritance2.5 Namespaces and Object-Orientation2.6 Shallow and Deep Copying2.7 Exercises
3.1 Experimental Studies3.2 The Seven Functions Used in This Book3.3 Asymptotic Analysis3.4 Simple Justification Techniques3.5 Exercises
4.1 Illustrative Examples4.2 Analyzing Recursive Algorithms4.3 Recursion Run Amok4.4 Further Examples of Recursion4.5 Designing Recursive Algorithms4.6 Eliminating Tail Recursion4.7 Exercises

5.1 Python's Sequence Types5.2 Low-Level Arrays5.3 Dynamic Arrays and Amortization5.4 Efficiency of Python's Sequence Types5.5 Using Array-Based Sequences5.6 Multidimensional Data Sets5.7 Exercises
6.1 Stacks6.2 Queues6.3 Double-Ended Queues6.4 Exercises
7.1 Singly Linked Lists7.2 Circularly Linked Lists7.3 Doubly Linked Lists7.4 The Positional List ADT7.5 Sorting a Positional List7.6 Case Study: Maintaining Access Frequencies7.7 Link-Based vs. Array-Based Sequences7.8 Exercises
8.1 General Trees8.2 Binary Trees8.3 Implementing Trees8.4 Tree Traversal Algorithms8.5 Case Study: An Expression Tree8.6 Exercises
9.1 The Priority Queue Abstract Data Type9.2 Implementing a Priority Queue9.3 Heaps9.4 Sorting with a Priority Queue9.5 Adaptable Priority Queues9.6 Exercises
10.1 Maps and Dictionaries10.2 Hash Tables10.3 Sorted Maps10.4 Skip Lists10.5 Sets, Multisets, and Multimaps10.6 Exercises
11.1 Binary Search Trees11.2 Balanced Search Trees11.3 AVL Trees11.4 Splay Trees11.5 (2,4) Trees11.6 Red-Black Trees11.7 Exercises
12.1 Why Study Sorting Algorithms?12.2 Merge-Sort12.3 Quick-Sort12.4 Studying Sorting through an Algorithmic Lens12.5 Comparing Sorting Algorithms12.6 Python's Built-In Sorting Functions12.7 Selection12.8 Exercises
13.1 Abundance of Digitized Text13.2 Pattern-Matching Algorithms13.3 Dynamic Programming13.4 Text Compression and the Greedy Method13.5 Tries13.6 Exercises
14.1 Graphs14.2 Data Structures for Graphs14.3 Graph Traversals14.4 Transitive Closure14.5 Directed Acyclic Graphs14.6 Shortest Paths14.7 Minimum Spanning Trees14.8 Exercises
15.1 Memory Management15.2 Memory Hierarchies and Caching15.3 External Searching and B-Trees15.4 External-Memory Sorting15.5 Exercises

Content preview from Data Structures and Algorithms in Python

Chapter 13 Text Processing

images

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 ...