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 6 SEARCHING 393 the keys themselves. In practice we can find the associated data once we have located K; for example, if K appears in location TABLE + i, the associated data (or a pointer to it) might be in location TABLE + i + 1, or in DATA + i, 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 elimi- nate searching from the topological sorting algorithm discussed in Section 2. 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 min- imize 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.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 deci- sions.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 = {a1 , a2 ,. , bn }, determine whether or not A ⊆ B. Three solutions suggest themselves: 394 SEARCHING 6 1.
Compare each ai sequentially with the bj’s until finding a match. Sort the a’s and b’s, then make one sequential pass through both files, checking the appropriate condition. Enter the bj’s in a table, then search for each of the ai. Each of these solutions is attractive for a different range of values of m and n.
Solution 1 will take roughly c1 mn units of time, for some constant c1 , and solution 2 will take about c2 (m lg m + n lg n) units, for some (larger) constant c2. With a suitable hashing method, solution 3 will take roughly c3 m + c4 n 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.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. 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, o, u, w, y in other positions. Assign the following numbers to the remaining letters after the first: b, f, p, v → 1 l→4 c, g, j, k, q, s, x, z → 2 m, n → 5 d, t → 3 r→6 3.
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. 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). 6 SEARCHING 395 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.
Ford, JACM 8 (1961), 538– 552; Leon Davidson, CACM 5 (1962), 169–171; Federal Population Censuses 1790–1890 (Washington, D.] 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. 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 trans- ferred 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 cos x 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.