fastdisjointset.java

Standord Classifier实现了一个基于Java的最大熵分类器。用于模式识别

package edu.stanford.nlp.util;

import java.util.*;

/**
 *  Fast Disjoint Set
 *
 *  Disjoint forest with path compression and union-by-rank.  The set
 *  is unmodifiable except by unions.
 *
 *  @author Dan Klein
 *  @version 4/17/01
 */
public class FastDisjointSet implements DisjointSet {

  class Element {
    Element parent;
    int rank;
    Object object;

    Element(Object o) {
      object = o;
      rank = 0;
      parent = this;
    }
  }

  Map objectToElement;

  private void linkElements(Element e, Element f) {
    if (e.rank > f.rank) {
      f.parent = e;
    } else {
      e.parent = f;
      if (e.rank == f.rank)
	f.rank++;
    }
  }

  private Element findElement(Element e) {
    if (e.parent == e)
      return e;
    Element rep = findElement(e.parent);
    e.parent = rep;
    return rep;
  }

  public Object find(Object o) {
    Element e = (Element)objectToElement.get(o);
    if (e == null)
      return null;
    Element element = findElement(e);
    return element.object;
  }

  public void union(Object a, Object b) {
    Element e = (Element)objectToElement.get(a);
    Element f = (Element)objectToElement.get(b);
    if (e == null || f == null)
      return;
    if (e == f)
      return;
    linkElements(findElement(e), findElement(f));
  }

  public FastDisjointSet(Set objectSet) {
    objectToElement = new HashMap();
    for (Iterator i = objectSet.iterator(); i.hasNext();) {
      // create an element
      Object o = i.next();
      Element e = new Element(o);
      objectToElement.put(o, e);
    }
  }

}