Please read the 'assignment - README.pdf' file, it will contain the instructions. This is for a beginner/intermediate, its not that difficult, it shouldnt take long. You need to write the program by creating a program.c file. There are two sample inputs (test0.txt and test1.txt) and two sample outputs (test0-output.txt and test1-output.txt), make sure you read the pdf file first to make you understand. You dont need to create an output file, just create the output in terminal when you run the program. There is a listops.rtf file, this should be a listops.c, and should use it for stage 3. Dont use fgets(), or any file I/O commands, its not needed. Just use getchar(). Thank you. My email is:
[email protected]The University of Melbourne School of Computing and Information Systems COMP10002 Foundations of Algorithms Semester 1, 2021 Assignment 2 Due: 4pm Tuesday 25th May 2021 Version 1.0 1 Learning Outcomes In this assignment you will demonstrate your understanding of dynamic memory allocation, linked data structures, and search algorithms. You will further extend your skills in program design and implementation. 2 The Story... Text analysis and understanding is becoming prevalent in our daily lives. For example, intelligent personal assistant apps such as Apple Siri and Google Now process user requests by first converting voice to text with a speech recognition algorithm, and then analysing the text and finding answers to the requests. Finally, the answers found are read out by a text to speech (TTS) algorithm. To help computers understand a sentence, there are a few standard preprocessing steps. Two preprocessing steps of interest in this assignment are called stemming and Part-Of-Speech (POS) tagging. Stemming reduces a word to its stem (that is, the root form). See the following example: Sentence: After stemming: she she sells sell seashells seashell Here, “sells” is the third-person present form of “sell”; “seashells” is the plural form of “seashell”. After stemming, the two words are reduced to their respective root forms. The word “she” is already in its root form, and hence is unchanged. POS tagging assigns parts of speech to each word, such as noun, verb, etc. See the following example: Sentence: POS tag she pronoun sells verb seashells noun There are various algorithms for stemming and POS tagging. The core of those algorithms are linguistic rules (such as “remove the ending ‘s’ of a plural noun to obtain its singular form”) and statistics (such as how often “cook” is used as a verb instead of a noun). Dictionaries are also used to support those algorithms. In this assignment, you will implement an algorithm for stemming and POS tagging using a dictionary. Note that you do not need to have any knowledge in linguistics to complete this assignment. 1 Oumar Al Arabi Oumar Al Arabi Oumar Al Arabi Oumar Al Arabi Oumar Al Arabi Oumar Al Arabi Oumar Al Arabi Oumar Al Arabi Oumar Al Arabi 3 Your Task You are given a dictionary (with at least one and up to 100 unique words) and a sentence to be processed in the following format. $allocate vt #0allocated1allocated2allocating $sell vt vi n #0sold1sold2selling3sells $she n pron #3they $the art # $zebra n #3zebra ********** she sells seashells The input starts with a list of unique dictionary words sorted alphabetically. Each word takes three lines. Line 1 starts with ‘$’, which indicates the start of a word and is followed by the word itself (e.g., “sell”). There are up to 22 lower-case English letters in each word, with no upper-case letters or special characters. Line 2 contains the possible POS tags of the word separated by space (e.g., “vt”, “vi”, and “n” represent verb used with object, verb used without object, and noun, respectively). You may assume up to 5 POS tags per word and up to 4 lower-case English letters per POS tag. (Hint: You may use either a single string or an array of strings to store the POS tags – the former is simpler.) Line 3 starts with ‘#’, which indicates the ending line of a word in the dictionary. It is followed by the variation forms of the word. Each word can have up to 4 forms where each variation form may contain up to 25 lower-case English letters: 1. Form ‘0’ is the past tense form (e.g., “sold”); 2. Form ‘1’ is the past participle form (e.g, “sold”); 3. Form ‘2’ is the present participle form (e.g., “selling”); 4. Form ‘3’ is the plural form (e.g., “sells”, note this is not the third-person present form). The variation forms follow the rules below: • A word may have (1) no variation forms, (2) the first three forms (such as a verb), (3) only the last form (such as a noun), or (4) all four forms (such as a word that can be either a verb or a noun). You do not need to check the POS tags to verify the variation forms that a word has. • The forms of a word always appears in the ascending order, e.g., “$0sold1sold2selling3sells”, not “$3sells0sold2selling1sold”. • The variation forms of a word can be the same (e.g., Forms 0 and 1 of “sell” are both “sold”). • A variation form of a word can be the word itself (e.g., Form 3 of “zebra” is still “zebra”). • You may assume that any two words in the dictionary will not share the same variation forms (e.g., the variation forms of “allocate” and “sell” are all different). You may also assume that any word will not be a variation form of another word (e.g., “allocate” is not a variation form of any other word in the dictionary). (Hint: You do not need to understand what these variation forms mean for the assignment. You may simply use a single string to store all variation forms of a word. For Stage 4, optionally, you can separate the different variation forms and store them in multiple strings, which will help make the search process faster.) 2 The line “**********” indicates the end of the dictionary and the start of a given sentence. The sentence given will occupy one line, where the words are separated by a single space. The sentence will contain at least one word, but there is no upper limit on the number of words or the number of characters in the sentence. Each word may contain up to 25 lower-case English letters. There will be no punctuation marks (e.g., ‘,’ or ‘.’). You will perform stemming and POS tagging on the sentence by consulting the given dictionary. 3.1 Stage 1 - Read One Dictionary Word (Up to 3 Marks) Your first task is to design a struct to represent one word. You will then read in one word from the input data (using standard input functions with input redirection; no file input operations needed), and output it in the following format. ==========================Stage 1========================== /* 26 ‘=’s each side */ Word 0: allocate POS: vt Form: 0allocated1allocated2allocating 3.2 Stage 2 - Read the Whole Dictionary (Up to 7 Marks) Next, continue to finish reading the whole dictionary. You need to design a proper data structure to store the words read in. An array of struct’s will do the job nicely. When this stage is done, your program should output: the total number of words in the dictionary and the average number of variation forms per word (up to two digits after the decimal point, by using “%.2f” in the printf() function). The output of this stage based on the sample input is as follows. ==========================Stage 2========================== Number of words: 5 Average number of variation forms per word: 1.80 3.3 Stage 3 - POS-Tag the Words in Sentence (Up to 13 Marks) Your third task is to read in the given sentence, break it into words, store the words in a linked data structure, and output the words together with their POS tags one at a line. The output of your program in this stage for the example above should be: ==========================Stage 3========================== she n pron sells NOT_FOUND seashells NOT_FOUND Hint: You may used the getword() function (Figure 7.13 in the textbook, link to source code available in lecture slides) to read the words in the sentence. You may modify the linked list in listops.c (link to source code available in lecture slides) to store the words. You are free to use other linked data structures (e.g., queue, stack, etc) if you wish. Make sure to attribute the use of external code properly. For POS tagging, you will use the binary search algorithm (Hint: You may use the binary_search() func- tion, link to source code available in lecture slides, or bsearch() provided in stdlib.h) to look up each word from the sentence in the dictionary. If the word is found, then output the word and all POS tags of the word. If the word is not found, then output the word and “NOT_FOUND”. In this sample output, “sells” has not been matched because we are not considering the root forms of the words in this stage. In real systems, stemming should happen before POS tagging. This is because, without stemming, a word (e.g., “sells”) that is not in its root form may not be found in the dictionary. In this assignment, we perform POS tagging first because it is a simpler task. If you are not confident with using linked data structures, you may use an array of strings to store the words, assuming a maximum of 20 words in the sentence. However, if you do so, the full mark of this stage will be reduced by 2 marks. Similarly, if you use sequential search for POS tagging instead of binary search, the full mark of this stage will also be reduced by 2 marks. 3 3.4 Stage 4 - Stem the Words in Sentence (Up to 15 Marks) The final task is stemming, that is, for each word in the given sentence, you need to look up its root form from the dictionary, and output the root form. If a word is already in its root form, or the word cannot be found in the dictionary, then simply output the word itself as the root form. Further, you need to perform POS tagging on this root form. The output of your program in this stage for the example above should be as follows (note a final newline character ‘\n’ at the end of the output). ==========================Stage 4========================== she she n pron sells sell vt vi n seashells seashells NOT_FOUND At the end of your submission file, you need to add a comment that states the worst-case time complexity of your root form search algorithm, and explains why it has that time complexity, assuming that there are s words in the sentence and d words in the dictionary, each dictionary word has up to f variation forms, and each form has a maximum length of m characters. Hint: A simple approach is that, for every word in the sentence, apply sequential search on the dictionary words and variation forms to look up the word. This is allowed for Stage 4 and will not incur mark penalties. As a challenge (no bonus marks), see if you can use binary search instead of sequential search to find the root form, for better efficiency. Note: if you use binary search in both Stages 3 and 4, you should not write more than one binary search function. You should use function