Suppose you are to develop an indexing application with the following conditions

Question

Suppose you are to develop an indexing application with the following conditions:

Input: A document (i.e., a web page) with a known number of words

Output: An index corresponding to the words of the document and their frequencies.

An example would be the portion in the figure below, which is extracted from the SEUmain page.

The following is the IDs for the words mentioned in the above portion:

   1        …       11       …             14          

Experts …     Arabic   …     Standardized

1           …        2       …             1              

The output index consists of two integers separated by a colon. The index for the word “Arabic” is 11:2. The first number before the colon represents the word’s ID, and the second number is the word's frequency (means, telling how many times the word has occurred in the document.)

Which data structure would you select for your solution? Give 2 reasons to justify your answer?       

Explanation / Answer

Answer - We will use HashMap for the above indexing application.

1 HashMap is a data structure consisting of collection of Key,Value Pairs,

Here the key would be the actual word,And value would be the pair of id and count of word.

2 It is the best data structure that can be used in this situation in terms of the time complexity.Entire index can be created in linear time and If there are no or less collisions each search would give the desired result in constant time.

In case of any doubt mention in the comments,will be happy to help out.Also like the answer if it helped you :).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.