The art of computer programming (volume 3 sorting and searching second edition) part 2
➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạmNội dung chi tiết: The art of computer programming (volume 3 sorting and searching second edition) part 2
The art of computer programming (volume 3 sorting and searching second edition) part 2
CHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 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 The art of computer programming (volume 3 sorting and searching second edition) part 2 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 ami organize the givenThe art of computer programming (volume 3 sorting and searching second edition) part 2
fads ill 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 datCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 ues of /; in a nonnumerical application, we might want to find the English translation of a given Russian word.Tn general, we shall suppose that a set of jV 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 spe The art of computer programming (volume 3 sorting and searching second edition) part 2 cial field called its key: this terminology is especially appropriate, because many people spend a great deal of time every day searching for their keThe art of computer programming (volume 3 sorting and searching second edition) part 2
ys. We generally require the A’ keys to be distinct, so that each key uniquely identifies its record. The collection of all records is called a table CHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 up 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 A' as its key. After the search is complete, two possibilities can arise: Either the search was .successful, having located the unique record The art of computer programming (volume 3 sorting and searching second edition) part 2 containing K; or it was unsuccessful, having determined that K is nowhere to be found. After an unsuccessful search it is sometime desirable to enterThe art of computer programming (volume 3 sorting and searching second edition) part 2
a new record, containing K. into the table; a method that does this is called a scarch-and-iỉiserlioỉi algorit hm. Some hardware devices known as assoCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 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 A', the algorithms in this chapter generally ignore everything but6SEARCHING 393the keys themselves. Ill practice we can find the associated The art of computer programming (volume 3 sorting and searching second edition) part 2 data once we have located /<; for example, if K appears in location TABLE + i, the associated data (or a pointer to it) might be in location TABLE 4-The art of computer programming (volume 3 sorting and searching second edition) part 2
i + 1. or ill DATA 4- i, etc. It is therefore convenient to gloss over the details of what should be done after A has been successfully found.SearchiCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 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 The art of computer programming (volume 3 sorting and searching second edition) part 2 for the predecessor or successor of a given item. Another way to avoid searching occurs if we arc allowed to choose the keys freely, since we might asThe art of computer programming (volume 3 sorting and searching second edition) part 2
well let them be the numbers {1,2........ArJ: then the record containing A can simplybe placed in location TABLE + A'. Both of these techniques were CHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 cts in the topological sorting algorithm had been given symbolic names instead of numbers. Ellicicnt algorithms for searching turn our 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 art of computer programming (volume 3 sorting and searching second edition) part 2 the sorting algorithms of Chapter 5 into internal versus external sorting. Or we might divide search methods into static versus dynamic searching, wheThe art of computer programming (volume 3 sorting and searching second edition) part 2
re "static” means that the contents of the table are essentially unchanging (so that it is important to minimize rhe search rime without regard for rhCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 le scheme is to classify search methods according to whether they are based on comparisons between keys or on digital properties of rhe keys, analogous to the distinction between sorting by comparison and sorting by distribution. Finally we might divide searching into those methods that use the actu The art of computer programming (volume 3 sorting and searching second edition) part 2 al keys and those that work with transformed keys.The organization of this chapter is essentially a combination of rhe latter two modes of classificatThe art of computer programming (volume 3 sorting and searching second edition) part 2
ion. Section G. I considers "brute force** sequential methods of search, then Section G.2 discusses rhe improvements that can be made based on compariCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 rtant 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 The art of computer programming (volume 3 sorting and searching second edition) part 2 algorithms.Searching and sorting are often closely related to each other. For example, consider the following problem: Given two sets of numbers, A =The art of computer programming (volume 3 sorting and searching second edition) part 2
{«1, a-2,..., am} and 13 = {bi,l)2,... ,bn}• determine whether or not A c Ỉ3. Three solutions suggest themselves:394 SEARCHING61.Compare? each (li seqCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 ition.3.Enter the 6/s in a table, then search for each of the O.Ị.Each of these solutions is attractive for a different range of values of m and n. Solution 1 will take roughly Cimn units of time, for some constant Cl, and solution 2 will take about cof/n 1g m + u 1g II) units, for some (larger) con The art of computer programming (volume 3 sorting and searching second edition) part 2 stant C2. With a suitable hashing method, solution 3 will take roughly c.ịin + c,f/i units of lime, for some (still larger) constants c,i and C.J. ItThe art of computer programming (volume 3 sorting and searching second edition) part 2
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 prefeCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 ere 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 The art of computer programming (volume 3 sorting and searching second edition) part 2 to find the correct record in spite of this error. If we make two copies of the file, one in which the keys arc in normal lexicographic order and anotThe art of computer programming (volume 3 sorting and searching second edition) part 2
her in which they are ordered from right to left (as if rhe words were spelled backwards), a misspelled search argument will probably agree up to halfCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 at 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 The art of computer programming (volume 3 sorting and searching second edition) part 2 transform the argument into some code that tends to bring together all variants of the same name. The following contemporary form of the ‘’Soundex’’The art of computer programming (volume 3 sorting and searching second edition) part 2
method, a technique that was originally developed by Margaret K. Odell and Robert c. Russell [see U.S. Patents 1261167 (1918). 1135663 (1922)], has ofCHAPTER SIXSEARCHINGLet's look at the record.— AL SMITH (1928)This chapter might have been given the more pretentious title “Storage ami Retrieval of The art of computer programming (volume 3 sorting and searching second edition) part 2 ign the following numbers to the remaining letters after the first:b,f. p. v -> 11 -> 4c,g, j, k. q, s, X, z —> 2 in, 11 —> 5d,t —> 3r —> 63.If two or more letters with the same code wen' adjacent in the original name (before step 1), or adjacent except for intervening h's and w's, omit all but the The art of computer programming (volume 3 sorting and searching second edition) part 2 first.4.Convert to the form “letter, digit, digit, digit" by adding trailing zeros (if there are less than three digits), or by dropping rightmost digThe art of computer programming (volume 3 sorting and searching second edition) part 2
its (if there are more than three).6SEARCHING 395For example, the names Euler, Gauss, Hilbert, Knuth. Lloyd. Lukasiewicz, and Wachs have the respectivGọi ngay
Chat zalo
Facebook