CSxxx Fundamentals of Information Retrieval
Lecture 3
Text Preprocessing
Krishnendu Ghosh
Department of Computer Science & Engineering
Indian Institute of Information Technology Dharwad
Unstructured Data in 1620
Incidence Vectors
1 if play contains word, 0 otherwise
Brutus AND Caesar BUT NOT Calpurnia
Information Retrieval
So we have a 0/1 vector for each term.
To answer query: take the vectors for Brutus, Caesar and Calpurnia (complemented) > bitwise AND.
Answers to query
Antony and Cleopatra, Act III, Scene ii
Agrippa [Aside to DOMITIUS ENOBARBUS]: Why, Enobarbus,
When Antony found Julius Caesar dead,
He cried almost to roaring; and he wept
When at Philippi he found Brutus slain.
Hamlet, Act III, Scene ii
Lord Polonius: I did enact Julius Caesar I was killed i’ the
Capitol; Brutus killed me.
Bigger Collections
Consider N = 1 million documents, each with about 1000 words.
Avg 6 bytes/word including spaces/punctuation
6GB of data in the documents.
Say there are M = 500K distinct terms among these.
Can’t build the matrix
500K x 1M matrix has half-a-trillion 0’s and 1’s.
But it has no more than one billion 1’s.
matrix is extremely sparse.
What’s a better representation?
We only record the 1 positions.
Why?
Inverted Index
For each term t, we must store a list of all documents that contain t.
Identify each doc by a docID, a document serial number.
Inverted Index
We need variable-size postings lists
On disk, a continuous run of postings is normal and best
In memory, can use linked lists or variable length arrays
Some tradeoffs in size/ease of insertion
Inverted Index Construction
Initial Stages of Text Processing
Indexing: Token Sequence
Indexing: Sorting
Indexing: Creating Dictionary & Postings
Indexing: Costs
Query Processing: AND
Consider processing the query: Brutus AND Caesar
Merging Postings
Algorithm: Merging (Intersecting 2 Postings Lists)
Boolean Queries: Exact match
Largest commercial (paying subscribers) legal search service (started 1975; ranking added 1992; new federated search added 2010)
Tens of terabytes of data; ~700,000 users
Majority of users still use boolean queries
Example query:
What is the statute of limitations in cases involving the federal tort claims act?
LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM
/3 = within 3 words, /S = in same sentence
Another example query:
Requirements for disabled people to be able to access a workplace
disabl! /p access! /s work-site work-place (employment /3 place
Note that SPACE is disjunction, not conjunction!
Long, precise queries; proximity operators; incrementally developed; not like web search
Many professional searchers still like Boolean search
You know exactly what you are getting
But that doesn’t mean it actually works better….
Boolean Queries: Merging
Exercise: Adapt the merge for the queries:
Can we still run through the merge in time O(x+y)?
What about an arbitrary Boolean formula?
(Brutus OR Caesar) AND NOT (Antony OR Cleopatra)
Boolean Queries: Query Optimization
What is the best order for query processing?
Consider a query that is an AND of n terms.
For each of the n terms, get its postings, then AND them together.
Boolean Queries: Query Optimization
Process in order of increasing frequency (start with smallest set, then keep cutting further)
Boolean Queries: Query Optimization
Exercise
Recommend a query processing order for
(tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)
Which two terms should we process first?
Boolean Queries: More Optimization
Boolean Queries: Query Processing
Exercise:
Exercise: Extend the merge to an arbitrary Boolean query. Can we always guarantee execution in time linear in the total postings size?
Hint: Begin with the case of a Boolean formula
A First Attempt: Biword Indexes
Longer Phrase Queries
stanford university AND university palo AND palo alto
Without the docs, we cannot verify that the docs matching the above Boolean query do contain the phrase.
Biword Indexes: Issues
Solution: Positional Indexes
In the postings, store, for each term the position(s) in which tokens of it appear:
<term, number of docs containing term;
doc1: position1, position2 … ;
doc2: position1, position2 … ;
etc.>
Solution: Positional Indexes
<be:993427;
1: 7, 18, 33, 72, 86, 231;
2: 3, 149;
4: 17, 191, 291, 430, 434; …
>
Processing a phrase query
to, be, or, not.
to:
2:1,17,74,222,551; 4:8,16,190,429,433; 7:13,23,191; ...
be:
1:17,19; 4:17,191,291,430,434; 5:14,19,101; ...
Proximity Queries
Positional Index Size
A positional index expands postings storage substantially
Even though indices can be compressed
Nevertheless, a positional index is now standardly used because of the power and usefulness of phrase and proximity queries … whether used explicitly or implicitly in a ranking retrieval system.
Positional Index Size
Rules of Thumb
A positional index is 2–4 as large as a non-positional index
Positional index size 35–50% of volume of original text
Caveat: all of this holds for “English-like” languages
Combination Schemes
Tokenization
Given a character sequence and a defined document unit, tokenization is the task of chopping it up into pieces, called tokens, perhaps at the same time throwing away certain characters, such as punctuation. Here is an example of tokenization:
These issues of tokenization are language-specific. It thus requires the language of the document to be known. Language identification based on classifiers that use short character subsequences as features is highly effective; most languages have distinctive signature patterns
Terms/Tokens
A token is an instance of a sequence of characters in some particular document that are grouped together as a useful semantic unit for processing.
A type is the class of all tokens containing the same character sequence.
A term is a (perhaps normalized) type that is included in the IR system’s dictionary.
Tokenization Issues
Hyphenation: In English, hyphenation is used for various purposes ranging from splitting up vowels in words (co-education) to joining nouns as names (Hewlett-Packard) to a copyediting device to show word grouping (the hold-him-back and-drag-him-away maneuver).
Compounds: Other languages make the problem harder in new ways. German writes compound nouns without spaces (e.g., Computerlinguistik COMPOUNDS ‘computational linguistics’; Lebensversicherungsgesellschaftsangestellter ‘life insurance company employee’). Retrieval systems for German greatly benefit from the use of a compound-splitter module, which is usually implemented by seeing if a word can be subdivided into multiple words that appear in a vocabulary.
This phenomenon reaches its limit case with major East Asian Languages (e.g., Chinese, Japanese, Korean, and Thai), where text is written without any spaces between words. One approach here is to perform word segmentation as prior linguistic processing.
Normalization
Token normalization is the process of canonicalizing tokens so that matches occur despite superficial differences in the character sequences of the tokens.
Approach 1: The most standard way to normalize is to implicitly create equivalence classes, which are normally named after one member of the set.
For instance, if the tokens anti-discriminatory and antidiscriminatory are both mapped onto the term antidiscriminatory, in both the document text and queries, then searches for one term will retrieve documents that contain either.
Normalization
Approach 2: An alternative to creating equivalence classes is to maintain relations between unnormalized tokens. These term relationships can be achieved in two ways. The usual way is to index unnormalized tokens and to maintain a query expansion list of multiple vocabulary entries to consider for a certain query term. A query term is then effectively a disjunction of several postings lists. The alternative is to perform the expansion during index construction.
When the document contains automobile, we index it under car as well (and, usually, also vice-versa). Use of either of these methods is considerably less efficient than equivalence classing, as there are more postings to store and merge.
The first method adds a query expansion dictionary and requires more processing at query time, while the second method requires more space for storing postings.
Capitalization/Case-folding
A common strategy is to do case-folding by reducing all letters to lower case.
The task can be done more accurately by a machine learning sequence model which uses more features to make the decision of when to case-fold. This is known as truecasing.
Stemming and Lemmatization
The goal of both stemming and lemmatization is to reduce inflectional forms and sometimes derivationally related forms of a word to a common base form.
For instance:
am, are, is ⇒be
car, cars, car’s, cars’⇒car
The result of this mapping of text will be something like:
the boy’s cars are different colors ⇒ the boy car be differ color
Stemming and Lemmatization
Stemming usually refers to a crude heuristic process that chops off the ends of words in the hope of achieving this goal correctly most of the time, and often includes the removal of derivational affixes.
Lemmatization usually refers to doing things properly with the use of a vocabulary and morphological analysis of words, normally aiming to remove inflectional endings only and to return the base or dictionary form of a word, which is known as the lemma.
If confronted with the token saw, stemming might return just s, whereas lemmatization would attempt to return either see or saw depending on whether the use of the token was as a verb or a noun. As an example of what can go wrong, note that the Porter stemmer stems all of the following words: operate operating operates operation operative operatives operational to oper.
Stemming
Sample text: Such an analysis can reveal features that are not easily visible from the variations in the individual genes and can lead to a picture of expression that is more biologically transparent and accessible to interpretation
Lovins stemmer: such an analys can reve featur that ar not eas vis from th vari in th individu gen and can lead to a pictur of expres that is mor biolog transpar and acces to interpres
Porter stemmer: such an analysi can reveal featur that ar not easili visibl from the variat in the individu gene and can lead to a pictur of express that is more biolog transpar and access to interpret
Paice stemmer: such an analys can rev feat that are not easy vis from the vary in the individ gen and can lead to a pict of express that is mor biolog transp and access to interpret.
Faster Postings List Intersection via Skip Pointers
If the list lengths are m and n, the intersection takes O(X + Y) operations. Can we do better than this?
One way to do this is to use a skip list by augmenting postings lists with skip pointers:
Algorithm
Faster Postings List Intersection via Skip Pointers
Where do we place skips? There is a tradeoff. More skips means shorter skip spans, and that we are more likely to skip. But it also means lots of comparisons to skip pointers, and lots of space storing skip pointers.
Choice: A simple heuristic for placing skips, which has been found to work well in practice, is that for a postings list of length P, use √P evenly-spaced skip pointers.
Issues: Building effective skip pointers is easy if an index is relatively static; it is harder if a postings list keeps changing because of updates. A malicious deletion strategy can render skip lists ineffective.
Thank You