public static class Hyponym {
  private List<String> hyponymPhrases;
  private List<String> listWords;
  private List<String> beginWords;
  private List<String> splitWords;
  private String langID;
    
  public Hyponym(String langID) {
    this.langID = langID;
    hyponymPhrases = new ArrayList<String>();
    listWords = new ArrayList<String>();
    beginWords = new ArrayList<String>();
    splitWords = new ArrayList<String>();
  }

  public void addBeginWords(String[] words) {
    add(words, beginWords);
    Helper.sortByLength(beginWords, false);
  }
    
  public void addHyponymPhrases(String[] phrases) {
    add(phrases, hyponymPhrases);
  }
    
  public void addListWords(String[] words) {
    add(words, listWords);
  }
    
  public void addSplitWords(String[] words) {
    add(words, splitWords);
    Helper.sortByLength(splitWords, false);
  }
    
  public List<String> getBeginWords() {
    return beginWords;
  }
    
  public List<String> getHyponymPhrases() {
    return hyponymPhrases;
  }

  public String getLangID() {
    return langID;
  }

  public String getListQuery() {
    StringBuffer buf = new StringBuffer("(");
    for (String word : listWords) {
      if (buf.length() > 1)
        buf.append(" OR ");
      buf.append(word);
    }
    buf.append(")");
    return buf.toString();
  }

  public List<String> getSplitWords() {
    return splitWords;
  }

  private void add(String[] strs, List<String> list) {
    for (String s : strs)
      if (!list.contains(s))
        list.add(s);
  }
}
 public class EvalResult {
  public int trialID = 0;
  public int numGoldEntity = 0;
  public int numGoldSynonym = 0;
  public double numCorrectSynonym = 0;
  public double numCorrectEntity = 0;
  public double numResultsAboveThreshold = 0;
  public double maxF1Precision = 0;
  public double maxF1Recall = 0;
  public double maxF1Threshold = 0;
  public double precision = 0;
  public double recall = 0;
  public double threshold = 0;
  public double meanAvgPrecision = 0;
  public File goldFile = null;
  public String seeds = "";
  public Feature method = null;
  private StringBuffer buf = new StringBuffer();
  public double getF1() { return Evaluator.computeF1(precision, recall); }
  public double getMaxF1() { return Evaluator.computeF1(maxF1Precision, maxF1Recall); }
  
  public String toString() {
    buf.setLength(0);
    buf.append("===================================================\n");
    if (goldFile != null && method != null)
      buf.append("Results of \"" + goldFile.getName() + "\" using method: " + method + "\n");
    if (seeds != null && seeds.trim().length() > 0)
      buf.append("Seeds: " + seeds + "\n");
    buf.append("Avg. number of results above threshold: " + Helper.formatNumber(numResultsAboveThreshold, 3) + "\n");
    buf.append("Avg. number of correct synonyms: " + Helper.formatNumber(numCorrectSynonym, 3) + " out of " + numGoldSynonym + "\n");
    buf.append("Avg. number of correct entities: " + Helper.formatNumber(numCorrectEntity, 3) + " out of " + numGoldEntity + "\n");
    buf.append("Max. Possible F1: " + Helper.formatNumber(getMaxF1(), 3));
    buf.append(" (Precision: " + Helper.formatNumber(maxF1Precision, 3));
    buf.append(", Recall: " + Helper.formatNumber(maxF1Recall, 3) + ")");
    buf.append(" at threshold: " + Helper.formatNumber(maxF1Threshold, 3) + "\n");
    buf.append("F1: " + Helper.formatNumber(getF1(), 3));
    buf.append(" (Precision: " + Helper.formatNumber(precision, 3));
    buf.append(", Recall: " + Helper.formatNumber(recall, 3) + ")");
    buf.append(" at threshold: " + Helper.formatNumber(threshold, 3) + "\n");
    buf.append("Mean Avg. Precision: " + Helper.formatNumber(meanAvgPrecision, 3));
    return buf.toString();
  }
  
  public String toTabSeperated() {
    buf.setLength(0);
    buf.append(Evaluator.getDataName(goldFile)).append("\t");
    buf.append(method).append("\t");
    buf.append(getMaxF1()).append("\t");
    buf.append(maxF1Precision).append("\t");
    buf.append(maxF1Recall).append("\t");
    buf.append(maxF1Threshold).append("\t");
    buf.append(getF1()).append("\t");
    buf.append(precision).append("\t");
    buf.append(recall).append("\t");
    buf.append(threshold).append("\t");
    buf.append(meanAvgPrecision).append("\n");
    return buf.toString();
  }    
} public class Evaluator {
  
  public static class GoldEntity {
    public Set<String> synonyms = new LinkedHashSet<String>();
  }
  
  public static Logger log = Logger.getLogger(Evaluator.class);
  public static final String EVAL_FILE_SUFFIX = ".xls"; // evaluation results
  public static final String GOLD_FILE_SUFFIX = ".txt"; // evaluation datasets
  public static final double DEFAULT_THRESHOLD = 0.8;
  
  private List<GoldEntity> goldList;
  private Set<String> goldSynonyms;
  private File goldFile;

  public static double computeF1(double prec, double recall) {
    return (prec + recall == 0) ? 0 : (2 * prec * recall) / (prec + recall);
  }
  
  public static String getLangID(File goldFile) {
    if (goldFile == null) return null;
    File parentFile = goldFile.getParentFile();
    if (parentFile == null) return null;
    return parentFile.getName();
  }
  
  public static String getDataName(File goldFile) {
    if (goldFile == null) return null;
    String name = goldFile.getName();
    if (name.endsWith(GOLD_FILE_SUFFIX))
      name = name.substring(0, name.length()-GOLD_FILE_SUFFIX.length());
    return name;
  }
  
  public static List<String> getFirstMentions(File goldFile) {
    List<GoldEntity> goldList = new ArrayList<GoldEntity>();
    Evaluator.loadGoldFile(goldFile, goldList);
    return getFirstMentions(goldList);
  }
  
  public static List<File> getGoldFiles(File dataDir) {
    return getGoldFiles(dataDir, null);
  }
  
  public static List<File> getGoldFiles(File dataDir, String langID) {
    File[] langDirs = dataDir.listFiles();
    List<File> list = new ArrayList<File>();
    
    for (File langDir : langDirs) {
      if (!langDir.isDirectory()) continue;
      if (langID != null && !langDir.getName().equals(langID)) continue;
      File[] files = langDir.listFiles();
      for (File file : files)
        if (file.isFile() && file.getName().endsWith(GOLD_FILE_SUFFIX))
          list.add(file);
    }
    return list;
  }
  
  public static Set<String> getGoldSynonyms(File goldFile) {
    Set<String> allGoldSynonyms = new HashSet<String>();
    List<GoldEntity> goldList = new ArrayList<GoldEntity>();
    loadGoldFile(goldFile, goldList);
    for (GoldEntity ge : goldList)
      allGoldSynonyms.addAll(ge.synonyms);
    return allGoldSynonyms;
  }
  
  public static void loadGoldFile(File goldFile, List<GoldEntity> goldList) {
    if (goldList == null) return;
    goldList.clear();
    log.info("Loading gold file: " + goldFile);
    String content = Helper.readFile(goldFile);
    String[] lines = content.split("\n");

    for (String line : lines) {
      String[] synonyms = line.split("\t");
      GoldEntity ge = makeGoldEntity(synonyms);
      goldList.add(ge);
    }
    log.info("Number of entities in gold file: " + goldList.size());
  }

  public static EvalResult mergeEvalResults(EvalResult[] evalResults) {
    int numTrials = 0;
    for (EvalResult evalResult : evalResults)
      if (evalResult != null)
        numTrials++;
    EvalResult result = new EvalResult();
    for (EvalResult evalResult : evalResults) {
      if (evalResult == null)
        continue;
      mergeEvalResults(evalResult, result, numTrials);
      result.seeds += evalResult.seeds;
      result.method = evalResult.method;
      result.goldFile = evalResult.goldFile;
      result.threshold = evalResult.threshold;
      result.numGoldEntity = evalResult.numGoldEntity;
      result.numGoldSynonym = evalResult.numGoldSynonym;
    }
    return result;
  }
  
  private static List<String> getFirstMentions(List<GoldEntity> goldList) {
    List<String> names = new ArrayList<String>();
    for (GoldEntity ge : goldList)
      names.add(ge.synonyms.iterator().next());
    return names;
  }
  
  private static GoldEntity makeGoldEntity(String[] synonyms) {
    GoldEntity ge = new GoldEntity();
    if (synonyms == null || synonyms.length == 0) return ge;
    
    for (String synonym : synonyms) {
      synonym = synonym.toLowerCase().replace('-', ' ').trim(); // added 04/03/2008
      if (synonym.length() == 0) continue;
      ge.synonyms.add(synonym);
      
      // remove punctuations and add to synonyms
      String optionalChars = WrapperFactory.OPTIONAL_CHAR_STR;
      if (synonym.matches("^.+" + optionalChars + ".+$")) {
        String s = synonym.replaceAll(optionalChars, "").trim();
        if (s.length() > 0)
          ge.synonyms.add(s);
        s = synonym.replaceAll(optionalChars, " ").replaceAll("\\s+", " ").trim();
        if (s.length() > 0)
          ge.synonyms.add(s);
      }
      
      // if is English, do something (added 10/20/2008)
      if (synonym.matches(".*[a-zA-Z].*")) {
        if (synonym.endsWith("y")) {
          ge.synonyms.add(synonym.substring(0, synonym.length()-1) + "ies");
        } else {
          ge.synonyms.add(synonym + "s");
          ge.synonyms.add(synonym + "es");
          ge.synonyms.add("the " + synonym);
//          ge.synonyms.add("comet " + synonym);
        }
      }
    }
    return ge;
  }
  
  private static EvalResult mergeEvalResults(EvalResult fromResult, EvalResult toResult, int numTrials) {
    toResult.numResultsAboveThreshold += fromResult.numResultsAboveThreshold / numTrials;
    toResult.numCorrectEntity += fromResult.numCorrectEntity / numTrials;
    toResult.numCorrectSynonym += fromResult.numCorrectSynonym / numTrials;
    toResult.maxF1Precision += fromResult.maxF1Precision / numTrials;
    toResult.maxF1Recall += fromResult.maxF1Recall / numTrials;
    toResult.maxF1Threshold += fromResult.maxF1Threshold / numTrials;
    toResult.precision += fromResult.precision / numTrials;
    toResult.recall += fromResult.recall / numTrials;
    toResult.meanAvgPrecision += fromResult.meanAvgPrecision / numTrials;
    return toResult;
  }
  
  public Evaluator() {
    goldList = new ArrayList<GoldEntity>();
    goldSynonyms = new HashSet<String>();
  }

  public EvalResult evaluate(EntityList entityList) {
    return evaluate(entityList, DEFAULT_THRESHOLD);
  }
  
  public EvalResult evaluate(EntityList entityList, double threshold) {
    EvalResult eval = new EvalResult();
    if (goldList.size() == 0) {
      log.error("No gold answers loaded!");
      return eval;
    }
    double maxF1 = 0;
    double sumOfPrecisions = 0;
    int numResultAboveThreshold = 0;
    int numCorrectSynonym = 0;
    int numCorrectEntity = 0;
    boolean[] seenGold = new boolean[goldList.size()];

    // traverse through the entire result list
    for (int i = 0; i < entityList.size(); i++) {
      Entity entity = entityList.get(i);
      entity.setCorrect(0);
      
      // count the number of correct synonyms
      if (goldSynonyms.contains(entity.getName().toString()))
        numCorrectSynonym++;

      // get precision at current rank
      double precision = (double) numCorrectSynonym / (i+1);
      
      // count the number of correct entities
      for (int j = 0; j < goldList.size(); j++) {
        Set<String> goldSynonyms = goldList.get(j).synonyms;
        if (goldSynonyms.contains(entity.getName().toString())) {
          entity.setCorrect(seenGold[j] ? 2 : 1);
          if (seenGold[j]) continue;
        } else continue;
        
        // this is the first 'correct' synonym encountered for an entity
        sumOfPrecisions += precision;
        numCorrectEntity++;
        seenGold[j] = true;
        break;
      }
      // get recall and F1 at current rank
      double recall = (double) numCorrectEntity / goldList.size();
      double F1 = computeF1(precision, recall);

      if (F1 > maxF1) {
        eval.maxF1Precision = precision;
        eval.maxF1Recall = recall;
        eval.maxF1Threshold = entity.getScore();
        maxF1 = F1;
      }

      if (entity.getScore() >= threshold) {
        eval.precision = precision;
        eval.recall = recall;
        eval.numCorrectEntity = numCorrectEntity;
        eval.numCorrectSynonym = numCorrectSynonym;
        numResultAboveThreshold++;
      }
    }
    eval.threshold = threshold;
    eval.numResultsAboveThreshold = numResultAboveThreshold;
    eval.meanAvgPrecision = sumOfPrecisions / goldList.size();
    eval.numGoldEntity = goldList.size();
    eval.numGoldSynonym = goldSynonyms.size();
    eval.goldFile = goldFile;
    entityList.setEvalResult(eval);
    return eval;
  }
  
  public String getDataName() {
    return getDataName(goldFile);
  }
  
  public List<String> getFirstMentions() {
    return getFirstMentions(goldList);
  }
  
  public List<GoldEntity> getGoldEntityList() {
    return goldList;
  }
  
  public File getGoldFile() {
    return goldFile;
  }
  
  public Set<String> getGoldSynonyms() {
    return goldSynonyms;
  }

  public void loadGoldFile(File goldFile) {
    this.goldFile = goldFile;
    loadGoldFile(goldFile, goldList);
    goldSynonyms.clear();
    for (GoldEntity ge : goldList)
      goldSynonyms.addAll(ge.synonyms);
  }

}
 public class Entity implements Comparable<Entity> {

  public static Logger log = Logger.getLogger(Entity.class);
  
  /** final score of this entity */
  public static final String SCORE = "Score";
  /** a name for the weight of string length */
  public static final String NAME_LENGTH = "Length";
  public static final String RELATION_SEPARATOR = "::";
  
  /** unknown correctness */
  public static final int UNKNOWN_CORRECT = -1;
  /** incorrect */
  public static final int INCORRECT = 0; 
  /** first correct */
  public static final int FIRST_CORRECT = 1;
  /** duplicated correct (synonym) */
  public static final int DUP_CORRECT = 2; 
  /** total # of types of correctness (ignoring the unknown) */
  public static final int NUM_CORRECT_TYPES = 3;  
  
  // a storage for weights
  private Map<String, Double> weightMap = null;
  // the canonical name of this entity
  private String[] names;
  // correctness of the entity (assigned by evaluator)
  private int correct = UNKNOWN_CORRECT;
  // total length of names
  private int length = 0;
  // is this a seed entity?
  private boolean isSeed = false;
  
  public static String[] splitRelation(String name) {
    return name.split(Pattern.quote(RELATION_SEPARATOR));
  }
  
  public Entity(Entity entity) {
    if (entity == null) return;
    setNames(entity.getNames());
    setSeed(entity.isSeed());
    setCorrect(entity.getCorrect());
  }
  
  public static Entity parseEntity(String name) {
      String[] names = splitRelation(name);
      switch (names.length) {
      case 1: return new Entity(names[0]);
      case 2: return new Entity(names[0],names[1]);
      }
      log.error("Bad entity string '"+name+"': Entities for parsing should have zero or one instance of the relation delimiter '"+RELATION_SEPARATOR+"'.");
      
      return null;
  }
  
  public Entity(String name) {
      if (name.contains(RELATION_SEPARATOR) && !GlobalVar.getGlobalVar().getExplicitRelations()) {
          log.warn(name+": Creating a relation using the Entity(String) constructor has been disabled. Use Entity.parseEntity(String) instead.");
      }
    setNames(new String[] {name});
  }
  
  public Entity(String name1, String name2) {
    setNames(new String[] {name1, name2});
  }
  
  public Entity(EntityLiteral content) {
      if (content.arg2 == null) setNames(new String[]{content.arg1});
      else setNames(new String[]{content.arg1,content.arg2});
}

public void addWeight(Object feature, double weight) {
    setWeight(feature, getWeight(feature) + weight);
  }
  
  public void clear() {
    if (weightMap != null)
      weightMap.clear();
  }
  
  /**
   * Compare in the order of:
   * 1) descending score
   * 2) ascending length
   * 3) ascending string
   */
  public int compareTo(Entity entity) {
    int result1 = Double.compare(entity.getScore(), getScore());
    if (result1 == 0) {
      int result2 = Double.compare(length(), entity.length());
      return (result2 == 0) ? getName().toString().compareTo(entity.getName().toString()) : result2;
    } else return result1;
  }
  
  public boolean containsFeature(Object feature) {
    return weightMap != null && weightMap.containsKey(feature.toString());
  }
  
  @Override
  public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass())
      return false;
    final Entity other = (Entity) obj;
    if (!Arrays.equals(names, other.names))
      return false;
    return true;
  }
  
  public int getCorrect() {
    return correct;
  }

  public String getCorrectMarker() {
    switch (correct) {
      case 0: return "-";
      case 1: return "+";
      case 2: return "*";
      default: return "";
    }
  }
  
  public EntityLiteral getName() {
    if (names == null) return null;
    return new EntityLiteral(names);
  }
  
  public String[] getNames() {
    return names;
  }
  
  public String getOriginal() {
    if (names == null) return null;
    String s1 = Originator.getOriginal(names[0]);
    if (names.length == 1) return s1;
    String s2 = Originator.getOriginal(names[1]);
    return s1 + RELATION_SEPARATOR + s2;
  }
  
  public String[] getOriginals() {
    if (names == null) return null;
    String[] array = new String[names.length];
    for (int i = 0; i < names.length; i++)
      array[i] = Originator.getOriginal(names[i]);
    return array;
  }
  
  public double getScore() {
    return getWeight(SCORE);
  }
  
  public double getWeight(Object feature) {
    if (feature == null) return 0;
    if (feature.equals(NAME_LENGTH)) return length();
    if (weightMap == null) return 0;
    Double weight = weightMap.get(feature.toString());
    return weight == null ? 0 : weight;
  }
  
  @Override
  public int hashCode() {
    return 31 + Arrays.hashCode(names);
  }

  /*public boolean isBad() {
    return names == null;
  }*/
  
  public boolean isCorrect() {
    return correct > 0;
  }
  
  public boolean isIncorrect() {
    return correct == INCORRECT;
  }
  
  public boolean isRelational() {
    return names != null && names.length > 1;
  }
  
  public boolean isSeed() {
    return isSeed;
  }

  public int length() {
    return length;
  }

  /**
   * Add all weights of the input entity
   * @param entity
   */
  public void merge(Entity entity) {
    if (entity.weightMap == null) return;
    for (Map.Entry<String, Double> entry : entity.weightMap.entrySet()) {
      String key = entry.getKey();
      addWeight(key, entry.getValue());
    }
  }

  public boolean remove(Object feature) {
    if (weightMap == null) return false;
    return (weightMap.remove(feature.toString()) != null);
  }

  public void setCorrect(int correct) {
    this.correct = correct;
  }
  
  public void setScore(double score) {
    setWeight(SCORE, score);
  }

  public void setSeed(boolean isSeed) {
    this.isSeed = isSeed;
  }

  public void setWeight(Object feature, double weight) {
    if (weightMap == null)
      weightMap = new HashMap<String, Double>();
    weightMap.put(StringFactory.get(feature.toString()), weight);
  }

  @Override
  public String toString() {
    return toString(null);
  }
  
  public String toString(Object feature) {
//    final int NUM_ORIGINALS = 3;
    final int NUM_DECIMAL = 6;
    
    Set<Object> features = new TreeSet<Object>();
    if (weightMap != null) {
      if (feature == null) {
        features.addAll(weightMap.keySet());
        features.remove(Entity.SCORE);
      } else features.add(feature);
    }
    StringBuffer buf = new StringBuffer();
    for (Object f : features) {
      String weightStr = Helper.formatNumber(getWeight(f), NUM_DECIMAL);
      buf.append(f).append(":").append(weightStr).append("\t");
    }
    String scoreStr = Helper.formatNumber(getScore(), NUM_DECIMAL);
    buf.append(scoreStr).append(" ").append(getCorrectMarker());
    String originals = getOriginal();
//    String originals = isRelational() ? getOriginal() : Originator.getOriginals(getName(), NUM_ORIGINALS);
    buf.append(originals);

    return buf.toString();
  }

  // TODO: change from String to SID?
  private void setNames(String[] inputs) {
    if (inputs == null) return;
    length = 0;
    String[] names = new String[inputs.length];
    for (int i = 0; i < inputs.length; i++) {
//      String name = WrapperFactory.tidy(inputs[i]);
      String name = inputs[i];
      if (Helper.empty(name)) return;
      names[i] = StringFactory.get(name);
      length += name.length();
    }
    this.names = names;
  }
} public class EntityList implements Iterable<Entity>, Comparable<EntityList>, Serializable {
  
  public static Logger log = Logger.getLogger(EntityList.class);
  public static GlobalVar gv = GlobalVar.getGlobalVar();
  
  public static final int MAX_SIZE = Cache.DEFAULT_MAX_SIZE;
  public static final double DELTA = 1e-8;
  public static final double OUTLIER_LENGTH_THRESHOLD = 1e-4;
  public static final double DEFAULT_LENGTH_RATIO = 0.1;  // 0.3
  
  public static final double THRESH = 0.1;  // precision at threshold
  public static final int RANK = 100; // precision at rank
  
  private static final long serialVersionUID = 7211782411429869181L;
  
  protected Map<EntityLiteral, Entity> entityMap;
  protected List<Entity> entityList;
  private EvalResult evalResult;
  private double listWeight;
  private int maxEntities;
  
  public EntityList() {
    entityMap = new HashMap<EntityLiteral, Entity>();
    entityList = new ArrayList<Entity>();
    setMaxEntities(WrapperFactory.MAX_CONTENTS_ALLOWED);
  }
  
  public EntityList(Collection<String> entityNames) {
    this();
    addAll(entityNames);
  }
  
  public EntityList(EntityList entityList) {
    this();
    addAll(entityList);
  }
  
  public EntityList(List<Entity> entityList) {
    this();
    addAll(entityList);
  }
  
  public EntityList(Set<Entity> entityList) {
    this();
    addAll(entityList);
  }
  
  /**
   * Remove all entities with a feature that is less than minValue
   * @param feature
   * @param minValue
   */
  public int absoluteFilter(Object feature, double minValue) {
    if (feature == null) return 0;
    boolean[] toRemove = new boolean[size()];
    for (int i = 0; i < size(); i++)
      if (get(i).getWeight(feature) < minValue)
        toRemove[i] = true;

    int numRemoved = remove(toRemove);
    if (numRemoved > 0)
      log.debug(numRemoved + " entities having " + feature + " < " + Helper.formatNumber(minValue, 5) + 
                " were filtered and " + size() + " remaining!");
    return numRemoved;
  }
  
  public Entity add(Entity entity) {
    if (entity == null) return null;
//    if (entity.isBad()) return;
    Entity e = get(entity);
    if (e == entity) return entity;
    
    // overwrites any existing entity
    if (e == null) {
      entityList.add(entity);
    } else {
      int index = entityList.indexOf(entity);
      if (index < 0) {
          log.error(entity.toString()+" not in entityList, but get("+entity.toString()+") returned "+e.toString()+", not entity or null");
      }
      entityList.set(index, entity);
    }
    entityMap.put(entity.getName(), entity);
    evalResult = null;
    return entity;
  }
  
  /**
   * Reduce the size of this list by the following procedure:
   * 1) sort this list by input 'feature' in descending order
   * 2) remove entities ranked lower than or equal to r
   * 3) reduce weight of entities above r by the weight of entity at r
   * where r is the half of MAX_SIZE
   * @param feature
   */
  public void reduceSize(Object feature) {
    if (size() <= MAX_SIZE) return;
    final int SIZE = (int) (MAX_SIZE * 0.5);
    log.info("Number of entities exceeds " + MAX_SIZE + ", reducing it to " + SIZE + "...");
    sortBy(feature, false);
    double midWeight = get(SIZE).getWeight(feature);
    
    for (int i = size()-1; i >= 0; i--) {
      if (i >= SIZE) remove(i);
      else get(i).addWeight(feature, -midWeight);
    }
  }
  
  public Entity add(String name) {
    if (Helper.empty(name)) return null;
//    Entity e1 = new Entity(name);
//    if (e1.isBad()) return null;
//    Entity e2 = get(e1);
//    if (e2 != null) return e2;
//    add(e1);
    Entity e = get(new EntityLiteral(name));
    if (e != null) return e;
    return add(new Entity(name));
  }
  
  public void addAll(Collection<String> names) {
    if (names == null) return;
    for (String name : names)
      add(name);
  }
  
  public void addAll(EntityList entities) {
    if (entities == null) return;
    for (Entity entity : entities)
      add(entity);
    addWeight(entities.getListWeight());
  }
  
  public void addAll(List<Entity> entities) {
    if (entities == null) return;
    for (Entity entity : entities)
      add(entity);
  }
  
  public void addAll(Set<Entity> entities) {
    if (entities == null) return;
    for (Entity entity : entities)
      add(entity);
  }
  
  /**
   * Add a weight to this entity list
   * @param weight
   */
  public void addWeight(double weight) {
    setListWeight(getListWeight() + weight);
  }
  
  /**
   * Add a weight to every entity in this list
   * @param feature
   * @param weight
   */
  public void addWeight(Object feature, double weight) {
    for (Entity entity : entityList)
      entity.addWeight(feature, weight);
  }
  
  public void assignScore(Object feature, boolean hasNoisySeeds) {
    if (feature == null) return;
    
    double maxScore = Double.NEGATIVE_INFINITY;
    double minScore = Double.POSITIVE_INFINITY;
    double weight;
    
    for (Entity entity : entityList) {
      weight = entity.getWeight(feature);
      maxScore = Math.max(weight, maxScore);
      minScore = Math.min(weight, minScore);
    }
    
    // prevents maxScore equals to minScore
    minScore -= DELTA;
    for (Entity entity : entityList) {
      weight = entity.getWeight(feature);
      if (!hasNoisySeeds && entity.isSeed()) // 2008-11-27
        weight = maxScore + weight * DELTA;
      weight = (weight - minScore) / (maxScore + Math.abs(maxScore) * DELTA - minScore);
      entity.setScore(weight);
    }
//    sortBy(Entity.SCORE, false);
  }
  
  public int averageFilter(Object feature) {
    double avg = this.getAverage(feature);
    return absoluteFilter(feature, avg);
  }
  
  public void clear() {
    entityMap.clear();
    entityList.clear();
    evalResult = null;
  }
  
  public int compareTo(EntityList entityList) {
    return Double.compare(entityList.getListWeight(), getListWeight());
  }
  
  public boolean contains(Entity entity) {
    return entityMap.containsKey(entity.getName());
  }
  
//  public boolean contains(String s) {
//    return entityMap.containsKey(s);
//  }
  
  public boolean contains(EntityLiteral e) {
      return entityMap.containsKey(e);
  }
  
  public boolean containsFeature(Object feature) {
    for (Entity entity : this)
      if (!entity.containsFeature(feature))
        return false;
    return true;
  }
  
  public int count(Object feature, double minValue) {
    int count = 0;
    for (Entity entity : this)
      if (entity.getWeight(feature) >= minValue)
        count++;
    return count;
  }
  
  /**
   * For every entity x that is contained by both lists, create a new entity x 
   * having such weight: r*w1 + (1-r)*w2, where w1 and w2 are the weights of an 
   * entity in *this* list and in the input list respectively.
   * @param entityList Input list
   * @param feature
   * @param ratio The proportion of weights taken from weight1 and weight2 for the new entity x.
   * @return A new list of intersected entities
   */
  public EntityList intersect(EntityList entityList, Object feature, double ratio) {
    if (ratio < 0 || ratio > 1)
      throw new IllegalArgumentException("Ratio must be between 0 and 1 (inclusively)");
    EntityList list = new EntityList();
    for (Entity e1 : this) {
      Entity e2 = entityList.get(e1);
      if (e2 == null) continue;
      
      // compute weight and score
      double weight = ratio * e1.getWeight(feature) + (1-ratio) * e2.getWeight(feature);
      if (weight <= 0) continue;
      double score = ratio * e1.getScore() + (1-ratio) * e2.getScore();
      if (score <= 0) continue;
      
      // assign weight and score
      Entity entity = new Entity(e1);
      entity.setWeight(feature, weight);
      entity.setScore(score);
      list.add(entity);
    }
    return list;
  }
  
  @Override
  public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null) return false;
    if (getClass() != obj.getClass())
      return false;
    final EntityList other = (EntityList) obj;
    if (entityMap == null) {
      if (other.entityMap != null)
        return false;
    } else if (!entityMap.keySet().equals(other.entityMap.keySet()))
      return false;
    return true;
  }
  
  /**
   * Computes the Euclidean Distance between entities of this class and the input entities
   * @param entities
   * @param feature
   * @return Euclidean distance
   */
  public double euclideanDistance(EntityList entities, Object feature) {
    Set<Entity> set = new HashSet<Entity>();
    set.addAll(this.getEntities());
    set.addAll(entities.getEntities());
    double sum = 0;
    for (Entity entity : set) {
      Entity e1 = this.get(entity);
      double w1 = (e1 == null) ? 0 : e1.getWeight(feature);
      Entity e2 = entities.get(entity);
      double w2 = (e2 == null) ? 0 : e2.getWeight(feature);
      sum += Math.pow(w1 - w2, 2);
    }
    return Math.sqrt(sum);
  }
  
  /**
   * Use for breaking ties between entities having the same score
   * @param feature
   */
  public void scoreByLength() {
    // calculate average length
    if (isEmpty()) return;
    double avg = getSumLength() / size();

    // calculate standard deviation
    double std = 0;
    for (Entity entity : this)
      std += Math.pow(entity.length() - avg, 2);
    std = Math.sqrt(std / size());
    if (std == 0) return;

    log.info("Diminishing entities with abnormal length (avg: " + Helper.formatNumber(avg, 2) + 
             ", std: " + Helper.formatNumber(std, 2) + ")...");
    
    // assign probability
    for (int i = 0; i < size(); i++) {
      Entity entity = get(i);
      double p = Helper.getPDF(entity.length(), avg, std);
      
      if (p < OUTLIER_LENGTH_THRESHOLD) {
        log.debug("Diminishing \"" + entity.getName() + "\": " + p);
        entity.setScore(0);
      } else {
        // add a very tiny weight to break any tie
        entity.addWeight(Entity.SCORE, p * DELTA);
      }
    }
  }
  
  public void sortByScore() {
    sortBy(Entity.SCORE, false);
  }
  
  /**
   * Filter out relational entities based on the type of relation
   * @param type 0: Many to Many, 1: One to Many, 2: Many to One, 3: One to One
   */
  public void filterRelation(int type) {
    if (!isRelational() || type == 0) return;
    boolean[] toRemove = new boolean[size()];
    Set<String> set = new HashSet<String>();
    
    for (int i = 0; i < size(); i++) {
      String[] names = get(i).getNames();
      
      if (type == 1 || type == 2) {
        String s = (type == 1) ? names[0] : names[1];
        toRemove[i] = !set.add(s);
      } else if (type == 3) {
        toRemove[i] = !set.add(names[0]) || !set.add(names[1]);
      }
    }
    int numRemoved = remove(toRemove);
    if (numRemoved > 0) {
      String s = null;
      switch (type) {
        case 1: s = "One to Many"; break;
        case 2: s = "Many to One"; break;
        case 3: s = "One to One"; break;
      }
      log.info(numRemoved + " entities were removed: relational type of " + type + " (" + s + ")");
    }
  }
  
  public Entity get(Entity entity) {
    return entityMap.get(entity.getName());
  }
  
  public Entity get(int i) {
    return entityList.get(i);
  }
  
  public Entity get(EntityLiteral name) {
      return entityMap.get(name);
  }
  
//  public Entity get(String name) {
//    return entityMap.get(name);
//  }
  
  public double getAverage(Object feature) {
    double sum = this.getSumWeights(feature);
    return sum / this.size();
  }
  
  public List<Entity> getEntities() {
    return entityList;
  }
  
  /**
   * Gather entities containing the input feature
   * @param feature
   * @return
   */
  public EntityList getEntities(Object feature) {
    return getEntities(feature, Double.MIN_VALUE);
  }
  
  /**
   * Gather entities with the input feature having at least some input weight
   * @param feature
   * @param weight
   * @return an EntityList of entities with a feature of at least some weight
   */
  public EntityList getEntities(Object feature, double weight) {
    EntityList list = new EntityList();
    for (Entity entity : this)
      if (entity.containsFeature(feature) && 
          entity.getWeight(feature) >= weight)
        list.add(entity);
    return list;
  }
  
  public List<EntityLiteral> getEntityLiterals() {
      List<EntityLiteral> list = new ArrayList<EntityLiteral>();
      for (Entity entity : entityList)
        list.add(entity.getName());
      return list;
    }
  public List<String[]> getEntityNames() {
    List<String[]> list = new ArrayList<String[]>();
    for (Entity entity : entityList)
      list.add(entity.getNames());
    return list;
  }
  
  public EvalResult getEvalResult() {
    return evalResult;
  }

  public double getListWeight() {
    return listWeight;
  }
  
  public int getMaxEntities() {
    return maxEntities;
  }
  
  public Double getMaxWeight(Object feature) {
    Double maxWeight = null;
    for (Entity entity : entityList) {
      double weight = entity.getWeight(feature);
      if (maxWeight == null) maxWeight = weight;
      else maxWeight = Math.max(weight, maxWeight);
    }
    return maxWeight;
  }
  
  public Integer getMinStringLength() {
    Integer min = null;
    for (Entity entity : this) {
      String[] names = entity.getNames();
      for (String name : names) {
        if (min == null) min = name.length();
        else min = Math.min(name.length(), min);
      }
    }
    return min;
  }
  
  /**
   * Returns the counts of incorrect (0), correct (1), and synonym (2) entities
   * @param threshold count only the entities having
   * 1) a rank higher than threshold (if threshold is at least one), or
   * 2) scores above threshold (if threshold is less than one)
   * @return an array of counts, indexed by the 'correctness' integer (see above)
   */
  public int[] getCorrectness(double threshold) {
    boolean isRank = (threshold >= 1);
    int[] counters = new int[Entity.NUM_CORRECT_TYPES];
    if (threshold <= 0) return counters;
    for (Entity entity : this) {
      if (isRank) {
        if (counters[Entity.INCORRECT] + counters[Entity.FIRST_CORRECT] == threshold) break;
      } else if (entity.getScore() < threshold) break;
      int correctness = entity.getCorrect();
      if (correctness == Entity.UNKNOWN_CORRECT) {
        log.warn("Found an entity with unknown correctness!");
        continue;
      }
      else counters[correctness]++;
    }
    return counters;
  }
  
  public double getPrecision(double threshold, int[] counters) {
    if (counters == null)
      counters = getCorrectness(threshold);
    int total = counters[Entity.INCORRECT] + counters[Entity.FIRST_CORRECT];
    return (total == 0) ? 0 : (double) counters[Entity.FIRST_CORRECT] / total;
  }
  
  public double getRecall(double threshold, int[] counters) {
    int numTrue = evalResult.numGoldEntity;
    if (numTrue <= 0) return 0;
    if (counters == null)
      counters = getCorrectness(threshold);
    return (double) counters[Entity.FIRST_CORRECT] / numTrue;
  }
  
  public double getF1(double threshold, int[] counters) {
    if (counters == null)
      counters = getCorrectness(threshold);
    double p = getPrecision(threshold, counters);
    double r = getRecall(threshold, counters);
    return (p+r == 0) ? 0 : (2*p*r) / (p+r);
  }
  
  public double getSumLength() {
    double sum = 0;
    for (Entity entity : this)
      sum += entity.length();
    return sum;
  }
  
  public double getSumOfLogWeights(Object feature) {
    double sum = 0;
    boolean isLogRanker = Ranker.isLogRanker(feature);
    for (Entity entity : entityList) {
      double weight = entity.getWeight(feature);
      sum += isLogRanker ? weight : Math.log(weight);
    }
    return sum;
  }
  
  public double getSumWeights(Object feature) {
    double sum = 0;
    for (Entity entity : entityList)
      sum += entity.getWeight(feature);
    return sum;
  }
  
  /**
   * Returns top entities
   * 1) having at least minEntities and at most maxEntities
   * 2) where each feature weight is at least the input threshold
   * @param feature
   * @param threshold
//   * @param minEntities
   * @param maxEntities
   * @return a sorted EntityList object
   */
//  public EntityList getTopEntities(Object feature, double threshold, int minEntities, int maxEntities) {
  public EntityList getTopEntities(Object feature, double threshold, int maxEntities) {
    EntityList list = this.getEntities(feature, threshold);
    /*if (list.size() < minEntities) {
      list = new EntityList(this);
      list.sortBy(feature, false);
      return list.subList(0, minEntities);
    } else {*/
      list.sortBy(feature, false);
      if (list.size() > maxEntities)
        return list.subList(0, maxEntities);
      else return list;
//    }
  }
  
  @Override
  public int hashCode() {
    return 31 + (entityMap == null ? 0 : entityMap.hashCode());
  }

  public boolean hasSpace() {
    for (Entity entity : this)
      if (entity.getName().toString().contains(" "))
        return true;
    return false;
  }
  
  /**
   * Preserves the order of the EntityList in this object
   * Retains weights of the entities in this object
   * @param entityList
   * @return overlapping entities of the input list and this class
   */
  public EntityList intersect(EntityList entityList) {
    EntityList list = new EntityList();
    for (Entity entity : this)
      if (entityList.contains(entity))
        list.add(entity);
    return list;
  }
  
  public boolean isEmpty() {
    return size() == 0;
  }
  
  public boolean isIntersected(EntityList entityList) {
    EntityList smaller = entityList, larger = this;
    if (this.size() < entityList.size()) {
      smaller = this;
      larger = entityList;
    }
    for (Entity entity : smaller)
      if (larger.contains(entity))
        return true;
    return false;
  }
  
  public boolean isRelational() {
    for (Entity entity : this)
      if (!entity.isRelational())
        return false;
    return true;
  }
  
  public Iterator<Entity> iterator() {
    return entityList.iterator();
  }
  
  public void merge(Entity entity) {
    Entity e = get(entity);
    if (e == null) add(entity);
    else e.merge(entity);
  }
  
  public void merge(EntityList entityList) {
    for (Entity entity : entityList)
      merge(entity);
  }
  
  public void normalize(Object feature) {
    double sum = getSumWeights(feature);
    if (sum == 0) return;
    for (Entity entity : this) {
      double weight = entity.getWeight(feature);
      if (weight < 0) {
        log.warn("Warn: " + entity.getName() + " contains negative weight of " + weight + " for feature: " + feature);
        continue;
      }
      entity.setWeight(feature, weight/sum);
    }
  }
  
  public void clearWeight(Object feature) {
    if (feature == null) return;
    for (Entity entity : this)
      entity.remove(feature);
  }

  public EntityList product(EntityList entityList, Object feature) {
    EntityList list = new EntityList();
    for (Entity e1 : this) {
      Entity e2 = entityList.get(e1);
      if (e2 == null) continue;
      double weight = e1.getWeight(feature) * e2.getWeight(feature);
      if (weight <= 0) continue;
      Entity entity = new Entity(e1);
      entity.setWeight(feature, weight);
      list.add(entity);
    }
    return list;
  }
  
  public int relativeFilter(Object feature, double ratio) {
    if (feature == null || ratio <= 0) return 0;
    Double maxWeight = getMaxWeight(feature);
    if (maxWeight == null) return 0;
    return absoluteFilter(feature, maxWeight * ratio);
  }
  
  /**
   * remove those marked entities
   * @param toRemove
   */
  public int remove(boolean[] toRemove) {
    if (toRemove == null) return 0;
    int size = Math.min(entityList.size(), toRemove.length);
    int offset = 0;
    
    for (int i = 0; i < size; i++) {
      if (!toRemove[i]) continue;
//      log.debug("Removing: " + entityList.get(i-offset).getName());
      remove(i-offset);
      offset++;
    }
    return offset;
  }
  
  public void remove(Entity entity) {
    if (entity == null) return;
    entityList.remove(entity);
    entityMap.remove(entity.getName());
  }
  
  public Entity remove(int i) {
    Entity entity = entityList.remove(i);
    entityMap.remove(entity.getName());
    return entity;
  }
  
  public void remove(Object feature) {
    for (Entity entity : this)
      entity.remove(feature);
  }
  
  public void remove(String entity) {
    if (entity == null) return;
    entityList.remove(entity);
    entityMap.remove(entity);
  }
  
  public void removeAll(EntityList list) {
    if (list == null) return;
    for (Entity entity : list)
      this.remove(entity);
  }
  
  public int removeAll(Object feature) {
    int sum = 0;
    for (Entity entity : entityList)
      sum += entity.remove(feature) ? 1 : 0;
    return sum;
  }
  
  public void removeContains(String superStr) {
    if (superStr == null) return;
    boolean[] toRemove = new boolean[this.size()];
    for (int i = 0; i < this.size(); i++) {
      String s = this.get(i).getName().toString();
      toRemove[i] = superStr.contains(s);
    }
    remove(toRemove);
  }

  public void setEvalResult(EvalResult evalResult) {
    this.evalResult = evalResult;
  }

  /**
   * Set the weight of this entity list
   * @param weight
   */
  public void setListWeight(double weight) {
    this.listWeight = weight;
  }
  
  public void setMaxEntities(int maxEntitiesInXML) {
    this.maxEntities = maxEntitiesInXML;
  }
  
  /**
   * Set weight to all entities in this list
   * @param feature
   * @param weight
   */
  public void setWeight(Object feature, double weight) {
    for (Entity entity : this)
      entity.setWeight(feature, weight);
  }
  
  public void shrink(Object feature, double shrinkPower) {
    shrink(feature, shrinkPower, DEFAULT_LENGTH_RATIO);
  }
  
  /**
   * Collapse a sorted list of entities, from top to bottom
   * Reduce the number of entities to maxEntities
   * @param byNameLength true to pre-sort by string length, otherwise by score, then collapse!
   * @param entityList
   * @return
   */
  public void shrink(Object feature, double shrinkPower, double lengthRatio) {
    log.info("Shrinking list with a shrinking power of " + shrinkPower + 
             " and length ratio of " + lengthRatio + "...");
    if (size() <= 1) return;
//    boolean[] toRemove = new boolean[size()];
    String hasSpace = hasSpace() ? " " : "";
    sortByNameLength(false);
    
    for (int i = 0; i < size(); i++) {
      Entity e1 = get(i);
      String name1 = e1.getName().toString();
      double w1 = e1.getWeight(feature);
      
      for (int j = i+1; j < size(); j++) {
//        if (toRemove[j]) continue;
        Entity e2 = get(j);
        double w2 = e2.getWeight(feature);
        if (w2 == 0) continue;
        String name2 = e2.getName().toString();

        if (name1.length() <= name2.length()) continue;
        if (w1 * shrinkPower <= w2) continue;
        double z = (double) name2.length() / name1.length();
        if (z < lengthRatio) continue;
        
        if (name1.startsWith(name2 + hasSpace) || 
            name1.endsWith(hasSpace + name2)) {
          log.debug(name1 + " (" + feature + ": " + Helper.formatNumber(w1, 5) + ") ===> " + 
                    name2 + " (" + feature + ": " + Helper.formatNumber(w2, 5) + ")");
          if (w2 > w1) {
            // assign first entity the weight of second entity
            e1.setWeight(feature, w2);
            e2.setWeight(feature, 0);
          }
//          toRemove[j] = true;
        }
      }
    }
    /*int numRemoved = remove(toRemove);
    if (numRemoved > 0)
      log.info(numRemoved + " entities were shrunk and " + size() + " remaining!");*/
    sortBy(feature, false);
  }
  
  public void shuffle(Random random) {
    if (random == null) return;
    Collections.shuffle(entityList, random);
  }
  
  public int size() {
    return entityList.size();
  }

  public void sort() {
    sortBy(Entity.SCORE, false);
  }

  public void sortBy(final Object feature, final boolean ascending) {
    Comparator<Entity> c = new Comparator<Entity>() {
      public int compare(Entity e1, Entity e2) {
        double w1 = e1.getWeight(feature), w2 = e2.getWeight(feature);
        if (ascending) return Double.compare(w1, w2);
        else return Double.compare(w2, w1);
      }
    };
    sortBy(c, feature, ascending);
  }
  
  public void sortByNameLength(final boolean ascending) {
    sortBy(Entity.NAME_LENGTH, ascending);
  }
  
  public EntityList subList(int fromIndex, int toIndex) {
    EntityList subList = new EntityList();
    toIndex = Math.min(toIndex, entityList.size());
    for (int i = fromIndex; i < toIndex; i++)
      subList.add(entityList.get(i));
    return subList;
  }
  
  public String toDetails(int numTop) {
    return toDetails(numTop, null);
  }
  
  public String getOneLineStat() {
    StringBuffer buf = new StringBuffer("[ ");
    String map = Helper.formatNumber(evalResult.meanAvgPrecision*100, 2);
    buf.append("MAP: ").append(map).append(", ");
    
    String pRank = Helper.formatNumber(getPrecision(RANK, null)*100, 2);
    buf.append("P@" + RANK + ": ").append(pRank).append(", ");
    
    int[] counters = getCorrectness(THRESH);
    int num = counters[Entity.FIRST_CORRECT] + counters[Entity.INCORRECT];
    double p = getPrecision(THRESH, counters), r = getRecall(THRESH, counters);
    String pStr = Helper.formatNumber(p*100, 2), rStr = Helper.formatNumber(r*100, 2);
    String f1Str = Helper.formatNumber(getF1(THRESH, counters)*100, 2);
    buf.append("F1@" + THRESH + ": ").append(f1Str).append(" ");
    buf.append("(P:").append(pStr).append(", ");
    buf.append("R:").append(rStr).append(", ");
    buf.append("#:").append(num).append(")");
    return buf.append(" ]").toString();
  }
  
  public String toDetails(int numTop, Object feature) {
    final int LINE_WIDTH = 80;
    numTop = Math.min(numTop, entityList.size());
    
//    StringBuffer buf = new StringBuffer("\n");
    StringBuffer buf = new StringBuffer();
    String title = "[ Listing " + numTop + " out of " + entityList.size() + " Entities ]";
    buf.append("\t").append(Helper.center(title, '-', 80)).append("\n");
    for (int i = 0; i < numTop; i++) {
      Entity entity = entityList.get(i);
      buf.append(i+1).append(".\t");
      buf.append(entity.toString(feature)).append("\n");
    }
    buf.append("\t");
    if (evalResult != null) {
      buf.append(Helper.center(getOneLineStat(), '-', LINE_WIDTH));
    } else {
      buf.append(Helper.repeat('-', LINE_WIDTH));
    }
    return buf.toString();
  }

  /**
   * Returns a list of entities sorted in score order
   */
  public String toString() {
    Set<Entity> entities = new TreeSet<Entity>();
    entities.addAll(getEntities());
    
    StringBuffer buf = new StringBuffer();
    for (Entity entity : entities) {
      if (buf.length() > 0) buf.append(", ");
      buf.append(entity.getCorrectMarker()).append(entity.getName());
    }
    return buf.toString();
  }
  
  public String toXML() {
    return XMLUtil.document2String(toXMLElement(null));
  }
  
  public Element toXMLElement(Document document) {
    XMLUtil xml = new XMLUtil(document);
    Element entitiesNode = xml.createElement("entities", null);
    xml.createAttrsFor(entitiesNode, new Object[]{
        "numEntities", entityList.size(),
    });
    int rank = 1;
    for (Entity entity : entityList) {
      // reduce the amount of garbage saved to the disk
      if (rank > maxEntities) break;
      
      List<Object> pairs = Ranker.toFeatureValuePairs(entity);
      pairs.add("rank"); pairs.add(rank++);
      pairs.add("score"); pairs.add(entity.getScore());
      if (entity.getCorrect() != -1) {
        pairs.add("correct"); pairs.add(entity.getCorrect());
      }
      Element entityNode = xml.createElementBelow(entitiesNode, "entity", entity.getOriginal());
      xml.createAttrsFor(entityNode, pairs.toArray(new Object[pairs.size()]));
    }
    return entitiesNode;
  }

  public void transferWeight(Object from, Object to) {
    for (Entity entity : this)
      entity.setWeight(to, entity.getWeight(from));
  }

  private void sortBy(Comparator<Entity> c, Object feature, boolean ascending) {
    log.debug("Sorting entities by " + feature + " in " + (ascending ? "a" : "de") + "scending order...");
    Collections.sort(entityList, c);
  }

    public Entity add(EntityLiteral content) {
        Entity e = new Entity(content);
        return add(e);
    }
} public class LangProvider {

  public static class Lang {
    String id, name;
    Pattern pattern;
    
    public Lang() {}
    
    public Lang(String[] array) {
      setId(array[ID]);
      setName(array[NAME]);
      String pattern = array[ALPHABET];
      String type = array[TYPE];
      if (type.equals(NON_SPACE_TYPE))
        pattern = toNonSpacePattern(pattern);
      else if (type.equals(HAS_SPACE_TYPE))
        pattern = toHasSpacePattern(pattern);
      setPattern(pattern);
    }
    
    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      final Lang other = (Lang) obj;
      if (id == null) {
        if (other.id != null) return false;
      } else if (!id.equals(other.id)) return false;
      return true;
    }
    
    public String getId() {
      return id;
    }
    
    public String getName() {
      return name;
    }
    
    public Pattern getPattern() {
      return pattern;
    }
    
    @Override
    public int hashCode() {
      return 31 + ((id == null) ? 0 : id.hashCode());
    }
    
    public void setId(String id) {
      this.id = id;
    }
    
    public void setName(String name) {
      this.name = name;
    }
    
    public void setPattern(Pattern pattern) {
      this.pattern = pattern;
    }
    
    public void setPattern(String pattern) {
      this.pattern = Pattern.compile(pattern);
    }
  }
  
  public static final int ID = 0;
  public static final int NAME = 1;
  public static final int ALPHABET = 2;
  public static final int TYPE = 3;
  
  public static final String NON_SPACE_TYPE = "0";
  public static final String HAS_SPACE_TYPE = "1";
  public static final String NEITHER_TYPE = "2";
  
  // languages with spaces
  public static final String[] ENG = new String[] {
    "en", "English", "[A-Za-z]", HAS_SPACE_TYPE
  };
  public static final String[] POR = new String[] {
    "pt", "Portuguese", "[A-Za-zÁÂÃÀÇÉÊÍÓÔÕÚáâãàçéêíóôõú]", HAS_SPACE_TYPE
  };
  public static final String[] FRE = new String[] {
    "fr", "French", ENG[ALPHABET], HAS_SPACE_TYPE
  };
  public static final String[] ITA = new String[] {
    "it", "Italian", "[A-IL-VZa-il-vz]", HAS_SPACE_TYPE
  };
  public static final String[] SPA = new String[] {
    "es", "Spanish", "[A-Za-zÑñ]", HAS_SPACE_TYPE
  };
  public static final String[] GER = new String[] {
    "de", "German", "[A-Za-zÄÖÜäöüß]", HAS_SPACE_TYPE
  };
  
  // languages without spaces
  public static final String[] CHT = new String[] {
    "zh-TW", "Traditional Chinese", "[\\p{InCJKUnifiedIdeographs}\\p{InBopomofo}\u02C7\u02CA\u02CB\u30FB]", NON_SPACE_TYPE
  };
  public static final String[] CHS = new String[] {
    "zh-CN", "Simplified Chinese", "[\\p{InCJKUnifiedIdeographs}]", NON_SPACE_TYPE
  };
  public static final String[] JAP = new String[] {
    "ja", "Japanese", "[\\p{InCJKUnifiedIdeographs}\\p{InKatakana}\\p{InHiragana}]", NON_SPACE_TYPE
  };
  public static final String[] KOR = new String[] {
    "ko", "Korean", "[\\p{InHangulSyllables}]", NON_SPACE_TYPE
  };
  
  // universal language
  public static final String[] UNI = new String[] {
    "un", "Universal", "[^\\x22-\\x25\\x28-\\x2C\\x3B-\\x40\\x5B-\\x5E\\x7B-\\x7E\\x2F\\x60]{2,}", NEITHER_TYPE
  };
  
  private static Set<Lang> langList = init();
  
  public static boolean supports(String id) {
    return getLang(id) != null;
  }
  
  /**
   * Auto-detect the language of the input collection of strings
   * @param ss input collection of strings
   * @return a Lang object, or null if they are not all in the same language
   */
  public static Set<Lang> detect(EntityList entities) {
    StringBuffer buf = new StringBuffer();
    for (Entity entity : entities)
      for (String name : entity.getNames())
        buf.append(name);
    return detect(buf.toString());
  }
  
  /**
   * Auto-detect the language of the input string
   * in the same order as in the Lang list
   * @param s input string
   * @return a Lang object, or null if the language is unrecognizable
   */
  public static Set<Lang> detect(String s) {
    Set<Lang> langSet = new LinkedHashSet<Lang>();
    for (Lang lang : langList)
      if (lang.getPattern().matcher(s.trim()).matches())
         langSet.add(lang);
    return langSet;
  }
  
  public static Set<Lang> getAllLangs() {
    return langList;
  }

  public static Lang getLang(String id) {
    if (id == null) return null;
    for (Lang lang : langList)
      if (lang.getId().equals(id))
        return lang;
    return null;
  }
  
  /**
   * Creates a Lang object using id1's ID and id2's pattern
   * @param id1
   * @param id2
   * @return
   */
  public static Lang getLang(String id1, String id2) {
    Lang lang1 = getLang(id1);
    if (lang1 == null) return null;
    Lang lang2 = getLang(id2);
    if (lang2 == null) return null;

    Lang lang = new Lang();
    lang.setName(lang1.getName() + " + " + lang2.getName());
    lang.setId(lang1.getId()); // web page retrieval langId
    lang.setPattern(lang2.getPattern()); // text extraction langId
    return lang;
  }
  
  public static Lang getLang(String[] array) {
    return getLang(array[ID]);
  }
  
  public static String getName(String id) {
    Lang lang = getLang(id);
    if (lang == null) return null;
    return lang.getName();
  }
  
  public static void main(String args[]) {
    String s = "Richard's office is in NSH-4622";
    Set<Lang> langSet = detect(s);
    
    System.out.println(s);
    if (!langSet.isEmpty())
      for (Lang lang : langSet)
        System.out.println(lang.getName());
    
    s = "波ㄆㄛ羅ㄌㄨㄛˊ蜜ㄇㄧˋ";
    System.out.println(LangProvider.getLang("zh-TW").pattern.matcher(s).matches());
  }
  
  private static Set<Lang> init() {
    Set<Lang> list = new LinkedHashSet<Lang>();
    list.add(new Lang(ENG));
    list.add(new Lang(CHT));
    list.add(new Lang(CHS));
    list.add(new Lang(JAP));
    list.add(new Lang(KOR));
    list.add(new Lang(POR));
    list.add(new Lang(FRE));
    list.add(new Lang(ITA));
    list.add(new Lang(SPA));
    list.add(new Lang(GER));
    list.add(new Lang(UNI));  // Universal (must be last)
    return list;
  }
  
  private static String toHasSpacePattern(String alphabets) {
    String puncts = "[ \\.:'&-]";
    String digitAlpha = "[\\d" + alphabets + "]";
    return alphabets + digitAlpha + "*(?:" + puncts + "[ ]?" + digitAlpha + "+)*";
  }
  
  private static String toNonSpacePattern(String alphabets) {
    return "[\\d" + alphabets + "]+";
  }
  
}
 public class Annotator {

  public class Annotation implements Comparable<Annotation> {
    private int startOffset;
    private int endOffset;
    private String type;

    public Annotation(int startOffset, int endOffset, String type) {
      this.startOffset = startOffset;
      this.endOffset = endOffset;
      this.type = type;
      trim();
    }
    
    public int compareTo(Annotation ann) {
      return Double.compare(startOffset, ann.start());
    }
    
    public int end() {
      return endOffset;
    }

    public String getText() {
      return text.substring(startOffset, endOffset);
    }

    public String getType() {
      return type;
    }

    public boolean isSourceType() {
      return type.equals(SOURCE_TYPE);
    }
    
    public boolean isTargetType() {
      return type.equals(TARGET_TYPE);
    }
    
    public void shift(int offset) {
      startOffset += offset;
      endOffset += offset;
    }
    
    public int start() {
      return startOffset;
    }
    
    @Override
    public String toString() {
      return "\"" + text.substring(startOffset, endOffset) + "@[" + startOffset + "," + (endOffset-1) + "]\"";
    }
    
    public void trim() {
      for (; startOffset < endOffset; startOffset++)
        if (!WrapperFactory.isPunct(text.charAt(startOffset))) break;

      for (; endOffset > startOffset; endOffset--)
        if (!WrapperFactory.isPunct(text.charAt(endOffset-1))) break;
    }
  }
  
  public static Logger log = Logger.getLogger(Annotator.class);

  public static final String QUERY_SYMBOL = "+";
  public static final String SOURCE_TYPE = "source";
  public static final String TARGET_TYPE = "target";
  public static final String START_SOURCE_MARKER = "<";
  public static final String END_SOURCE_MARKER = ">";
  public static final String START_TARGET_MARKER = "{";
  public static final String END_TARGET_MARKER = "}";
  public static final int LAPLACIAN_SMOOTHING = 1;
  
  protected List<Annotation> annotations;
  protected String text;
  protected int queryType;
  
  public static void main(String args[]) {
//    String s = "Richard Wang studies at Carnegie Mellon University!";
    String s = "|a          a            a|";
    Annotator annotator = new Annotator(s);
    annotator.annotateSource("|");
    annotator.annotateTarget("a");
    log.info(annotator);
    log.info("Score: " + annotator.getDistScore());
    log.info("# Sources: " + annotator.countSource());
    log.info("# Targets: " + annotator.countTarget());
  }
  
  private static int determineQueryType(String s) {
    int queryType = 0;
    for (; ; queryType++)
      if (!s.substring(queryType, queryType+1).equals(QUERY_SYMBOL))
        break;
    return queryType;
  }
  
  private static boolean hasOverlap(Annotation ann1, Annotation ann2) {
    return ann1.end() > ann2.start() && ann2.end() > ann1.start();
  }
  
  public Annotator(String text) {
    annotations = new ArrayList<Annotation>();
    this.text = text;
    queryType = 0;
  }
  
  public void annotateSource(String s) {
    annotate(s, SOURCE_TYPE);
  }
  
  public void annotateTarget(String s) {
    annotate(s, TARGET_TYPE);
  }
  
  public void clearSource() {
    clearAnnotations(SOURCE_TYPE);
  }
  
  public void clearTarget() {
    clearAnnotations(TARGET_TYPE);
  }
  
  public int countSource() {
    return countType(SOURCE_TYPE);
  }
  
  public int countTarget() {
    return countType(TARGET_TYPE);
  }
  
  public boolean existSource() {
    return countSource() > 0;
  }
  
  public boolean existTarget() {
    return countTarget() > 0;
  }
  
  /**
   * Check input annotation newAnn against existing annotations and 
   * suggest new annotations that do not overlap with the existing ones
   * @param newAnn
   * @return a list of new suggested annotations; if no overlap, then the original annotation is returned.
   */
  public List<Annotation> fixOverlap(Annotation newAnn) {
    List<Annotation> anns = new ArrayList<Annotation>();
    String type = newAnn.getType();
    boolean hasOverlap = false;
    
    for (Annotation oldAnn : annotations) {
      if (!hasOverlap(newAnn, oldAnn)) continue;
      hasOverlap = true;
      if (newAnn.start() < oldAnn.start() && newAnn.end() > oldAnn.end()) {
        // "those vintage Disney movies e.g. Aladdin@[39,78]" overlaps with existing annotation "Disney movies e.g.@[53,70]"
        anns.add(new Annotation(newAnn.start(), oldAnn.start(), type));
        anns.add(new Annotation(oldAnn.end(), newAnn.end(), type));
      } else if (newAnn.end() > oldAnn.end()) {
        // "e.g. Aladdin@[67,78]" overlaps with existing annotation "Disney movies e.g.@[53,70]"
        anns.add(new Annotation(oldAnn.end(), newAnn.end(), type));
      } else if (newAnn.start() < oldAnn.start()) {
        // "the CLASSIC disney movies@[16,40]" overlaps with existing annotation "disney movies i.e @[28,45]"
        anns.add(new Annotation(newAnn.start(), oldAnn.start(), type));
      }
    }
    if (!hasOverlap)
      anns.add(newAnn);
    return anns;
  }
  
  public List<Annotation> getAnnotations() {
    return annotations;
  }
  
  public double getDistScore() {
    Annotation prevSourceAnn = null;
    Annotation nextSourceAnn = null;
    double score = 0;
    Collections.sort(annotations);
    
    for (int i = 0; i < annotations.size(); i++) {
      Annotation currAnn = annotations.get(i);
      if (currAnn.isSourceType()) {
        prevSourceAnn = currAnn;
        continue;
      }
      // current annotation is 'target' type from this point on...
      int minCharDist = Integer.MAX_VALUE;
      if (prevSourceAnn != null)
        minCharDist = currAnn.startOffset - prevSourceAnn.end();

      // find the next 'source' annotation
      if (nextSourceAnn == null || currAnn.end() > nextSourceAnn.start()) {
        nextSourceAnn = null;
        for (int j = i+1; j < annotations.size(); j++) {
          Annotation ann = annotations.get(j);
          if (ann.isSourceType()) {
            nextSourceAnn = ann;
            break;
          }
        }
      }
      if (nextSourceAnn != null) {
        int charDist = nextSourceAnn.start() - currAnn.endOffset;
        minCharDist = Math.min(charDist, minCharDist);
      }
      if (minCharDist == Integer.MAX_VALUE) break;
      score += 1.0 / ((minCharDist+1) + LAPLACIAN_SMOOTHING);
    }
    return score;
  }
  
  public int getQueryType() {
    return queryType;
  }

  public String getText() {
    return text;
  }
  
  public String toString() {
    if (text == null) return null;
    Collections.sort(annotations);
    StringBuffer buf = new StringBuffer();
    int prevEndOffset = 0;
    
    for (Annotation ann : annotations) {
      if (prevEndOffset > ann.start())
        continue;
      buf.append(text.substring(prevEndOffset, ann.start()));
      buf.append(ann.isTargetType() ? START_TARGET_MARKER : START_SOURCE_MARKER);
      buf.append(text.substring(ann.start(), ann.end()));
      buf.append(ann.isTargetType() ? END_TARGET_MARKER : END_SOURCE_MARKER);
      prevEndOffset = ann.end();
    }
    buf.append(text.substring(prevEndOffset));
    return buf.toString();
  }

  private void annotate(String s, String type) {
    if (s == null || type == null) return;
    s.trim();
    
    queryType = determineQueryType(s);
    String patternStr;
    if (queryType > 0) {
      s = s.substring(queryType);
      patternStr = WrapperFactory.toPhraseRE(s);
    } else {
      patternStr = WrapperFactory.toEntityRE(s);
    }
    patternStr = "(?is:" + patternStr + ")";
    Matcher m = Pattern.compile(patternStr).matcher(text);

    while (m.find()) {
      Annotation newAnn = new Annotation(m.start(), m.end(), type);
      boolean hasOverlap = false;
      
      for (Annotation oldAnn : annotations) {
        hasOverlap = hasOverlap(newAnn, oldAnn);
        if (hasOverlap) {
//          log.debug("New annotation " + newAnn + " overlaps with existing annotation " + oldAnn);
          break;
        }
      }
      if (hasOverlap) continue;
//      log.info("-->" + text);
//      log.info("!!!" + newAnn);
      annotations.add(newAnn);
    }
  }

  private void clearAnnotations(String type) {
    if (type == null) return;
    for (Iterator<Annotation> i = annotations.iterator(); i.hasNext();) {
      Annotation ann = i.next();
      if (ann.getType().equals(type))
        i.remove();
    }
  }

  private int countType(String type) {
    int count = 0;
    if (type == null)
      return count;
    for (Annotation ann : annotations)
      if (ann.getType().equals(type))
        count++;
    return count;
  }
}
 public class Proximator {
  
  public static enum Proxistat { DIST, CHUNK, EXCERPT, SNIPPET, SOURCE, PROXISCORE }
  
  public static Logger log = Logger.getLogger(Proximator.class);
  public static GlobalVar gv = GlobalVar.getGlobalVar();
  
  public static final double DEFAULT_LAMBDA = 0.1;
  public static final double DEFAULT_SIM_THRESHOLD = 0.8;
  public static final int DEFAULT_EXTRACTION_MODE = 0;
  public static final int DEFAULT_MIN_SNIPPET_FREQ = 3;
  public static final int DEFAULT_NUM_TOP_TRANS = 3;
  public static final int DEFAULT_NUM_RESULTS = 100;
  public static final int DEFAULT_ENGINE = -1; // 4: use Yahoo! only
  
  private Map<Entity, Set<Snippet>> snippetMap;
  private Proximator reverseProximator;
//  private TranslationPair transPair;
  private BadWordFilterer badWordFilterer;
  private Set<String> sourceSet;
  private Pattern contentPattern;
  private EntityList entityList;
  private String targetLangID;
  private WebFetcher fetcher;
  private Entity total;
  
  private int numTopTrans;
  private int minSnippetFreq;
  private int extractionMode; // 0: translation, 1: e.g. member, 2: general member
  private double simThreshold;
  private double lambda;
  
  public static void main(String args[]) {
    Proximator proximator = new Proximator("en");
    Proximator rProximator = new Proximator("zh-TW");
    proximator.setReverseProximator(rProximator);

//    translator.setSource("約翰甘迺迪");
//    translator.setSource("侏儸紀公園");
//    translator.setSource("不可能的任務");
//    translator.setSource("George W. Bush");
//    translator.setSource("Doraemon");
//    translator.setSource("도라에몽");
//    translator.setSource("Wanted");
//    translator.setSource("The Dark Knight");
//    translator.setSource("senba");

    String[] sources = new String[] {
        "海角七號",
        "校樹青青",
        "悲情城市",
        "匹茲堡海盜",
        "紐約洋基",
        "洛杉磯道奇",
        "不可能的任務",
        "甘迺迪",
        "侏儸紀公園",
        "救難小英雄澳洲歷險記",
        "小美人魚",
        "哈利波特",
    };
    
    /*String[] sources = new String[] {
        "獅子王",
    };*/
    
//    translator.setToLangID("zh-TW");
    /*String[] sources = new String[] {
        "The Lord of the Rings",
        "The Lion King",
        "The Little Mermaid",
        "Beauty and the Beast",
    };*/
    
//    for (String source : sources)
    proximator.addSources(Arrays.asList(sources), false);

    for (String source : sources) {
      EntityList entities = proximator.getTargets(source);
      log.info("-----------------------------" + source + "-------------------------------");
      for (Entity entity : entities)
        log.info(entity);
//      Entity entity = translator.getTarget(source);
//      if (entity != null)
//        log.info(source + " translates to " + entity.getName());
    }
  }

  private static void assignDistScore(String transID, EntityList entities, Set<Excerpt> excerpts) {
    for (Entity entity : entities) {
      for (Excerpt excerpt : excerpts) {
        excerpt.clearTarget();
        // kmr possible gotcha
        excerpt.annotateTarget(entity.getName().toString());
        double distScore = excerpt.getDistScore();
        
        if (distScore > 0) {
          entity.addWeight(transID, distScore);
          entity.addWeight(Proxistat.DIST, distScore);
        }
      }
    }
  }
  
  private static Set<Snippet> getSnippetWithIndex(int index, Set<Snippet> snippets) {
    Set<Snippet> set = new HashSet<Snippet>();
    for (Snippet snippet : snippets)
      if (snippet.getIndex() == index)
        set.add(snippet);
    return set;
  }
  
  public Proximator(String targetLangID) {
//    transPair = new TranslationPair();
    entityList = new EntityList();
    sourceSet = new HashSet<String>();
    snippetMap = new HashMap<Entity, Set<Snippet>>();
    total = new Entity(Proxistat.class.getName());
    fetcher = new WebFetcher();
    fetcher.setAnnotateQuery(true);
    
    setTargetLangID(targetLangID);
    //setEngine(DEFAULT_ENGINE);
    setEngine(gv.getUseEngine());
    setMinSnippetFreq(DEFAULT_MIN_SNIPPET_FREQ);
    setExtractionMode(DEFAULT_EXTRACTION_MODE);
    setNumTopTrans(DEFAULT_NUM_TOP_TRANS);
    setSimThreshold(DEFAULT_SIM_THRESHOLD);
    setLambda(DEFAULT_LAMBDA);
    setNumResults(DEFAULT_NUM_RESULTS);
    
    badWordFilterer = new BadWordFilterer();
    badWordFilterer.loadStopwords(gv.getStopwordsList());
  }
  
  public void addSource(String source) {
    addSources(Arrays.asList(source), true);
  }
  
  /**
   * Adds a set of source words
   * @param sources a collection of source words
   * @param asOneQuery true to use all words as one search query string, 
   * false to use each word as an individual query string
   */
  public void addSources(List<String> sources, boolean asOneQuery) {
    Lang targetLang = LangProvider.getLang(targetLangID);
    if (targetLang == null) return;
    contentPattern = targetLang.getPattern();

    // the snippets fetched are indexed by source word's index in the list
    fetcher.setNumSubSeeds(asOneQuery ? 0 : 1);
    Set<Snippet> snippets = fetcher.fetchSnippets(sources, null);

    int numSources = (int) total.getWeight(Proxistat.SOURCE);
    int numEntities = (int) total.getWeight(Proxistat.CHUNK);
    
    if (asOneQuery) {
      addSources(sources, snippets);
    } else {
      List<String> list = new LinkedList<String>();
      for (int i = 0; i < sources.size(); i++) {
        String source = sources.get(i);
        System.out.print("Proximating in " + LangProvider.getName(targetLangID) + " using query: " + source + Helper.repeat(' ', 20) + "\r");
        list.add(source);
        addSources(list, getSnippetWithIndex(i, snippets));
        list.clear();
      }
      System.out.println();
    }
    
    log.info("Fetched " + ((int) total.getWeight(Proxistat.SOURCE)-numSources) + " sources, " + 
             snippets.size() + " snippets, and " +
             ((int) total.getWeight(Proxistat.CHUNK)-numEntities) + " entities in total!");
  }
  
  public void addStopword(String stopword, boolean isUnigram) {
    badWordFilterer.add(stopword, isUnigram);
  }
  
  public void addStopwords(Collection<String> stopwords, boolean isUnigram) {
    badWordFilterer.add(stopwords, isUnigram);
  }
  
  public void clear() {
    entityList.clear();
    sourceSet.clear();
    snippetMap.clear();
    total.clear();
  }
  
  public boolean[] getEngine() {
    return fetcher.getUseEngine();
  }
  
  public int getExtractionMode() {
    return extractionMode;
  }

  public double getLambda() {
    return lambda;
  }
  
  public double getMinSnippetFreq() {
    return minSnippetFreq;
  }
  
  public int getNumResults() {
    return fetcher.getNumResults();
  }
  
  public int getNumSource() {
    return sourceSet.size();
  }

  public int getNumTopTrans() {
    return numTopTrans;
  }
  
  public Proximator getReverseProximator() {
    return reverseProximator;
  }

  public double getSimThreshold() {
    return simThreshold;
  }

  public Entity getTarget(String source) {
    if (reverseProximator == null) {
      log.fatal("Reverse translator for language " + targetLangID + " is missing!");
      return null;
    }
    Entity bestTarget = null;
    double maxWeight = Double.MIN_VALUE;
    
    // collapse numTopTrans of translations
    EntityList targetList = getTargets(source);
    targetList = targetList.subList(0, numTopTrans*2);
    // shrink completely by name length
    targetList.shrink(Proxistat.PROXISCORE, Double.POSITIVE_INFINITY);
    targetList = targetList.subList(0, numTopTrans);
    
    for (int i = 0; i < targetList.size(); i++) {
      Entity targetEnt = targetList.get(i);
      double targetWeight = targetEnt.getWeight(Proxistat.PROXISCORE);
      // kmr possible gotcha
      EntityList sourceList = reverseProximator.getTargets(targetEnt.getName().toString());
      
      for (int j = 0; j < Math.min(numTopTrans, sourceList.size()); j++) {
        Entity sourceEnt = sourceList.get(j);
        double sourceWeight = sourceEnt.getWeight(Proxistat.PROXISCORE);
        // kmr possible gotcha
        double similarity = StringEditDistance.levenshtein(sourceEnt.getName().toString(), source);
        if (similarity < simThreshold) continue;
        log.info(source + " --> " + targetEnt.getName() + "(" + Math.round(targetWeight*100) + 
                 "%) --> " + sourceEnt.getName() + "(" + Math.round(sourceWeight*100) + "%)");
        double weight = targetWeight * sourceWeight * similarity;
        if (weight > maxWeight) {
          maxWeight = weight;
          bestTarget = targetEnt;
        }
      }
    }
    return bestTarget;
  }

  public String getTargetLangID() {
    return targetLangID;
  }
  
  public EntityList getTargets(List<String> sources, boolean asOneQuery) {
    if (sources.isEmpty()) {
      log.error("Error: Missing input source words!");
      return new EntityList();
    }
    
    String transID = getTransID(Helper.toReadableString(sources));
    if (!sourceSet.contains(transID))
      addSources(sources, asOneQuery);
    
    // return immediately if not in translation mode
    if (extractionMode != 0)
      return entityList;
    
    // get a list of entities in this document (document of the input source)
    EntityList subList = entityList.getEntities(transID);
    
    // get the sum of wtf(x) for all entities x in this document
    double WTF_d = subList.getSumWeights(transID) + subList.size();
    
    // get the sum of wtf(x) for all entities x in the rest of the documents
    double WTF_c = entityList.size();
    for (String s : sourceSet)
      if (!s.equals(transID))
        WTF_c += entityList.getSumWeights(getTransID(s));
    
    // added 10/15/2009 for testing
    /*int numSnippets = (int) total.getWeight(Proxistat.SNIPPET);
    int numExcerpts = (int) total.getWeight(Proxistat.EXCERPT);
    int numChunks = (int) total.getWeight(Proxistat.CHUNK);*/
    
    for (Entity e : subList) {
      
      // get wtf(x) for the input x in this document only
      double wtf_d = e.getWeight(transID) + 1;
      
      // get the sum of wtf(x) for all input x in other documents
      double wtf_c = 1;
      for (String s : sourceSet)
        if (!s.equals(transID))
          wtf_c += e.getWeight(getTransID(s));
      
      // compute the score using linear interpolation of the probabilities
      double prob_wtf_d = wtf_d / WTF_d;
      double prob_wtf_c = wtf_c / WTF_c;
      double score = lambda*prob_wtf_d + (1-lambda)*(1-prob_wtf_c);
      
      // added 10/15/2009 for testing
      /*double pSnippet = (numSnippets == 0) ? 0 : e.getWeight(Proxistat.SNIPPET) / numSnippets;
      double pExcerpt = (numExcerpts == 0) ? 0 : e.getWeight(Proxistat.EXCERPT) / numExcerpts;
      score = lambda * ((double) 1/3 * pSnippet + (double) 1/3 * pExcerpt + (double) 1/3 * prob_wtf_d) + (1-lambda)*(1-prob_wtf_c);
      score = (double) 1/3 * pSnippet + (double) 1/3 * pExcerpt + (double) 1/3 * prob_wtf_d;*/

      e.setWeight(Proxistat.PROXISCORE, score);
    }
    // shrink partially
    subList.shrink(Proxistat.PROXISCORE, 1);
    return subList;
  }

  public EntityList getTargets(String source) {
    return getTargets(Arrays.asList(source), true);
  }

  public Entity getTotal() {
    return total;
  }

  public String getTransID(String source) {
      return source + "." + targetLangID;
  }

  /*public TranslationPair getTransPair() {
    return transPair;
  }*/

  public void setEngine(int engine) {
    fetcher.setUseEngine(engine);
  }

  public void setExtractionMode(int mode) {
    this.extractionMode = mode;
  }

  public void setLambda(double lambda) {
    this.lambda = lambda;
  }

  public void setMinSnippetFreq(int minExcerptFreq) {
    this.minSnippetFreq = minExcerptFreq;
  }

  public void setNumResults(int numResults) {
    fetcher.setNumResults(numResults);
  }

  public void setNumTopTrans(int numTopTrans) {
    this.numTopTrans = numTopTrans;
  }

  public void setReverseProximator(Proximator reverseTranslator) {
    this.reverseProximator = reverseTranslator;
  }
  
  public void setSimThreshold(double simThreshold) {
    this.simThreshold = simThreshold;
  }
  
  public void setTargetLangID(String targetLangID) {
    if (!LangProvider.supports(targetLangID)) {
      log.error("Unknown lang: " + targetLangID);
      return;
    }
    this.targetLangID = targetLangID;
    fetcher.setLangID(targetLangID);
  }

  private void addSources(List<String> sources, Set<Snippet> snippets) {
    Set<Excerpt> goodExcerpts = new HashSet<Excerpt>();
    EntityList entities = extract(snippets, goodExcerpts);
    
    // output excerpts for debugging purposes
    /*int i = 1;
    for (Excerpt excerpt : excerpts)
      log.debug((i++) + ". " + excerpt);*/
    
    // filter out entities not having enough snippet frequency
//    log.info(this.getClass().getSimpleName() + " is removing instances with snippet-freq < " + minSnippetFreq);
    entities.absoluteFilter(Proxistat.SNIPPET, minSnippetFreq);
    
    // inserts weighted term frequency (WTF) as a feature (keyed by 'transID')
    // this is very computational expensive, try to minimize entities 
    // as much as possible before reaching this step
    String transID = getTransID(Helper.toReadableString(sources));
    assignDistScore(transID, entities, goodExcerpts);
    
    sourceSet.add(transID);
  }

  private void extract(Excerpt excerpt, EntityList entities) {
    if (extractionMode == 1)
      excerpt.chopText();
    
    String excerptStr = excerpt.toString();
    Matcher m = contentPattern.matcher(excerpt.getText());
    while (m.find()) {
      Annotation ann = excerpt.new Annotation(m.start(), m.end(), Annotator.TARGET_TYPE);
      
      for (Annotation a : excerpt.fixOverlap(ann)) {
        String chunk = a.getText().trim();
        
        if (extractionMode == 0) {
          entities.add(extract(chunk, a.start(), excerptStr));
        } else {
          for (String subChunk : HyponymProvider.split(chunk, targetLangID))
            entities.add(extract(subChunk, a.start(), excerptStr));
        }
      }
    }
  }

  private EntityList extract(Set<Snippet> snippets, Set<Excerpt> goodExcerpts) {
    EntityList sourceEntities = new EntityList();
    EntityList snippetEntities = new EntityList();
    EntityList excerptEntities = new EntityList();
    Set<Excerpt> excerpts = new HashSet<Excerpt>();
    
    for (Snippet snippet : snippets) {
      snippetEntities.clear();
      
      // collect all bilingual excerpts (title + summary)
      excerpts.clear();
      excerpts.add(snippet.getTitle());
      excerpts.addAll(snippet.getExcerpts());
      
      for (Excerpt excerpt : excerpts) {
        // ignore excerpts that do not contain any source annotation
        if (excerpt.countSource() == 0) continue;

        // extract entities in target language from the excerpt
        excerptEntities.clear();
        extract(excerpt, excerptEntities);
        if (excerptEntities.isEmpty()) continue;
        
        goodExcerpts.add(excerpt);
        excerptEntities.addWeight(Proxistat.EXCERPT, 1);
        total.addWeight(Proxistat.EXCERPT, 1);
        snippetEntities.addAll(excerptEntities);
      }
      
      if (snippetEntities.isEmpty()) continue;
      snippetEntities.addWeight(Proxistat.SNIPPET, 1);
      total.addWeight(Proxistat.SNIPPET, 1);
      sourceEntities.addAll(snippetEntities);
    }
    
    sourceEntities.addWeight(Proxistat.SOURCE, 1);
    total.addWeight(Proxistat.SOURCE, 1);
    return sourceEntities;
  }

  private Entity extract(String content, int startOffset, String excerpt) {
    // tidy the extracted content, but not to its canonical form
    content = WrapperFactory.tidy(content, true);
    
    // verify the content
    if (!WrapperFactory.checkSimpleContent(content)) return null;
    if (badWordFilterer.isBad(content)) return null;
    // discard entities starting with a number (added 11/01/2008)
    if (content.matches("^\\d+.*$")) return null;
    
    // remove the beginning words (e.g., "the") (added 10/19/2008)
    if (extractionMode == 1 && startOffset == 0)
      content = HyponymProvider.removeBeginWord(content, targetLangID);

    // tidy the extracted content to its canonical form
    Entity entity = entityList.add(WrapperFactory.tidy(content, false));
    entity.addWeight(Proxistat.CHUNK, 1);
    total.addWeight(Proxistat.CHUNK, 1);
    
    // store the original surface string
    Object[] keys = new Object[] {excerpt, startOffset, targetLangID};
    EntityLiteral e = entity.getName();
    Originator.add(e.arg1, content, keys);
    if (e.arg2 != null)
        Originator.add(e.arg2, content, keys);
    
    return entity;
  }
}
 public static enum Proxistat { DIST, CHUNK, EXCERPT, SNIPPET, SOURCE, PROXISCORE }
 public class GlobalVar {
  
  public static final String PROP_ENV_NAME = "SEAL_PROP";
  public static final String PROP_FILE_PATH = "seal.properties";
  public static final String COMMA_REGEXP = "\\s*,\\s*";
  public static final String CLUEWEB_TMP_DIR="clueweb.tmpdir";
  public static final String CLUEWEB_HEADER_TIMEOUT_MS = "clueweb.headerTimeout";
  public static final String CLUEWEB_TIMEOUT_NUMTRIALS = "clueweb.numtrials";
  public static final String CLUEWEB_TIMEOUT_REPORTING_MS = "clueweb.timeoutReporting";
  public static Logger log = Logger.getLogger(GlobalVar.class);
  
  private static GlobalVar gv = null;
  private static Properties prop = null;
  
  // Basic parameters
  private static String langID;
  private static Feature feature;
  private static boolean hasNoisySeeds;
  private static int useEngine;
  private static String yahooAPIKey;
  private static String yahooBossKey;
  private static long googleHitGapInMS;
  private static File resultDir;
  private static int minSeedsBracketed;
  private static String bingAPIKey;
  private static String googleCustomAPIKey;
  private static  String setExpander;

  // Fetching parameters
  private static int numResults;
  private static int numSubSeeds;
  
  // OfflineSeal and WrapperSavingAsia parameters
    private static boolean isFetchFromWeb; //wwc - keeps WebManager from getting stuff from web
    private static File localDir; //wwc - files that will be searched by the OfflineSearcher
    private static File indexDir; //wwc - index of files in localDir
    private static File localRoot; //wwc - set if files are indexed relative to some root directory
    private static File savedWrapperDir; //wwc - stores wrappers generated by OfflineSeal or WrapperSavingAsia
    private static int wrapperSaving; //wwc - policy on wrapper saving, 2 means save to savedWrapperDir

  // Optimization parameters
  private static int wrapperLevel;
  private static int minContextLength;
  private static int maxDocSizeInKB;
  private static int timeOutInMS;
  private static File cacheDir;
  private static File urlBlackList;
  private static File stopwordsList;
  
  // Iterative expansion parameters
  private static SeedingPolicy policy;
  private static int numExpansions;
  private static int numTrueSeeds;
  private static int numPossibleSeeds;
  
  // Bilingual
  private static String langID2;
  
  // Experiments parameters
  private static List<Feature> expFeatures;
  private static List<String> expDatasets;
  private static File evalDir;
  private static File dataDir;
  private static int numTrials;

  // Question Answering parameters
  private static int topSystem;
  private static boolean useGoogleSets;
  private static double ephyraThreshold;
  private static double sealThreshold;
  private static double interThreshold;
  private static double unionThreshold;
  private static double method1Threshold;
  

  private static boolean explicitRelations;
  private static boolean storeContentWeights;
  
  // ClueWeb parameters
  private static boolean cluewebKeepResponseFile;
  private static boolean cluewebKeepQueryFile;
  private static boolean cluewebMemoryManagement;
  private static boolean multiquery;
  /**
   * Looks for a GlobalVar in the following order:
   * 1) System environment: PROP_ENV_NAME
   * 2) Fixed location: PROP_FILE_PATH
   * @return
   */
  public static GlobalVar getGlobalVar() {
    if (gv != null) return gv;
    gv = new GlobalVar();
    String propFilePath = System.getenv(PROP_ENV_NAME);
    if (propFilePath == null) {
      propFilePath = System.getProperty(PROP_FILE_PATH,PROP_FILE_PATH);
    }
    gv.load(propFilePath);
    return gv;
  }

  public void load(String propFilePath) {
      File propFile = new File(propFilePath);
      log.debug("Loading seal.properties from "+propFilePath);
      prop = Helper.loadPropertiesFile(propFile);
      if (prop == null) {
        log.fatal("Missing \"" + PROP_FILE_PATH + "\" in your classpath!");
        System.exit(1);
      }
      //merge any command-line overrides
      Properties sysprop = System.getProperties();
      prop.putAll(sysprop); // this is messy(noisy) but easy
      
      gv.load(prop);
  }




  
  /**
   * Merges the input properties with the previously loaded properties.
   * Input property names overwrite the loaded property names.
   * @param in the input properties
   */
  public void merge(Properties in) {
    if (prop != null)
      prop.putAll(in);
    else prop = in;
    load(prop);
  }
  
  private static String getProperty(String key, String defaultValue) {
    if (prop == null) {
      log.warn("Properties file not found! Using default: \"" + defaultValue + 
               "\" for the property name: \"" + key + "\"");
      return defaultValue;
    }
    String value = prop.getProperty(key);
    if (value == null || value.trim().length() == 0) {
      log.warn("Missing or invalid property name: \"" + key + "\", using default: \"" + defaultValue + "\"");
      value = defaultValue;
    }
    return value;
  }
  
  private static void setProperties(Properties prop) {
    GlobalVar.prop = prop;
  }
  
  private static List<Feature> toFeatures(String in) {
    if (in == null) return null;
    String[] array = in.split(COMMA_REGEXP);
    List<Feature> list = new ArrayList<Feature>();
    for (String s : array) {
      Feature feature = Feature.valueOf(s.trim());
      if (feature != null)
        list.add(feature);
    }
    return list;
  }
  
  private static List<String> toStrings(String in) {
    if (in == null) return null;
    String[] array = in.split(COMMA_REGEXP);
    List<String> list = new ArrayList<String>();
    for (String s : array) {
      s = s.toLowerCase().trim();
      if (s.length() > 0)
        list.add(s);
    }
    return list;
  }
  
  private static File toFile(String in) {
    return in == null ? null : new File(in);
  }
  
  public void load(Properties prop) {
    setProperties(prop);
    
    // expansion parameters
    wrapperLevel = Integer.parseInt(getProperty("wrapperLevel", "0"));
    minSeedsBracketed = Integer.parseInt(getProperty("minSeedsBracketed", "0"));
    minContextLength = Integer.parseInt(getProperty("minContextLength", "1"));
    maxDocSizeInKB = Integer.parseInt(getProperty("maxDocSizeInKB", "512"));
    
    langID = getProperty("langID", "un");
    langID2 = getProperty("langID2", "un");
    yahooAPIKey = getProperty("yahooAPIKey", "");
    yahooBossKey = getProperty("yahooBossKey", "");
    bingAPIKey = getProperty("bingAPIKey","");
    googleCustomAPIKey = getProperty("googleCustomAPIKey","");
    numResults = Integer.parseInt(getProperty("numResults", "100"));
    numSubSeeds = Integer.parseInt(getProperty("numSubSeeds", "0"));
    timeOutInMS = Integer.parseInt(getProperty("timeOutInMS", "10000")); // 10 sec.
    isFetchFromWeb = Boolean.parseBoolean(getProperty("isFetchFromWeb", "true")); // wwc
    hasNoisySeeds = Boolean.parseBoolean(getProperty("hasNoisySeeds", "false"));
    useGoogleSets = Boolean.parseBoolean(getProperty("useGoogleSets", "false"));
    setExpander = getProperty("setExpander",
            useGoogleSets ?
            "com.rcwang.seal.expand.GoogleSets" : 
            "com.rcwang.seal.expand.Seal");
    useEngine = Integer.parseInt(getProperty("useEngine", "6"));
    cacheDir = toFile(getProperty("cacheDir", "cache"));
    localDir = toFile(getProperty("localDir", "local"));
    indexDir = toFile(getProperty("indexDir", "index")); // wwc
    localRoot = toFile(getProperty("localRoot", null)); // wwc
    savedWrapperDir = toFile(getProperty("savedWrapperDir", "wrapper")); // wwc
    wrapperSaving = Integer.parseInt(getProperty("wrapperSaving", "0")); // wwc
    resultDir = toFile(getProperty("resultDir", null));
    feature = Feature.valueOf(getProperty("feature", "WLW"));
    policy = SeedingPolicy.valueOf(getProperty("policy", "ISS_UNSUPERVISED"));
    numTrueSeeds = Integer.parseInt(getProperty("numTrueSeeds", "2"));
    numPossibleSeeds = Integer.parseInt(getProperty("numPossibleSeeds", "0"));
    // every hit to Google must be at least x milliseconds in between
    googleHitGapInMS = Long.parseLong(getProperty("googleHitGapInMS", "5000"));
    expFeatures = toFeatures(getProperty("expFeatures", null));
    expDatasets = toStrings(getProperty("expDatasets", null));
    urlBlackList = toFile(getProperty("urlBlackList", null));
    stopwordsList = toFile(getProperty("stopwordsList", null));
    
    // evaluation parameters
    evalDir = new File(getProperty("evalDir", "eval"));
    dataDir = new File(getProperty("dataDir", "data"));
    numTrials = Integer.parseInt(getProperty("numTrials", "0"));
    numExpansions = Integer.parseInt(getProperty("numExpansions", "0"));
    
    // qa
    topSystem = Integer.parseInt(getProperty("topSystem", "0"));
    ephyraThreshold = Double.parseDouble(getProperty("ephyraThreshold", "0"));
    sealThreshold = Double.parseDouble(getProperty("sealThreshold", "0"));
    interThreshold = Double.parseDouble(getProperty("interThreshold", "0"));
    unionThreshold = Double.parseDouble(getProperty("unionThreshold", "0"));
    method1Threshold = Double.parseDouble(getProperty("method1Threshold", "0"));
    
    // are all relations created using Entity(String,String) constructor?
    explicitRelations = Boolean.parseBoolean(getProperty("explicitRelations","false"));
    
    // should individual content weights be stored in addition to aggregated weights?
    // (for NELL scoring)
    storeContentWeights = Boolean.parseBoolean(getProperty("storeContentWeights","false"));
    
    // clueweb
    cluewebKeepQueryFile    = Boolean.parseBoolean(getProperty("cluewebKeepQueryFile","false"));
    cluewebKeepResponseFile = Boolean.parseBoolean(getProperty("cluewebKeepResponseFile","false"));
    cluewebMemoryManagement = Boolean.parseBoolean(getProperty("cluewebMemoryManagement","true"));
    multiquery = Boolean.parseBoolean(getProperty("multiquery","false"));
  }
  
  public Properties getProperties() { return prop; }
  
  public File getCacheDir() { return cacheDir; }
  public void setCacheDir(File cacheDir) { GlobalVar.cacheDir = cacheDir; }
  
  public File getIndexDir() { return indexDir; } //wwc
  public void setIndexDir(File indexDir) { GlobalVar.indexDir = indexDir; } //wwc

  public File getLocalDir() { return localDir; } //wwc
  public void setLocalDir(File localDir) { GlobalVar.localDir = localDir; } //wwc

  public File getLocalRoot() { return localRoot; } //wwc
  public void setRootOfIndexedFiles(File localRoot) { GlobalVar.localRoot = localRoot; } //wwc

  public File getSavedWrapperDir() { return savedWrapperDir; } //wwc
  public void setSavedWrapperDir(File savedWrapperDir) { GlobalVar.savedWrapperDir = savedWrapperDir; } //wwc

  public int getWrapperSaving() { return wrapperSaving; } //wwc
  public void setWrapperSaving(int wrapperSaving) { GlobalVar.wrapperSaving = wrapperSaving; } //wwc

  public File getDataDir() { return dataDir; }
  public void setDataDir(File dataDir) { GlobalVar.dataDir = dataDir; }
  
  public File getEvalDir() { return evalDir; }
  public void setEvalDir(File evalDir) { GlobalVar.evalDir = evalDir; }
  
  public String getLangID() { return langID; }
  public void setLangID(String langID) { GlobalVar.langID = langID; }
  
  public int getMaxDocSizeInKB() { return maxDocSizeInKB; }
  public void setMaxDocSizeInKB(int maxDocSizeInKB) { GlobalVar.maxDocSizeInKB = maxDocSizeInKB; }
  
  public int getMinContextLength() { return minContextLength; }
  public void setMinContextLength(int minContextLength) { GlobalVar.minContextLength = minContextLength; }
  
  public int getMinSeedsBracketed() { return minSeedsBracketed; }
  public void setMinSeedsBracketed(int minSeedsBracketed) { GlobalVar.minSeedsBracketed = minSeedsBracketed; }
  
  public int getNumExpansions() { return numExpansions; }
  public void setNumExpansions(int numExpansions) { GlobalVar.numExpansions = numExpansions; }
  
  public int getNumResults() { return numResults; }
  public void setNumResults(int numResults) { GlobalVar.numResults = numResults; }
  
  public int getNumSubSeeds() { return numSubSeeds; }
  public void setNumSubSeeds(int numSubSeeds) { GlobalVar.numSubSeeds = numSubSeeds; }
  
  public int getNumTrials() { return numTrials; }
  public void setNumTrials(int numTrials) { GlobalVar.numTrials = numTrials; }

  public File getResultDir() { return resultDir; }
  public void setResultDir(File resultDir) { GlobalVar.resultDir = resultDir; }
  
  public File getStopwordsList() { return stopwordsList; }
  public void setStopwordsList(File stopwordsList) { GlobalVar.stopwordsList = stopwordsList; }
  
  public int getTimeOutInMS() { return timeOutInMS; }
  public void setTimeOutInMS(int timeOutInMS) { GlobalVar.timeOutInMS = timeOutInMS; }
  
  public File getUrlBlackList() { return urlBlackList; }
  public void setUrlBlackList(File urlBlackList) { GlobalVar.urlBlackList = urlBlackList; }
  
  public String getYahooAPIKey() { return yahooAPIKey; }
  public void setYahooAPIKey(String yahooAPIKey) { GlobalVar.yahooAPIKey = yahooAPIKey; }
  
  public boolean getIsFetchFromWeb() { return isFetchFromWeb; } //wwc
  public void setIsFetchFromWeb(boolean isFetchFromWeb) { GlobalVar.isFetchFromWeb = isFetchFromWeb; } //wwc

  public boolean hasNoisySeeds() { return hasNoisySeeds; }
  public void setHasNoisySeeds(boolean hasNoisySeeds) { GlobalVar.hasNoisySeeds = hasNoisySeeds; }

  public Feature getFeature() { return feature; }
  public void setFeature(Feature feature) { GlobalVar.feature = feature; }
  
  public SeedingPolicy getPolicy() { return policy; }
  public void setPolicy(SeedingPolicy policy) { GlobalVar.policy = policy; }

  public int getNumPossibleSeeds() { return numPossibleSeeds; }
  public void setNumPossibleSeeds(int numPossibleSeeds) { GlobalVar.numPossibleSeeds = numPossibleSeeds; }

  public int getNumTrueSeeds() { return numTrueSeeds; }
  public void setNumTrueSeeds(int numTrueSeeds) { GlobalVar.numTrueSeeds = numTrueSeeds; }

  public List<Feature> getExpFeatures() { return expFeatures; }
  public void setExpFeatures(List<Feature> expFeatures) { GlobalVar.expFeatures = expFeatures; }

  public List<String> getExpDatasets() { return expDatasets; }
  public void setExpDatasets(List<String> expDatasets) { GlobalVar.expDatasets = expDatasets; }

  public long getGoogleHitGapInMS() { return googleHitGapInMS; }
  public void setGoogleHitGapInMS(long googleHitGap) { GlobalVar.googleHitGapInMS = googleHitGap; }

  public int getTopSystem() { return topSystem; }
  public void setTopSystem(int topSystem) { GlobalVar.topSystem = topSystem; }

  public double getEphyraThreshold() { return ephyraThreshold; }
  public void setEphyraThreshold(double ephyraThreshold) { GlobalVar.ephyraThreshold = ephyraThreshold; }

  public double getSealThreshold() { return sealThreshold; }
  public void setSealThreshold(double sealThreshold) { GlobalVar.sealThreshold = sealThreshold; }

  public double getInterThreshold() { return interThreshold; }
  public void setInterThreshold(double interThreshold) { GlobalVar.interThreshold = interThreshold; }

  public double getUnionThreshold() { return unionThreshold; }
  public void setUnionThreshold(double unionThreshold) { GlobalVar.unionThreshold = unionThreshold; }

  public double getMethod1Threshold() { return method1Threshold; }
  public void setMethod1Threshold(double method1Threshold) { GlobalVar.method1Threshold = method1Threshold; }

  public boolean isUseGoogleSets() { return useGoogleSets; }
  public void setUseGoogleSets(boolean useGoogleSets) {GlobalVar.useGoogleSets = useGoogleSets; }

  public String getLangID2() { return langID2; }
  public void setLangID2(String langID2) { GlobalVar.langID2 = langID2; }

  public int getUseEngine() { return useEngine; }
  public void setUseEngine(int useEngine) { GlobalVar.useEngine = useEngine; }

  public int getWrapperLevel() { return wrapperLevel; }
  public void setWrapperLevel(int wrapperLevel) { GlobalVar.wrapperLevel = wrapperLevel; }

  public String getYahooBossKey() { return yahooBossKey; }
  public void setYahooBossKey(String yahooBossKey) { GlobalVar.yahooBossKey = yahooBossKey; }

  public boolean getExplicitRelations() { return explicitRelations; }
  public boolean isStoreContentWeights() { return storeContentWeights; }

  public String getBingAPIKey() { return bingAPIKey; }
  public void setBingAPIKey(String k) { GlobalVar.bingAPIKey = k; }

  public String getGoogleCustomAPIKey() { return googleCustomAPIKey; }
  public void setGoogleCustomAPIKey(String k) { GlobalVar.googleCustomAPIKey = k; }
  
  public boolean getClueWebMemoryManagement() { return cluewebMemoryManagement; }
  public void setClueWebMemoryManagement(boolean b) { cluewebMemoryManagement = b; }
  
  public boolean getClueWebKeepResponseFile() { return cluewebKeepResponseFile; }
  public void setClueWebKeepResponseFile(boolean b) { cluewebKeepResponseFile = b; }
  
  public boolean getClueWebKeepQueryFile() { return cluewebKeepQueryFile; }
  public void setClueWebKeepQueryFile(boolean b) { cluewebKeepQueryFile = b; }
  
  public boolean isMultiquery() { return multiquery; }
  public void setMultiquery(boolean b) { multiquery = b; }




  public String getSetExpander() { return setExpander; }




 }
 public class Helper {
  
  public static Logger log = Logger.getLogger(Helper.class);
  
  public static final String UNICODE = "UTF-8";
  public static final String COMMON_ENCODING = "ISO-8859-1";
  public static final String DATE_FORMAT = "yyyy-MM-dd";  // must match below
  public static final String DATE_PATTERN = "\\d+{4}-\\d+{2}-\\d+{2}";  // must match above
  public static final String TIME_FORMAT = "h:mm:ss aa";
  public static final String DATE_TIME_FORMAT = DATE_FORMAT + " " + TIME_FORMAT;
  public static final NumberFormat NUM_FORMAT = NumberFormat.getInstance();
  
  public static String repeat(char c, int n) {
    StringBuffer buf = new StringBuffer();
    for (; n > 0; n--)
      buf.append(c);
    return buf.toString();
  }
  
  public static String center(String s, char filler, int width) {
    if (s.length() >= width) return s;
    int numFillers = (width - s.length()) / 2;
    return repeat(filler, numFillers) + s + repeat(filler, numFillers);
  }
  
  public static String addQuote(String s) {
    s = s.trim();
    if (!s.startsWith("\""))
      s = "\"" + s;
    if (!s.endsWith("\""))
      s += "\"";
    return s;
  }
  
  public static double getPDF(double x, double avg, double std) {
    double diff = x - avg;
    double exp = Math.exp(-0.5 * Math.pow(diff / std, 2));
    return exp / (std * Math.sqrt(2 * Math.PI));
  }
  
  public static String addQuote(String[] ss) {
    StringBuffer buf = new StringBuffer();
    for (String s : ss)
      buf.append(buf.length() > 0 ? " " : "").append(addQuote(s));
    return buf.toString();
  }
  
  public static File createDir(File dir) {
    if (dir != null && !dir.isDirectory()) {
      log.info("Creating directory: " + dir.getAbsolutePath());
      if (!dir.mkdirs())
          log.error("Could not create requested directories for "+dir.getAbsolutePath());
    }
    return dir;
  }
  
  public static File createTempFile (String content) {
    File temp = null;
    try {
      temp = File.createTempFile("tmp", null);
    } catch (IOException ioe) {
      log.error("Error creating temp file: " + ioe);
      return null;
    }
    temp.deleteOnExit();
    writeToFile(temp, content, "UTF-8", false);
    return temp;
  }
  
  public static String decodeURLString(String s) {
    if (s == null) return null;
    try {
      return URLDecoder.decode(s, UNICODE);
    } catch (UnsupportedEncodingException e) {
      log.error(e.toString());
      return null;
    }
  }
  
  public static void die(String s) {
    System.err.println("[FATAL] " + s);
    System.exit(1);
  }
  
  public static boolean empty(EntityList entityList) {
    return entityList == null || entityList.isEmpty();
  }
  
  public static boolean empty(String s) {
    return s == null || s.trim().length() == 0;
  }
  
  // encode the query and formulate the query URL
  public static String encodeURLString(String s) {
    if (s == null) return null;
    try {
      return URLEncoder.encode(s, UNICODE);
    } catch (UnsupportedEncodingException e) {
      log.error(e.toString());
      return null;
    }
  }
  
  /**
   * Returns the String bounded by "left" and "after" in String s
   * @param s
   * @param left
   * @param right
   * @return the bounded String
   */
  public static String extract(String s, String left, String right) {
    int leftOffset, rightOffset;
    if (left == null) {
      leftOffset = 0;
      left = "";
    } else {
      leftOffset = s.indexOf(left);
      if (leftOffset == -1)
        return null;
    }
    if (right == null) {
      rightOffset = s.length();
    } else {
      rightOffset = s.indexOf(right, leftOffset + left.length());
      if (rightOffset == -1)
        return null;
    }
    return s.substring(leftOffset + left.length(), rightOffset);
  }

  public static String formatNumber(double number, int decimal) {
    NUM_FORMAT.setMaximumFractionDigits(decimal);
    NUM_FORMAT.setMinimumFractionDigits(decimal);
    return NUM_FORMAT.format(number).replace(",", "");
  }
  
  public static int getStringSize(String s) {
    int docSize = -1;
    try {
      docSize = s.getBytes("US-ASCII").length;
    } catch (UnsupportedEncodingException e) {
      e.printStackTrace();
    }
    return docSize;
  }
  
  /***
   * Creates a unique ID based on the current date and time
   * @return a unique ID
   */
  public static String getUniqueID () {
    Calendar cal = Calendar.getInstance(TimeZone.getDefault());
    SimpleDateFormat sdf = new SimpleDateFormat("MMdd-HHmmss");
    sdf.setTimeZone(TimeZone.getDefault());
    return sdf.format(cal.getTime());
  }
  
  public static Properties loadPropertiesFile(File propFile) {
    if (propFile == null)
      return null;
    Properties props = new Properties();
    InputStream in;
    try {
      in = readFileToStream(propFile);
      if (in != null) {
        props.load(in);
        in.close();
      }
    } catch (FileNotFoundException e) {
      log.error("Properties file not found: " + e);
      return null;
    } catch (IOException e) {
      log.error("Read properties file error: " + e);
      return null;
    }
    return props;
  }
  
  public static <T> T loadSerialized(File file, Class<? extends T> c) {
    log.info("Loading serialized object from: " + file);
    FileInputStream fis = null;
    ObjectInputStream in = null;
    T object = null;
    try {
      fis = new FileInputStream(file);
      in = new ObjectInputStream(fis);
      object = c.cast(in.readObject());
      in.close();
    } catch(IOException ex) {
      ex.printStackTrace();
    } catch(ClassNotFoundException ex) {
      ex.printStackTrace();
    }
    return object;
  }

  public static double log2(double d) {
    return Math.log(d) / Math.log(2);
  }
  
  public static String merge(String[] strList, String delimiter) {
    StringBuffer buf = new StringBuffer();
    for (String s : strList) {
      if (buf.length() > 0)
        buf.append(delimiter);
      buf.append(s);
    }
    return buf.toString();
  }
  
  public static void printElapsedTime(long startTime) {
    log.info("Elapsed time: " + (System.currentTimeMillis() - startTime) / 1000.0 + " seconds");
  }
  
  public static void printDebugInfo() {
    log.info("Originator Size: " + Originator.size() + " (" + Originator.getNumStrings() + ")");
    log.info("String     Size: " + StringFactory.getStrSize());
    log.info("String ID  Size: " + StringFactory.getIDSize());
    Helper.printMemoryUsed();
  }
  
  public static void printMemoryUsed() {
    for (int i = 0; i < 3; i++) System.gc();
    long memSize = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
    String memSizeStr = Helper.formatNumber((double) memSize / 1024 / 1024, 2);
    log.info(" Memory used: " + memSizeStr + "MB");
  }
  
  public static String readFile(File f) {
    return readFile(f, "UTF-8", false);
  }

  /**
   * Reads in a file, if not found, search on the class path
   * @param file the input file
   * @param charset the character set
   * @param binary is the file binary or text (non-binary)?
   * @return the content of the file
   */
  public static String readFile(File file, String charset, boolean binary) {
    if (file == null || charset == null)
      return null;
    InputStream in = readFileToStream(file);
    if (in == null)
      return null;
    StringBuffer buf = new StringBuffer();
    try {
      BufferedReader bReader = new BufferedReader(new InputStreamReader(in, charset));
      if (!binary) {
        String line;
        while ((line = bReader.readLine()) != null)
          buf.append(line).append("\n");
      } else {
        char[] c = new char[(int) file.length()];
        bReader.read(c);
        buf.append(c);
      }
      bReader.close();
    } catch (Exception e) {
      log.error("Could not read \"" + file + "\": " + e);
      return null;
    }
    String result = buf.toString();
    // get rid of BOM (byte order marker) from UTF-8 file
    if (result.length() > 0 && result.charAt(0) == 65279)
      result = result.substring(1);
    return result;
  }
  
  public static InputStream readFileToStream(File in) {
    if (in == null) return null;
    InputStream s = null;
    try {
      if (in.exists()) // if file exist locally
        s = new FileInputStream(in);
      if (s == null) // if file exist somewhere on the class path
        s = ClassLoader.getSystemResourceAsStream(in.getPath());
      if (s == null) { // if file still could not be found
        log.error("Could not find \"" + in + "\" locally ("+in.getAbsolutePath()+") or on classpath");
        return null;
      }
    } catch (Exception e) {
      log.error("Could not read \"" + in + "\": " + e);
      return null;
    }
    return s;
  }
  
  public static void recursivelyRemove(File f) {
    if (f == null || !f.exists()) return;
    if (f.isDirectory()) {
      File[] files = f.listFiles();
      for (File file : files)
        recursivelyRemove(file);
    }
    String type = f.isDirectory() ? "directory" : "file";
    boolean deleted = f.delete();
    if (!deleted)
      log.error("Cannot delete the " + type + ": " + f);
    else log.debug("Successfully deleted the " + type + ": " + f);
  }
  
  public static String removeQuote(String s) {
    if (s == null) return null;
    s = s.trim();
    if (s.startsWith("\"") && s.endsWith("\""))
      s = s.substring(1, s.length()-1);
    return s;
  }
  
  public static void saveSerialized(Object object, File file, boolean overwrite) {
    if (!overwrite && file.exists()) {
      log.info("Serialized file " + file + " already exists! Skip saving...");
      return;
    }
    log.info("Saving serialized object to: " + file);
    if (file.getParentFile() != null)
      Helper.createDir(file.getParentFile());
    FileOutputStream fos = null;
    ObjectOutputStream out = null;
    try {
      fos = new FileOutputStream(file);
      out = new ObjectOutputStream(fos);
      out.writeObject(object);
      out.close();
    } catch(IOException ex) {
      ex.printStackTrace();
    }
  }

  public static void sortByLength(List<String> list, final boolean ascending) {
    Comparator<String> c = new Comparator<String>() {
      public int compare(String e1, String e2) {
        int length1 = e1.length();
        int length2 = e2.length();
        if (ascending)
          return Double.compare(length1, length2);
        else return Double.compare(length2, length1);
      }
    };
    Collections.sort(list, c);
  }
  
  /**
   * Converts an integer to a binary array with a specified max size
   * input: 11, output: [1011]
   * @param integer
   * @param size
   * @return
   */
  public static boolean[] toBinaryArray(int integer, int size) {
    boolean[] b = new boolean[size];
    String s = Integer.toBinaryString(integer);
    if (s.length() > b.length)
      s = s.substring(s.length()-b.length);
    // algorithm bug fixed kmr jan 2012
    // the 1s place is at the end of the string, so start there
    for (int i = s.length()-1; i >=0; i--)
      // the 1s element is at b[0] so start there
      b[s.length()-1-i] = (s.charAt(i) == '1');
    return b;
  }

  public static String toFileName(String s) {
    return s.replaceAll("[\\/:\\*?\"<>|\\s]+", "_");
  }

  public static File toFileOrDie(String filename) {
    if (filename == null)
      die("Could not find the file: " + filename);
    File file = new File(filename);
    if (!file.exists())
      die("Could not find the file: " + filename);
    return file;
  }

  public static String toReadableString(Collection<String> list) {
    Set<String> seeds = new TreeSet<String>();
    if (list != null)
      seeds.addAll(list);
    StringBuffer buf = new StringBuffer();
    buf.append("{");
    for (String seed : seeds) {
      if (buf.length() > 1)
        buf.append(", ");
      buf.append(seed);
    }
    buf.append("}");
    return buf.toString();
  }

  public static String toReadableDouble(Collection<Double> doubles) {
    StringBuffer buf = new StringBuffer();
    buf.append("{");
    for (Double d : doubles) {
      if (buf.length() > 1)
        buf.append(", ");
      buf.append(Helper.formatNumber(d, 5));
    }
    buf.append("}");
    return buf.toString();
  }
  
  public static String toReadableTime(Long timestamp, String format) {
    SimpleDateFormat sdf = new SimpleDateFormat(format);
    sdf.setTimeZone(TimeZone.getDefault());
    if (timestamp == null)
      timestamp = System.currentTimeMillis();
    return sdf.format(new Date(timestamp));
  }

  public static String toSeedsFileName(Collection<String> seedList) {
    Set<String> seeds = new TreeSet<String>();
    if (seedList != null)
      seeds.addAll(seedList);
    StringBuffer buf = new StringBuffer();
    for (String seed : seeds) {
      if (buf.length() > 0)
        buf.append("+");
      buf.append(seed);
    }
    return toFileName(buf.toString());
  }
  
  /**
   * Converts a String array to a Collection of Unicode
   * @param strs
   * @return
   */
  public static Set<String> toUnicode(Collection<String> strs) {
    Set<String> set = new HashSet<String>();
    if (strs == null) return set;
    for (String s : strs) {
      s = toUnicode(s);
      if (!empty(s))
        set.add(s.toLowerCase());  // added 04/21/2008
    }
    return set;
  }

  /**
   * Converts a string to unicode
   * @param s
   * @return
   */
  public static String toUnicode(String s) {
    if (s == null) return null;
    try {
      s = new String(s.getBytes(COMMON_ENCODING), UNICODE);
    } catch (UnsupportedEncodingException e) {
      log.error(e);
    }
    return s.trim();
  }

  public static URL toURL(String s) {
    try {
      return new URL(s);
    } catch (MalformedURLException e) {
      return null;
    }
  }

  public static void writeToFile(File out, String content) {
    writeToFile(out, content, UNICODE, false);
  }

  public static void writeToFile(File out, String content, boolean append) {
    writeToFile(out, content, UNICODE, append);
  }
  
  public static void writeToFile(File out, String content, String charset, boolean append) {
    if (out == null || content == null) return;
    try {
      BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(out, append), charset));
      bWriter.write(content);
      bWriter.close();
    } catch (IOException e) {
      log.error("Writing to " + out + ": " + e);
    }
  }

public static Object toReadableString(Set<EntityLiteral> contents) {
        Set<EntityLiteral> seeds = new TreeSet<EntityLiteral>();
        if (contents != null)
          seeds.addAll(contents);
        StringBuffer buf = new StringBuffer();
        buf.append("{");
        for (EntityLiteral seed : seeds) {
          if (buf.length() > 1)
            buf.append(", ");
          buf.append(seed.toString());
        }
        buf.append("}");
        return buf.toString();
      }
}

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import org.apache.log4j.Logger;
import com.rcwang.seal.asia.HyponymProvider.Hyponym;
import com.rcwang.seal.eval.EvalResult;
import com.rcwang.seal.eval.Evaluator;
import com.rcwang.seal.expand.Entity;
import com.rcwang.seal.expand.EntityList;
import com.rcwang.seal.expand.LangProvider;
import com.rcwang.seal.translation.Annotator;
import com.rcwang.seal.translation.Proximator;
import com.rcwang.seal.translation.Proximator.Proxistat;
import com.rcwang.seal.util.GlobalVar;
import com.rcwang.seal.util.Helper;

/**************************************************************************
 * Developed by Language Technologies Institute, Carnegie Mellon University
 * Written by Richard Wang (rcwang#cs,cmu,edu)
 **************************************************************************/
package com.rcwang.seal.asia;




public class NoisyInstanceExtractor {

  public static Logger log = Logger.getLogger(NoisyInstanceExtractor.class);
  
  public static final double SHRINK_POWER = 3; // [3] 1: shrink mildly, 5: shrink strongly
//  public static final int MAX_WRAPPER_SEEDS = 1000;  // [1000] consider only these top extracted instances
  public static final int NUM_RESULTS = 200;  // number of webpages per hyponym pattern (>100 requires multiple queries)
  public static final int MIN_ENTITIES = 2;  // [10] use back-off method if # of extracted instances is lower than this
//  public static final int MIN_SOURCE = 2; // filter entities having hyponym freq lower than this
  public static final int MAX_TO_PRINT = 20;  // number of extracted instances to print
  
  public static final int DEFAULT_ENGINE = -1; // 4: use Yahoo! only (due to mass amount of queries)
  public static final int DEFAULT_MIN_SNIPPET_FREQ = 2; // 2

  public static final String HIRAGANA_PATTERN = ".*\\p{InHiragana}+.*"; // reg-exp for hiragana
  public static final String DEFAULT_OUTPUT_FEATURE = "EG_PATTERN";
  
  // coefficient for each statistics
  public static final double HYPONYM_WEIGHT = (double) 1/4;
  public static final double SNIPPET_WEIGHT = (double) 1/4;
  public static final double EXCERPT_WEIGHT = (double) 1/4;
  public static final double CHUNK_DIST_WEIGHT = (double) 1/4;
  
  private int engine;
  private int confidence = 0;
  private int minSnippetFreq;

  private Evaluator evaluator;
