program1.py

import re, sys 

seen_tags = {}
likelihood, likelihood_totals = {}, {} # latter hash map is for calculating probabilities
transition, transition_totals = {}, {}
transition['BS'], transition_totals['BS'] = {}, 0
transition['ES'] = {}
transition_totals['ES'] = 0

likelihood['BS'] = {}
likelihood_totals['BS'] = 0
likelihood['ES'] = {}
likelihood_totals['ES'] = 0

seen_words = {}

def train(training_corpus):
    with open(training_corpus, 'r') as fi: 
        prev_tag = 'BS'
        for line in fi:
            if line != '\n':
                # print(line)
                split_line = line.strip('\n').split()
                # print(split_line)
                if len(split_line) == 2:
                    cur_word = split_line[0].lower()
                    cur_tag = split_line[1]
                    # print('cur_word: ', cur_word)
                    # print('cur_tag: ', cur_tag)
                    if cur_word not in seen_words:
                        seen_words[cur_word] = 1

                    if cur_tag not in seen_tags: # handle all new tags
                        seen_tags[cur_tag] = 1
                        likelihood[cur_tag] = {}
                        likelihood_totals[cur_tag] = 0
                        transition[cur_tag] = {}
                        transition_totals[cur_tag] = 0
                
                    # likelihood['IN'] -> {'in':1}
                    likelihood[cur_tag][cur_word] = likelihood[cur_tag].setdefault(cur_word, 0) + 1
                    likelihood_totals[cur_tag] = likelihood_totals.setdefault(cur_tag, 0) + 1

                    # transition['BS'] -> {'IN':1}
                    transition[prev_tag][cur_tag] = transition[prev_tag].setdefault(cur_tag,0)  + 1
                    transition_totals[prev_tag] = transition_totals.setdefault(prev_tag, 0) + 1 
                    # In    IN
                    # an    DT
                    # ... .
                    prev_tag = cur_tag
            else: # line is '\n', meaning a sentence has ended
                cur_tag = 'ES'
                cur_word = ''
                likelihood['ES'][cur_word] = likelihood[cur_tag].setdefault(cur_word, 0) + 1
                likelihood_totals['ES'] = likelihood_totals.setdefault(cur_tag, 0) + 1

                transition[prev_tag][cur_tag] = transition[prev_tag].setdefault(cur_tag,0)  + 1
                transition_totals[prev_tag] = transition_totals.setdefault(prev_tag, 0) + 1 
                prev_tag = 'BS'

        for key in likelihood.keys(): 
            for entry in likelihood[key]:
                likelihood[key][entry] = likelihood[key][entry] / likelihood_totals[key]

        for key in transition.keys():
            for entry in transition[key]:
                transition[key][entry] = transition[key][entry] / transition_totals[key]
       
    fi.close()


def transduce(test_corpus):
    sentences = []
    with open(test_corpus, 'r') as fi: 
        cur_sentence = ['BS']
        for line in fi:
            if line == '\n':
                cur_sentence.append('ES')
                sentences.append(cur_sentence)
                cur_sentence = ['BS']
            else:
                cur_sentence.append(line.strip('\n'))
    fi.close()
    for sentence in sentences:
        make_table(sentence)
        

def make_table(sentence):
    # print('!!: ', sentence)
    tags_list = list(seen_tags.keys())
    rows = len(tags_list) + 2 # 'seen_tags' doesn't include 'BS', 'ES' 
    # sample seen_tags: 
    # ['IN', 'DT', 'NNP', 'CD', 'NN', '``', "''", 'POS', '(', 'VBN', 'NNS', 'VBP', ',', 'CC', ')', 'VBD', 'RB', 'TO', '.', 'VBZ', 'NNPS', 'PRP', 'PRP$', 'VB', 'JJ', 'MD', 'VBG', 'RBR']
    cols = len(sentence) # 'sentence' starts with 'BS', ends with 'ES'
    table = [[0] * cols for i in range(rows)]
    table[0][0] = 1

    '''
    For all states at position 1, multiply transition probability from Start (position 0) by
    likelihood that word at position 1 occurs in that state. Choose highest score for each cell.

    - Iterate 'table' based on 'tag_list'.
    - All further comments in this section are based on this sample tag_list

    - e.g., # ['IN', 'DT', 'NNP', 'CD', 'NN', '``', "''", 'POS', '(', 'VBN', 'NNS', 'VBP', ',', 'CC', ')', 'VBD', 'RB', 'TO', '.', 'VBZ', 'NNPS', 'PRP', 'PRP$', 'VB', 'JJ', 'MD', 'VBG', 'RBR']
    - len(tag_list) = 28
    '''
    cur_col = 1
    # print(transition['BS'])
    for r in range(len(tags_list)): # 0, 27
        cur_tag = tags_list[r] # 'IN', 'DT', ... 
        cur_row = r + 1 # 1, 28

        prev_tag = 'BS' 
        cur_trans_prob = transition[prev_tag].setdefault(cur_tag, 0)
        # print(cur_trans_prob)
        table[cur_row][cur_col] = max(cur_trans_prob, table[cur_row][cur_col])
    ''' 
    For n from 2 up to 'end' column -- not including end column.
    • for each cell [n,s] in column n and each state [n-1,s'] in column n-1:
    • get the product of:
        – likelihood that token n occurs in state s
        – the transition probability from s' to s
        – the score stored in [n-1,s']
    • At each position [n,s], record the max of the s scores calculated

    e.g., 
    sentence: ['BS', 'Ms.', 'Haag', 'plays', 'Elianti', '.', 'ES']
    len(sentence) = 7
    tags_list: ['NNP', 'VBZ', '.']
    '''
    for cur_col in range(2, len(sentence)-1): # 2, 3, 4, 5
        cur_word = sentence[cur_col] # plays, Elianti, ., 
        if cur_word in '$#"()\'.:':
            # TODO: hard code this later, when writing to file 
            pass
        for p in range(len(tags_list)): # 0, 1, 2
            prev_tag = tags_list[p] # 'NNP', 'VBZ', '.'
            for r in range(len(tags_list)): # 0, 1, 2
                cur_tag = tags_list[r] # 'NNP', 'VBZ', '.'
                cur_row = r + 1 # 1, 2, 3

                cur_trans_prob = transition[prev_tag].setdefault(cur_tag, 1/2000000)
                cur_likely_prob = likelihood[cur_tag].setdefault(cur_word, 1/2000000)
                prev_tag_prob = table[p+1][cur_col-1]
                cur_product = cur_trans_prob * cur_likely_prob * prev_tag_prob
                # if prev_tag == 'NNP':
                #     print('prev_tag: ', prev_tag, '  cur_tag: ', cur_tag, '  cur_trans_prob: ', cur_trans_prob, '  cur max: ', table[cur_row][cur_col])
                table[cur_row][cur_col] = max(cur_product, table[cur_row][cur_col])
    
    ''' Write to file '''
    results = []
    # after each column, get col_max probability and col_max_tag, save the latter, and write to file.
    for c in range(1, len(sentence)-1): # 1, ... 5
        col_max = 0
        col_max_tag = ''
        cur_word = sentence[c]

        if cur_word == '``':
            cur_tag = '``'
        elif cur_word[len(cur_word)-1:] == '$':
            cur_tag = '$'
        elif cur_word == '(':
            cur_tag = '('
        elif cur_word =='--':
            cur_tag = ':'
        elif cur_word.lower() in ['if', 'in', 'of', 'by', 'at', 'about', 'as', '@', 'for', 'after', 'ago', 'down', 'around']:
            cur_tag = 'IN'
        elif cur_word in ['I', 'you', 'he', 'she', 'they']:
            cur_tag = 'PRP'
        elif cur_word.lower() in ['his', 'her', 'their', 'my', 'our', 'your']:
            cur_tag = 'PRP$'
        elif cur_word == 'To':
            cur_tag = 'TO'
        elif cur_word.lower() in ['but', 'and', 'or', 'either', 'vs.']:
            cur_tag = 'CC'
        elif cur_word in ['American', 'Canadian', 'Japanese', 'European', 'African', 'Asian', 'French', 'British', 'Chinese', 'national']:
            cur_tag = 'JJ'
        elif cur_word.lower() in ['la', 'de']:
            cur_tag = 'FW'
        elif cur_word.lower() in ['one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine', 'ten']:
            cur_tag = 'CD'
        elif len(cur_word) == 1 and cur_word in ['b','c','d','e','f','g','h','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']:
            cur_tag = 'SYM'
        elif cur_word == 'more' or cur_word == 'less':
            cur_tag = 'RBR'
        elif cur_word.lower() == 'nevertheless':
            cur_tag = 'RB'
        elif (cur_word[0:1].isupper() and c > 1 and sentence[c-1] != '--' and sentence[c-1] != '(') or (cur_word in ['January', 'February', 'March', 'April', 'May', 'June', 'July', 'August', 'September', 'October', 'November', 'December', 'Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Mr.', 'Ms.', 'Mrs.', 'Sen.']):
            cur_tag = 'NNP'
        elif '-' in cur_word and cur_word[0:1].isupper():
            cur_tag = 'JJ'
        else:
            for r in range(len(tags_list)):
                cur_row = r+1
                cur_tag = tags_list[r]
                if table[cur_row][c] > col_max:
                    col_max = table[cur_row][c]
                    col_max_tag = cur_tag
                cur_tag = f'{col_max_tag}'
        #print(cur_word, " -- ", col_max_tag) 
        results.append(f'{cur_word}\t{cur_tag}')
    output_file = open('test_output.pos', 'a', encoding='utf-8')
    for result in results:
        output_file.write(result +"\n")
    output_file.write('\n')
    output_file.close()

    '''
    Ms.     NNP 8    DT
    Haag    NNP 8    IN
    plays   VBZ 8    IN
    Elianti NNP 8    IN
    .       . 8      IN
    '''

    # for row in table:
    #     print(row)

    # print(tags_list)
if __name__ == '__main__':
    #print('enter: python3 program1.py shorterWSJ_02-21.pos shorterWSJ_24.words')
    # python3 program1.py WSJ_02-21.pos WSJ_24.words
    training_corpus = sys.argv[1] 
    test_corpus= sys.argv[2] 

    output_file = open('test_output.pos', 'w')
    output_file.close()

    train(training_corpus)
    transduce(test_corpus)