Patterns Separating Large Texts

Description of the problem

The other day, I was looking at a problem of pattern matching. Specifically, I was thinking about what parts of a pattern is most significant when trying to match it against a large set of strings. The solution I gave used entropy, much of the same way decision trees use entropy but instead of minimizing entropy I chose the maximization route.

In that problem I had one luxury: the strings (both the pattern string and the strings in the set) had a beginning and an end. In cases like genome sequences this is one luxury we don’t have. Plus there are the problems of mutations, insertions and deletions. An exact match is usually not the thing one wants. I guess the success of BLAST, or BITAP type algorithms and their variations, comes from the fact that these are fast approximate matching algorithms.1

So, today I will consider another matching problem: I were to find a specific pattern (preferably large) to match against a large set of large strings, which part of the pattern should I choose to match against the large set?

Given a large pattern and even larger string, or set of strings, to match which part, or parts, of the string should I choose to maximize my chances of a total match?

Let me make this clear: this is not an alternative to fast approximate search algorithms such as BLAST, but rather a complement by helping us to choose a specific part of the pattern to match against the large set of strings.

The delimiters

Assume we have an alphabet consisting of letters \(a_0,a_1,\ldots,a_n\) and a language which uses this alphabet to form its vocabulary and sentences. Assume that the language uses \(a_0\) as the delimiter to delineate the beginnings and the ends of each word. What is the expected value of the length of a word in this language? This is a nice small problem I need to understand before I embark on solving the other problem.

Each language (human or otherwise) has a specific distribution of characters (assuming the languages we compare use the same set of characters). Assume \(p_0,p_1,\ldots,p_n\) be the probabilities of seeing the characters \(a_0, a_1,\ldots,a_n\) respectively. Then the expected length is the result from an infinite series: \[ E(\ell) = \sum_{\ell=0}^\infty \ell (1-p_0)^\ell p_0 \] The sum can be obtained from the power series \[ x(1-x) \frac{d}{dx}\sum_{\ell=0}^\infty x^\ell = x(1-x)\frac{d}{dx}\frac{1}{1-x} = \frac{x}{1-x} \] by substituting \(1-p_0\) for \(x\). Thus \[ E(\ell) = \frac{1-p_0}{p_0} = \left(\frac{1}{p_0}-1\right) \]

Experiment with Mark Twain

First let me do a small experiment with a text from English.

Below, I will find the character distributions form the texts “Adventures of Tom Sawyer” and “Adventures of Huckleberry Finn” by Mark Twain. The first function processes the text file:

(defun character-distribution (file)
   (let ((hash (make-hash-table)))
      (with-open-file (in file :direction :input)
         (do ((line (read-line in nil) (read-line in nil)))
             ((null line) hash)
           (map nil 
                (lambda (x) (setf (gethash x hash) (1+ (gethash x hash 0))))
                (string-downcase line))))))

CHARACTER-DISTRIBUTION

And the function that calculates the probabilities:

(defun experiment (distribution myfilter)
   (let ((n 0)
         (probs nil))

      (maphash 
         (lambda (x y) (if (funcall myfilter x) (incf n y)))
         distribution)

      (maphash 
         (lambda (x y) (push (cons x (/ y n 1.0d0)) probs)) 
         distribution)

      (cons 
         n 
         (remove-if-not 
             (lambda (x) (funcall myfilter (car x)))
             (sort probs (lambda (x y) (> (cdr x) (cdr y))))))))

EXPERIMENT

I will need a filter function will drop all characters other than ‘a’ to 'z’ or space. Then we perform the test on the text I chose:

(defvar text-result 
          (experiment 
             (character-distribution "../data/twain-tom-sawyer.txt")
             (lambda (x) (or (char= x #\Space) (char<= #\a x #\z)))))

TEXT-RESULT

Character Probability

1. Here is a good place to look at for these. ↩︎

   :::