attributeparser.java

一个很好的LIBSVM的JAVA源码。对于要研究和改进SVM算法的学者。可以参考。来自数据挖掘工具YALE工具包。

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2001-2004
 *      Simon Fischer, Ralf Klinkenberg, Ingo Mierswa, 
 *          Katharina Morik, Oliver Ritthoff
 *      Artificial Intelligence Unit
 *      Computer Science Department
 *      University of Dortmund
 *      44221 Dortmund,  Germany
 *  email: [e-mail]
 *  web:   http://yale.cs.uni-dortmund.de/
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as 
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version. 
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 *  USA.
 */
package edu.udo.cs.yale.example;

import edu.udo.cs.yale.generator.FeatureGenerator;
import edu.udo.cs.yale.generator.GenerationException;
import edu.udo.cs.yale.generator.ConstantGenerator;
import edu.udo.cs.yale.example.ExampleSet;
import edu.udo.cs.yale.tools.LogService;

import java.io.File;
import java.io.Reader;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Collection;
import java.util.HashSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/** Parses a file containing construction descriptions and adds the new attributes to the example set.
 *
 *  @author simon, ingo
 *  @version $Id: AttributeParser.java,v 2.11 2004/08/27 11:57:31 ingomierswa Exp $
 */
public class AttributeParser {

    /** This string separates the name from the construction description of each attribute. */
    public static final String NAME_CONSTRUCTION_DESC_SEP = "::";

    /** Maps construction descriptions of all generated attributes (including intermediate attributes)
     *  to the attributes. */
    private Map allAttributes = new HashMap();;

    /** A list of the newly generated attributes specified in the file.*/
    private List newAttributes = new LinkedList();

    /** The example table to which the attributes should be added. */
    private ExampleTable exampleTable;

    public AttributeParser(ExampleTable et) {
	this.exampleTable = et;
	for (int i = 0; i < exampleTable.getNumberOfAttributes(); i++) {
	    addAttribute(exampleTable.getAttribute(i));
	}
    }

    /** Returns all attributes that must be generated. */
    private Collection getAttributes() {
	return allAttributes.values();
    }

    /** Returns a list of all parsed attributes. */
    public List getNewAttributes() {
	return newAttributes;
    }

    /** Parses one line. */
    public Attribute parse(String string) throws GenerationException {
	String attributeName = null;
	String attributeString = null;
	int nameIndex = string.indexOf(NAME_CONSTRUCTION_DESC_SEP);
	int commaIndex = string.indexOf(",");
        // allow empty spaces at commas (only for space as NAME_CONSTRUCTION_DESC_SEP)
// 	if ((commaIndex == -1) ||
// 	    ((nameIndex != -1) && (nameIndex < commaIndex)))  {
	if (nameIndex != -1) {
	    attributeName   = string.substring(0, nameIndex).trim();
	    attributeString = string.substring(nameIndex + NAME_CONSTRUCTION_DESC_SEP.length()).trim();
	} else {
	    attributeString = string;
	}
	//System.out.println("Name: " + attributeName + ", att: " + attributeString);
	Attribute att = parseAttribute(attributeString);
	if (attributeName != null)
	    att.setName(attributeName);
	newAttributes.add(att);
	return att;
    }

    /** Parses all lines. */
    public void parseAll(Reader reader) throws IOException, GenerationException {
	BufferedReader in = new BufferedReader(reader);
	String line = null;
	while ((line = in.readLine()) != null)
	    parse(line);
	in.close();
    }


    /** Adds a new attribute to the map. If the map already contains an attribute with the same construction
     *  description, this attribute is returned. */
    private Attribute addAttribute(Attribute a) {
	Attribute oldAtt = (Attribute)allAttributes.get(a.getConstructionDescription());
	if (oldAtt != null) {
	    return oldAtt;
	} else {
	    allAttributes.put(a.getConstructionDescription(), a);
	    return a;
	}
    }

    private static int getClosingBracketIndex(String string, int startIndex) throws GenerationException {
	int openCount   = 1;
	while (true) {
	    int nextOpen    = string.indexOf("(", startIndex+1);
	    int nextClosing = string.indexOf(")", startIndex+1);
	    if (nextClosing == -1) throw new GenerationException("Malformed attribute description: mismatched parantheses");
	    if ((nextOpen != -1) && (nextOpen < nextClosing)) {
		openCount++;
		startIndex = nextOpen;
	    } else {
		openCount--;
		startIndex = nextClosing;
	    }
	    if (openCount == 0) {
		return nextClosing;
	    }
	}
    }

    private Attribute parseAttribute(String string) throws GenerationException {
	Attribute[] attributes = parseAttributes(string);
	if (attributes.length != 1) throw new GenerationException("Malformed function description: too many attributes");
	return attributes[0];
    }

    /** Recursively parses the string starting at the current position. */
    private Attribute[] parseAttributes(String string) throws GenerationException {
	List attributes = new LinkedList();

	int start = 0;

	while (start < string.length()) {
	    int leftBr = string.indexOf("(", start);
	    int comma  = string.indexOf(",", start);
	    if ((comma == -1) && (leftBr == -1)) {
		int end = string.length();
		String name = string.substring(start, end).trim();
		if (name.startsWith(ConstantGenerator.FUNCTION_NAME)) {
		    throw new GenerationException("The function name '" + ConstantGenerator.FUNCTION_NAME + 
						  "' must be used with empty arguments!");
		} else {
		    Attribute attribute = new Attribute(name);
		    attributes.add(addAttribute(attribute));
		    start = string.length();
		}
	    } else if ((leftBr == -1) ||
		       ((comma < leftBr) && (comma != -1))) {
		int end = comma;
		String name = string.substring(start, end).trim();
		if (name.startsWith(ConstantGenerator.FUNCTION_NAME)) {
		    throw new GenerationException("The function name '" + ConstantGenerator.FUNCTION_NAME + 
						  "' must be used with empty arguments!");
		} else {
		    Attribute attribute = new Attribute(name);
		    attributes.add(addAttribute(attribute));
		    start = end+1;
		}
	    } else {
		int rightBr  = getClosingBracketIndex(string, leftBr);
		String functionName = string.substring(start, leftBr).trim();
		Attribute[] arguments = parseAttributes(string.substring(leftBr+1, rightBr).trim());
		attributes.add(addAttribute(new Attribute(functionName, arguments)));
		start = string.indexOf(",", rightBr)+1;
		if (start <= 0) start = string.length();
	    }
	}	

	Attribute[] attributeArray = new Attribute[attributes.size()];
	attributes.toArray(attributeArray);
	return attributeArray;
    }

    /** Returns a collection of feature generators that can generate the attributes that are
     *  not yet generated. The attributes are then removed from the map. */
    private Collection applicableGenerators() throws GenerationException {
	Set generators = new HashSet();
	Iterator i = allAttributes.values().iterator();
	while (i.hasNext()) {
	    Attribute a = (Attribute)i.next();
	    if (exampleTable.getAttribute(a) == null) {
		if (argumentsAlreadyGenerated(a)) {
		    FeatureGenerator fg = FeatureGenerator.createGeneratorForFunction(a.getFunctionName());
		    if (fg != null) {
			Attribute[] args = a.getArguments();
			if (args != null) {
			    for (int n = 0 ; n < args.length; n++) {
				args[n] = exampleTable.getAttribute(args[n]);
			    }
			    if (fg.getInputAttributes().length != args.length) {
				throw new GenerationException(fg + " has arity " + fg.getInputAttributes().length + "!");
			    } else {
				fg.setArguments(args);
			    }
			}
			generators.add(fg);
			i.remove();
		    }
		}
	    } else {
		i.remove();
	    }
	}
	return generators;
    }

    /** Returns true if the example set already contains <tt>a</tt>. */
    private boolean argumentsAlreadyGenerated(Attribute a) {
	Attribute[] arguments = a.getArguments();
	if (arguments == null) return true;
	for (int i = 0; i < arguments.length; i++) {
	    if (exampleTable.getAttribute(arguments[i]) == null) return false; 
	}
	return true;
    }

    /** Generates new attributes as long as it is possible. */
    public void generateAll(ExampleSet exampleSet) throws GenerationException {
	List allGeneratedAttributes = new LinkedList();
	Collection generators;
	while ((generators = applicableGenerators()).size() > 0) {
	    // as a side effect, generated attributes are removed from allAttributes
	    allGeneratedAttributes.addAll(FeatureGenerator.generateAll(exampleTable, generators));
	}

	Iterator i = allAttributes.values().iterator();
	while (i.hasNext()) {
	    LogService.logMessage("Could not generate attribute "+i.next(), LogService.ERROR);
	}
	if (allAttributes.size() >  0) 
	    throw new GenerationException("Couldn't generate all attributes! Failing: " + allAttributes);

	// replace generated attribute names by user specified names and add the new
	// attributes to the example set
	if (exampleSet != null) {
	    i = newAttributes.iterator();
	    while (i.hasNext()) {
		Attribute attribute     = (Attribute)i.next();
		int realIndex           = allGeneratedAttributes.indexOf(attribute);
		Attribute realAttribute = null;
		if (realIndex != -1) {
		    realAttribute = (Attribute)allGeneratedAttributes.get(realIndex);
		    realAttribute.setName(attribute.getName());
		} else {
		    realAttribute = attribute;
		}
		if (!exampleSet.contains(realAttribute))
		    exampleSet.addAttribute(realAttribute);
	    }
	}

	// delete intermediate attributes
	allGeneratedAttributes.removeAll(newAttributes);
	LogService.logMessage("Removing "+allGeneratedAttributes.size()+" intermediate attributes.", LogService.MINIMUM);
	i = allGeneratedAttributes.iterator();
	while (i.hasNext()) {
	    exampleTable.removeAttribute((Attribute)i.next());
	}
    }
}