source: trunk/gsdl/packages/kea/kea-3.0/KEAFilter.java@ 8815

/*
 *    KEAFilter.java
 *    Copyright (C) 2000, 2001 Eibe Frank
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program 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, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

import java.util.*;
import java.io.*;

import weka.core.*;
import weka.filters.*;
import weka.classifiers.*;

/**
 * This filter converts the incoming data into data appropriate for
 * keyphrase classification. It assumes that the dataset contains two
 * string attributes. The first attribute should contain the text of a
 * document. The second attribute should contain the keyphrases
 * associated with that document (if present). 
 *
 * The filter converts every instance (i.e. document) into a set of
 * instances, one for each word-based n-gram in the document. The
 * string attribute representing the document is replaced by some
 * numeric features, the estimated probability of each n-gram being a
 * keyphrase, and the rank of this phrase in the document according to
 * the probability.  Each new instances also has a class value
 * associated with it. The class is "true" if the n-gram is a true
 * keyphrase, and "false" otherwise. Of course, if the input document
 * doesn't come with author-assigned keyphrases, the class values for
 * that document will be missing.  
 *
 * @author Eibe Frank ([email protected])
 * @version 1.0
  */
public class KEAFilter extends Filter implements OptionHandler {

  /** Index of attribute containing the documents */
  private int m_DocumentAtt = 0;

  /** Index of attribute containing the keyphrases */
  private int m_KeyphrasesAtt = 1;

  /** The maximum length of phrases */
  private int m_MaxPhraseLength = 3;

  /** The minimum length of phrases */
  private int m_MinPhraseLength = 1;

  /** Is keyphrase frequency attribute being used? */
  private boolean m_KFused = false;

  /** Flag for debugging mode */
  private boolean m_Debug = false;

  /** Determines whether internal periods are allowed */
  private boolean m_DisallowInternalPeriods = false;

  /** The minimum number of occurences of a phrase */
  private int m_MinNumOccur = 2;

  /** The number of features describing a phrase */
  private int m_NumFeatures = 2;

  /* Indices of attributes in m_ClassifierData */
  private int m_TfidfIndex = 0;
  private int m_FirstOccurIndex = 1;
  private int m_KeyFreqIndex = 2;

  /** The punctuation filter used by this filter */
  private KEAPhraseFilter m_PunctFilter = null;

  /** The numbers filter used by this filter */
  private NumbersFilter m_NumbersFilter = null;
 
  /** The actual classifier used to compute probabilities */
  private DistributionClassifier m_Classifier = null;

  /** The dictionary containing the document frequencies */
  private HashMap m_Dictionary = null;

  /** The dictionary containing the keyphrases */
  private HashMap m_KeyphraseDictionary = null;

  /** The number of documents in the global frequencies corpus */
  private int m_NumDocs = 0;

  /** Template for the classifier data */
  private Instances m_ClassifierData = null;

  /** The stemmer to be used */
  private Stemmer m_Stemmer = new IteratedLovinsStemmer();

  /** The list of stop words to be used */
  private Stopwords m_Stopwords = new StopwordsEnglish();

  /** Determines whether check for proper nouns is performed */
  private boolean m_CheckForProperNouns = true;

  /**
   * Get the M_CheckProperNouns value.
   * @return the M_CheckProperNouns value.
   */
  public boolean getCheckForProperNouns() {
    return m_CheckForProperNouns;
  }

  /**
   * Set the M_CheckProperNouns value.
   * @param newM_CheckProperNouns The new M_CheckProperNouns value.
   */
  public void setCheckForProperNouns(boolean newM_CheckProperNouns) {
    this.m_CheckForProperNouns = newM_CheckProperNouns;
  }
  
  /**
   * Get the M_Stopwords value.
   * @return the M_Stopwords value.
   */
  public Stopwords getStopwords() {
    return m_Stopwords;
  }

  /**
   * Set the M_Stopwords value.
   * @param newM_Stopwords The new M_Stopwords value.
   */
  public void setStopwords(Stopwords newM_Stopwords) {
    this.m_Stopwords = newM_Stopwords;
  }

  
  /**
   * Get the Stemmer value.
   * @return the Stemmer value.
   */
  public Stemmer getStemmer() {

    return m_Stemmer;
  }

  /**
   * Set the Stemmer value.
   * @param newStemmer The new Stemmer value.
   */
  public void setStemmer(Stemmer newStemmer) {

    this.m_Stemmer = newStemmer;
  }

  /**
   * Get the value of MinNumOccur.
   *
   * @return Value of MinNumOccur.
   */
  public int getMinNumOccur() {
    
    return m_MinNumOccur;
  }
  
  /**
   * Set the value of MinNumOccur.
   *
   * @param newMinNumOccur Value to assign to MinNumOccur.
   */
  public void setMinNumOccur(int newMinNumOccur) {
    
    m_MinNumOccur = newMinNumOccur;
  }
  
  /**
   * Get the value of MaxPhraseLength.
   *
   * @return Value of MaxPhraseLength.
   */
  public int getMaxPhraseLength() {
    
    return m_MaxPhraseLength;
  }
  
  /**
   * Set the value of MaxPhraseLength.
   *
   * @param newMaxPhraseLength Value to assign to MaxPhraseLength.
   */
  public void setMaxPhraseLength(int newMaxPhraseLength) {
    
    m_MaxPhraseLength = newMaxPhraseLength;
  }
  
  /**
   * Get the value of MinPhraseLength.
   *
   * @return Value of MinPhraseLength.
   */
  public int getMinPhraseLength() {
    
    return m_MinPhraseLength;
  }
  
  /**
   * Set the value of MinPhraseLength.
   *
   * @param newMinPhraseLength Value to assign to MinPhraseLength.
   */
  public void setMinPhraseLength(int newMinPhraseLength) {
    
    m_MinPhraseLength = newMinPhraseLength;
  }

  /**
   * Returns the index of the stemmed phrases in the output ARFF file.
   */
  public int getStemmedPhraseIndex() {

    return m_DocumentAtt;
  }

  /**
   * Returns the index of the unstemmed phrases in the output ARFF file.
   */
  public int getUnstemmedPhraseIndex() {

    return m_DocumentAtt + 1;
  }

  /**
   * Returns the index of the phrases' probabilities in the output ARFF file.
   */
  public int getProbabilityIndex() {

    int index = m_DocumentAtt + 4;

    if (m_Debug) {
      if (m_KFused) {
    index++;
      }
    }
    return index;
  }

  /**
   * Returns the index of the phrases' ranks in the output ARFF file.
   */
  public int getRankIndex() {

    return getProbabilityIndex() + 1;
  }

  /**
   * Get the value of DocumentAtt.
   *
   * @return Value of DocumentAtt.
   */
  public int getDocumentAtt() {
    
    return m_DocumentAtt;
  }
  
  /**
   * Set the value of DocumentAtt.
   *
   * @param newDocumentAtt Value to assign to DocumentAtt.
   */
  public void setDocumentAtt(int newDocumentAtt) {
    
    m_DocumentAtt = newDocumentAtt;
  }
  
  /**
   * Get the value of KeyphraseAtt.
   *
   * @return Value of KeyphraseAtt.
   */
  public int getKeyphrasesAtt() {
    
    return m_KeyphrasesAtt;
  }
  
  /**
   * Set the value of KeyphrasesAtt.
   *
   * @param newKeyphrasesAtt Value to assign to KeyphrasesAtt.
   */
  public void setKeyphrasesAtt(int newKeyphrasesAtt) {
    
    m_KeyphrasesAtt = newKeyphrasesAtt;
  }
  
  
  /**
   * Get the value of Debug.
   *
   * @return Value of Debug.
   */
  public boolean getDebug() {
    
    return m_Debug;
  }
  
  /**
   * Set the value of Debug.
   *
   * @param newDebug Value to assign to Debug.
   */
  public void setDebug(boolean newDebug) {
    
    m_Debug = newDebug;
  }

  /**
   * Sets whether keyphrase frequency attribute is used.
   */
  public void setKFused(boolean flag) {

    m_KFused = flag;
    if (flag) {
      m_NumFeatures = 3;
    } else {
      m_NumFeatures = 2;
    }
  }

  /**
   * Gets whether keyphrase frequency attribute is used.
   */
  public boolean getKFused() {

    return m_KFused;
  }

  /**
   * Get whether the supplied columns are to be processed
   *
   * @return true if the supplied columns won't be processed
   */
  public boolean getDisallowInternalPeriods() {

    return m_DisallowInternalPeriods;
  }

  /**
   * Set whether selected columns should be processed. If true the 
   * selected columns won't be processed.
   *
   * @param invert the new invert setting
   */
  public void setDisallowInternalPeriods(boolean disallow) {

    m_DisallowInternalPeriods = disallow;
  }

  /**
   * Parses a given list of options controlling the behaviour of this object.
   * Valid options are:<p>
   *
   * -K<br>
   * Specifies whether keyphrase frequency statistic is used.<p>
   *
   * -M length<br>
   * Sets the maximum phrase length (default: 3).<p>
   *
   * -L length<br>
   * Sets the minimum phrase length (default: 1).<p>
   *
   * -D<br>
   * Turns debugging mode on.<p>
   *
   * -I index<br>
   * Sets the index of the attribute containing the documents (default: 0).<p>
   *
   * -J index<br>
   * Sets the index of the attribute containing the keyphrases (default: 1).<p>
   *
   * -P<br>
   * Disallow internal periods <p>
   *
   * -O number<br>
   * The minimum number of times a phrase needs to occur (default: 2). <p>
   *
   * @param options the list of options as an array of strings
   * @exception Exception if an option is not supported
   */
  public void setOptions(String[] options) throws Exception {

    setKFused(Utils.getFlag('K', options));
    setDebug(Utils.getFlag('D', options));
    String docAttIndexString = Utils.getOption('I', options);
    if (docAttIndexString.length() > 0) {
      setDocumentAtt(Integer.parseInt(docAttIndexString) - 1);
    } else {
      setDocumentAtt(0);
    }
    String keyphraseAttIndexString = Utils.getOption('J', options);
    if (keyphraseAttIndexString.length() > 0) {
      setKeyphrasesAtt(Integer.parseInt(keyphraseAttIndexString) - 1);
    } else {
      setKeyphrasesAtt(1);
    }
    String maxPhraseLengthString = Utils.getOption('M', options);
    if (maxPhraseLengthString.length() > 0) {
      setMaxPhraseLength(Integer.parseInt(maxPhraseLengthString));
    } else {
      setMaxPhraseLength(3);
    }
    String minPhraseLengthString = Utils.getOption('M', options);
    if (minPhraseLengthString.length() > 0) {
      setMinPhraseLength(Integer.parseInt(minPhraseLengthString));
    } else {
      setMinPhraseLength(1);
    }
    String minNumOccurString = Utils.getOption('O', options);
    if (minNumOccurString.length() > 0) {
      setMinNumOccur(Integer.parseInt(minNumOccurString));
    } else {
      setMinNumOccur(2);
    }
    setDisallowInternalPeriods(Utils.getFlag('P', options));
   }

  /**
   * Gets the current settings of the filter.
   *
   * @return an array of strings suitable for passing to setOptions
   */
  public String [] getOptions() {

    String [] options = new String [13];
    int current = 0;

    if (getKFused()) {
      options[current++] = "-K";
    }
    if (getDebug()) {
      options[current++] = "-D";
    }
    options[current++] = "-I"; 
    options[current++] = "" + (getDocumentAtt() + 1);
    options[current++] = "-J"; 
    options[current++] = "" + (getKeyphrasesAtt() + 1);
    options[current++] = "-M"; 
    options[current++] = "" + (getMaxPhraseLength());
    options[current++] = "-L"; 
    options[current++] = "" + (getMinPhraseLength());
    options[current++] = "-O"; 
    options[current++] = "" + (getMinNumOccur());

    if (getDisallowInternalPeriods()) {
      options[current++] = "-P";
    }

    while (current < options.length) {
      options[current++] = "";
    }
    return options;
  }

  /**
   * Returns an enumeration describing the available options
   *
   * @return an enumeration of all the available options
   */
  public Enumeration listOptions() {

    Vector newVector = new Vector(7);

    newVector.addElement(new Option(
          "\tSpecifies whether keyphrase frequency statistic is used.",
              "K", 0, "-K"));
    newVector.addElement(new Option(
          "\tSets the maximum phrase length (default: 3).",
              "M", 1, "-M <length>"));
    newVector.addElement(new Option(
          "\tSets the minimum phrase length (default: 1).",
              "L", 1, "-L <length>"));
    newVector.addElement(new Option(
          "\tTurns debugging mode on.",
              "D", 0, "-D"));
    newVector.addElement(new Option(
          "\tSets the index of the document attribute (default: 0).",
              "I", 1, "-I"));
    newVector.addElement(new Option(
          "\tSets the index of the keyphrase attribute (default: 1).",
              "J", 1, "-J"));
    newVector.addElement(new Option(
          "\tDisallow internal periods.",
              "P", 0, "-P"));
    newVector.addElement(new Option(
          "\tSet the minimum number of occurences (default: 2).",
              "O", 1, "-O"));

    return newVector.elements();
  }

  /**
   * Returns a string describing this filter
   *
   * @return a description of the filter suitable for
   * displaying in the explorer/experimenter gui
   */
  public String globalInfo() {
    return "Converts incoming data into data appropriate for " +
      "keyphrase classification.";
  }

  /**
   * Sets the format of the input instances.
   *
   * @param instanceInfo an Instances object containing the input
   * instance structure (any instances contained in the object are
   * ignored - only the structure is required).
   * @return true if the outputFormat may be collected immediately 
   */
  public boolean setInputFormat(Instances instanceInfo) throws Exception {

    if (instanceInfo.classIndex() >= 0) {
      throw new Exception("Don't know what do to if class index set!");
    }
    if (!instanceInfo.attribute(m_KeyphrasesAtt).isString() ||
    !instanceInfo.attribute(m_DocumentAtt).isString()) {
      throw new Exception("Keyphrase attribute and document attribute " +
              "need to be string attributes.");
    }
    m_PunctFilter = new KEAPhraseFilter();
    int[] arr = new int[1];
    arr[0] = m_DocumentAtt;
    m_PunctFilter.setAttributeIndicesArray(arr);
    m_PunctFilter.setInputFormat(instanceInfo);
    m_PunctFilter.setDisallowInternalPeriods(getDisallowInternalPeriods());
    m_NumbersFilter = new NumbersFilter();
    m_NumbersFilter.setInputFormat(m_PunctFilter.getOutputFormat());
    super.setInputFormat(m_NumbersFilter.getOutputFormat());
    return false;
  }

  /**
   * Input an instance for filtering. Ordinarily the instance is processed
   * and made available for output immediately. Some filters require all
   * instances be read before producing output.
   *
   * @param instance the input instance
   * @return true if the filtered instance may now be
   * collected with output().
   * @exception Exception if the input instance was not of the correct 
   * format or if there was a problem with the filtering.
   */
  public boolean input(Instance instance) throws Exception {

    if (getInputFormat() == null) {
      throw new Exception("No input instance format defined");
    }
    if (m_NewBatch) {
      resetQueue();
      m_NewBatch = false;
    }

    if (m_Debug) {
      System.err.println("-- Reading instance");
    }

    m_PunctFilter.input(instance);
    m_PunctFilter.batchFinished();
    instance = m_PunctFilter.output();

    m_NumbersFilter.input(instance);
    m_NumbersFilter.batchFinished();
    instance = m_NumbersFilter.output();
    
    if (m_Dictionary == null) {
      bufferInput(instance);
      return false;
    } else {
      FastVector vector = convertInstance(instance, false);
      Enumeration enum = vector.elements();
      while (enum.hasMoreElements()) {
    Instance inst = (Instance)enum.nextElement();
    push(inst);
      }
      return true;
    }
  }

  /**
   * Signify that this batch of input to the filter is finished. 
   * If the filter requires all instances prior to filtering,
   * output() may now be called to retrieve the filtered instances.
   *
   * @return true if there are instances pending output
   * @exception Exception if no input structure has been defined
   */
  public boolean batchFinished() throws Exception {

    if (getInputFormat() == null) {
      throw new Exception("No input instance format defined");
    }
    if (m_Dictionary == null) {
      buildGlobalDictionaries();
      buildClassifier();
      convertPendingInstances();
    } 
    flushInput();
    m_NewBatch = true;
    return (numPendingOutput() != 0);
  }

  /**
   * Builds the global dictionaries.
   */
  private void buildGlobalDictionaries() throws Exception {

    if (m_Debug) {
      System.err.println("--- Building global dictionaries");
    }
    
    // Build dictionary of n-grams with associated
    // document frequencies
    m_Dictionary = new HashMap();
    for (int i = 0; i < getInputFormat().numInstances(); i++) {
      String str = getInputFormat().instance(i).stringValue(m_DocumentAtt);
      HashMap hash = getPhrasesForDictionary(str);
      Iterator it = hash.keySet().iterator();
      while (it.hasNext()) {
    String phrase = (String)it.next();
    Counter counter = (Counter)m_Dictionary.get(phrase);
    if (counter == null) {
      m_Dictionary.put(phrase, new Counter());
    } else {
      counter.increment();
    }
      }
    }
    
    if (m_KFused) {
      
      // Build dictionary of n-grams that occur as keyphrases
      // with associated keyphrase frequencies
      m_KeyphraseDictionary = new HashMap();
      for (int i = 0; i < getInputFormat().numInstances(); i++) {
    String str = getInputFormat().instance(i).stringValue(m_KeyphrasesAtt);
    HashMap hash = getGivenKeyphrases(str, false);
    if (hash != null) {
      Iterator it = hash.keySet().iterator();
      while (it.hasNext()) {
        String phrase = (String)it.next();
        Counter counter = (Counter)m_KeyphraseDictionary.get(phrase);
        if (counter == null) {
          m_KeyphraseDictionary.put(phrase, new Counter());
        } else {
          counter.increment();
        }
      }
    }
      }
    } else {
      m_KeyphraseDictionary = null;
    }
    
    // Set the number of documents in the global corpus
    m_NumDocs = getInputFormat().numInstances();
  }
 
  /**
   * Builds the classifier.
   */
  private void buildClassifier() throws Exception {
    
    // Generate input format for classifier
    FastVector atts = new FastVector();
    for (int i = 0; i < getInputFormat().numAttributes(); i++) {
      if (i == m_DocumentAtt) {
    atts.addElement(new Attribute("TFxIDF"));
    atts.addElement(new Attribute("First_occurrence"));
    if (m_KFused) {
      atts.addElement(new Attribute("Keyphrase_frequency"));
    }
      } else if (i == m_KeyphrasesAtt) {
    FastVector vals = new FastVector(2);
    vals.addElement("False");
    vals.addElement("True");
    atts.addElement(new Attribute("Keyphrase?", vals));
      } 
    }
    m_ClassifierData = new Instances("ClassifierData", atts, 0);
    m_ClassifierData.setClassIndex(m_NumFeatures);
    
    if (m_Debug) {
      System.err.println("--- Converting instances for classifier");
    }
    
    // Convert pending input instances into data for classifier
    for(int i = 0; i < getInputFormat().numInstances(); i++) {
      Instance current = getInputFormat().instance(i);

      // Get the key phrases for the document
      String keyphrases = current.stringValue(m_KeyphrasesAtt);
      HashMap hashKeyphrases = getGivenKeyphrases(keyphrases, false);
      HashMap hashKeysEval = getGivenKeyphrases(keyphrases, true);

      // Get the phrases for the document
      HashMap hash = new HashMap();
      int length = getPhrases(hash, current.stringValue(m_DocumentAtt));

      // Compute the feature values for each phrase and
      // add the instance to the data for the classifier
      Iterator it = hash.keySet().iterator();
      while (it.hasNext()) {
    String phrase = (String)it.next();
    FastVector phraseInfo = (FastVector)hash.get(phrase);
    double[] vals =  featVals(phrase, phraseInfo, true,
                  hashKeysEval, hashKeyphrases, length);
    Instance inst = new Instance(current.weight(), vals);
    m_ClassifierData.add(inst);
      }
    }
    
    if (m_Debug) {
      System.err.println("--- Building classifier");
    }
    
    // Build classifier
    FilteredClassifier fclass = new FilteredClassifier();
    fclass.setClassifier(new weka.classifiers.NaiveBayesSimple());
    fclass.setFilter(new DiscretizeFilter());
    m_Classifier = fclass;
    m_Classifier.buildClassifier(m_ClassifierData);

    if (m_Debug) {
      System.err.println(m_Classifier);
    }

    // Save space
    m_ClassifierData = new Instances(m_ClassifierData, 0);
  }

  /** 
   * Conmputes the feature values for a given phrase.
   */
  private double[] featVals(String phrase, FastVector phraseInfo, 
                boolean training, HashMap hashKeysEval,
                HashMap hashKeyphrases, int length) {

    // Compute feature values
    Counter counterLocal = (Counter)phraseInfo.elementAt(1);
    double[] newInst = new double[m_NumFeatures + 1];
      
    // Compute TFxIDF
    Counter counterGlobal = (Counter)m_Dictionary.get(phrase);
    double localVal = counterLocal.value(), globalVal = 0;
    if (counterGlobal != null) {
      globalVal = counterGlobal.value();
      if (training) {
    globalVal = globalVal - 1;
      }
    }
    
    // Just devide by length to get approximation of probability
    // that phrase in document is our phrase
    newInst[m_TfidfIndex] = (localVal / ((double)length)) *
      (-Math.log((globalVal + 1)/ ((double)m_NumDocs + 1)));
      
    // Compute first occurrence
    Counter counterFirst = (Counter)phraseInfo.elementAt(0);
    newInst[m_FirstOccurIndex] = (double)counterFirst.value() /
      (double)length;
    
    // Is keyphrase frequency attribute being used?
    if (m_KFused) {
      Counter keyphraseC = (Counter)m_KeyphraseDictionary.get(phrase);
      if ((training) && (hashKeyphrases != null) &&
      (hashKeyphrases.containsKey(phrase))) {
    newInst[m_KeyFreqIndex] = keyphraseC.value() - 1;
      } else {
    if (keyphraseC != null) {
      newInst[m_KeyFreqIndex] = keyphraseC.value();
    } else {
      newInst[m_KeyFreqIndex] = 0;
    }
      }
    }

    // Compute class value
    String phraseInEvalFormat = evalFormat((String)phraseInfo.elementAt(2));
    if (hashKeysEval == null) { // no author-assigned keyphrases
      newInst[m_NumFeatures] = Instance.missingValue();
    } else if (!hashKeysEval.containsKey(phraseInEvalFormat)) {
      newInst[m_NumFeatures] = 0; // No keyphrase
    } else {
      hashKeysEval.remove(phraseInEvalFormat);
      newInst[m_NumFeatures] = 1; // Keyphrase
    }
    return newInst;
  }

  /**
   * Sets output format and converts pending input instances.
   */
  private void convertPendingInstances() throws Exception {

    if (m_Debug) {
      System.err.println("--- Converting pending instances");
    }
    
    // Create output format for filter
    FastVector atts = new FastVector();
    for (int i = 0; i < getInputFormat().numAttributes(); i++) {
      if (i == m_DocumentAtt) {
    atts.addElement(new Attribute("N-gram", null));
    atts.addElement(new Attribute("N-gram-original", null));
    atts.addElement(new Attribute("TFxIDF"));
    atts.addElement(new Attribute("First_occurrence"));
    if (m_Debug) {
      if (m_KFused) {
        atts.addElement(new Attribute("Keyphrase_frequency"));
      }
    }
    atts.addElement(new Attribute("Probability"));
    atts.addElement(new Attribute("Rank"));
      } else if (i == m_KeyphrasesAtt) {
    FastVector vals = new FastVector(2);
    vals.addElement("False");
    vals.addElement("True");
    atts.addElement(new Attribute("Keyphrase?", vals));
      } else {
    atts.addElement(getInputFormat().attribute(i));
      }
    }
    Instances outFormat = new Instances("KEAdata", atts, 0);
    setOutputFormat(outFormat);
    
    // Convert pending input instances into output data
    for(int i = 0; i < getInputFormat().numInstances(); i++) {
      Instance current = getInputFormat().instance(i);
      FastVector vector = convertInstance(current, true);
      Enumeration enum = vector.elements();
      while (enum.hasMoreElements()) {
    Instance inst = (Instance)enum.nextElement();
    push(inst);
      }
    }
  } 

  /**
   * Converts an instance.
   */
  private FastVector convertInstance(Instance instance, boolean training) 
    throws Exception {

    FastVector vector = new FastVector();

    if (m_Debug) {
      System.err.println("-- Converting instance");
    }

    // Get the key phrases for the document
    HashMap hashKeyphrases = null;
    HashMap hashKeysEval = null;
    if (!instance.isMissing(m_KeyphrasesAtt)) {
      String keyphrases = instance.stringValue(m_KeyphrasesAtt);
      hashKeyphrases = getGivenKeyphrases(keyphrases, false);
      hashKeysEval = getGivenKeyphrases(keyphrases, true);
    }

    // Get the phrases for the document
    HashMap hash = new HashMap();
    int length = getPhrases(hash, instance.stringValue(m_DocumentAtt));

    // Compute number of extra attributes
    int numFeatures = 5;
    if (m_Debug) {
      if (m_KFused) {
    numFeatures = numFeatures + 1;
      }
    } 

    // Set indices of key attributes
    int phraseAttIndex = m_DocumentAtt;
    int tfidfAttIndex = m_DocumentAtt + 2;
    int distAttIndex = m_DocumentAtt + 3;
    int probsAttIndex = m_DocumentAtt + numFeatures - 1;

    // Go through the phrases and convert them into instances
    Iterator it = hash.keySet().iterator();
    while (it.hasNext()) {
      String phrase = (String)it.next();
      FastVector phraseInfo = (FastVector)hash.get(phrase);
      double[] vals =  featVals(phrase, phraseInfo, training,
                hashKeysEval, hashKeyphrases, length);
      Instance inst = new Instance(instance.weight(), vals);
      inst.setDataset(m_ClassifierData);

      // Get probability of phrase being key phrase
      double[] probs = m_Classifier.distributionForInstance(inst);
      double prob = probs[1];

      // Compute attribute values for final instance
      double[] newInst = 
    new double[instance.numAttributes() + numFeatures];
      int pos = 0;
      for (int i = 0; i < instance.numAttributes(); i++) {
    if (i == m_DocumentAtt) {
        
      // Add phrase
      int index = outputFormatPeek().attribute(pos).
        addStringValue(phrase);
      newInst[pos++] = index;
      
      // Add original version
      index = outputFormatPeek().attribute(pos).
        addStringValue((String)phraseInfo.elementAt(2));
      newInst[pos++] = index;

      // Add TFxIDF
      newInst[pos++] = inst.value(m_TfidfIndex);
        
      // Add distance
      newInst[pos++] = inst.value(m_FirstOccurIndex);

        // Add other features
      if (m_Debug) {
        if (m_KFused) {
          newInst[pos++] = inst.value(m_KeyFreqIndex);
        }
      }

      // Add probability 
      probsAttIndex = pos;
      newInst[pos++] = prob;

      // Set rank to missing (computed below)
      newInst[pos++] = Instance.missingValue();
    } else if (i == m_KeyphrasesAtt) {
      newInst[pos++] = inst.classValue();
    } else {
      newInst[pos++] = instance.value(i);
    }
      }
      Instance ins = new Instance(instance.weight(), newInst);
      ins.setDataset(outputFormatPeek());
      vector.addElement(ins);
    }

    // Add dummy instances for keyphrases that don't occur
    // in the document
    if (hashKeysEval != null) {
      Iterator phrases = hashKeysEval.keySet().iterator();
      while (phrases.hasNext()) {
    String phrase = (String)phrases.next();
    double[] newInst = 
      new double[instance.numAttributes() + numFeatures];
    int pos = 0;
    for (int i = 0; i < instance.numAttributes(); i++) {
      if (i == m_DocumentAtt) {
        
        // Add phrase
        int index = outputFormatPeek().attribute(pos).
          addStringValue(phrase);
        newInst[pos++] = (double)index;
        
        // Add original version
        index = outputFormatPeek().attribute(pos).
          addStringValue((String)hashKeysEval.get(phrase));
        newInst[pos++] = (double)index;
        
        // Add TFxIDF
        newInst[pos++] = Instance.missingValue();
        
        // Add distance
        newInst[pos++] = Instance.missingValue();
          
        // Add other features
        if (m_Debug) {
          if (m_KFused) {
        newInst[pos++] = Instance.missingValue();
          }
        }

        // Add probability and rank
        newInst[pos++] = -Double.MAX_VALUE;
        newInst[pos++] = Instance.missingValue();
      } else if (i == m_KeyphrasesAtt) {
        newInst[pos++] = 1; // Keyphrase
      } else {
        newInst[pos++] = instance.value(i);
      } 
    }
    Instance inst = new Instance(instance.weight(), newInst);
    inst.setDataset(outputFormatPeek());
    vector.addElement(inst);
      }
    }

    // Sort phrases according to their distance (stable sort)
    double[] vals = new double[vector.size()];
    for (int i = 0; i < vals.length; i++) {
      vals[i] = ((Instance)vector.elementAt(i)).value(distAttIndex);
    }
    FastVector newVector = new FastVector(vector.size());
    int[] sortedIndices = Utils.stableSort(vals);
    for (int i = 0; i < vals.length; i++) {
      newVector.addElement(vector.elementAt(sortedIndices[i]));
    }
    vector = newVector;

    // Sort phrases according to their tfxidf value (stable sort)
    for (int i = 0; i < vals.length; i++) {
      vals[i] = -((Instance)vector.elementAt(i)).value(tfidfAttIndex);
    }
    newVector = new FastVector(vector.size());
    sortedIndices = Utils.stableSort(vals);
    for (int i = 0; i < vals.length; i++) {
      newVector.addElement(vector.elementAt(sortedIndices[i]));
    }
    vector = newVector;

    // Sort phrases according to their probability (stable sort)
    for (int i = 0; i < vals.length; i++) {
      vals[i] = 1 - ((Instance)vector.elementAt(i)).value(probsAttIndex);
    }
    newVector = new FastVector(vector.size());
    sortedIndices = Utils.stableSort(vals);
    for (int i = 0; i < vals.length; i++) {
      newVector.addElement(vector.elementAt(sortedIndices[i]));
    }
    vector = newVector;

    // Compute rank of phrases. Check for subphrases that are ranked
    // lower than superphrases and assign probability -1 and set the
    // rank to Integer.MAX_VALUE
    int rank = 1;
    for (int i = 0; i < vals.length; i++) {
      Instance currentInstance = (Instance)vector.elementAt(i);

      // Short cut: if phrase very unlikely make rank very low and continue
      if (Utils.grOrEq(vals[i], 1.0)) {
    currentInstance.setValue(probsAttIndex + 1, Integer.MAX_VALUE);
    continue;
      }

      // Otherwise look for super phrase starting with first phrase
      // in list that has same probability, TFxIDF value, and distance as
      // current phrase. We do this to catch all superphrases
      // that have same probability, TFxIDF value and distance as current phrase.
      int startInd = i;
      while (startInd < vals.length) {
    Instance inst = (Instance)vector.elementAt(startInd);
    if ((inst.value(tfidfAttIndex) != 
         currentInstance.value(tfidfAttIndex)) ||
        (inst.value(probsAttIndex) != 
         currentInstance.value(probsAttIndex)) ||
        (inst.value(distAttIndex) !=
         currentInstance.value(distAttIndex))) {
      break;
    }
    startInd++;
      }
      String val = currentInstance.stringValue(phraseAttIndex);
      boolean foundSuperphrase = false;
      for (int j = startInd - 1; j >= 0; j--) {
    if (j != i) {
      Instance candidate = (Instance)vector.elementAt(j);
      String potSuperphrase = candidate.stringValue(phraseAttIndex);
      if (val.length() <= potSuperphrase.length()) {
        if (KEAFilter.contains(val, potSuperphrase)) {
          foundSuperphrase = true;
          break;
        }
      }
    }
      }
      if (foundSuperphrase) {
    currentInstance.setValue(probsAttIndex + 1, Integer.MAX_VALUE);
      } else {
    currentInstance.setValue(probsAttIndex + 1, rank++);
      }
    }
    return vector;
  }
    
  /** 
   * Checks whether one phrase is a subphrase of another phrase.
   */
  private static boolean contains(String sub, String sup) {

    int i = 0;
    while (i + sub.length() - 1 < sup.length()) {
      int j;
      for (j = 0; j < sub.length(); j++) {
    if (sub.charAt(j) != sup.charAt(i + j)) {
      break;
    }
      }
      if (j == sub.length()) {
    if ((i + j) < sup.length()) {
      if (sup.charAt(i + j) == ' ') {
        return true;
      } else {
        return false;
      }
    } else {
      return true;
    }
      }

      // Skip forward to next space
      do {
    i++;
      } while ((i < sup.length()) && (sup.charAt(i) != ' '));
      i++;
    }
    return false;
  }

  /**
   * Returns a hashtable. Fills the hashtable
   * with the stemmed n-grams occuring in the given string
   * (as keys) and the number of times it occurs.
   */
  private HashMap getPhrasesForDictionary(String str) {

    String[] buffer = new String[m_MaxPhraseLength];
    HashMap hash = new HashMap();

    StringTokenizer tok = new StringTokenizer(str, "\n");
    while (tok.hasMoreTokens()) {
      String phrase = tok.nextToken();
      int numSeen = 0;
      StringTokenizer wordTok = new StringTokenizer(phrase, " ");
      while (wordTok.hasMoreTokens()) {
    String word = wordTok.nextToken();
    
    // Store word in buffer
    for (int i = 0; i < m_MaxPhraseLength - 1; i++) {
      buffer[i] = buffer[i + 1];
    }
    buffer[m_MaxPhraseLength - 1] = word;
    
    // How many are buffered?
    numSeen++;
    if (numSeen > m_MaxPhraseLength) {
      numSeen = m_MaxPhraseLength;
    }
    
    // Don't consider phrases that end with a stop word
    if (m_Stopwords.isStopword(buffer[m_MaxPhraseLength - 1])) {
      continue;
    }
    
    // Loop through buffer and add phrases to hashtable
    StringBuffer phraseBuffer = new StringBuffer();
    for (int i = 1; i <= numSeen; i++) {
      if (i > 1) {
        phraseBuffer.insert(0, ' ');
      }
      phraseBuffer.insert(0, buffer[m_MaxPhraseLength - i]);
      
      // Don't consider phrases that begin with a stop word
      if ((i > 1) && 
          (m_Stopwords.isStopword(buffer[m_MaxPhraseLength - i]))) {
        continue;
      }
      
      // Only consider phrases with minimum length
      if (i >= m_MinPhraseLength) {
        
        // Stem string
        String orig = phraseBuffer.toString();
        String internal = internalFormat(orig);
        Counter count = (Counter)hash.get(internal);
        if (count == null) {
          hash.put(internal, new Counter());
        } else {
          count.increment();
        }
        
        // Add components if phrase is single word before
        // conversion into internal format (i.e. error-correcting)
        /*if ((orig.indexOf(' ') == -1) &&
          (internal.indexOf(' ') != -1)) {
          StringTokenizer tokW = new StringTokenizer(internal, " ");
          while (tokW.hasMoreTokens()) {
          String comp = (String)tokW.nextToken();
          Counter countW = (Counter)hash.get(comp);
          if (countW == null) {
          hash.put(comp, new Counter());
          } else {
          countW.increment();
          }
          }
          }*/
      }
    }
      }
    }
    return hash;
  }

  /**
   * Expects an empty hashtable. Fills the hashtable
   * with the stemmed n-grams occuring in the given string
   * (as keys). Stores the position, the number of occurences,
   * and the most commonly occurring orgininal version of
   * each n-gram.
   *
   * N-grams that occur less than m_MinNumOccur are not used.
   *
   * Returns the total number of words (!) in the string.
   */
  private int getPhrases(HashMap hash, String str) {

    String[] buffer = new String[m_MaxPhraseLength];
    
    StringTokenizer tok = new StringTokenizer(str, "\n");
    int pos = 1; 
    while (tok.hasMoreTokens()) {
      String phrase = tok.nextToken();
      int numSeen = 0;
      StringTokenizer wordTok = new StringTokenizer(phrase, " ");
      while (wordTok.hasMoreTokens()) {
    String word = wordTok.nextToken();
    
    // Store word in buffer
    for (int i = 0; i < m_MaxPhraseLength - 1; i++) {
      buffer[i] = buffer[i + 1];
    }
    buffer[m_MaxPhraseLength - 1] = word;
    
    // How many are buffered?
    numSeen++;
    if (numSeen > m_MaxPhraseLength) {
      numSeen = m_MaxPhraseLength;
    }
    
    // Don't consider phrases that end with a stop word
    if (m_Stopwords.isStopword(buffer[m_MaxPhraseLength - 1])) {
      pos++;
      continue;
    }
    
    // Loop through buffer and add phrases to hashtable
    StringBuffer phraseBuffer = new StringBuffer();
    for (int i = 1; i <= numSeen; i++) {
      if (i > 1) {
        phraseBuffer.insert(0, ' ');
      }
      phraseBuffer.insert(0, buffer[m_MaxPhraseLength - i]);
      
      // Don't consider phrases that begin with a stop word
      if ((i > 1) && 
          (m_Stopwords.isStopword(buffer[m_MaxPhraseLength - i]))) {
        continue;
      }
      
      // Only consider phrases with minimum length
      if (i >= m_MinPhraseLength) {
        
        // Stem string
        String phrStr = phraseBuffer.toString();
        String internal = internalFormat(phrStr);
        FastVector vec = (FastVector)hash.get(internal);
        if (vec == null) {
          vec = new FastVector(3);
          
          // HashMap for storing all versions
          HashMap secHash = new HashMap();
          secHash.put(phrStr, new Counter());
          
          // Update hashtable with all the info
          vec.addElement(new Counter(pos + 1 - i));
          vec.addElement(new Counter());
          vec.addElement(secHash);
          hash.put(internal, vec);
        } else {
          
          // Update number of occurrences
          ((Counter)((FastVector)vec).elementAt(1)).increment();
          
          // Update hashtable storing different versions
          HashMap secHash = (HashMap)vec.elementAt(2);
          Counter count = (Counter)secHash.get(phrStr);
          if (count == null) {
        secHash.put(phrStr, new Counter());
          } else {
        count.increment();
          }
        }
      }
    }
    pos++;
      }
    }
    
    // Replace secondary hashtables with most commonly occurring
    // version of each phrase (canonical) form. Delete all words
    // that are proper nouns.
    Iterator phrases = hash.keySet().iterator();
    while (phrases.hasNext()) {
      String phrase = (String)phrases.next();
      FastVector info = (FastVector)hash.get(phrase);

      // Occurring less than m_MinNumOccur?
      if (((Counter)((FastVector)info).elementAt(1)).value() < m_MinNumOccur) {
    phrases.remove();
    continue;
      }

      // Get canonical form
      String canForm = canonicalForm((HashMap)info.elementAt(2));
      if (canForm == null) {
    phrases.remove();
      } else {
    info.setElementAt(canForm, 2);
      }
    }
    return pos;
  }

  /**
   * Create canonical form of phrase.
   */
  private String canonicalForm(HashMap secHash) {

    int max = 0; String bestVersion = null;
    boolean allFullyHyphenated = true;
    int num = 0;
    Iterator versions = secHash.keySet().iterator();
    while (versions.hasNext()) {
      num++;
      String version = (String)versions.next();

      // Are all the words joined up?
      if (!isFullyHyphenated(version)) {
    allFullyHyphenated = false;
      }

      // Check for how often this version occurs
      Counter count = (Counter)secHash.get(version);
      if (count.value() > max) {
    max = count.value();
    bestVersion = version;
      }
    }
    if ((getCheckForProperNouns()) && (num == 1) && properNoun(bestVersion)) {
    //if (allProperNouns) {
      return null;
    } else {
      if (isFullyHyphenated(bestVersion) &&
      !allFullyHyphenated) {
    bestVersion = bestVersion.replace('-', ' ');
      }
      return bestVersion;
    }
  }

  /**
   * Checks whether the given phrase is
   * fully hyphenated.
   */
  private boolean isFullyHyphenated(String str) {
    
    return (str.indexOf(' ') == -1);
  }

  /**
   * Checks whether the given string is a 
   * proper noun.
   *
   * @return true if it is a potential proper noun
   */
  private static boolean properNoun(String str) {

    // Is it more than one word?
    if (str.indexOf(' ') != -1) {
      return false;
    }

    // Does it start with an upper-case character?
    if (Character.isLowerCase(str.charAt(0))) {
      return false;
    } 

    // Is there at least one character that's
    // not upper-case?
    for (int i = 1; i < str.length(); i++) {
      /*if (Character.isUpperCase(str.charAt(i))) {
    return false;
    }*/
      if (!Character.isUpperCase(str.charAt(i))) {
    return true;
      }
    }
    //return true;
    return false;
  }

  /**
   * Generates the evaluation format of a phrase.
   */
  private String evalFormat(String str) {
    
    return m_Stemmer.stemString(str);
  }

  /** 
   * Generates the internal format of a phrase.
   */
  private String internalFormat(String str) {

    // Remove some non-alphanumeric characters
    str = str.replace('-', ' ');
    str = str.replace('/', ' ');
    str = str.replace('&', ' ');

    // Stem string
    return m_Stemmer.stemString(str);
  }

  /**
   * Gets all the phrases in the given string and puts them into the
   * hashtable.  Also stores the original version of the stemmed
   * phrase in the hash table.  
   */
  private HashMap getGivenKeyphrases(String str,
                       boolean forEval) {

    FastVector vector = new FastVector();
    HashMap hash = new HashMap();
    
    StringTokenizer tok = new StringTokenizer(str, "\n");
    while (tok.hasMoreTokens()) {
      String orig = tok.nextToken();
      orig = orig.trim();
      if (orig.length() > 0) {
    String modified;
    if (!forEval) {
      modified = internalFormat(orig);
    } else {
      modified = evalFormat(orig);
    }
    if (!hash.containsKey(modified)) {
      hash.put(modified, orig);
    } else {
      if (forEval) {
        System.err.println("WARNING: stem of author-assigned keyphrase " +
                   orig + " matches existing stem (skipping it)!");
      }
    }
      }
    }
    if (hash.size() == 0) {
      return null;
    } else {
      return hash;
    }
  }

  /**
   * Main method for testing this class.
   *
   * @param argv should contain arguments to the filter: use -h for help
   */
  public static void main(String [] argv) {
    
    try {
      if (Utils.getFlag('b', argv)) {
    Filter.batchFilterFile(new KEAFilter(), argv);
      } else {
    Filter.filterFile(new KEAFilter(), argv);
      }
    } catch (Exception ex) {
      System.out.println(ex.getMessage());
    }
  }
}