Tanl Linguistic Pipeline

tag/Tanlpos/SuffixGuesser.cpp

/*
**  Tanl
**  tag/TanlPos/SuffixGuesser.cpp
**  ----------------------------------------------------------------------
**  Copyright (c) 2005  Giuseppe Attardi (attardi@di.unipi.it).
**  ----------------------------------------------------------------------
**
**  This file is part of Tanl.
**
**  Tanl is free software; you can redistribute it and/or modify it
**  under the terms of the GNU General Public License, version 3,
**  as published by the Free Software Foundation.
**
**  Tanl is distributed in the hope that it will be useful,
**  but WITHOUT ANY WARRANTY; without even the implied warranty of
**  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
**  GNU General Public License for more details.
**
**  You should have received a copy of the GNU General Public License
**  along with this program.  If not, see <http://www.gnu.org/licenses/>.
**  ----------------------------------------------------------------------
*/

#include "SuffixGuesser.h"
#include "serialization.h"

// standard
#include <limits>
#include <cmath>

using namespace std;

namespace Tanl { namespace POS {

Counts* Counts::update(TagID tag, int count)
{
  if (tagCounts.find(tag) == tagCounts.end())
    tagCounts[tag] = count;
  else
    tagCounts[tag] += count;
  this->count += count;
  return this;
}

void Counts::serialize(ostream &out)
{
  POS::serialize(count, out);
  POS::serialize(tagCounts, out);
}

void Counts::serialize(istream &in)
{
  POS::serialize(count, in);
  POS::serialize(tagCounts, in);
}

// ----------------------------------------------------------------------

void TrieNode::serialize(std::ostream &out)
{
  POS::serialize(terminal, out);
  if (tag_info) {
    POS::serialize(true, out);
    tag_info->serialize(out);
  } else
    POS::serialize(false, out);

  POS::serialize(size(), out);
  FOR_EACH (TrieNode, (*this), it) {
    POS::serialize(it->first, out);
    it->second->serialize(out);
  }
}

void TrieNode::serialize(std::istream &in)
{
  POS::serialize(terminal, in);
  bool istag = false;
  POS::serialize(istag, in);
  if (istag) {
    tag_info = new Counts();
    tag_info->serialize(in);
  } else
    tag_info = 0;

  size_t size;
  POS::serialize(size, in);
  for (size_t i = 0; i < size; i++) {
    char first;
    TrieNode *second = new TrieNode;
    POS::serialize(first, in);
    second->serialize(in);
    (*this)[first] = second;
  }
}

bool TrieNode::empty_node()
{
  return size() == 0 && tag_info == 0 && !terminal;
}

void TrieNode::set_tag_info(Counts* tag)
{
  if (tag_info && tag != tag_info)
    delete tag_info;
  tag_info = tag;
}

TrieNode* TrieNode::add_char(Counts* legacy_counts, bool after_branch, int ix,
                             int stop, string& word, TagID tag, int count)
{
  if (!legacy_counts)
    legacy_counts = new Counts();
  Counts* inherited_counts = tag_info ? tag_info : legacy_counts;

  if (empty_node() && ix < stop) {
    // Arrived to the end with an empty node, return a teminal
      terminal = true;
    } else if (size() == 1 && ix < stop) {
    // One child with no tag info at the end, then set the tag info to the inherited
      TrieNode* child = begin()->second;
      if (!child->empty_node() && !child->tag_info)
        child->tag_info = new Counts(inherited_counts);
    } else if (size() > 1 && ix < stop) {
    // More than one child and at the end
    } else if (empty_node()) {
    // When empty, create a child node with the rest of the suffix and set counts
      Counts* temp = new Counts(inherited_counts);
      TrieNode* child = EMPTY_NODE->add_char(temp, false, ix - 1, stop, word, tag, count);
      (*this)[word[ix]] = child;
    } else if (terminal) {
    // When on a terminal, expand it
      TrieNode* child = EMPTY_NODE->add_char(0, true, ix - 1, stop, word, tag, count);
      terminal = false;
      (*this)[word[ix]] = child;
    } else if (size() == 1 && begin()->first == word[ix]) {
    // When the char already exists (with one child), update the child with the new suffix
      char c = word[ix];
      TrieNode* child = (*this)[c];
      child->add_char(new Counts(inherited_counts), false, ix - 1, stop, word, tag, count);
    } else if (size() == 1) {
    // When there is one child and the char is new, then create a new branch
      TrieNode* child = begin()->second;
      if (!child->empty_node() && !child->tag_info)
        child->tag_info = new Counts(inherited_counts);
      TrieNode* newchild = EMPTY_NODE->add_char(0, true, ix - 1, stop, word, tag, count);
      (*this)[word[ix]] = newchild;
    } else {
    // The general branching case
      char c = word[ix];
      if (find(c) == end())
        (*this)[c] = EMPTY_NODE->add_char(0, true, ix - 1, stop, word, tag, count);
      else
        (*this)[c]->add_char(new Counts(inherited_counts), true, ix - 1, stop, word, tag, count);
    }

  if (after_branch)
    set_tag_info(inherited_counts->update(tag, count));
  if (tag_info != legacy_counts)
    delete legacy_counts;

  return this;
}

// ----------------------------------------------------------------------

void SuffixGuesser::serialize(std::ostream &out)
{
  POS::serialize(theta, out);
  trie.serialize(out);
}

void SuffixGuesser::serialize(std::istream &in)
{
  POS::serialize(theta, in);
  trie.serialize(in);
}

void SuffixGuesser::add_word(int n, string& word, int tag, int count)
{
  int start = word.length() - 1;
  int stop = max(0, start - n + 1);
  trie = *(trie.add_char(0, true, start, stop, word, tag, count));
}

double SuffixGuesser::tagprob(string& word, int tagid)
{
  double theta_plus_one = theta + 1.0;
  double accu = 0.0;
  TrieNode::counts_iterator it(word, &trie);
  Counts* tag_info;
  while ((tag_info = it.next())) {
    int suff_count = tag_info->count;
    TagCounts& tag_counts = tag_info->tagCounts;
    TagCounts::iterator cit = tag_counts.find(tagid);
    double tag_prob = 0.0;
    if (cit != tag_counts.end())
      tag_prob = cit->second / suff_count;
    accu = (accu + tag_prob * theta) / theta_plus_one;
  }
  return log(accu);
}

double SuffixGuesser::tagprobs(string& word, vector<double>& probs)
{
  double theta_plus_one = theta + 1.0;
  // zero out the probs
  for (unsigned int i = 0; i < probs.size(); ++i)
    probs[i] = 0.0;

  TrieNode::counts_iterator it(word, &trie);
  Counts* tag_info;
  while ((tag_info = it.next())) {
    int suff_count = tag_info->count;
    TagCounts& tag_counts = tag_info->tagCounts;
    FOR_EACH (TagCounts, tag_counts, tagit) {
      int tagid = tagit->first;
      int freq = tagit->second;
      double tag_prob = double(freq) / suff_count;
      probs[tagid] = (probs[tagid] + tag_prob * theta) / theta_plus_one;
    }
  }
  /* take logarithm and search for the maximum.
   * bayesian inversion is not done here anymore, it is now done: hmm_tagger.
   * This way
   * 1. a maxent model will more easily be pluggable here.
   * 2. the hmm_tagger can throw away unlikely tags before inversion.
   */
  double max = -1 * numeric_limits<double>::infinity();
  for (unsigned int i = 0; i < probs.size(); ++i) {
    // P(t|w) = log(probs[i])
    // P(t) = apriori_tag_probs[i]
    // P(w|t) = log(probs[i] - log(apriori_tag_probs[i]

    double prob = log(probs[i]);
    probs[i] = prob;
    if (prob > max)
      max = prob;
  }
  return max;
}

double SuffixGuesser::calculate_theta(vector<double>& apriori_tag_probs)
{
  /* we follow libmmoot's solution here, not Brants 2000's formula.
   * p_av = E_{P_t}(P_t()) [weighted avg: stddev]
   */
  double p_av = 0.0;
  for (unsigned int i = 0; i < apriori_tag_probs.size(); i++) {
    double tagp = apriori_tag_probs[i];
    p_av += tagp * tagp;
  }
  double theta = 0.0;
  for (unsigned int i = 0; i < apriori_tag_probs.size(); i++) {
    double tagp = apriori_tag_probs[i];
    double d = tagp - p_av;
    theta += tagp * d * d;
  }
  return sqrt(theta);
}

} // namespace POS
} // namespace Tanl

 

Copyright © 2005-2011 G. Attardi. Generated on 3 Mar 2011 by doxygen 1.6.1.