mootSuffixTrie.h

Go to the documentation of this file.

/* -*- Mode: C++ -*- */

/*
   libmoot : moocow's part-of-speech tagging library
   Copyright (C) 2003-2009 by Bryan Jurish <moocow@cpan.org>

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 3 of the License, or (at your option) any later version.
   
   This library 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
   Lesser General Public License for more details.
   
   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/

/*--------------------------------------------------------------------------
 * File: mootSuffixTrie.h
 * Author: Bryan Jurish <moocow@cpan.org>
 * Description:
 *   + moocow's PoS tagger : suffix trie
 *--------------------------------------------------------------------------*/

#ifndef _MOOT_SUFFIX_TRIE_H
#define _MOOT_SUFFIX_TRIE_H

#include <mootEnum.h>
#include <mootLexfreqs.h>
#include <mootNgrams.h>
#include <mootAssocVector.h>
#include <mootTrieVector.h>

moot_BEGIN_NAMESPACE

typedef AssocVector<mootEnumID,ProbT> SuffixTrieDataT;

//template<>
class SuffixTrie : public TrieVector<SuffixTrieDataT>
{
public:
  //------------------------------------------------------------
  // SuffixTrie: Static Data
  //static const size_t SuffixTrieDefaultMaxLen = 10;
  static const size_t SuffixTrieDefaultMaxLen = 0;

public:
  //------------------------------------------------------------
  // SuffixTrie: Types

  typedef mootEnumID              TagID;

  typedef mootEnum<mootTagString> TagIDTable;

  typedef TrieVector<SuffixTrieDataT>  TrieType;

public:
  //------------------------------------------------------------
  // SuffixTrie: data
  CountT        maxcount;  
  ProbT         theta;     


public:
  //------------------------------------------------------------
  // SuffixTrie: Methods

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


  SuffixTrie(size_t max_length =SuffixTrieDefaultMaxLen,
             bool   use_case   =true,
             size_t max_count  =10)
    : TrieType(max_length,use_case),
      maxcount(max_count)
  {};

  ~SuffixTrie(void) {};

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


  bool build(const mootLexfreqs &lf,
             const mootNgrams   &ng,
             const TagIDTable   &tagids,
             TagID eos_tagid,
             bool  verbose=false);

  bool _build_insert(const mootLexfreqs &lf);

  bool _build_assoc(const mootLexfreqs &lf, const TagIDTable &tagids);

  bool _build_compute_theta(const mootLexfreqs &lf,
                            const mootNgrams   &ng,
                            const TagIDTable   &tagids,
                            TagID eos_tagid);

  bool _build_compute_mles(const mootLexfreqs &lf,
                           const mootNgrams   &ng,
                           const TagIDTable   &tagids,
                           TagID eos_tagid);

  bool _build_invert_mles(const mootNgrams &ng,
                          const TagIDTable &tagids,
                          TagID eos_tagid);

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


  inline iterator find_ancestor_nonempty(iterator dtr, size_t *matchlen=NULL)
  {
    if (matchlen) *matchlen = 0;
    for ( ; dtr != end() && dtr->data.empty(); dtr=find_mother(*dtr)) {
      if (matchlen) (*matchlen)--;
    }
    return dtr;
  };

  inline const_iterator const_find_ancestor_nonempty(const_iterator dtr, size_t *matchlen=NULL)
    const
  {
    if (matchlen) *matchlen = 0;
    for ( ; dtr != end() && dtr->data.empty(); dtr=find_mother(*dtr)) {
      if (matchlen) (*matchlen)--;
    }
    return dtr;
  };


  inline iterator rfind_longest_nonempty(const mootTokString &tokstr,
                                         size_t              *matchlen=NULL)
  { return find_ancestor_nonempty(rfind_longest(tokstr,matchlen),matchlen); };

  inline const_iterator rfind_longest_nonempty(const mootTokString &tokstr,
                                               size_t              *matchlen=NULL)
    const
  { return const_find_ancestor_nonempty(rfind_longest(tokstr,matchlen),matchlen); };


  inline const SuffixTrieDataT& sufprobs(const mootTokString &tokstr, size_t *matchlen=NULL)
    const
  {
    const_iterator ti = rfind_longest_nonempty(tokstr,matchlen);
    return (ti==end() ? default_data() : ti->data);
  };

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

  void txtdump(FILE *out, const TagIDTable &tagids) const;

}; //-- /class SuffixTrie

moot_END_NAMESPACE

#endif // _MOOT_SUFFIX_TRIE_H