Tanl Linguistic Pipeline

tag/NER/NerFeatureExtractor.cpp

/*
**  Tanl
**  NER/NerFeatureExtractor.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/>.
**  ----------------------------------------------------------------------
*/

// Local
#include "NerFeatureExtractor.h"

// standard
#include <sstream>

// library
#include "conf/conf_bool.h"
#include "conf/conf_string.h"

using namespace Tanl::Classifier;
using namespace Tanl::Text;

namespace Tanl {
namespace NER {

// Data uses old IOB conventions.
IXE::conf<bool> oldIOB("OldIOB", true);

IXE::conf<bool> refine("Refine", true);

// ======================================================================

  static vector<string> dictTags;
  static string const Money     = "D1";
  static string const Name      = "D2";
  static string const Time      = "D4";
  static string const PrevName  = "D5";
  static string const NextPerson= "D6";

// ======================================================================

  /*
   * Token Types (not used).
   */
  // These must be aligned with EntityType::Type
  char const* TokenTypes[] = {
    "UNKNOWN",
    "WORD",
    "QUANTITY",
    "NAME",
    "TIME",
    "SYMBOL",
    "PUNCT",
    "ADDRESS",
    "PERSON",
    "ORGANIZATION",
    "LOCATION",
    "PRODUCT",
    "NUMBER",
    "MONEY",
    "MEASURE",
    "DURATION",
    "DATE",
    "TIME",
    "URL",
    "EMAIL"
  };

// ======================================================================

  // Global lists ////////////////////////////////////////
  //
  // FWL (Frequent Word List): words that occur in more than 10 documents
  //
  // CPW (Common Preceding Words): 20 words that most often precede
  //    a certain class
  //
  // CPB (Common Preceding Bigrams): bigrams that often precede
  //    a certain class
  //
  // SUF (Suffix for Class): common 3-4 letter suffix for a certain class
  //    (-ian, -ish)
  //
  // EFW (Entity First Words): list of words starting a Named entity sequence
  //                            Added for Italian.
  //    Organization: centro, giunta, banca
  //    Locations: via, piazza
  //    Person: De, S.
  //
  // ELW (Entity Last Words): list of words terminating a Named entity sequence
  //    Organization: Inc, Org, Co
  //    Locations: center, museum, square, street
  //    Person: Jr, II, III
  //
  // LIW (Lowercase Intermediate Words): list of lowercase words appearing in a
  //    Named entity sequence
  //    Organization: al, in, zonder, vor, for
  //    Person: "van der", "de", "of"
  //

  // Lexical Features ////////////////////////////////////////

  char const* Capitalized[4]    = {"initCaps_HL", "initCaps_AU", "initCaps_DL",
                                   "initCaps_TXT"};

  // first word of sentence is capitalized
  char const* firstWordCap[4]   = {"firstWordInitCaps_HL",
                                   "firstWordInitCaps_AU",
                                   "firstWordInitCaps_DL",
                                   "firstWordInitCaps_TXT"};

  // first word but not capitalized
  char const* firstWordLow[4]   = {"firstWordNotInitCaps_HL",
                                   "firstWordNotInitCaps_AU",
                                   "firstWordNotInitCaps_DL",
                                   "firstWordNotInitCaps_TXT"};

  string const HyphenCapCap     = "U-U"; // Str1-Str2
  string const HyphenLowCap     = "L-U"; // str1-Str2
  string const HyphenCapLow     = "U-L"; // Str1-str2

  // Local Features ////////////////////////////////////////

  string const seqCap           = "I";  // previous, current and next are Capitalized
  string const notSeqCap        = "NI"; // not SeqCap
  string const CapNoNext        = "initCaps__Next";     // current is Capitalized, no next
  string const LowNoNext        = "nonInitCaps__Next";  // current is not Capitalized, no next
  string const CapNoPrev        = "initCaps__Prev";     // current is Capitalized, no previous
  string const LowNoPrev        = "nonInitCaps__Prev";  // current is not Capitalized, no previous is not

  string const Cap              = "initCaps_";
  string const Low              = "nonInitCaps_";


  string const withinQuotes     = "quote";      // word is in sequence within quotes
  string const rare             = "rare";       // word not present in FWL

  // w-2, w-1 appear in CPB list
  vector<string> bigramTags;

  // 3-letter suffix present in PRE list
  vector<string> prefixTags;

  // 3-letter suffix present in SUF list
  vector<string> suffixTags;

  // present in List of First words
  vector<string> firstWordTags;

  // present in List of Last words
  vector<string> lastWordTags;

  // word in List ELW appears within sequence of Caps
  vector<string> lowerSeqTags;  // FIXME: not used

  // word appearing in list Lower Words appearing within names for given class
  vector<string> lowerIntermTags;

  // Global features ////////////////////////////////////////

  // another occurrence of current word was tagged as given class
  vector<string> prevTags;

  // another occurrence of current word was first word
  vector<string> otherFirstTags;

  // another occurrence of current word was last word
  vector<string> otherLastTags;

  string const otherCapitalized = "otherInitCap";// an occurrence not as first word was
                                // Capitalized
  string const otherNotCapitalized      = "otherNotInitCap";// an occurrence not as first word was
                                // not Capitalized

  // Acronyms
  // An AllUpper word is stored as an acronym.
  // Caps sequences with those initials will be given the following features:
  string const Acronym          = "acronym";    // e.g. FCC
  string const AcronymBegin     = "cI"; // e.g. Federal
  string const AcronymContinue  = "cJ"; // e.g. Communication
  string const AcronymEnd       = "cK"; // e.g. Committee

  /*
    Not used: we rely on POS tagger for disambiguating these cases.

  // Longest Common Caps Sequence
  // To avoid confusing "Also Texas Instruments Corp." as a whole company name,
  // the longest common Caps sequence occurring in a document is noted.
  // So if "Xerox Corp." also appears, the following features are set:
  string const LongestB         = "cL"; // Texas
  string const LongestC         = "cM"; // Instruments
  string const LongestE         = "cN"; // Corp.
  */

bool allUpper(char const* s)
{
  char* scan = (char*)s;
  while (*scan)
    if (!isupper(*scan++))
      return false;
  return true;
}

bool allQuotes(char const* s)
{
  return (::strspn(s, "\"") == ::strlen(s));
}

// ======================================================================

IXE::conf_set<std::string> Resources::entityTypes("Classes");

void Resources::resize()
{
  size_t nClasses = entityTypes->size();
  dict.resize(nClasses);
  designators.resize(nClasses);
  preBigrams.resize(nClasses);
  prefixes.resize(nClasses);
  suffixes.resize(nClasses);
  firstWords.resize(nClasses);
  lastWords.resize(nClasses);
  lowerInterm.resize(nClasses);
  dictTags.resize(nClasses);
  bigramTags.resize(nClasses);
  prefixTags.resize(nClasses);
  suffixTags.resize(nClasses);
  firstWordTags.resize(nClasses);
  lastWordTags.resize(nClasses);
  lowerSeqTags.resize(nClasses);
  lowerIntermTags.resize(nClasses);
  prevTags.resize(nClasses);
  otherFirstTags.resize(nClasses);
  otherLastTags.resize(nClasses);
  int i = 0;
  FOR_EACH (set<string>, *entityTypes, it) {
    dictTags[i] = "UNI-" + *it;
    bigramTags[i] = "BI-" + *it;
    prefixTags[i] = "Pref-" + *it;
    suffixTags[i] = "Suf-" + *it;
    firstWordTags[i] = "FW-" + *it;
    lastWordTags[i] = "LW-" + *it;
    lowerSeqTags[i] = "lS" + *it;
    lowerIntermTags[i] = "lI" + *it;
    prevTags[i] = "PrevOccur-" + *it;
    otherFirstTags[i] = "OtherFirst-" + *it;
    otherLastTags[i] = "OtherLast-" + *it;
    i++;
  }
}

Resources::Resources(string& resourceDir, string& locale,
                     char const* POStag, char const* NEtag) :
  language(locale.c_str()),
  POStag(POStag),
  NEtag(NEtag)
{
  load(resourceDir);
}

void Resources::load(string& resourceDir)
{
  resize();
  int i = 0;
  FOR_EACH (std::set<std::string>, *entityTypes, it)
    classId[it->c_str()] = i++;

  // Dictionaries
  load(dict, (resourceDir + "/Dict.lst").c_str());
  moneyDict.load((resourceDir + "/money.lst").c_str());
  namesDict.load((resourceDir + "/names.lst").c_str());
  timeDict.load((resourceDir + "/time.lst").c_str());

  // Frequent Word List
  FWL.load((resourceDir + "/FrequentWords.lst").c_str());

  // Designators
  load(designators, (resourceDir + "/Designators.lst").c_str());

  // Preceding Bigrams
  load(preBigrams, (resourceDir + "/Bigrams.lst").c_str());

  // Prefix
  load(prefixes, (resourceDir + "/Prefix.lst").c_str());

  // Suffix
  load(suffixes, (resourceDir + "/Suffix.lst").c_str());

  // First word
  load(firstWords, (resourceDir + "/First.lst").c_str());

  // Last word
  load(lastWords, (resourceDir + "/Last.lst").c_str());

  // Lower intermediate word
  load(lowerInterm, (resourceDir + "/LowerIn.lst").c_str());

}

template<class WordSet>
void Resources::load(vector<WordSet>& sets, char const* file)
{
  ifstream ifs(file);
  char line[MAX_LINE_LEN];

  while (ifs.getline(line, MAX_LINE_LEN)) {
    // split line
    char* next = line;
    char* className = strtok_r(0, " \t", &next);
    if (!className)
      continue;
    char* word = next + strspn(next, " \t");
    if (strlen(word) == 0)
      continue;
    // determine class
    int cid = classId[className];
    sets[cid].insert(word);
  }
}

char const* Resources::typeName(EntityType et)
{
  if (et.subtype != (EntityType::Subtype)EntityType::NoType)
    return TokenTypes[et.subtype];
  else if (et.type != EntityType::NoType)
    return TokenTypes[et.type];
  else
    return 0;
}

Text::RegExp::Pattern number("\\d+");
string numRep("+NUM+");

// ======================================================================

NerFeatureExtractor::NerFeatureExtractor(Resources& resources) :
  resources(resources),
  tokenCategorizer(resources.language),
  insideQuotes(false)
{
  prevClass.resize(resources.typesCount());
  otherFirst.resize(resources.typesCount());
  otherLast.resize(resources.typesCount());
}

void NerFeatureExtractor::extract(Classifier::Features& features, const int& position)
{
  Token* token = (*sentence)[position];
  char const* word = token->form.c_str();
  char const* prevWord = (position > 0) ? (*sentence)[position-1]->form.c_str() : 0;
  char const* nextWord = (position+1 < sentence->size()) ? (*sentence)[position+1]->form.c_str() : 0;

  //======================================================================
  // Lexical Features

  size_t len = strlen(word);
  size_t sentLen = sentence->size();

  // 1st word and initCaps
  if (!prevWord && isupper(word[0]))
    features.add(firstWordCap[zone]);

  // initCaps and not 1st word
  if (prevWord && isupper(word[0]))
      features.add(Capitalized[zone]);

  // 1st word and not initCaps
  if (!prevWord && !isupper(word[0]))
    features.add(firstWordLow[zone]);

  // AllUpper
  if (allUpper(word)) {
    if (acronyms.contains(word))
      features.add(Acronym);
  }

  //======================================================================
  // Local Features
  string upNext(nextWord ? nextWord : "");
  to_upper(upNext);
  number.replace(upNext, numRep, true);
  string upPrev(prevWord ? prevWord : "");
  to_upper(upPrev);
  number.replace(upPrev, numRep, true);

  string nextPos(nextWord ? (*sentence)[position+1]->get(resources.POStag)->c_str() : "");
  string prevPos(position > 0 ? (*sentence)[position-1]->get(resources.POStag)->c_str() : "");

  // next word
  if (nextWord) {
    if (isupper(word[0]))
      features.add(Cap + upNext + "Next");
    //features.add(Cap + nextPos + "Next");
    else
      features.add(Low + upNext + "Next");
    //features.add(Low + nextPos + "Next");
  } else if (isupper(word[0]))
    features.add(CapNoNext);
  else
    features.add(LowNoNext);

  // previous word
  if (prevWord) {
    if (isupper(word[0]))
      features.add(Cap + upPrev + "Prev");
    //features.add(Cap + prevPos + "Prev");
     else
       features.add(Low + upPrev + "Prev");
    //features.add(Low + prevPos + "Prev");
  } else if (isupper(word[0]))
    features.add(CapNoPrev);
  else
    features.add(LowNoPrev);

  // Case Sequence
  if (prevWord && nextWord &&
      isupper(prevWord[0]) && isupper(word[0]) && isupper(nextWord[0]))
    features.add(seqCap);
  else
    features.add(notSeqCap);

  // hyphenate words
  if (strchr(word, '-')) {
    char copy[800];
    strncpy(copy, word, sizeof(copy));
    char* next = copy;
    char* word1 = strtok_r(0, "-", &next);
    char* word2 = strtok_r(0, "-", &next);
    if (word1 && word2) {
      bool up1 = isupper(word1[0]);
      bool up2 = isupper(word2[0]);
      if (next[0] == '\0') {    // just two
        if (up1 && up2)
          features.add(HyphenCapCap);
        else {
          to_upper(word1);
          string upper1(word1);
          number.replace(upper1, numRep, true);
          to_upper(word2);
          string upper2(word2);
          number.replace(upper2, numRep, true);
          if (up1) {
            features.add(HyphenCapLow);
            features.add(string("U-") + upper1);
            features.add(string("L_") + upper2);
          } else if (up2) {
            features.add(HyphenLowCap);
            features.add(string("L-") + upper1);
            features.add(string("U_") + upper2);
          }
        }
      }
    }
  }

  string upper(word);
  to_upper(upper);
  number.replace(upper, numRep, true);

  // rare words
  if (!resources.FWL.contains(upper))
    features.add(rare);

  size_t nClasses = resources.typesCount();
  // bigrams
  if (position > 1) {
    string bigram = (*sentence)[position-2]->form + '_' + prevWord;
    to_upper(bigram);
    for (int i = 0; i < nClasses; ++i) {
      if (resources.preBigrams[i].contains(bigram))
        features.add(bigramTags[i]);
    }
  }

  for (int i = 0; i < nClasses; ++i) {
    if (resources.firstWords[i].contains(word))
      features.add(firstWordTags[i]);
  }

#ifdef EXTRA
  for (int i = 0; i < nClasses; ++i) {
    if (resources.lastWords[i].contains(word))
      features.add(lastWordTags[i]);
  }

  for (int i = 0; i < nClasses; ++i) {
    if (resources.lowerInterm[i].contains(word))
      features.add(lowerIntermTags[i]);
  }
#endif

  //======================================================================
  // Dictionary Features

  if (position > 0) {
    for (int i = 0; i < nClasses; ++i) {
      if (resources.dict[i].contains(word)) 
        features.add(dictTags[i]);
    }
  }

  // features according to feature model
  char feature[256];
  int featIndex = 0;
  // Morphological features (constant feature, not including token attribute)
  FOR_EACH (FeatureSpecs, *morphFeatureSpecs, fit) {
    string const& attrName = (*fit)->name;
    Text::RegExp::Pattern const& p = (*fit)->pattern;
    char featId = 'A' + featIndex++;
    FOR_EACH (vector<int>, (*fit)->tokens, tit) {
      // find token
      int dx = *tit;
      int idx = position + dx;
      Token* tok = (0 <= idx && idx < sentLen) ? (*sentence)[idx] : 0;
      if (tok) {
        string const* item = tok->get(attrName.c_str());
        if (item && !item->empty() && p.test(*item)) {
          // skip empty attributes
          if (dx < 0)
            snprintf(feature, sizeof(feature), "%dM%c", -dx, featId);
          else
            snprintf(feature, sizeof(feature), "M%c%d", featId, dx);
          features.add(feature);
        }
      }
    }
  }
  // Composite feature: identifier + token attribute.
  FOR_EACH (FeatureSpecs, *featureSpecs, fit) {
    string const& attrName = (*fit)->name;
    Text::RegExp::Pattern const& p = (*fit)->pattern;
    int attrIndex = token->attrIndex(attrName.c_str());
    char featId = 'A' + attrIndex;              // feature type identifier
    FOR_EACH (vector<int>, (*fit)->tokens, tit) {
      // find token
      int dx = *tit;
      int idx = position + dx;
      Token* tok = (0 <= idx && idx < sentLen) ? (*sentence)[idx] : 0;
      if (tok) {
        string const* item = tok->get(attrName.c_str());
        if (item && !item->empty() && p.test(*item)) {
          // skip empty attributes
          if (dx < 0)
            snprintf(feature, sizeof(feature), "%d%c%s", -dx, featId, item->c_str());
          else
            snprintf(feature, sizeof(feature), "%c%d%s", featId, dx, item->c_str());
          features.add(feature);
        }
      }
    }
  }
  // Add word by default
  features.add("word=" + upper);

  // Global features
  unordered_map<string, bool>::iterator it = capitalized.find(upper);
  if (it != capitalized.end()) {
    if (it->second)
      features.add(otherCapitalized);
    else
      features.add(otherNotCapitalized);
  } else if (position > 0)      // non ambiguous position
    capitalized[upper] = isupper(word[0]); // FIXME: only first occurrence counts

  // Acronyms
  if (nextWord && isupper(word[0])) {
    string acronym;
    for (int i = position; i < sentLen; i++) {
      char c = (*sentence)[i]->form[0];
      if (isupper(c))
        acronym.push_back(c);
      else
        break;
    }
    if (acronym.size() > 1)
      acronyms.insert(acronym.c_str());
  }

#ifdef HYP_BUG
  /* FIXIM: hyp has bug array cont[4] is not initialized */
  // presence of a Last Word in capitalized sequence
  if (position < sentLen-1) {
    if (isupper(word[0])) {
      // Find end of initcaps
      int endPos;
      for (endPos = position + 1; endPos < sentLen; endPos++)
        if (!isupper(((*sentence)[endPos]->form)[0]))
          break;

      for (int j = position + 1; j < endPos; j++) {
        for (int i = 0; i < nClasses; i++) {
          char const* other = (*sentence)[j]->form.c_str();
          if (resources.lastWords[i].contains(other)) {
            features.add(otherLastTags[i]);
            otherLast[i].insert(other);
            break;
          }
        }
      }
    }
  }
#endif

  // Global Class of word in Cap sequence that occurred as first word
  for (int i = 0; i < nClasses; i++) {
    if (otherFirst[i].contains(word))
      features.add(otherFirstTags[i]);
  }

  // Global Class of word in Cap sequence that occurred as last word
  for (int i = 0; i < nClasses; i++) {
    if (otherLast[i].contains(word))
      features.add(otherLastTags[i]);
  }

  // Global Name Class of previous occurences
  for (int i = 0; i < nClasses; i++) {
    if (prevClass[i].contains(upper))
      features.add(prevTags[i]);
  }

  // char suffixes
  if (upper.size() > 3) {
    for (int i = 0; i < nClasses; ++i) {
      if (resources.suffixes[i].match(upper))
        features.add(suffixTags[i]);
    }
  }

  // char prefixes
  if (upper.size() > 3) {
    upper.erase(3);
    for (int i = 0; i < nClasses; ++i) {
      if (resources.prefixes[i].contains(upper))
        features.add(prefixTags[i]);
    }
  }

  // inside quotes
  if (insideQuotes)
    features.add(withinQuotes);
  /* Chieu was cheating here, assuming to know the word after the entity:
  if (prevWord && nextWord &&
      strpbrk(prevWord, "\"()[]{}'<>") &&
      strpbrk(afterWWord, "\"()[]{}'<>"))
    features.add(withinQuotes);
  */
  // prepare for next position
  if (allQuotes(word))
    insideQuotes = !insideQuotes;
}

void NerFeatureExtractor::analyze(Sentence* sent, int zone)
{
  sentence = sent;
  this->zone = zone;
  int len = sentence->size();
  tokenTypes.resize(len);
  insideQuotes = false;
  int i = 0;
  for (Sentence::const_iterator sit = sentence->begin();
       sit != sentence->end(); ++sit, ++i) {
    Token* tok = *sit;
    tokenTypes[i] = tokenCategorizer.analyze(tok->form.c_str());
    if (oldIOB) {
      // convert to new IOB convention:
      string const* tag = tok->get(resources.NEtag);
      if (!tag)
        continue;
      if (*tag == "O" || (*tag)[0] == 'B' || tag->empty()) // empty when tagging
        continue;
      string const* prevTag = (i > 0) ? (*sent)[i-1]->get(resources.NEtag) : 0;
      string nt(*tag);
      if (!prevTag || (*prevTag)[0] == 'O') {
        nt[0] = 'B';            // begin
        tok->set(resources.NEtag, nt);
      }
    }
    if (refine) {
      // refine classes, for each C: B-C, I-C, E-C (end), U-C (unique)
      string const* tag = tok->get(resources.NEtag);
      if (!tag)
        continue;
      if (*tag == "O" || tag->empty()) // empty when tagging
        continue;
      string const* nextTag = (i < len-1) ? (*sent)[i+1]->get(resources.NEtag) : 0;
      string nt(*tag);
      if (nextTag) {
        if ((*nextTag)[0] == 'B' || (*nextTag)[0] == 'O') {
          if ((*tag)[0] == 'B') {
            nt[0] = 'U';                // unique
            tok->set(resources.NEtag, nt);
          } else {              // last
            nt[0] = 'E';
            tok->set(resources.NEtag, nt);
          }
        }
      } else if ((*tag)[0] == 'B') { // last unique
        nt[0] = 'U';
        tok->set(resources.NEtag, nt);
      } else {                  // inside
        nt[0] = 'E';            // last
        tok->set(resources.NEtag, nt);
      }
    }
  }
}

void NerFeatureExtractor::reset()
{
  insideQuotes = false;

  // global document features
  for (int i = 0; i < resources.typesCount(); ++i) {
    prevClass[i].clear();
    otherFirst[i].clear();
    otherLast[i].clear();
  }
  acronyms.clear();
  capitalized.clear();
}

void NerFeatureExtractor::classified(int position, char const* className)
{
  Token* token = (*sentence)[position];
  char const* word = token->form.c_str();
  designated(word, className);
  // set the NETAG of token
  token->set(resources.NEtag, className);
}

void NerFeatureExtractor::designated(char const* word, char const* neTag)
{
  if (strlen(neTag) < 2)        // O
    return;
  int i = 0;
  FOR_EACH (set<string>, *resources.entityTypes, it) {
    if (neTag+2 == *it) { // skip X- from tag
      string upper(word);
      to_upper(upper);
      number.replace(upper, numRep, true);
      prevClass[i].insert(upper.c_str());
    }
    i++;
  }
}

} // namespace NER
} // namespace Tanl

 

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