An introduction to information retrieval. Manning_ Raghavan (2009) (811397), страница 20
Текст из файла (страница 20)
Change letters to digits as follows:B, F, P, V to 1.C, G, J, K, Q, S, X, Z to 2.D,T to 3.L to 4.M, N to 5.R to 6.4. Repeatedly remove one out of each pair of consecutive identical digits.5. Remove all zeros from the resulting string. Pad the resulting string withtrailing zeros and return the first four positions, which will consist of aletter followed by three digits.For an example of a soundex map, Hermann maps to H655. Given a query(say herman), we compute its soundex code and then retrieve all vocabularyterms matching this soundex code from the soundex index, before runningthe resulting query on the standard inverted index.This algorithm rests on a few observations: (1) vowels are viewed as interchangeable, in transcribing names; (2) consonants with similar sounds (e.g.,D and T) are put in equivalence classes.
This leads to related names oftenhaving the same soundex codes. While these rules work for many cases,especially European languages, such rules tend to be writing system dependent. For example, Chinese names can be written in Wade-Giles or Pinyintranscription. While soundex works for some of the differences in the twotranscriptions, for instance mapping both Wade-Giles hs and Pinyin x to 2,it fails in other cases, for example Wade-Giles j and Pinyin r are mappeddifferently.?Exercise 3.14Find two differently spelled proper nouns whose soundex codes are the same.Exercise 3.15Find two phonetically similar proper nouns whose soundex codes are different.Online edition (c) 2009 Cambridge UP3.5 References and further reading3.565References and further readingKnuth (1997) is a comprehensive source for information on search trees, including B-trees and their use in searching through dictionaries.Garfield (1976) gives one of the first complete descriptions of the permutermindex.
Ferragina and Venturini (2007) give an approach to addressing thespace blowup in permuterm indexes.One of the earliest formal treatments of spelling correction was due toDamerau (1964). The notion of edit distance that we have used is due to Levenshtein (1965) and the algorithm in Figure 3.5 is due to Wagner and Fischer(1974). Peterson (1980) and Kukich (1992) developed variants of methodsbased on edit distances, culminating in a detailed empirical study of several methods by Zobel and Dart (1995), which shows that k-gram indexingis very effective for finding candidate mismatches, but should be combinedwith a more fine-grained technique such as edit distance to determine themost likely misspellings.
Gusfield (1997) is a standard reference on stringalgorithms such as edit distance.Probabilistic models (“noisy channel” models) for spelling correction werepioneered by Kernighan et al. (1990) and further developed by Brill andMoore (2000) and Toutanova and Moore (2002). In these models, the misspelled query is viewed as a probabilistic corruption of a correct query. Theyhave a similar mathematical basis to the language model methods presentedin Chapter 12, and also provide ways of incorporating phonetic similarity,closeness on the keyboard, and data from the actual spelling mistakes ofusers. Many would regard them as the state-of-the-art approach.
Cucerzanand Brill (2004) show how this work can be extended to learning spellingcorrection models based on query reformulations in search engine logs.The soundex algorithm is attributed to Margaret K. Odell and Robert C.Russelli (from U.S. patents granted in 1918 and 1922); the version describedhere draws on Bourne and Ford (1961). Zobel and Dart (1996) evaluate various phonetic matching algorithms, finding that a variant of the soundexalgorithm performs poorly for general spelling correction, but that other algorithms based on the phonetic similarity of term pronunciations performwell.Online edition (c) 2009 Cambridge UPOnline edition (c) 2009 Cambridge UPDRAFT! © April 1, 2009 Cambridge University Press. Feedback welcome.4INDEXINGINDEXER67Index constructionIn this chapter, we look at how to construct an inverted index.
We call thisprocess index construction or indexing; the process or machine that performs itthe indexer. The design of indexing algorithms is governed by hardware constraints. We therefore begin this chapter with a review of the basics of computer hardware that are relevant for indexing.
We then introduce blockedsort-based indexing (Section 4.2), an efficient single-machine algorithm designed for static collections that can be viewed as a more scalable version ofthe basic sort-based indexing algorithm we introduced in Chapter 1. Section 4.3 describes single-pass in-memory indexing, an algorithm that haseven better scaling properties because it does not hold the vocabulary inmemory. For very large collections like the web, indexing has to be distributed over computer clusters with hundreds or thousands of machines.We discuss this in Section 4.4. Collections with frequent changes require dynamic indexing introduced in Section 4.5 so that changes in the collection areimmediately reflected in the index.
Finally, we cover some complicating issues that can arise in indexing – such as security and indexes for rankedretrieval – in Section 4.6.Index construction interacts with several topics covered in other chapters.The indexer needs raw text, but documents are encoded in many ways (seeChapter 2). Indexers compress and decompress intermediate files and thefinal index (see Chapter 5).
In web search, documents are not on a localfile system, but have to be spidered or crawled (see Chapter 20). In enterprise search, most documents are encapsulated in varied content management systems, email applications, and databases.
We give some examplesin Section 4.7. Although most of these applications can be accessed via http,native Application Programming Interfaces (APIs) are usually more efficient.The reader should be aware that building the subsystem that feeds raw textto the indexing process can in itself be a challenging problem.Online edition (c) 2009 Cambridge UP684 Index construction◮ Table 4.1 Typical system parameters in 2007. The seek time is the time neededto position the disk head in a new position. The transfer time per byte is the rate oftransfer from disk to memory when the head is in the right position.Symbolsbp4.1Statisticaverage seek timetransfer time per byteprocessor’s clock ratelowlevel operation(e.g., compare & swap a word)size of main memorysize of disk spaceValue5 ms = 5 × 10−3 s0.02 µs = 2 × 10−8 s109 s−10.01 µs = 10−8 sseveral GB1 TB or moreHardware basicsWhen building an information retrieval (IR) system, many decisions are basedon the characteristics of the computer hardware on which the system runs.We therefore begin this chapter with a brief review of computer hardware.Performance characteristics typical of systems in 2007 are shown in Table 4.1.A list of hardware basics that we need in this book to motivate IR systemdesign follows.CACHINGSEEK TIME• Access to data in memory is much faster than access to data on disk.
Ittakes a few clock cycles (perhaps 5 × 10−9 seconds) to access a byte inmemory, but much longer to transfer it from disk (about 2 × 10−8 seconds). Consequently, we want to keep as much data as possible in memory, especially those data that we need to access frequently. We call thetechnique of keeping frequently used disk data in main memory caching.• When doing a disk read or write, it takes a while for the disk head tomove to the part of the disk where the data are located. This time is calledthe seek time and it averages 5 ms for typical disks.
No data are beingtransferred during the seek. To maximize data transfer rates, chunks ofdata that will be read together should therefore be stored contiguously ondisk. For example, using the numbers in Table 4.1 it may take as little as0.2 seconds to transfer 10 megabytes (MB) from disk to memory if it isstored as one chunk, but up to 0.2 + 100 × (5 × 10−3 ) = 0.7 seconds if itis stored in 100 noncontiguous chunks because we need to move the diskhead up to 100 times.• Operating systems generally read and write entire blocks. Thus, readinga single byte from disk can take as much time as reading the entire block.Online edition (c) 2009 Cambridge UP4.2 Blocked sort-based indexingBUFFER69Block sizes of 8, 16, 32, and 64 kilobytes (KB) are common.
We call the partof main memory where a block being read or written is stored a buffer.• Data transfers from disk to memory are handled by the system bus, not bythe processor. This means that the processor is available to process dataduring disk I/O. We can exploit this fact to speed up data transfers bystoring compressed data on disk. Assuming an efficient decompressionalgorithm, the total time of reading and then decompressing compresseddata is usually less than reading uncompressed data.• Servers used in IR systems typically have several gigabytes (GB) of mainmemory, sometimes tens of GB.
Available disk space is several orders ofmagnitude larger.4.2TERM IDR EUTERS -RCV1Blocked sort-based indexingThe basic steps in constructing a nonpositional index are depicted in Figure 1.4 (page 8). We first make a pass through the collection assembling allterm–docID pairs. We then sort the pairs with the term as the dominant keyand docID as the secondary key. Finally, we organize the docIDs for eachterm into a postings list and compute statistics like term and document frequency. For small collections, all this can be done in memory.
In this chapter,we describe methods for large collections that require the use of secondarystorage.To make index construction more efficient, we represent terms as termIDs(instead of strings as we did in Figure 1.4), where each termID is a uniqueserial number. We can build the mapping from terms to termIDs on the flywhile we are processing the collection; or, in a two-pass approach, we compile the vocabulary in the first pass and construct the inverted index in thesecond pass. The index construction algorithms described in this chapter alldo a single pass through the data. Section 4.7 gives references to multipassalgorithms that are preferable in certain applications, for example, when diskspace is scarce.We work with the Reuters-RCV1 collection as our model collection in thischapter, a collection with roughly 1 GB of text.
It consists of about 800,000documents that were sent over the Reuters newswire during a 1-year period between August 20, 1996, and August 19, 1997. A typical document isshown in Figure 4.1, but note that we ignore multimedia information likeimages in this book and are only concerned with text. Reuters-RCV1 coversa wide range of international topics, including politics, business, sports, and(as in this example) science.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
