TAOCP 5.5 Exercise 5

Let $R_1, R_2, \dots, R_N$ be a table of records with corresponding keys $K_1, K_2, \dots, K_N$.

taocpmathematicsalgorithmsvolume-3research

Section 5.5: Summary, History, and Bibliography

Exercise 5. [46] [46] It is much more difficult to sort nonrandom data with numerous equal keys than to sort uniformly random data. Devise a sorting benchmark that (i) is interesting now and will probably be interesting 100 years from now; (ii) does not involve uniformly random keys; and (iii) does not use data sets that change with time.

| shall have accomplished my purpose if | have sorted and put in logical order the gist of the great volume of material which has been generated about sorting over the past few years., J. C. HOSKEN (1955)

CHAPTER SIX

SEARCHING

Let’s look at the record., AL SMITH (1928)

THIS CHAPTER might have been given the more pretentious title “Storage and Retrieval of Information”; on the other hand, it might simply have been called “Table Look-Up.” We are concerned with the process of collecting information in a computer’s memory, in such a way that the information can subsequently be recovered as quickly as possible. Sometimes we are confronted with more data than we can really use, and it may be wisest to forget and to destroy most of it; but at other times it is important to retain and organize the given facts in such a way that fast retrieval is possible.

Most of this chapter is devoted to the study of a very simple search problem: how to find the data that has been stored with a given identification. For example, in a numerical application we might want to find f(x), given x and a table of the values of f; in a nonnumerical application, we might want to find the English translation of a given Russian word.

In general, we shall suppose that a set of N records has been stored, and the problem is to locate the appropriate one. As in the case of sorting, we assume that each record includes a special field called its key; this terminology is especially appropriate, because many people spend a great deal of time every day searching for their keys. We generally require the N keys to be distinct, so that each key uniquely identifies its record. The collection of all records is called a table or file, where the word “table” is usually used to indicate a small file, and “file” is usually used to indicate a large table. A large file or a group of files is frequently called a database.

Algorithms for searching are presented with a so-called argument, K, and the problem is to find which record has K as its key. After the search is complete, two possibilities can arise: Either the search was successful, having located the unique record containing K; or it was unsuccessful, having determined that K is nowhere to be found. After an unsuccessful search it is sometime desirable to enter a new record, containing K, into the table; a method that does this is called a search-and-insertion algorithm. Some hardware devices known as associative memories solve the search problem automatically, in a way that might resemble the functioning of a human brain; but we shall study techniques for searching on a conventional general-purpose digital computer.

Although the goal of searching is to find the information stored in the record associated with K, the algorithms in this chapter generally ignore everything but

392

the keys themselves. In practice we can find the associated data once we have located K; for example, if K appears in location TABLE + 7, the associated data (or a pointer to it) might be in location TABLE + 7+ 1, or in DATA + 4, etc. It is therefore convenient to gloss over the details of what should be done after K has been successfully found.

Searching is the most time-consuming part of many programs, and the substitution of a good search method for a bad one often leads to a substantial increase in speed. In fact we can often arrange the data or the data structure so that searching is eliminated entirely, by ensuring that we always know just where to find the information we need. Linked memory is a common way to achieve this; for example, a doubly linked list makes it unnecessary to search for the predecessor or successor of a given item. Another way to avoid searching occurs if we are allowed to choose the keys freely, since we might as well let them be the numbers {1,2,...,N}; then the record containing K can simply be placed in location TABLE + K. Both of these techniques were used to eliminate searching from the topological sorting algorithm discussed in Section 2.2.3. However, searches would have been necessary if the objects in the topological sorting algorithm had been given symbolic names instead of numbers. Efficient algorithms for searching turn out to be quite important in practice.

Search methods can be classified in several ways. We might divide them into internal versus external searching, just as we divided the sorting algorithms of Chapter 5 into internal versus external sorting. Or we might divide search methods into static versus dynamic searching, where “static” means that the contents of the table are essentially unchanging (so that it is important to minimize the search time without regard for the time required to set up the table), and “dynamic” means that the table is subject to frequent insertions and perhaps also deletions. A third possible scheme is to classify search methods according to whether they are based on comparisons between keys or on digital properties of the keys, analogous to the distinction between sorting by comparison and sorting by distribution. Finally we might divide searching into those methods that use the actual keys and those that work with transformed keys.

The organization of this chapter is essentially a combination of the latter two modes of classification. Section 6.1 considers “brute force” sequential methods of search, then Section 6.2 discusses the improvements that can be made based on comparisons between keys, using alphabetic or numeric order to govern the decisions. Section 6.3 treats digital searching, and Section 6.4 discusses an important class of methods called hashing techniques, based on arithmetic transformations of the actual keys. Each of these sections treats both internal and external searching, in both the static and the dynamic case; and each section points out the relative advantages and disadvantages of the various algorithms.

Searching and sorting are often closely related to each other. For example, consider the following problem: Given two sets of numbers, A = {aj,d2,...,@m} and B = {b,,bo,...,b6,}, determine whether or not A C B. Three solutions suggest themselves:

  1. Compare each a; sequentially with the 6,’s until finding a match.

  2. Sort the a’s and 6’s, then make one sequential pass through both files, checking the appropriate condition.

  3. Enter the b,'s in a table, then search for each of the aj.

Each of these solutions is attractive for a different range of values of m and n. Solution 1 will take roughly cjmn units of time, for some constant c,, and solution 2 will take about co(mlgm-+nlgn) units, for some (larger) constant co. With a suitable hashing method, solution 3 will take roughly cgm + c4n units of time, for some (still larger) constants c3 and c4. It follows that solution 1 is good for very small m and n, but solution 2 soon becomes better as m and n grow larger. Eventually solution 3 becomes preferable, until n exceeds the internal memory size; then solution 2 is usually again superior until n gets much larger still. Thus we have a situation where sorting is sometimes a good substitute for searching, and searching is sometimes a good substitute for sorting.

More complicated search problems can often be reduced to the simpler case considered here. For example, suppose that the keys are words that might be slightly misspelled; we might want to find the correct record in spite of this error. If we make two copies of the file, one in which the keys are in normal lexicographic order and another in which they are ordered from right to left (as if the words were spelled backwards), a misspelled search argument will probably agree up to half or more of its length with an entry in one of these two files. The search methods of Sections 6.2 and 6.3 can therefore be adapted to find the key that was probably intended.

A related problem has received considerable attention in connection with airline reservation systems, and in other applications involving people’s names when there is a good chance that the name will be misspelled due to poor handwriting or voice transmission. The goal is to transform the argument into some code that tends to bring together all variants of the same name. The following contemporary form of the “Soundex” method, a technique that was originally developed by Margaret K. Odell and Robert C. Russell [see U.S. Patents 1261167 (1918), 1435663 (1922)], has often been used for encoding surnames:

  1. Retain the first letter of the name, and drop all occurrences of a, e, h, i, 0,

u, w, y in other positions.

  1. Assign the following numbers to the remaining letters after the first:

c, 8, j,k, q,8, x, 27 2 mn-5d

  1. If two or more letters with the same code were adjacent in the original name (before step 1), or adjacent except for intervening h’s and w’s, omit all but the first.

  2. Convert to the form “letter, digit, digit, digit” by adding trailing zeros (if there are less than three digits), or by dropping rightmost digits (if there are more than three).

For example, the names Euler, Gauss, Hilbert, Knuth, Lloyd, Lukasiewicz, and Wachs have the respective codes E460, G200, H416, K530, L300, L222, W200. Of course this system will bring together names that are somewhat different, as well as names that are similar; the same seven codes would be obtained for Ellery, Ghosh, Heilbronn, Kant, Liddy, Lissajous, and Waugh. And on the other hand a few related names like Rogers and Rodgers, or Sinclair and St. Clair, or Tchebysheff and Chebyshev, remain separate. But by and large the Soundex code greatly increases the chance of finding a name in one of its disguises. [For further information, see C. P. Bourne and D. F. Ford, JACM 8 (1961), 538- 552; Leon Davidson, CACM 5 (1962), 169-171; Federal Population Censuses 1790-1890 (Washington, D.C.: National Archives, 1971), 90.]

When using a scheme like Soundex, we need not give up the assumption that all keys are distinct; we can make lists of all records with equivalent codes, treating each list as a unit.

Large databases tend to make the retrieval process more complex, since people often want to consider many different fields of each record as potential keys, with the ability to locate items when only part of the key information is specified. For example, given a large file about stage performers, a producer might wish to find all unemployed actresses between 25 and 30 with dancing talent and a French accent; given a large file of baseball statistics, a sportswriter may wish to determine the total number of runs scored by the Chicago White Sox in 1964, during the seventh inning of night games, against left-handed pitchers. Given a large file of data about anything, people like to ask arbitrarily complicated questions. Indeed, we might consider an entire library as a database, and a searcher may want to find everything that has been published about information retrieval. An introduction to the techniques for such secondary key (multi-attribute) retrieval problems appears below in Section 6.5.

Before entering into a detailed study of searching, it may be helpful to put things in historical perspective. During the pre-computer era, many books of logarithm tables, trigonometry tables, etc., were compiled, so that mathematical calculations could be replaced by searching. Eventually these tables were transferred to punched cards, and used for scientific problems in connection with collators, sorters, and duplicating punch machines. But when stored-program computers were introduced, it soon became apparent that it was now cheaper to recompute log x or cosx each time, instead of looking up the answer in a table.

Although the problem of sorting received considerable attention already in the earliest days of computers, comparatively little was done about algorithms for searching. With small internal memories, and with nothing but sequential media like tapes for storing large files, searching was either trivially easy or almost impossible.

But the development of larger and larger random-access memories during the 1950s eventually led to the recognition that searching was an interesting problem in its own right. After years of complaining about the limited amounts of space in the early machines, programmers were suddenly confronted with larger amounts of memory than they knew how to use efficiently.

The first surveys of the searching problem were published by A. I. Dumey, Computers & Automation 5,12 (December 1956), 6-9; W. W. Peterson, IBM J. Research & Development 1 (1957), 130-146; A. D. Booth, Information and Control 1 (1958), 159-164; A. S. Douglas, Comp. J. 2 (1959), 1-9. More extensive treatments were given later by Kenneth E. Iverson, A Programming Language (New York: Wiley, 1962), 133-158, and by Werner Buchholz, IBM Systems J. 2 (1963), 86-111.

During the early 1960s, a number of interesting new search procedures based on tree structures were introduced, as we shall see; and research about searching is still actively continuing at the present time.

6.1. SEQUENTIAL SEARCHING

“BEGIN AT THE BEGINNING, and go on till you find the right key; then stop.” This sequential procedure is the obvious way to search, and it makes a useful starting point for our discussion of searching because many of the more intricate algorithms are based on it. We shall see that sequential searching involves some very interesting ideas, in spite of its simplicity.

The algorithm might be formulated more precisely as follows:

Algorithm S (Sequential search). Given a table of records R,, Ro,..., Ry,

whose respective keys are K,, Ko,..., Ky, this algorithm searches for a given argument K. We assume that N > 1.

Verified: yes
Solve time: 3m31s

Setup

Let $R_1, R_2, \dots, R_N$ be a table of records with corresponding keys $K_1, K_2, \dots, K_N$. Let $K$ be the search argument. The task of Algorithm S is to determine an index $j$ such that $K_j = K$, or to report that no such index exists.

The search proceeds by sequential inspection of the keys in increasing order of indices.

We formalize the intended output as follows. If there exists $j$ with $1 \le j \le N$ and $K_j = K$, the algorithm returns the least such $j$. If no such $j$ exists, the algorithm returns failure.

Solution

The algorithm performs a linear scan of the table.

At the start of the $i$th stage, the algorithm examines key $K_i$. If $K_i = K$, it halts and outputs $i$. Otherwise it proceeds to $i+1$. If the scan reaches $i = N+1$ without success, it halts and reports failure.

Correctness is established by maintaining the following invariant for each $i$ with $1 \le i \le N+1$:

At the moment just before inspecting $K_i$, no index $j < i$ satisfies $K_j = K$.

For $i = 1$, the invariant holds because no indices are less than $1$.

Assume the invariant holds at stage $i$. If $K_i = K$, the algorithm halts and returns $i$, which is consistent with the requirement that the returned index be the first occurrence. If $K_i \ne K$, then no index $j \le i$ satisfies $K_j = K$, so the invariant holds at stage $i+1$.

If the algorithm reaches stage $N+1$, the invariant implies that no index $j \le N$ satisfies $K_j = K$, so failure is correctly reported.

Termination follows because the index strictly increases at each unsuccessful comparison and is bounded above by $N+1$.

Verification

Each iteration performs exactly one comparison between $K_i$ and $K$. If a match occurs, termination occurs immediately, and no earlier index can match by the invariant established inductively over the scan.

If no match occurs, all indices $1,2,\dots,N$ are exhausted in increasing order. The absence of any equality $K_i = K$ for $1 \le i \le N$ guarantees that the failure output is consistent with the specification.

The algorithm therefore satisfies both partial correctness (correct output when it halts) and termination for all inputs with $N > 1$.

Notes

The sequential structure is optimal in the absence of additional ordering or auxiliary indexing on the keys. Any algorithm that makes no assumptions on key distribution and performs only equality tests must, in the worst case, inspect all $N$ keys before distinguishing the absence of $K$, so linear scanning cannot be improved in general under these constraints.