04 Tolerant Retrieval & Spelling Correction

Question 1

What is Permuterm index?

Answer 1

a time-efficient and elegant solution to the string dictionary problem in which pattern queries may possibly include one wild-card symbol

hello$, ello$h, llo$he, lo$hel, o$hell, and $hello

Question 2

What is a problem about Permuterm index?

Answer 2

space inefficient: because it quadruples the dictionary size

Question 3

What is k-gram index?

Answer 3

the dictionary which contains sequence of k characters (k-gram) occuring in a term

“etr” : beetroot, metric, petrify

Question 4

k-gram index vs. permuterm index

Answer 4

• k-gram index is more space efficient
• Permuterm index doesn’t require postfiltering

Question 5

What are problems with processing wildcard queries in the term-document index?

Answer 5

1. potentially execute a large number of Boolean queries
2. if users use them a lot, the cost of answering query will increase

Question 6

What are two methods for spelling correction ?

Answer 6

1. Isolated word: check each word on its own for misspelling
2. Contex-sensitive: look at surrounding words

Question 7

How does isolated word spelling correction works?

Answer 7

1. get correct spellings from a list of correct words (e.g. dictionaries)
2. return the correct word that has the smallest distance to misspelled word

Question 8

What is edit distance ?

Answer 8

edit distance is the minimum number of basic operations that convert string1 to string2

Question 9

What are basic operations in Levenshtein distance ?

Answer 9

1. insert
2. delete
3. replace

Question 10

What are basic operations in Damerau-Levenshtein distance ?

Answer 10

1. insert
2. delete
3. replace
4. transposition

Question 11

What is weighted edit distance ?

Answer 11

Weight of an operation depends on the characters involved

Application example: capture keyboard errors

Question 12

How to use edit distance for spelling correction ?

Answer 12

1. Compare to all terms, but stop after specific edit distance has been reached
2. Generate all writing variations of query and compare to dictionary
3. Add (some) writing variations of the dictionary to the dictionary

Question 13

How does k-gram indexes for spelling correction works ?

Answer 13

• Use the k-gram index to retrieve “correct” words that match query term k-grams
• Threshold by number of matching k-grams

Bigrams: bo, or, rd, dr, ro, oo, om

Question 14

What is an issue with k-gram for spelling correction ?

Answer 14

• measure of overlap is not normalized
• fixed number of treshold does not work for word of different length

Question 15

What is Jaccard coefficient ?

Answer 15

• A commonly used measure of overlap of two sets
• A and B don’t have to be the same size

Question 16

How does context-sensitive spelling correction work ?

Answer 16

• list all possible phrases as queries
• the one with most hits = “correct”

not very efficient