Processing Text

●​ Corpus: collection of some types of documents

○​ Corpus of news/articles
○​ Usually share some characteristics

●​ We can rely on the textual characteristics to build text-based engines

●​ The laws apply to:
○​ Different languages
○​ Different text domains

1.​ Words to Terms

●​ Text transformation/processing: convert words into index terms

○​ Index term: representation of the content of a document (used for searching)
●​ Tokenization: split words apart
●​ Stopping: ignore some words to make query processing more efficient and effective
●​ Stemming: allow similar words (like “run” and “running”) to match each other

⇒ Search engines is about deciphering the meaning of text by the counts of word occurrences
and co-occurrences (the number of times group of words occur together in documents)

2.​ Text Statistics

●​ Distribution of word frequencies is very skewed

○​ Words like “the”, “of” account for 10% of all word occurrences
○​ ½ of all unique words in a large sample of text occur only once

●​ Knowing (1) how fast the vocabulary size grows with the size of a corpus and (2) how
the words are distributed helps us determine:
○​ Indexing technique
○​ Storage: how to store data + storage availability

Probability
●​ Experiment: a specific set of actions the results of which can not be predicted with
certainty
●​ Sample space: possible set of recorded data
●​ Event space: subsets of a sample space defined by a specific event/outcome
○​ Example: The event that the sum of 2 dice is 4

●​ Zipf’s law: The frequency of the rth most common word is inversely proportional to r
 ○​ Graph frequency vs. rank → hard exponential decay (the more frequent the word,
the higher the rank)
○​ The rank of word r * its frequency f is approximately a constant k
■​ 𝑟 × 𝑓 = 𝑘
●​ If rank 1 term occurs cN times, ten rank 2 occurs cN/2, …
○​ Most frequent word (1/1) will occur 2x as frequently as the
2nd most frequent (½).
○​ Alternatively:
■​ 𝑟 × 𝑃𝑟 = 𝑐 where
●​ 𝑃𝑟: probability of occurrence for the rth ranked word
●​ 𝑐 (≈ 0. 1): a constant
○​ Might be inaccurate for low and high ranks
■​ Not accurate at tails
○​ There might be words with the same frequency n ⇒ Count: 𝑟𝑛 − 𝑟𝑛+1 (where 𝑟𝑛 is
the rank of the last word in the group, 𝑟𝑛+1 is the rank of the last word of the
previous group of words with higher frequency)

●​ Vocabulary Growth: as the size of the corpus grows, new words occur
○​ Can be due to: typos, new words in the vocabulary, …
β
○​ Heap’s law: 𝑣 = 𝑘 × 𝑛
■​ 𝑣: vocab size for a corpus of size 𝑛 words
■​ 𝑘, β: parameters (peculiar to each collection)
●​ 10 ≤ 𝑘 ≤ 100
●​ β ≈ 0. 5

3.​ Document Parsing

Process:
1.​ Taking a document
2.​ Turn it into a representation (like metadata)
a.​ Non-context: bag of words
b.​ word2vec: ML algorithm to see what’s the probability of seeing a word next to
another
On the other hand
1.​ Taking a query
2.​ Turn it into a representation (have to be of the same form as the document)

⇒ Compare them
⇒ Evaluate the comparisons (how related is this to the query)
⇒ Feedback (eg: based on how many times you clicked on something)
Basic inverted index construction:

●​ Token: a semantic unit

○​ Instance of a word occurring in a doc. Example: Bush, bush, friends
○​ Tokenizing: figuring out how to divide up the documents into fragments

●​ Text preprocessing:
○​ Remove punctuations
○​ Lowercase

●​ Inverted index: map a word to the documents it appears

○​ Term: entry in dictionary (normalized). Example: bush, friend
○​ Type: class of all tokens containing the same character sequence (Example: “to
be or not to be” has 6 tokens, 4 terms)

What’s in a document
●​ Multiple language
●​ Multiple character set/encoding: How do we go from the binary to the characters
●​ Different compressing algorithms: zipped/compressed
 ●​ Recognition of the content and structure of text documents
○​ Tokenizing/lexical analysis: recognizing each word occurrence in the sequence
of characters in a document
○​ Metadata: document attributes (date/author); tags to identify document
components

Big challenge in querying: Vocabulary mismatch

●​ Word boundary variation
○​ eusa is different from e-usa = usa = u.s.a = us of a
●​ Morphological variation
○​ Policeman = policemen = police vs. policy = politics
●​ Spelling variation:
○​ Gaddafi = Gadhafi = …
●​ Synonymy and Polysemy
○​ apple vs. Apple vs. Big Apple

a)​ Tokenizing

Challenges:
●​ Small words important in queries that are disregarded
●​ Hyphenated/non-hyphenated forms of many words are common
●​ Special characters
●​ Capitalized words (since tokenizing lowercases everything)
●​ Apostrophes (‘) that can be part of a word
●​ Periods
⇒ Can treat hyphens, apostrophes and periods as spaces
⇒ No single right way to do it

1.​ First pass: identifying markup or tags in the document (accommodate syntax errors in
the structure)
2.​ Second pass: identify structure in appropriate parts of the document

b)​ Stopping

●​ Function words: words that have little meaning apart from other words
●​ Stopwords: function words in the context of information retrievals
○​ We will throw them out → decrease index size, increase retrieval efficiency
○​ Can be customized for specific parts of the document structure/fields (like
“click”, “here”, “privacy” are stopwords when processing anchor text)
⇒ Downside of just removing the stopwords: Cannot search on them!
 c)​ Stemming

Pros:
+​ Smaller dictionary size
+​ Increased recall (number of documents returned)

Cons:
-​ Exact quotes
-​ Decrease in specificity
-​ Decrease in precision (more *junk*)

●​ Component of text processing that captures the relationships between different

variations of a word
○​ Reduce the different forms of a word to a common stem that occur because of
■​ Inflection (eg, plurals, tenses) or
■​ Derivations (making a verb in to a noun by adding the suffix -ation)
→ For example, “swimming” and “swam” can be reduced to “swim”

●​ 2 types of stemmers:
○​ Algorithmic: decide whether 2 words are related
■​ Simplest: “s” signifies plurality
●​ False negatives: cannot detect a relationship (example: country
and countries)
●​ False positives: detect a relationship when there is none (example:
I and is)
⇒ Solution: consider more kinds of suffixes → reduce false
negative, but false positives increase
■​ Porter stemmer:
●​ The most popular algorithmic stemmer
●​ Used in many information retrieval experiments and systems
since the 70s
○​ Dictionary-based: store term relationships based on pre-created dictionaries of
related terms
■​ Instead of computing the relationship between words, these just store
lists of related words in a large dictionary
■​ Drawback: tend to be static + less flexible (while language evolves
constantly)

○​ Combine the 2:
■​ Use algorithmic to deal with new/unrecognized words
■​ Dictionary is used to detect relationships between common words
 ■​ Krovetz stemmer: use dictionary to check the validity of a word + if not
found, then check for suffixes → feed to the dictionary again
●​ Lower false positive than Porter
●​ Higher false negative

d)​ Phrases and N-grams

●​ Phrase: a simple noun phrase (can be nouns, or adjectives followed by nouns)

○​ POS tagging:
■​ Too slow
■​ Alternative: store word position information in the indexes → only identify
phrases when a query is processed

⇒ Testing word proximities at query time is likely to be too slow

⇒ Identify n words to be a unit during text processing

●​ n-gram: sequence of n words

○​ Generated by choosing a particular value for n
○​ Then move that window forward one unit (character/word) at a time
■​ Example: “hello” contains the following bigrams: he, el, ll, lo
○​ Indexes based on n-grams are larger than word indexes

4.​ Document Structure and Markup

●​ Document parsers use the structure of web pages (example, from HTML markup) for
ranking algorithm
○​ Headings indicate that the phrase is particularly important

●​ XML: allows each application to define what the element types

○​ Defined by a schema (like a database schema)
○​ Therefore, its elements are more tied to the semantics of the data than HTML
elements

5.​ Link Analysis

●​ Links tell relationship between pages–help with ranking pages

●​ Anchor Text: 2-3 words describing the topic of the linked page
○​ For a link www.ebay.com is highly linked to “eBay” in the anchor text
○​ This motivates a simple ranking algorithm: search through all links in the
collection, looking for anchor text that matches user’s query
●​ PageRank:
○​ Naive: Use page rank to measure popularity of pages
■​ Like count the number of inlinks (links pointing to a page) for each page
■​ Susceptible to spam!
○​ PageRank: Google search engine
■​ A value associated with a web page
■​ Help search engines sift through all pages containing the word “eBay” to
find the most popular one
■​ The PageRank for a page = Sum(Page that goes to it / count of pages
that it links to)

○​ If we take into account “distraction” links on the site…

■​ Adjust the PR to be the weighted average of clicking on that link (λ) vs.
not clicking on that link

○​ Rank sinks: pages with no outbound links (accumulate PR but do not distribute it)

●​ Link quality:
○​ Hard to assess: web page designers may try to create useless links to improve
the PR → link spam
■​ Solution: detect link spam in comment sections and ignore them during
indexing
●​ Easier solution: put rel=nofollow to unimportant links

6.​ Internationalization

●​ Monolingual search engine: search engine designed for a particular language

●​ Challenge:
○​ Word segmentation: identifying breaks within sequence of words/index terms
■​ Techniques: Hidden Markov Model