../

Tolerant Retrieval

Dictionary Storing Mechanism

Question 1: What are the two main data structures to store dictionaries

Question 2: What are the pros of using a hashtable

Question 3: What are the cons of using a hashtable

Question 4: What are the pros of using a Tree

Question 5: What are the cons of using a Tree

Question 6: Draw a sample tree

Wild Card Queries

Question 7: Using tree how would you retrieve queries like mon*

Question 8: Using tree how would you retrieve queries like *ed

Question 9: What is the flaw with using trees to process wildcard queries

Question 10: What is the solution for handling arbitrary wildcard queries using b-trees

Refer Permuterm for concepts

Question 11: What is the problem with permuterm index

Bi-gram index

Question 12: How would you construct a bi-gram index

Question 13: Are bigram index and biword index the same?

Question 14: How would you process a wild card query using n-gram indices

Question 15: Give the pros and cons of bi-gram and Permuterm

Spelling Correction

Question 16: What are the two main uses of spelling correction

Question 17: What are the two types of spelling correction

Question 18: Give one practical use case of spelling correction

Question 19: In isolated word correction what are the choices for the source of lexicon?

Question 20: What is a subtle drawback of using the indexed corpus as a source of lexicons

Question 21: What are the three ways to do isolated spelling correction?

Question 22: Why do we need weighted edit distance?

Question 23: Give the Levenshtein edit distance algorithm 

def edit_distance(a:str, b:str):
 	mat = [[0 for _ in range(len(b)+1)] for _ in range(len(a)+1)] 
 	mat[0][0] = 0;
 	for i in range(len(a)+1):
 		mat[i][0] = i
 	for i in range(len(b)+1):
 		mat[0][i] = i
 	for i in range(1, len(a)+1):
 		for j in range(1, len(b)+1):
 			mat[i][j] = min(
	 			mat[i-1][j-1] + (0 if a[i-1] == b[j-1] else 1),
		 		mat[i-1][j]+1,
	 			mat[i][j-1]+1 )
 	return mat[-1][-1]

Question 24: Give the heuristic for filling each of the cells in computing edit distance

Diag (0 if equal or 1 if not equal) Above +1
Left +1 Min of all the other three

Question 25: Give the structure of a k-gram index

dict(k-gram, term[]) It is a mapping from a k-gram to the terms from the original index that contains that k-gram

Question 26: What is the formula for Jaccard Coefficient

Question 27: Give pseudo code for computing JC using only one of the kgrams 

def jaccard_coefficient(query:str, term:str, k:int)->float:
  kgram = kgram_create(query, k)
  ins = 0
  for q in kgram:
  	if q in term:
  		ins += 1
  return ins/(kgram_num(term, k) + len(kgram) - ins)

Question 28: How to do context sensitive correction

Question 29: Give the mathematical formula for ranking the alternative spellings

Soundex

Question 30: Give the format of a soundex reduced term

Question 31: Give the soundex algorithm

  • Retain the first word
  • Replace letters using the following rules
    • aeiou why - 0
    • bfpv - 1
    • other letters - 2
    • dt - 3
    • l - 4
    • mn- 5
    • r - 6
  • Remove all the numbers that repeat
  • Remove all the 0s
  • Pad with trailing zeros until you get a 4 character sequence
  • Return the 4 character sequence

Question 32: What should you do first - remove consecutive digits or remove zeros?

Remove consecutive digits