Information Retrieval Techniques: Normalization and Indexing Pipeline

INFORMATION RETRIEVAL INFORMATION RETRIEVAL TECHNIQUES TECHNIQUES BY DR. ADNAN ABID Lecture # 9 Terms Normalization 1

ACKNOWLEDGEMENTS ACKNOWLEDGEMENTS The presentation of this lecture has been taken from the following sources 1. Introduction to information retrieval by Prabhakar Raghavan, Christopher D. Manning, and Hinrich Sch tze 2. Managing gigabytes by Ian H. Witten, Alistair Moffat, Timothy C. Bell 3. Modern information retrieval by Baeza-Yates Ricardo, 4. Web Information Retrieval by Stefano Ceri, Alessandro Bozzon, Marco Brambilla

Outline Outline Normalization Case folding Normalization to terms Thesauri and soundex 3

Basic indexing pipeline Documents to be indexed Friends, Romans, countrymen. Tokenizer Friends Romans Countrymen Token stream Linguistic modules friend roman countryman Modified tokens 2 4 Indexer friend 1 2 roman Inverted index 16 13 countryman 4

Normalization to terms Normalization to terms We may need to normalize words in indexed text as well as query words into the same form We want to match U.S.A. and USA Tokens are transformed to terms which are then entered into the index A term is a (normalized) word type, which is an entry in our IR system dictionary We most commonly implicitly define equivalence classes of terms by, e.g., deleting periods to form a term U.S.A.,USA USA deleting hyphens to form a term anti-discriminatory, antidiscriminatory antidiscriminatory 5

1. Normalization: other languages 1. Normalization: other languages Accents: e.g., French r sum vs. resume. Simple remedy remove accent but not good in case of Resume with and without accent. Clich = Cliche (with and without accent same meaning) Important consideration: Are the users going to use accents while writing queries? Umlauts: e.g., German: Tuebingen vs. T bingen Should be equivalent Even in languages that standard have accents, users often may not type them Often best to normalize to a de-accented term Tuebingen, T bingen, Tubingen Tubingen 6

Normalization: other languages Normalization: other languages Normalization of things like date forms 7 30 vs. 7/30 (date or mathematical expression) July 30, 7-30 Diversification: 7/30 = 7/30, Japanese use of kana vs. Chinese characters In Japanese there are several different character sets and normalization needs to take care of this fact, and it should be able to resolve the query entered using any char-set In German MIT is a word, so how to differentiate the usage if it is University of the word MIT? Tokenization and normalization may depend on the language and so is intertwined with language detection Same method of normalization should be used while indexing as well as while query processing Is this German mit ? Morgen will ich in MIT 7

2. Case folding 2. Case folding Reduce all letters to lower case exception: upper case in mid-sentence? e.g., General Motors Fed vs. fed SAIL vs. sail Often best to lower case everything, since users will use lowercase regardless of correct capitalization A word starting with a capital letter in the middle of sentence is for nouns, so case folding may be given importance in this case. However, if users are not going to use capital letters then there is no point in improving index. Longstanding Google example: [fixed in 2011 ] Query C.A.T. #1 result is for cats not Caterpillar Inc. 8

3. Normalization to terms 3. Normalization to terms An alternative to equivalence classing is to do asymmetric expansion An example of where this may be useful Enter: window Search: window, windows Enter: windows Search: Windows, windows, window Enter: Windows Search: Windows Potentially more powerful, but less efficient Increases the size of the postings list, but give more control in query processing. 9

4. Thesauri and 4. Thesauri and soundex soundex Do we handle synonyms and homonyms? Synonym: Diff words same meanings. (Automobile / Car) Homonyms: Same words different meanings (Jaguar) (Blackberry) For homonyms postings for all variants against same index word (term). For Synonym E.g., by hand-constructed equivalence classes car = automobile color = colour We can rewrite to form equivalence-class terms When the document contains automobile, index it under car-automobile (and vice-versa) Or we can expand a query When the query contains automobile, look under car as well What about spelling mistakes? Chebichev One approach is Soundex, which forms equivalence classes of words based on phonetic heuristics Groups the words that sound similar into same equivalence class. 10

Resources Resources MG 3.6, 4.3; MIR 7.2 Porter s stemmer: http//www.sims.berkeley.edu/~hearst/irbook/porter.html H.E. Williams, J. Zobel, and D. Bahle, Fast Phrase Querying with Combined Indexes , ACM Transactions on Information Systems. http://www.seg.rmit.edu.au/research/research.php?author=4 11