class_docstr: TnT - Statistical POS tagger
  
  IMPORTANT NOTES:
  
  * DOES NOT AUTOMATICALLY DEAL WITH UNSEEN WORDS
  
    - It is possible to provide an untrained POS tagger to
      create tags for unknown words, see __init__ function
  
  * SHOULD BE USED WITH SENTENCE-DELIMITED INPUT
  
    - Due to the nature of this tagger, it works best when
      trained over sentence delimited input.
    - However it still produces good results if the training
      data and testing data are separated on all punctuation eg: [,.?!]
    - Input for training is expected to be a list of sentences
      where each sentence is a list of (word, tag) tuples
    - Input for tag function is a single sentence
      Input for tagdata function is a list of sentences
      Output is of a similar form
  
  * Function provided to process text that is unsegmented
  
    - Please see basic_sent_chop()
  
  
  TnT uses a second order Markov model to produce tags for
  a sequence of input, specifically:
  
    argmax [Proj(P(t_i|t_i-1,t_i-2)P(w_i|t_i))] P(t_T+1 | t_T)
  
  IE: the maximum projection of a set of probabilities
  
  The set of possible tags for a given word is derived
  from the training data. It is the set of all tags
  that exact word has been assigned.
  
  To speed up and get more precision, we can use log addition
  to instead multiplication, specifically:
  
    argmax [Sigma(log(P(t_i|t_i-1,t_i-2))+log(P(w_i|t_i)))] +
           log(P(t_T+1|t_T))
  
  The probability of a tag for a given word is the linear
  interpolation of 3 markov models; a zero-order, first-order,
  and a second order model.
  
    P(t_i| t_i-1, t_i-2) = l1*P(t_i) + l2*P(t_i| t_i-1) +
                           l3*P(t_i| t_i-1, t_i-2)
  
  A beam search is used to limit the memory usage of the algorithm.
  The degree of the beam can be changed using N in the initialization.
  N represents the maximum number of possible solutions to maintain
  while tagging.
  
  It is possible to differentiate the tags which are assigned to
  capitalized words. However this does not result in a significant
  gain in the accuracy of the results.
class_docstr_tok: ["TnT","-","Statistical","POS","tagger","IMPORTANT","NOTES",":","*","DOES","NOT","AUTOMATICALLY","DEAL","WITH","UNSEEN","WORDS","-","It","is","possible","to","provide","an","untrained","POS","tagger","to","create","tags","for","unknown","words",",","see","__init__","function","*","SHOULD","BE","USED","WITH","SENTENCE-DELIMITED","INPUT","-","Due","to","the","nature","of","this","tagger",",","it","works","best","when","trained","over","sentence","delimited","input",".","-","However","it","still","produces","good","results","if","the","training","data","and","testing","data","are","separated","on","all","punctuation","eg",":","[",",",".","?","!","]","-","Input","for","training","is","expected","to","be","a","list","of","sentences","where","each","sentence","is","a","list","of","(","word",",","tag",")","tuples","-","Input","for","tag","function","is","a","single","sentence","Input","for","tagdata","function","is","a","list","of","sentences","Output","is","of","a","similar","form","*","Function","provided","to","process","text","that","is","unsegmented","-","Please","see","basic_sent_chop","(",")","TnT","uses","a","second","order","Markov","model","to","produce","tags","for","a","sequence","of","input",",","specifically",":","argmax","[","Proj","(","P","(","t_i|t_i-1",",","t_i-2",")","P","(","w_i|t_i",")",")","]","P","(","t_T+1","|","t_T",")","IE",":","the","maximum","projection","of","a","set","of","probabilities","The","set","of","possible","tags","for","a","given","word","is","derived","from","the","training","data",".","It","is","the","set","of","all","tags","that","exact","word","has","been","assigned",".","To","speed","up","and","get","more","precision",",","we","can","use","log","addition","to","instead","multiplication",",","specifically",":","argmax","[","Sigma","(","log","(","P","(","t_i|t_i-1",",","t_i-2",")",")","+log","(","P","(","w_i|t_i",")",")",")","]","+","log","(","P","(","t_T+1|t_T",")",")","The","probability","of","a","tag","for","a","given","word","is","the","linear","interpolation","of","3","markov","models",";","a","zero-order",",","first-order",",","and","a","second","order","model",".","P","(","t_i|","t_i-1",",","t_i-2",")","=","l1","*","P","(","t_i",")","+","l2","*","P","(","t_i|","t_i-1",")","+","l3","*","P","(","t_i|","t_i-1",",","t_i-2",")","A","beam","search","is","used","to","limit","the","memory","usage","of","the","algorithm",".","The","degree","of","the","beam","can","be","changed","using","N","in","the","initialization",".","N","represents","the","maximum","number","of","possible","solutions","to","maintain","while","tagging",".","It","is","possible","to","differentiate","the","tags","which","are","assigned","to","capitalized","words",".","However","this","does","not","result","in","a","significant","gain","in","the","accuracy","of","the","results","."]
docstr: :param sent : List of words remaining in the sentence
  :type sent  : [word,]
  :param current_states : List of possible tag combinations for
                          the sentence so far, and the log probability
                          associated with each tag combination
  :type current_states  : [([tag, ], logprob), ]
  
  Tags the first word in the sentence and
  recursively tags the reminder of sentence
  
  Uses formula specified above to calculate the probability
  of a particular tag
docstr_tok: [":","param","sent",":","List","of","words","remaining","in","the","sentence",":","type","sent",":","[","word",",","]",":","param","current_states",":","List","of","possible","tag","combinations","for","the","sentence","so","far",",","and","the","log","probability","associated","with","each","tag","combination",":","type","current_states",":","[","(","[","tag",",","]",",","logprob",")",",","]","Tags","the","first","word","in","the","sentence","and","recursively","tags","the","reminder","of","sentence","Uses","formula","specified","above","to","calculate","the","probability","of","a","particular","tag"]
code: def _tagword(self, sent, current_states):
      """
      :param sent : List of words remaining in the sentence
      :type sent  : [word,]
      :param current_states : List of possible tag combinations for
                              the sentence so far, and the log probability
                              associated with each tag combination
      :type current_states  : [([tag, ], logprob), ]
  
      Tags the first word in the sentence and
      recursively tags the reminder of sentence
  
      Uses formula specified above to calculate the probability
      of a particular tag
      """
  
      # if this word marks the end of the sentence,
      # return the most probable tag
      if sent == []:
          (h, logp) = current_states[0]
          return h
  
      # otherwise there are more words to be tagged
      word = sent[0]
      sent = sent[1:]
      new_states = []
  
      # if the Capitalisation is requested,
      # initialise the flag for this word
      C = False
      if self._C and word[0].isupper():
          C = True
  
      # if word is known
      # compute the set of possible tags
      # and their associated log probabilities
      if word in self._wd:
          self.known += 1
  
          for history, curr_sent_logprob in current_states:
              logprobs = []
  
              for t in self._wd[word].keys():
                  tC = (t, C)
                  p_uni = self._uni.freq(tC)
                  p_bi = self._bi[history[-1]].freq(tC)
                  p_tri = self._tri[tuple(history[-2:])].freq(tC)
                  p_wd = self._wd[word][t] / self._uni[tC]
                  p = (
                      self._l1 * p_uni
                      + self._l2 * p_bi
                      + self._l3 * p_tri
                  )
                  p2 = log(p, 2) + log(p_wd, 2)
  
                  # compute the result of appending each tag to this history
                  new_states.append(
                      (history + [tC], curr_sent_logprob + p2)
                  )
  
      # otherwise a new word, set of possible tags is unknown
      else:
          self.unknown += 1
  
          # since a set of possible tags,
          # and the probability of each specific tag
          # can not be returned from most classifiers:
          # specify that any unknown words are tagged with certainty
          p = 1
  
          # if no unknown word tagger has been specified
          # then use the tag 'Unk'
          if self._unk is None:
              tag = ("Unk", C)
  
          # otherwise apply the unknown word tagger
          else:
              [(_w, t)] = list(self._unk.tag([word]))
              tag = (t, C)
  
          for history, logprob in current_states:
              history.append(tag)
  
          new_states = current_states
  
      # now have computed a set of possible new_states
  
      # sort states by log prob
      # set is now ordered greatest to least log probability
      new_states.sort(reverse=True, key=itemgetter(1))
  
      # del everything after N (threshold)
      # this is the beam search cut
      if len(new_states) > self._N:
          new_states = new_states[: self._N]
  
      # compute the tags for the rest of the sentence
      # return the best list of tags for the sentence
      return self._tagword(sent, new_states)
  
file_path: nltk/nltk/tag/tnt.py
imports: from math import log
  from operator import itemgetter
  from nltk.probability import ConditionalFreqDist, FreqDist
  from nltk.tag.api import TaggerI
label_desc: Use image node_id 7 for calling the TnT obj's underlying member method code with example usage: obj._tagword(sent, current_states) and returns: self, h