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

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

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

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

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

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

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

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

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)

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

Types of codes
- Fixed-length codes
- Variable-length codes
Advantages
- Less disk space utilization
- Better caching (more data per block)
- Better data transfer

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 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

Advantage:
- Store arbitrary large numbers
- Store small values with little cost
Types
- Unary code
- Elias’ gamma code
- Elias delta 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} \)

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 \)

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