program.py

import re, sys # ree.. sys.. puffs

pennTB_tags = []
# dictionaries for calculating likelihood probabilities
likelihood, likelihood_totals = {}, {} 

# dictionaries for calculating transition probabilities
# e.g., P("fish"|verb)
transition, transition_totals = {}, {} 

# for the transition dictionary, we need to add the non-PennTreeBank tag, "begin-sentence"
transition['BS'], transition_totals['BS']= {}, 0

# a dictionary that all seen words from the training corpus will be added to.
# (used a dictionary instead of a list for faster look-up later, for determining OOV words)
encountered_words = {}

sentences = [] # should look like ["fish", "sleep", ".", "\n"] 
result_tags = [] # should look like ["NN", "VB", "." ] 


def train(training_corpus):
    
    # from hardcoding
    # for tag in pennTB_tags:
    #     likelihood[tag], likelihood_totals[tag] = {}, 0
    #     transition[tag], transition_totals[tag] = {}, 0

    # what this block of code does (it's messy but i think it works)
    # opens the training corpus (e.g., WSJ_02-21.pos or fishsleeptraining.pos)
    # for each line in the file, populate the likelihood and transition dictionaries with the seen word and seen tag. 
    prev_tag = '\n'
    with open(training_corpus, 'r') as fi: 
        
        for line in fi:
            line_list = line.strip("\n").split("\t")

            if len(line_list) == 2: 
                cur_word, cur_tag = line_list[0].lower(), line_list[1]

                if cur_tag not in pennTB_tags:
                    pennTB_tags.append(cur_tag)
                    likelihood[cur_tag] = {}
                    likelihood_totals[cur_tag] = 0
                    transition[cur_tag] = {}
                    transition_totals[cur_tag] = 0

                if cur_word not in encountered_words:
                    encountered_words[cur_word] = 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
                if prev_tag == '\n': # beginning of sentence 
                    transition['BS'][cur_tag] = transition['BS'].setdefault(cur_tag,0) + 1
                    transition_totals['BS'] = transition_totals.setdefault('BS', 0) + 1
                else:
                    transition[prev_tag][cur_tag] = transition[prev_tag].setdefault(cur_tag,0)+1
                    transition_totals[prev_tag] = transition_totals.setdefault(cur_tag, 0) + 1
                prev_tag = cur_tag



    # comment these out to see a snippet of the populated "likelihood" and "transition" dictionaries
   
    # print('likelihood dict:\n')
    # print(likelihood['IN'])
    '''
    sample result:
    {'in': 16697, 'of': 23001, 'at': 4700, 'by': 4625, 'about': 1580, 'for': 8439, 'from': 4501, 'on': 5217, 'as': 3821, 'that': 4840, 'among': 417, 'against': 500, 'since': 559, 'within': 201, 'after': 1077, 'until': 306, 'than': 1608, 'under': 667, 'if': 1202, 'while': 657, 'around': 179, 'with': 4396, 'into': 921, 'because': 1026, 'so': 154, 'like': 425, 'though': 235, 'through': 559, 'over': 738, 'before': 508, 'during': 437, 'without': 275, 'beyond': 76, 'along': 107, 'out': 355, 'between': 482, 'next': 81, 'except': 55, 'behind': 80, 'whether': 257, 'near': 83, 'although': 268, 'up': 279, 'despite': 209, 'above': 143, 'below': 132, 'across': 73, 'off': 116, 'atop': 5, 'amid': 63, 'once': 39, 'unless': 87, 'unlike': 58, 'throughout': 53, 'toward': 134, 'but': 8, 'per': 97, 'down': 144, 'outside': 69, 'via': 157, 'alongside': 5, 'besides': 29, 'upon': 37, 'towards': 5, 'worth': 7, 'aboard': 6, 'de': 27, 'inside': 26, 'onto': 28, 'vs': 9, 'past': 14, 'en': 5, 'then': 1, 'lest': 2, 'whereas': 3, 'plus': 10, 'ago': 113, 'albeit': 4, 'a\\/k\\/a': 1, 'beside': 4, 'becase': 1, 'fiscal': 1, 'versus': 1, 'underneath': 2, "'til": 1, 'notwithstanding': 5, 'par': 1, 'pending': 1, 'beneath': 10, 'till': 5, 'minus': 1, 'nearer': 1, 'opposite': 1, 'post': 1, 'neither': 1, 'amongst': 1, 'v': 1, 'save': 1, 'astride': 2, 'expect': 1, 'nearest': 1}
    '''

    # print('\n\ntransition dict:\n')
    # print(transition['DT'])
    '''
    sample result: 
    {'NNP': 8363, 'NN': 39609, 'JJ': 18603, 'NNPS': 420, 'VBN': 874, 'NNS': 6086, 'CD': 2294, 'WP': 69, 'RBR': 164, 'VBG': 674, 'JJR': 546, 'WRB': 9, 'IN': 961, 'RBS': 229, 'DT': 237, 'VBZ': 759, 'MD': 222, 'JJS': 781, 'TO': 53, 'VBP': 171, 'PRP$': 66, 'PRP': 116, 'VBD': 245, 'CC': 183, 'FW': 24, 'VB': 33, 'WDT': 19, 'POS': 15, 'EX': 6, 'UH': 3, 'RP': 6, 'PDT': 2}
    '''
 
    # now, we get the probabilities by doing freq/total 
    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]
    
    # print(pennTB_tags)
    # print(encountered_words)
    print("HERE!")
    # print(likelihood)
    # print(transition)

    # print("\n\nlikelihood dictionary:\n",likelihood)
    # print("\n\ntransition dictionary:\n",transition)

    fi.close()
# END of TRAINING STAGE of program

   
# START of TRANSDUCER STAGE of program
def test(test_corpus):

    def print_table(chart):
        print("\n\n")
        for row in chart:
            print(row, '\n')
        print('\n')

    def populate_table(table, cur_sent):
        def backtrack(table): 
            for index, word in enumerate(cur_sent): # 0'fish', 1'sleep'
                sentences.append(word)
                cur_word_max = 0
                cur_word_likeliest_tag = ""
                for row in range(1, len(table)-1): # rows: 1 - 2: 1:NN, 2:VB, 
                    if table[row][index+1] > cur_word_max: # index+1==word_to_token_num[word]
                        cur_word_max = table[row][index+1]
                        cur_word_likeliest_tag = seen_tags[row-1]

                result_tags.append(cur_word_likeliest_tag)
            print(sentences)
            print(result_tags)
        
        
    # TODO_ FIX:
        word_to_token_num = {}
        for i, word in enumerate(cur_sent): # 0:fish, 1: sleep
            word_to_token_num[word] = i+1 
        # word_to_token_num = {fish:1, sleep}

        num_rows = len(table) 
        num_cols = len(table[0])
        rows = seen_tags # e.g., [NN, VB]

        table[0][0] = 1 # make the first entry, in the 'start' colun
        # print(transition)

        for index, word in enumerate(cur_sent):
            pass
        for word in cur_sent: # e.g., fish', 'sleep'
            cur_col = word_to_token_num[word]  #cur_col == token number
            
            for cur_row in range(1, len(seen_tags) + 1): #1..2
                # print("cur row, cur col: ", cur_row, cur_col)
                
                if cur_row == 1: 
                    if rows[cur_row-1] in transition['BS']:
                        # print('seen tag: ', rows[cur_row-1])
                        transitional_probability = transition['BS'].setdefault(rows[cur_row-1], 1)
                    else:
                        transitional_probability = 1

                    # print("transitional: " , transitional_probability)
                    
                    emission_probability = likelihood[rows[cur_row-1]].setdefault(word, 1/1000)# P('fish'|verb)
                    # print("emission_probabilty = ", emission_probability)
                    table[cur_row][cur_col] = max(table[cur_row][cur_col], transitional_probability * emission_probability) 
                else: 
                    # to fill table[cur_row = verb][cur_col = 2]:
                    prev_score = table[cur_row][cur_col-1]
                    if rows[cur_row-1] in transition['BS']: # !!!!!!!!!!! ok this is wrong. but idk what to replace it with
                        transitional_probability = transition['BS'].setdefault(rows[cur_row-1], 1)
                    else:
                        transitional_probability = 1 
                    """
                    for some reason, even with a training corpus of 3K words, most of the viterbi table emission_p values are 1/1000
                    and most transitional_probabilities are 1 (see above)"""
                    emission_probability = likelihood[rows[cur_row-1]].setdefault(word, 1/1000)# P('fish'|verb)
                    table[cur_row][cur_col] = max(table[cur_row][cur_col], transitional_probability * emission_probability) 
        
        #fill last column
        last_token_column = num_cols -2
        max_in_last_token_col = -1
        # back_index = 
        for r in range(len(table)): # r: 0, 1, 2, 3 
            # print(table[r][last_token_column])
            max_in_last_token_col = max(table[r][last_token_column], max_in_last_token_col)
            table[num_rows-1][num_cols-1] = max_in_last_token_col
       
        # print(seen_tags)
        
        backtrack(table)
        
    cur_sent = []
    with open(test_corpus, 'r') as file_in:
        for word in file_in:
            if word != '\n': # word is still part of current sentence
                cur_sent.append(word.replace('\n',''))
            
            else: # word == '\n'; end of current sentence
        
                
                # cur_sent = [] do this at end. 

                # make a chart with len(cur_sent) + 2 col, num(trained_tags) rows
                seen_tags = []
                for tag in pennTB_tags:
                    if likelihood[tag] != {}:
                        seen_tags.append(tag)

                rows, cols = len(seen_tags) + 2, len(cur_sent) + 2

                viterbi_chart = [[0]*cols for i in range(rows)]
                print_table(viterbi_chart)
          
                populate_table(viterbi_chart, cur_sent)
                print_table(viterbi_chart)

                #cur_sent = [] #uncomment this out later.
    file_in.close()


if __name__ == '__main__':
    #print('enter: python3 program.py WSJ_02-21.pos WSJ_24.words')

    training_corpus_input = sys.argv[1] # we expect a training corpus
    test_corpus_input = sys.argv[2] # and a test corpus, in that order

    train(training_corpus_input)
    test(test_corpus_input)

    # tagged_corpus = open("submission.pos", "w")
    # # again this does NOT handle punctuation or '\n' , i'm manually adding a \n at the end of each sentence
    # for i in range(len(sentences)):
    #     cur_word = sentences[i]
        
    #     tagged_corpus.write(cur_word + '\t' + result_tags[i])
    #     tagged_corpus.write('\n')
    #     # print(cur_word + '\t' + result_tags[i])
    
    # tagged_corpus.close()

    # python3 program.py shorterWSJ_02-21.pos shorterWSJ_24.words
    # python3 program.py FStrain.pos FStest.words