CS336 intelligent Information Retrieval: MidtermMarch 10th 20081. (20 points) Huffman coding. Build a decoding tree, complete thecoding table and encode the following strings: (1) highhgih (2) bbaicdffe2. (30 points) Given the following document, what are the tokens/terms left for indexing after the five steps of document preprocessing. You should describe the specific operations at each step and then apply them manually to the document. For the stemming part, you can use existing stemming tools on the Internetto figure out the stem for each word.An Eritrean rebel group that has waged Africa's longest civil war has agreed to negotiatewith the Ethiopian government for an end to the 26-year-old rebellion, a Sudanese newspaper reported Sunday. Omar Reyh, chairman of the Eritrean Liberation Front-Unified Organization, said Sudan proposed the talks after a recent visit to Khartoum by an Ethiopian delegation, theAl-Siyassa newspaper reported. The newspaper quoted Reyh as saying he met Saturday with Sudanese Prime Minister Sadek Mahdi, who suggested Sudan as the site for the negotiations.3. (20 points). Evaluate the performance of three rankings using average precision and the F measure, and then compare these two measures.•Let, Rq = {d3, d5, d9, d25, d44}, the set of relevant documents•|Rq| = 5, number of relevant documents for q• Ranking A: d3, d5, d91, d15, d9, d44, d56, d711, d8, d25,•Ranking B: d13, d5, d9, d25, d319, d3, d516, d44, d81, d23,•Ranking C: d3, d5, d9, d25, d319,4. (20 points) Explain the inverted list that is used to index documents. Describe and compare three data structures that can be used to store the word entries for the inverted list. Which one do you prefer and why?5. (10 points) In the Vector-space retrieval model, how do you represent documents and query? How do you calculate the similarity between a document and a