Hey Everyone,

Post your solutions to the practice midterm problems to this thread. Remember to list all your teammates.

Best,

Chris

Devangi, Pranjali, Mustafa

1. Consider the "As I was going to St Ives ..." riddle, explain how the nextPhrase algorithm would work on inputs:<br>nextPhrase("had", "seven", 10). As there are variants to the riddle, tell me which one you are using as you go<br>through the solution.<br>

   As I was going to St. Ives,<br> I met a man with seven wives,<br> Each wife had seven sacks,<br> Each sack had seven cats,<br> Each cat had seven kits:<br> Kits, cats, sacks, and wives,<br> How many were there going to St. Ives?<br>

After removing punctuations, and giving positions:<br>

1 as <br> 2 i <br> 3 was <br> 4 going <br> 5 to <br> 6 st <br> 7 ives<br> 8 i <br> 9 met <br> 10 a <br> 11 man <br> 12 with <br> 13 seven <br> 14 wives<br> 15 each <br> 16 wife <br> 17 had <br> 18 seven <br> 19 sacks<br> 20 each <br> 21 sack <br> 22 had <br> 23 seven <br> 24 cats<br> 25 each <br> 26 cat <br> 27 had <br> 28 seven <br> 29 kits<br> 30 kits <br> 31 cats <br> 32 sacks <br> 33 and <br> 34 wives<br> 35 how <br> 36 many <br> 37 were <br> 38 there <br> 39 going <br> 40 to <br> 41 st <br> 42 ives<br> <br> Dictionary:<br> <br> As : 1<br> I : 2, 8<br> Was: 3<br> Going: 4<br> To: 5, 40<br> St: 6, 41<br> Ives: 7, 42<br> Met : 9<br> A : 10<br> Man : 11<br> With: 12<br> Seven : 13, 18, 23, 28<br> Wives : 14, 16, 34<br> <br>

nextPhrase(“had”, “seven”, 10):<br> <br> For every term in (“had”, “seven”)<br> <br> term = “had”<br> v = next(“had”, 10)<br> v = 17<br>

term = “seven”<br> v = next(“seven”, 17)<br> v = 18<br> <br> U = 18<br> <br> For every term but last in (“had”, “seven”) (reverse)<br> <br> term = “seven”<br> u = prev(“had”, 18)<br> u = 17<br> V - u = 18 - 17 = 1 (== n - 1 == 2-1)<br> <br> Therefore, return [17, 18]<br> <br>

By Vrinda and Sriramm:

Q9.Suppose n=3 what would be the character n-grams for the word toast? (1pt) What is stopping? (1pt) What is stemming (1pt)? Give an example of the kinds of rules used by a Porter stemmer.\ ; Toast - .toast. :

• .to
• toa
• oas
• ast
• st.

; Stopping: The removal of unnecessary function words from the text that provide no extra meaning to the text, rather only modifying or indicating grammatical relationships; is called stopping.

; Stemming: Stemming considers the morphology, or internal structure, of terms, and reduces each term to a root form for comparison based on its morphology, for example, a query term such as “orienteering” to match an occurrence of “orienteers”, or “runs” to match “running”.

; Rules used by Porter Stemmer: *sses -> ss *ies -> i

Devangi, Pranjali, Mustafa<br>

1. Suggest a data structure that could be used to implement an inverted index in PHP, and give a working code <br>snippet to show how to implement first(t), last(t) from our inverted index ADT.<br><br>

According to the slides: "All PHP arrays can be viewed as associative arrays". <br> We will thus use an associative array for our inverted index and indexed arrays for the posting list within the index.<br><br>

// assume our associated array inverted index is globally accessible and referred to as inverted_index<br><br> function first(t) {<br> if (array_key_exists(t, inverted_index))<br> return reset(inverted_index[t]);<br> return false;<br> }<br> <br> function last(t) {<br> if (array_key_exists(t, inverted_index))<br> return end(inverted_index[$t]);<br> return false;<br> }<br><br>

Austin Anderson, Justin Chang, Vaishnavi Nagireddy

6.Define the following terms (1pt each): (a) docid index, (b) frequency index, (c) positional index, and (d) schema-independent index.

Docid index: A docid index is the simplest type of inverted index. For each term, it contains the document identifiers of all documents in which the term appears.

Example: let’s consider some terms “a”,”am”,”good”. A docid index consists of the document id which gives the document number in which the term appears.

Frequency index: In a frequency index, each entry in an inverted list consists of two components: a document ID and a term frequency value. Each posting in a frequency index is of the form (d, ft_d).

Example: If we have a document containing terms in it, our frequency index looks like

Positional index: A positional index consists of postings of the form (document,frequency of term in that document, (term’s posting list)) and it also supports all search operations supported by a frequency index.

Example: A positional list for terms “better”,”do”,”good”,”man” will look like

Schema-independent index: A schema-independent index considers the whole corpus as a single document. So, it contains word's positions of the individual term occurrences.

Example: A schema-independent index for our terms “a”,”am”,”as” will be like

Question 1

by Kevin Schumacher, William Wang, Paaras Chad

a.) Probability Ranking Principle definition: A query response is most useful to a user if it ranks the documents in descending relevance. The query “search engine” could return search pages and have informational pages describing how a search engine works. This is an example of probability ranking principle because the most relevant items (actual search engines) are at the top while slightly less relevant items like how a search engine works are just below it in relevancy and in result order.

b.)Specificity definition: We only want relevant information. Query “Covid-19” returns the CDC’s Covid response page. This example of specificity because the CDC is the greatest authority on Covid and will therefore have the most relevant information.

c.)Exhaustivity definition: Give all of the possible results on a topic. The query “All dogs go to heaven” returns all documents that contain the phrase. This is an example of exhaustivity because all of the possible results are given in the output.

d.) Novelty definition: Don’t just repeat information, each result should give new information. For the query “Covid-19 news” it should return articles like case count in March and another article case count in February. This is an example of novelty because the results doesn’t return 50 articles from about the case count in March.

Austin, Vaishnavi, Justin

	Prev(term, pos)
	If( term doesn’t exist OR first occurrence of term is after pos)
		Return -inf
	If(last occurrence of term is before current)
		Return last occurrence of term

	Initialize high to the length of term's posting list
	Initialize jump to -1
	Initialize low to high + jump

	While (low is greater than 0 and the positon of the term at index low is greater than or equal to current)
		Set high to be equal to low
		Set jump to be twice its previous value
		Set low to be itself plus jump
	If (low is less than 0)
		Set low to be 0
	Use binarySearch on the window of low->high to find the highest index of term whose position is before current
	Return the position of the term at index returned by binarySearch

Question 2

by Kevin Schumacher, William Wang, Paaras Chad

Relentless, insatiable deadlines!

This manuscript's still full of red lines.

First I'll sweat through the edits

and check all the credits

then chill with my favorite red wine

28 total words

All bigrams have a M1 of 1. Except for M1(“red lines.”), M1(“the edits”), M1(“ the credits”), M1(“red wine”) all of these are equal to 1/2.

The MLE of the second line is (1/28)^6 • (1/14) = (1/6746464256) = 1.48 • 10 ^ (-10)

By Vrinda and Sriramm ; : Q10. Briefly explain and give example of the following (1pt each): (a) sort-based dictionary, (b) per-term index, (c) move-to-front heuristic, (d) merge based index construction.

; : (a) sort-based dictionary - In sort-based dictionaries, the terms that appear in the text collection are sorted in the form of an array or a search tree. Traversal is done through tree traversal. The problems with sort based dictionaries are that all the values should be of the same size. To overcome this problem, we use two arrays- a primary array that contains integers which point to a secondary array containing the actual terms. ; : For example: ; : Sorted dictionary in memory looks like: ; : absence -> 2345, absent -> 26783, …, shake -> 456, shaken -> 1672, shakespeare -> 89541, … zygote -> 6734, zygotes -> 1333. ; : Dictionary on disk has “absence” and “absent” nearby and similarly “shake”, “shaken”, “shakespeare”. So, this sort-based lookup makes searching for terms like “absen*” and “shake*” easier.

;

: (b) per-term index - per-term index is a set of positions of the terms that are kept as a synchronisation points (something like checkpoints) such that we do not have to go through the entire partitions of the disks to find the position. ; : For example, the per term indices for “widget” in a document are 12334, 13456, 34598. So, consider that the disk has three partitions. There are 15 other positions at which the term occurs. If we need next(“widget”, 25987), we would know that we have to start searching between 13456 and 34598. ; : ;

: (c) move-to-front heuristic - In the “move-to-front” heuristic, the terms are inserted at the back of the list. The terms will be moved to the front of the lists when they are searched. So, the next time when the term is looked up or searched, it will be present in the beginning of the list. ; : For example, if a new term(in our context) such as “Aztec” is encountered, it is initially inserted at the end of the list. When the term is searched for the first time, it is moved to the front of the posting list, such that when the lookup happens again, the term will be present in the front of the list. ; : ;

: (d)Merge-based index - merge-based index is similar to hash-based indexing, in the way that if the index list is small, it can fit into the memory (main memory) and if not, it uses dynamic partitioning to build an in-memory index and as soon as it runs out of memory, it builds an on-disk inverted file by transferring the in-memory index data to disk, deletes the in-memory index, and continues indexing. This procedure is repeated until the whole collection has been indexed, resulting in a set of index files, each representing a part of the whole collection, called an index partition. In a final step, the index partitions are merged into the final index. When we do lookups, we have to search through these index partitions of disk. The posting lists are sorted lexicographically and stored in the disk partitions. ; : For Example: Let the max amount of in-memory words be 6. ; : Text - ; : Doc1: “Do you quarrel, sir? ; : Doc2: “If you do, stay here, if not, then go.” ; : Doc3: “Try sir.” ; : Partition 1: ; : do - [(1, 1)] ; : you - [(1, 2)] ; : quarrel - [(1, 3)] ; : sir - [(1, 4)] ; : Partition 2: ; : if - [(2, 1), (2, 6)] ; : you - [(2, 2)] ; : do - [(2, 3)] ; : stay - [(2, 4)] ; : here - [(2, 5)] ; : not - [(2, 7)] ; : then - [(2, 8)] ; : go - [(2, 9)] ; : Partition 3: ; : try - [(3, 1)] ; : sir - [(3, 2)] ; : Recombining: ; : { do: [(1, 1), (2, 3)], go: [(2, 9)], here: [(2, 5)], if: [(2, 1), (2, 6)], not: [(2, 7)], quarrel: [(1, 3)], sir: [(1, 4), (3, 2)], stay: [(2, 4)], then: [(2, 8)], try: [(3, 1)], you: [(1, 2), (2, 2)] }