# Linear interpolation (for trigram model only)
def LinearInterpolation(ngram, freqs):
  global A, B, C # meta-parameters given by global variables A, B, C
  n = len(ngram)
  if n != 3:
    raise NotImplementedError, "linear interpolation is only defined for trigrams"


  condProb3 = MLE(ngram, freqs)
  condProb2 = MLE(ngram[1:], freqs)
  condProb1 = MLE(ngram[2], freqs)

  if condProb2 == 0:
      return condProb1

  if condProb3 == 0:
      norm = 1.0/(B+C)
      b = B*norm
      c = C*norm
      return b*condProb2 + c*condProb1

  return A*condProb3 + B*condProb2 + C*condProb1