An introduction to information retrieval. Manning_ Raghavan (2009) (811397), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Due to differences in the language and writing system,word segmentation is most usual for Japanese (Luk and Kwok 2002, KishidaOnline edition (c) 2009 Cambridge UP462 The term vocabulary and postings listsSKIP LISTet al. 2005). The structure of a character k-gram index over unsegmented textdiffers from that in Section 3.2.2 (page 54): there the k-gram dictionary pointsto postings lists of entries in the regular dictionary, whereas here it pointsdirectly to document postings lists.

For further discussion of Chinese wordsegmentation, see Sproat et al. (1996), Sproat and Emerson (2003), Tseng et al.(2005), and Gao et al. (2005).Lita et al. (2003) present a method for truecasing. Natural language processing work on computational morphology is presented in (Sproat 1992,Beesley and Karttunen 2003).Language identification was perhaps first explored in cryptography; forexample, Konheim (1981) presents a character-level k-gram language identification algorithm. While other methods such as looking for particular distinctive function words and letter combinations have been used, with theadvent of widespread digital text, many people have explored the character n-gram technique, and found it to be highly successful (Beesley 1998,Dunning 1994, Cavnar and Trenkle 1994).

Written language identificationis regarded as a fairly easy problem, while spoken language identificationremains more difficult; see Hughes et al. (2006) for a recent survey.Experiments on and discussion of the positive and negative impact ofstemming in English can be found in the following works: Salton (1989), Harman (1991), Krovetz (1995), Hull (1996).

Hollink et al. (2004) provide detailedresults for the effectiveness of language-specific methods on 8 European languages. In terms of percent change in mean average precision (see page 159)over a baseline system, diacritic removal gains up to 23% (being especiallyhelpful for Finnish, French, and Swedish). Stemming helped markedly forFinnish (30% improvement) and Spanish (10% improvement), but for mostlanguages, including English, the gain from stemming was in the range 0–5%, and results from a lemmatizer were poorer still.

Compound splittinggained 25% for Swedish and 15% for German, but only 4% for Dutch. Ratherthan language-particular methods, indexing character k-grams (as we suggested for Chinese) could often give as good or better results: using withinword character 4-grams rather than words gave gains of 37% in Finnish, 27%in Swedish, and 20% in German, while even being slightly positive for otherlanguages, such as Dutch, Spanish, and English. Tomlinson (2003) presentsbroadly similar results. Bar-Ilan and Gutman (2005) suggest that, at thetime of their study (2003), the major commercial web search engines sufferedfrom lacking decent language-particular processing; for example, a query onwww.google.fr for l’électricité did not separate off the article l’ but only matchedpages with precisely this string of article+noun.The classic presentation of skip pointers for IR can be found in Moffat andZobel (1996).

Extended techniques are discussed in Boldi and Vigna (2005).The main paper in the algorithms literature is Pugh (1990), which uses multilevel skip pointers to give expected O(log P) list access (the same expectedOnline edition (c) 2009 Cambridge UP2.5 References and further reading47efficiency as using a tree data structure) with less implementational complexity.

In practice, the effectiveness of using skip pointers depends on varioussystem parameters. Moffat and Zobel (1996) report conjunctive queries running about five times faster with the use of skip pointers, but Bahle et al.(2002, p. 217) report that, with modern CPUs, using skip lists instead slowsdown search because it expands the size of the postings list (i.e., disk I/Odominates performance). In contrast, Strohman and Croft (2007) again showgood performance gains from skipping, in a system architecture designed tooptimize for the large memory spaces and multiple cores of recent CPUs.Johnson et al.

(2006) report that 11.7% of all queries in two 2002 web querylogs contained phrase queries, though Kammenhuber et al. (2006) reportonly 3% phrase queries for a different data set. Silverstein et al. (1999) notethat many queries without explicit phrase operators are actually implicitphrase searches.Online edition (c) 2009 Cambridge UPOnline edition (c) 2009 Cambridge UPDRAFT! © April 1, 2009 Cambridge University Press. Feedback welcome.3WILDCARD QUERY3.149Dictionaries and tolerantretrievalIn Chapters 1 and 2 we developed the ideas underlying inverted indexesfor handling Boolean and proximity queries.

Here, we develop techniquesthat are robust to typographical errors in the query, as well as alternativespellings. In Section 3.1 we develop data structures that help the searchfor terms in the vocabulary in an inverted index. In Section 3.2 we studythe idea of a wildcard query: a query such as *a*e*i*o*u*, which seeks documents containing any term that includes all the five vowels in sequence.The * symbol indicates any (possibly empty) string of characters.

Users posesuch queries to a search engine when they are uncertain about how to spella query term, or seek documents containing variants of a query term; for instance, the query automat* would seek documents containing any of the termsautomatic, automation and automated.We then turn to other forms of imprecisely posed queries, focusing onspelling errors in Section 3.3. Users make spelling errors either by accident,or because the term they are searching for (e.g., Herman) has no unambiguousspelling in the collection.

We detail a number of techniques for correctingspelling errors in queries, one term at a time as well as for an entire stringof query terms. Finally, in Section 3.4 we study a method for seeking vocabulary terms that are phonetically close to the query term(s). This can beespecially useful in cases like the Herman example, where the user may notknow how a proper name is spelled in documents in the collection.Because we will develop many variants of inverted indexes in this chapter,we will use sometimes the phrase standard inverted index to mean the invertedindex developed in Chapters 1 and 2, in which each vocabulary term has apostings list with the documents in the collection.Search structures for dictionariesGiven an inverted index and a query, our first task is to determine whethereach query term exists in the vocabulary and if so, identify the pointer to theOnline edition (c) 2009 Cambridge UP503 Dictionaries and tolerant retrievalBINARY TREEB- TREEcorresponding postings.

This vocabulary lookup operation uses a classicaldata structure called the dictionary and has two broad classes of solutions:hashing, and search trees. In the literature of data structures, the entries inthe vocabulary (in our case, terms) are often referred to as keys. The choiceof solution (hashing, or search trees) is governed by a number of questions:(1) How many keys are we likely to have? (2) Is the number likely to remainstatic, or change a lot – and in the case of changes, are we likely to only havenew keys inserted, or to also have some keys in the dictionary be deleted? (3)What are the relative frequencies with which various keys will be accessed?Hashing has been used for dictionary lookup in some search engines.

Eachvocabulary term (key) is hashed into an integer over a large enough spacethat hash collisions are unlikely; collisions if any are resolved by auxiliarystructures that can demand care to maintain.1 At query time, we hash eachquery term separately and following a pointer to the corresponding postings, taking into account any logic for resolving hash collisions.

There is noeasy way to find minor variants of a query term (such as the accented andnon-accented versions of a word like resume), since these could be hashed tovery different integers. In particular, we cannot seek (for instance) all termsbeginning with the prefix automat, an operation that we will require belowin Section 3.2. Finally, in a setting (such as the Web) where the size of thevocabulary keeps growing, a hash function designed for current needs maynot suffice in a few years’ time.Search trees overcome many of these issues – for instance, they permit usto enumerate all vocabulary terms beginning with automat.

The best-knownsearch tree is the binary tree, in which each internal node has two children.The search for a term begins at the root of the tree. Each internal node (including the root) represents a binary test, based on whose outcome the searchproceeds to one of the two sub-trees below that node. Figure 3.1 gives an example of a binary search tree used for a dictionary. Efficient search (with anumber of comparisons that is O(log M )) hinges on the tree being balanced:the numbers of terms under the two sub-trees of any node are either equalor differ by one.

Характеристики

Список файлов книги