Text Processing

Text Processing

1. Pattern-Matching Algorithms

   • Brute Force
     • When applying this technique in a general situation, we typically enumerate all possible configurations of the inputs involved and pick the best of all these enumerated configurations.
   • Boyer-Moore
     • improve the running time of the brute-force algorithm by adding two potentially time-saving heuristics.
       • Looking-Glass Heuristic
       • Character-Jump Heuristic
       • when a mismatch is found near the right end of the pattern, we may end up realigning the pattern beyond the mismatch, without ever examining several characters of the text preceding the mismatch.
   • Knuth-Morris-Pratt
     • precompute self-overlaps between portions of the pattern so that when a mismatch occurs at one location, we immediately know the maximum amount to shift the pattern before continuing the search.

2. Tries

   • Trie: tree-based data structure for storing strings in order to support fast pattern matching.
     • Standard Tries
     • Compressed Tries
     • Suffix Tries

3. Text Compression

   • Huffman Coding
     • The algorithm proceeds in a series of rounds.
       • In each round, the algorithm takes the two binary trees with the smallest frequencies and merges them into a single binary tree.
         • It repeats this process until only one tree is left.

4. Greedy Method

   • Sequence of choices. Sequence starts from a condition, and computes the cost for that initial condition.
     • The pattern asks that we iteratively make additional choices by identifying the decision that achieves the best cost improvement from all of the choices that are currently possible.

5. Dynamic Programming

   • Matrix Chain-Product
   • DNA and text sequence alignment