martes, 8 de julio de 2008

WordFrequency (I): Obtener un listado de las palabras más frecuentes en un conjunto de webs

Introducción

Vamos a desarrollar paso a paso un pequeño programa cuya finalidad es extraer la lista de las palabras más usadas en un listado de páginas web.

La idea es extraer este listado, para enfocarnos a la hora de estudiar vocabulario de un nuevo idioma. O incluso sólo por curiosidad: lo podemos utilizar con un texto nuestro, a ver si repetimos una palabra demasiadas veces.

El lenguaje elegido es java versión 6.0, dado su carácter multiplataforma y su capacidad de ser ejecutado desde una página web como un applet, con lo que no es necesario descargar ni instalar nada para ejecutarlo.

El código fuente estará disponible con licencia GPL, lo que quiere decir que puedes utilizar este código donde quieras y como quieras, siempre que mantengas la referencia al autor original, y el programa que hagas con este código sea también GPL (también distribuyas el código fuente).

Para el desarrollo estoy utilizando el JDK de Sun, y el editor Eclipse, muy cómodo y potente. Todo software libre o gratuíto.

En lugar de mostrar todo el código fuente, vamos a mostrar sólo las partes más interesantes del programa: para cada funcionalidad principal, cómo se ha implementado.

Descargar una página web via http

Por medio de un objeto de la clase java.net.URLConnection obtendremos un stream que podremos utilizar para leer datos de forma estándar, por ejemplo llamando a br.readLine()

URL url = new URL(urlstring);
URLConnection connection = url.openConnection();
BufferedReader br = new BufferedReader(new InputStreamReader(connection.getInputStream()));

Parsear un documento html

Por medio de la clase javax.swing.text.html.HTMLEditorKit parsearemos el documento html en un objeto de tipo javax.swing.text.html.HTMLDocument, que nos permitirá navegar por sus elementos. En este caso seleccionaremos los elementos de tipo HTML.Tag.CONTENT, que es un alias que representa cualquier elemento html que contenga texto. Otros elementos interesantes pueden ser HTML.Tag.A, HTML.Tag.IMG, HTML.Tag.H1...

HTMLEditorKit htmlKit = new HTMLEditorKit();
HTMLDocument htmlDoc = (HTMLDocument) htmlKit.createDefaultDocument();
HTMLEditorKit.Parser parser = new ParserDelegator();
HTMLEditorKit.ParserCallback callback = htmlDoc.getReader(0);
parser.parse(br, callback, true);

// Iterate over all the text tags and insert an entry into the hash map or increase its number of occurrences 

for (HTMLDocument.Iterator iterator = htmlDoc.getIterator(HTML.Tag.CONTENT); iterator.isValid(); iterator.next())
{
    int startOffset = iterator.getStartOffset();
    int endOffset = iterator.getEndOffset();
    int length = endOffset - startOffset;
    String text = htmlDoc.getText(startOffset, length).trim();
}

Con este código, para cada elemento encontrado, habremos almacenado en la variable text el texto que contiene.

Esta clase HTMLDocument también permite acceder a los atributos de cada elemento, como el atributo src de un elemento A. Esto puede ser particularmente útil si queremos por ejemplo extraer las páginas web enlazadas desde una página web dada, o las imágenes que contiene:

for (HTMLDocument.Iterator iterator = htmlDoc.getIterator(HTML.Tag.A); iterator.isValid(); iterator.next())
{
    Object href = iterator.getAttributes().getAttribute( HTML.Attribute.HREF );
 
    if (href != null) // the 'A' element contains the 'href' attribute
    {
        System.out.println("Link found: \"" + href.toString() + "\"");
    }
}

Calcular la frecuencia de aparición de cada palabra

Creamos un objeto de tipo HashMap, que contiene pares "llave-valor", y cada llave es única; esto es, si hacemos hash.put("a", valor) y "a" ya existe, estamos modificando la anterior entrada de "a". La búsqueda (hash.get()) en esta estructura es muy rápida.

HashMap hash = new HashMap();

Para cada palabra encontrada, incrementaremos su valor asociado, que nos indicará el número de veces que esta palabra ha aparecido en la entrada.

// we insert or update the entry in the hashmap by 1
Integer in = (Integer)hash.get(palabra);
if (in == null) in = Integer.valueOf(1);
else in = Integer.valueOf(in.intValue() + 1);

hash.put(palabra, in);

Una vez hemos recopilado la frecuencia de aparición de cada palabra en esta estructura, podemos, por ejemplo, ordenar estos datos, insertándolos en una colección de tipo java.util.TreeSet y su especialmente útil iterador descendingIterator, que recorre el árbol en orden inverso. También utilizamos esta ordenación para seleccionar los 'n' elementos con valor más alto

// generate an ordered set with the most frequent words (at most maxRecords)
TreeSet orderedSet = new TreeSet();
 
Set s = hash.entrySet();
iter = s.iterator();
while (iter.hasNext())
{
    Map.Entry act = (Map.Entry)iter.next();
    orderedSet.add(new DataRecord((Integer)act.getValue(), (String)act.getKey()));
}
 
iter = orderedSet.descendingIterator();
DataRecord min = null;
i = maxRecords;
while ( iter.hasNext() && (i-- > 0) )
{
    min = (DataRecord)iter.next();
}
if (iter.hasNext())
    min = (DataRecord)iter.next();
 
return orderedSet.descendingSet().headSet(min, true);

Y ya sólo nos queda mostrar o almacenar los datos obtenidos.

Material

La implementación del programa comentado en este artículo se puede descargar bajo licencia GPLv3. El código comentado se encuentra dentro de la clase WordFrequencyCalculator.

Download

Y eso es todo por el momento. Cualquier duda o sugerencia que tengáis, dejadla en los comentarios. Y si realizáis cualquier mejora interesante al código, u os es útil de cualquier otra forma, por favor comentádmelo, por curiosidad.

No hay comentarios: