Before finishing, we would like to give some extra material that might be of interest.

First, we believe that it is extremely useful to know of freely available tools for on-line text searching, so we cover the existing software of this kind we are aware of.

Second, we give pointers to other books, journals, conferences, and online resources one may want to read to enter deeper into the area of text searching. This is also of interest to readers with a specific algorithmic problem not addressed in this book and not solved by the available software.

Finally, we include a section with problems related to combinatorial pattern matching. The section aims at briefing over the different extensions to the basic text searching problem, explaining the main concepts and existing results, and pointing to more comprehensive material covering them.

Up to date information and errata related to this book will be available at http://www.dcc.uchile.cl/~gnavarro/FPMbook.

Available software

We present in this section a sample of freely available software for on-line pattern matching.

7.1.1 Gnu Grep

What it is GNU (http://www.gnu.org) is an organization devoted to the development of free software. One of its products, Grep, permits fast searching of simple strings, multiple strings, and regular expressions in a set of files. Approximate searching is not supported. Gnu Grep is twice as fast as the classical Unix Grep.

Grep reports the lines in the file that contain matches. However, there are many configuration options that permit reporting the lines that do not match, the number of lines that match, whole files containing matches, and so on. The software provides a very powerful syntax that includes operators that go beyond regular expressions.

Basic concepts

The string matching problem is that of finding all the occurrences of a given pattern p = p1p2 … pm a large text T = t1t2 … tn, where both T and p are sequences of characters from a finite character set Σ. Given strings x, y, and z, we say that x is a prefix of xy, a suffix of yx, and a factor of yxz.

Many algorithms exist to solve this problem. The oldest and most famous are the Knuth-Morris-Pratt and the Boyer-Moore algorithms. These algorithms appeared in 1977. The first is worst-case linear in the size of the text. This O(n) complexity is a lower bound for the worst case of any string matching algorithm. The second is O(mn) in the worst case but is sublinear on average, that is, it may avoid reading some characters of the text. An O(nlog|Σ|m/m) lower bound on the average complexity has been proved in [Yao79].

Since 1977, many studies have been undertaken to find simpler algorithms, optimal average-case algorithms, algorithms that could also search extended patterns, constant space algorithms, and so on. There exists a large variety of research directions that have been tried, many of which lead to different string matching algorithms.

The aim of this chapter is not to present as many algorithms as possible, nor to give an exhaustive list of them. Instead, we will present the most efficient algorithms, which means the algorithms that for some pattern length and some alphabet size yield the best experimental results. Among those that have more or less the same efficiency, we will present the simplest.

The algorithms we present derive from three general search approaches, according to the way the text is searched. For all of them, a search window of the size of the pattern is slid from left to right along the text, and the pattern is searched for inside the window.

Basic concepts

Up to now we have considered search patterns that are sequences of characters. However, in many cases one may be interested in a more sophisticated form of searching. The most complex patterns that we consider in this book are regular expressions, which are covered in Chapter 5. However, regular expression searching is costly in processing time and complex to program, so one should resort to it only if necessary. In many cases one needs far less flexibility, and the search problem can be solved more efficiently with much simpler algorithms.

We have designed this chapter on “extended strings” as a middle point between simple strings and regular expressions. We provide simple search algorithms for a number of enhancements over the basic string search, which can be solved more easily than general regular expressions. We focus on those used in text searching and computational biology applications.

We consider four extensions to the string search problem: classes of characters, bounded length gaps, optional characters, and repeatable characters. The first one allows specifying sets of characters at any pattern or text position. The second permits searching patterns containing bounded length gaps, which is of interest for protein searching (e.g., PROSITE patterns [Gus97, HBFB99]). The third allows certain characters to appear optionally in a pattern occurrence, and the last permits a given character to appear multiple times in an occurrence, which includes wild cards. We finally consider some limited multipattern search capabilities.

Different occurrences of a pattern may have different lengths, and there may be several occurrences starting or ending at the same text position. Among the several choices for reporting these occurrences, we choose to report all the initial or all the final occurrence positions, depending on what is more natural for each algorithm.

In this chapter we make heavy use of bit-parallel algorithms. With some extra work, other algorithms can be adapted to handle some extended patterns as well, but bit-parallel algorithms provide the maximum flexibility and in general the best performance.

Why this book? Our aim and focus

String matching can be understood as the problem of finding a pattern with some property within a given sequence of symbols. The simplest case is that of finding a given string inside the sequence.

This is one of the oldest and most pervasive problems in computer science. Applications requiring some form of string matching can be found virtually everywhere. However, recent years have witnessed a dramatic increase in interest in string matching problems, especially within the rapidly growing communities of information retrieval and computational biology.

Not only are these communities facing a drastic increase in the text sizes they have to manage, but they are demanding more and more sophisticated searches. The patterns of interest are not just simple strings but also include wild cards, gaps, and regular expressions. The definition of a match may also permit slight differences between the pattern and its occurrence in the text. This is called “approximate matching” and is especially interesting in text retrieval and computational biology.

The problems arising in this field can be addressed from different view-points. In particular, string matching is well known for being amenable to approaches that range from the extremely theoretical to the extremely practical. The theoretical solutions have given rise to important algorithmic achievements, but they are rarely useful in practice: A well-known fact in the community is that simpler ideas work better in practice. Two typical examples are the famous Knuth-Morris-Pratt algorithm, which in practice is twice as slow as the brute force approach, and the well-known Boyer-Moore family, whose most successful members in practice are highly simplified variants of the original proposal.

It is hard, however, to find the simpler ideas in the literature. In most current books on text algorithms, the string matching part covers only the classic theoretical algorithms. There are three reasons for that.

Basic concepts

Approximate string matching, also called “string matching allowing errors,” is the problem of finding a pattern p in a text T when a limited number k of differences is permitted between the pattern and its occurrences in the text.

From the many existing models defining a “difference,” we focus on the most popular one, called Levenshtein distance or edit distance [Lev65]. Other more complex models exist, especially in computational biology, but the edit distance model has received the most attention and the most effective algorithms have been developed for it. Some of these algorithms can be extended to more complex models.

Under edit distance, one difference equals one edit operation: a character insertion, deletion, or substitution. That is, the edit distance between two strings x and y, ed(x, y), is the minimum number of edit operations required to convert x into y, or vice versa. For example, ed(annual, annealing) = 4. The approximate string matching problem becomes that of finding all occurrences in T of every p′ that satisfies ed(p,p′) ≤ k. To ensure a linear size output it is customary to report only the starting or ending positions of the occurrences.

Note that the problem only makes sense for 0 < k < m, because otherwise every text substring of length m can be converted into p by substituting the m characters. The case k = 0 corresponds to exact string matching. We call α = k/m the “error level.” It gives a measure of the “fraction” of the pattern that can be altered.

We concentrate on algorithms that are the fastest in the cases that are likely to be of use in some foreseeable application, particularly text retrieval and computational biology. In particular, α < 1/2 in most cases of interest.

We present four approaches. The first approach, which is also the oldest and most flexible, adapts a dynamic programming algorithm that computes edit distance.

In the preceding chapters we investigated in detail the scenario of a student perceptron learning from a teacher perceptron. This is a typical example of what is commonly referred to as supervised learning. But we all gratefully acknowledge that learning from examples does not always require the presence of a teacher!

However, what is it that can be learned besides some specific classification of examples provided by a teacher? The key observation is that learning from unclassified examples is possible if their distribution has some underlying structure. The main issue in unsupervised learning is then to extract these intrinsic features from a set of examples alone. This problem is central to many pattern recognition and data compression tasks with a variety of important applications [110].

Far from attempting to review the many existing approaches to unsupervised learning, we will show in the present chapter how statistical mechanics methods introduced before can be applied to some special scenarios of unsupervised learning closely related to the teacher–student perceptron problem. This will illustrate on the one hand how statistical mechanics can be used for the analysis of unsupervised situations, while on the other hand we will gain new understanding of the supervised problem by reformulating it as a special case of an unsupervised one.

For a fixed set of input examples, one can decompose the N-sphere into cells each consisting of all the perceptron coupling vectors J giving rise to the same classification of those examples. Several aspects of perceptron learning discussed in the preceding chapters are related to the geometric properties of this decomposition, which turns out to have random multifractal properties. Our outline of the mathematical techniques related to the multifractal method will of course be short and ad rem; see [172, 173] for a more detailed introduction. But this alternative description provides a deeper and unified view of the different learning properties of the perceptron. It highlights some of the more subtle aspects of the thermodynamic limit and its role in the statistical mechanics analysis of perceptron learning. In this way we finish our discussion of the perceptron with an encompassing multifractal description, preparing the way for the application of this approach to the analysis of multilayer networks.

The shattered coupling space

Consider a set of p = αN examples ξµ generated independently at random from the uniform distribution on the N-sphere. Each hyperplane perpendicular to one of these inputs cuts the coupling space of a spherical perceptron, which is the very same N-sphere, into two half-spheres according to the two possible classifications of the example.

In this book we have discussed how various aspects of learning in artificial neural networks may be quantified by using concepts and techniques developed in the statistical mechanics of disordered systems. These methods grew out of the desire to understand some strange low-temperature properties of disordered magnets; nevertheless their usefulness for and efficiency in the analysis of a completely different class of complex systems underlines the generality and strength of the principles of statistical mechanics.

In this final chapter we have collected some additional examples of non-physical complex systems for which an analysis using methods of statistical mechanics similar to those employed for the study of neural networks has given rise to new and interesting results. Compared with the previous chapters, the discussions in the present one will be somewhat more superficial – merely pointing to the qualitative analogies with the problems elucidated previously, rather than working out the consequences in full detail. Moreover, some of the problems we consider are strongly linked to information processing and artificial neural networks, whereas others are not. In all cases quenched random variables are used to represent complicated interactions which are not known in detail, and the typical behaviour in a properly defined thermodynamic limit is of particular interest.

Support vector machines

The main reason which prevents the perceptron from being a serious candidate for the solution of many real-world learning problems is that it can only implement linearly separable Boolean functions.

The Gibbs rule discussed in the previous chapter characterizes the typical generalization behaviour of the students forming the version space. It is hence well suited for a general theoretical analysis. For a concrete practical problem it is, however, hardly the best choice and there is a variety of other learning rules which are often more direct and may also show a better performance. The purpose of this chapter is to introduce a representative selection of these learning rules, to discuss some of their features, and to compare their properties with those of the Gibbs rule.

The Hebb rule

The oldest and maybe most important learning rule was introduced by D. Hebb in the late 1940s. It is, in fact, an application at the level of single neurons of the idea of Pavlov coincidence training. In his famous experiment, Pavlov showed how a dog, which was trained to receive its food when, at the same time, a light was being turned on, would also start to salivate when the light alone was lit. In some way, the coincidence of the two events, food and light, had established a connection in the brain of the dog such that, even when only one of the events occurred, the memory of the other would be stimulated. The basic idea behind the Hebb rule [32] is quite similar: strengthen the connection of neurons that fire together.

As a rule teachers are unreliable. From time to time they mix up questions or answer absentmindedly. How much can a student network learn about a target rule if some of the examples in the training set are corrupted by random noise? What is the optimal strategy for the student in this more complicated situation?

To analyse these questions in detail for the two-perceptron scenario is the aim of the present chapter. Let us emphasize that quite generally a certain robustness with respect to random influences is an indispensable requirement for any information processing system, both in biological and in technical contexts. If learning from examples were possible only for perfectly error-free training sets it would be of no practical interest. In fact, since the noise blurring the correct classifications of the teacher may usually be assumed to be independent of the examples, one expects that it will remain possible to infer the rule, probably at the expense of a larger training set.

A general feature of noisy generalization tasks is that the training set is no longer generated by a rule that can be implemented by the student. The problem is said to be unrealizable. A simple example is a training set containing the same input with different outputs, which is quite possible for noisy teachers. This means that for large enough training sets no student exists who is able to reproduce all classifications and the version space becomes empty.

So far we have been considering learning scenarios in which generalization shows up as a gradual process of improvement with the generalization error ε decreasing continuously from its initial pure guessing value ε = 0.5 to the asymptotic limit ε = 0. In the present chapter we study systems which display a quite different behaviour with sudden changes of the generalization ability taking place during the learning process. The reason for this new feature is the presence of discrete degrees of freedom among the parameters, which are adapted during the learning process. As we will see, discontinuous learning is a rather subtle consequence of this discreteness and methods of statistical mechanics are well suited to describe the situation. In particular the abrupt changes which occur in the generalization process can be described as first order phase transitions well studied in statistical physics.

Smooth networks

The learning scenarios discussed so far have been described in the framework of statistical mechanics as a continuous shift of the balance between energetic and entropic terms. In the case of perfect learning the energy describes how difficult it is for the student vector to stay in the version space (see (2.13)). For independent examples it is naturally given as a sum over the training set and scales for large α as e ∼ αε since the generalization error ε gives the probability of error and hence of an additional cost when a new example is presented.

In the present chapter we introduce the basic notions necessary to study learning problems within the framework of statistical mechanics. We also demonstrate the efficiency of learning from examples by the numerical analysis of a very simple situation. Generalizing from this example we will formulate the basic setup of a learning problem in statistical mechanics to be discussed in numerous modifications in later chapters.

Artificial neural networks

The statistical mechanics of learning has been developed primarily for networks of so-called formal neurons. The aim of these networks is to model some of the essential information processing abilities of biological neural networks on the basis of artificial systems with a similar architecture. Formal neurons, the microscopic building blocks of these artificial neural networks, were introduced more than 50 years ago by McCulloch and Pitts as extremely simplified models of the biological neuron [1]. They are bistable linear threshold elements which are either active or passive, to be denoted in the following by a binary variable S = ±1. The state Si of a given neuron i changes with time because of the signals it receives through its synaptic couplings Jij from either the “outside world” or other neurons j.

More precisely, neuron i sums up the incoming activity of all the other neurons weighted by the corresponding synaptic coupling strengths to yield the post-synaptic potential ∑jJij Sj and compares the result with a threshold θi specific to neuron i.