使用Stemming和Part-Of-Speech算法进行文本分析。
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.
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.
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:
- Form ‘0’ is the past tense form (e.g., “sold”);
- Form ‘1’ is the past participle form (e.g, “sold”);
- Form ‘2’ is the present participle form (e.g., “selling”);
- 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.)
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.
Stage 1 - Read One Dictionary Word
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==========================
Word 0: allocate
POS: vt
Form: 0allocated1allocated2allocating
Stage 2 - Read the Whole Dictionary
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
Stage 3 - POS-Tag the Words in Sentence
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() function, 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.
Stage 4 - Stem the Words in Sentence
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 pointers to customise the behaviour of the binary search function for different use cases.
Submission and Assessment
This assignment is worth 15% of the final mark. A detailed marking scheme will be provided on Canvas.
You need to submit your code in Grok Learning for assessment. Submission will NOT be done via Canvas. Instead, you will need to:
- Log in to Grok Learning using your student login details.
- Navigate to the Assignment 2 module of our subject COMP10002 2021 S1: Foundations of Algorithms.
- Place all your code in the program.c tab window (including any function from listops.c used).
- Compile your code by clicking on the Compile button.
- Once the compilation is successful, click on the Mark button to submit your code. (You can submit as many times as you want to. Only the last submission made before the deadline will be marked. Submissions made after the deadline will be marked with late penalties as detailed at the end of this document. Do not press the Mark button after the deadline unless a late submission is intended.)
- Two sample tests will be run automatically after you make a submission. Make sure that your submission passes these sample tests.
- Two hidden tests will be run for marking purpose. Results of these tests will not be available until after the submissions are marked.
You can (and should) submit both early and often - to check that your program compiles correctly on our test system, which may have some different characteristics to the lab machines and your own machines.
You will be given a sample test file test0.txt and the sample output test0-output.txt. You can test your code on your own machine with the following command and compare the output with test0-output.txt:
mac: ./program < test0.txt /* Here '<' feeds the data from test0.txt into program */
Note that we are using the following command to compile your code on the submission system (we name the source code file program.c).
gcc -Wall -std=c99 -o program program.c
The flag “-std=c99” enables the compiler to use a more modern standard of the C language - C99. To ensure that your submission works properly on the submission system, you should use this command to compile your code on your local machine as well.