## Implementation ### Document preparation - Workflow 1. Character sequence decoding 2. Document delinearization 3. Tokenization 4. Filtration 5. Stemming and lemmatization 6. Representation - Problems - Heterogeneous data (date formats, coding) - Multiple forms of the same word (apple, Apple, apples, Apple's) - Important: Query must be processed the same way ![](images/docprep.png) #### Character sequence decoding - Goal: Get textual representation - Problems: Different formats - e.g., DOC, PDF, HTML, RTF - Solution: Converters - Problem: Different character encodings - e.g., UTF-8, ASCII, ISO-8859-1 - Character encoding unspecified/wrongly specified - Solution: Heuristics for auto-detection - Problem: Double-column PDF with images ##### Heuristics for encoding detection - Coding scheme method - Exclude encodings by checking for illegal byte sequences - Character distribution method - Use language statistics of character frequencies - Compare byte frequency with character frequency - Collect co-occurring bytes (?) - Two-char sequence distribution method - Use statistics about 2-grams - Pairs of adjacent characters #### Document delinearization - Goal: - Split documents into smaller parts - Select *document unit* (e.g., file, email, web page, slides) - Motivation: - Unix Email ``mbox``-Format contains multiple emails, which could be considered as single document - Split large documents to parallelize processing - Split by heuristics #### Tokenization - Goal: Convert text into sequence of *tokens* - Definition *token*: Useful semantic unit for processing - Aspects: - Tokenization is language-specific - Tokenization rules affect the expressiveness - Every transformation has problems - Tasks: - Token normalization - Equivalence classing for tokens ##### Transformation/normalization rules - Split whitespaces (several problems, see below) - Remove formatting information (e.g., HTML-tags) - Replace/remove diacritics (e.g., accents, umlauts) - Remove punctuation (e.g., U.S.A. becomes USA) - Case folding - e.g., convert to lower case - Exception for names - Truecasing: Heuristics for case folding ##### Problems - Multiple related words form one *token* - e.g., San Francisco, New York - No whitespaces in text - e.g., Chinese characters (one word or multiple) - Solution: Word segmentation - Formatting - e.g., dates, telephone numbers - Different format, could be the same token - Compounds - e.g., white space vs. whitespace - Solution: compound splitter (check if subwords are contained in vocabulary) - Hyphens - e.g., Hewlett-Packard, co-education - Case folding - e.g., windows vs. Windows - Punctuation - e.g., C.A.T. vs. cat #### Filtration - Goal: Remove stop words - *Stop word*: Common word without representational value - Problem: Phrase queries - e.g., King of Finland - Stop word is necessary - Strategies: 1. General - Sort tokens by collection frequency - Identify top-k as stop list 2. Domain-specific - Use predefined stop list - Trend: Small stop lists - e.g., 7-12 terms - Storage no problem due to good compression - Web search engine: No stop words #### Stemming and lemmatization - Definition *Lemmatization*: Group together different inflected forms of a word (professional) - Definition *Stemming*: Lemmatization using crude heuristics (no context, no rules) - Problem with lemmatization - Computationally expensive (for large collections) - Gains (mean average precision) over stemmers are modest for English (0-5%) - Stemmers: - Porter stemmer (1980) - Lovins stemmer (1968) - Paice/Husk stemmer (1990) ##### Porter stemmer - Porter, 1980 - Stemmer tool for english language - Idea: Suffixes are mostly made from combination of smaller, simpler suffixes - Algorithm uses five steps - Each step applies rules to change the suffix of a word - e.g., ing->EMPTY, ies->i #### Representation - Input: List of tokens (stemmed) - Output: Final document representation (e.g., bag-of-words, vector) - Next step: Build index ### Indexing - Important aspects - Indexing granularity (e.g., book, chapter, paragraph, sentence) - Handling large collections - Reduce disk accesses - Goal: Inverted index - Index is term-postings-mapping - Optional: Add idf to term - Optional: Sort - *Postings list*: Tuples with docID and term frequency - Requirements - Keep index small - Minimize disk accesses - Solution: Use compression - Indexing types - Static/dynamic #### Static/dynamic indexing - Static indexing - Build index at design time - Dynamic indexing - Situation: Changes in collection - Problem: Complete rebuild too expensive - Solution: - Auxiliary index in-memory - Merge with disk-index if too large #### Algorithm 2. Run document preparation (assign *docID*) 3. Compile list of terms 4. Assign *termID* to each term 5. Create matrix/list (termID, docID, tf) 6. Sort list by *termID* and *docID* - Alternative: Sort by *termID* and *tf* #### Handle large collections - Small collection: Fit in main memory (no problem) - Large collection: Disk access necessary - Sort-based inversion - External sorting algorithm - Merge-based inversion - Read/index in-memory until buffer filled - Flush to disk and merge - Advantage: Practical, scalable #### Compression - Types of codes - Fixed-length codes - Variable-length codes - Advantages - Less disk space utilization - Better caching (more data per block) - Better data transfer ##### Enhancements of the postings list - Storing gaps - Store gaps between two document IDs - Use gaps instead of document IDs - Skip lists - Goal: Reduce number of disk accesses - Add evenly spaced skip pointers to list - Skip pointer consists of pointer to posting and its value - Intersecting (AND-query) two postings lists one can follow the skip pointer ##### Fixed-length codes - Fixed-length for document ID and term frequency - e.g., 32 bit and 16 bit - Size: `$ df(t) * 48 $` bit - Problem: Not space-efficient - Few documents occur very frequently - Most documents occur very rarely - Solution: Variable-length integers ##### Variable-length codes - Advantage: - Store arbitrary large numbers - Store small values with little cost - Types - Unary code - Elias' gamma code - Elias delta code ###### Unary code - Use for integers `$ x>0 $` - Representation: `$ x-1 $` ones and trailing zero - Example: `$ 6=111110 $` - Optimal for `$ P(x) \approx 2^{-x} $` - Alternative: Store `$ x $` ones and trailing zero (not necessary in IR) ###### Elias gamma code - Use for integers `$ x>0 $` - Representation - `$ x = 2^a+b $` - `$ a=\lfloor \log_2 x \rfloor $` - `$ 0\leq b < 2^a $` - Concatenate `$ a+1 $` in unary code and `$ b $` in binary with width `$ a $` - Example: `$ 12=2^3+4=1110100 $` - Optimal for `$ P(x) \approx \frac{1}{2x^2} $` ###### Elias delta code - Use Elias gamma code - Motivation: Elias gamma code becomes long for large numbers - Encode the `$ a $` part with Elias gamma code - Example: - `$ 1025 = 2^{10} + 1 $` - `$ 10=2^3+2 $` - `$ \gamma = 1111111110,0000000001 $` - `$ \delta = 110,010,0000000001 $` ### Handle phrase queries - Phrase query: Query with word order - Strategies - Post-processing - Prune using normal retrieval - Search documents for phrase - Positional postings - Add word positions into each posting - Check positions during evaluation - Partial phrase index - Create multi-term-index for certain phrases - Hybrid processing - Use phrase index for frequent terms - Use positional postings (efficient due to compression) - If not positional postings found, use post-processing technique