Monday, January 25, 2010

Tokenizer / tag extraction method

I was in need for a method to extract a list of tokens from a given text.
The list should not contain stopwords like "the, a, on, of, etc" or punctuation marks and needs to be sorted by most used token.
This is what i came up with:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public static class Tokenizer
{
private class Token
{
public string Value { get; set; }
public int Count { get; set; }
}

/// <summary>
/// Tokenize a string and return tokens as list sorted by most occurances
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public static List<string> TokenizeString(string input)
{
string cleanText = String.Empty;

// Replace all non-alphanumeric characters with a space
new List<Char>(input.ToCharArray()).ForEach(c =>
cleanText += (Char.IsLetterOrDigit(c) || Char.IsWhiteSpace(c))
? c.ToString()
: " ");

// We want all tokens in lowercase
cleanText = cleanText.ToLower();

// Split input string on whitespaces
List<string> tokens = cleanText.Split(' ').ToList<string>();

// Remove stop words, whitespace and tokens shorter than 3 chars from token list
// NOTE: Configuration.StopWords is of type List<string> and contains the stopwords (loaded from a configuration file)
Configuration.StopWords.ForEach(stopWord =>
tokens.RemoveAll(token =>
token == stopWord || String.IsNullOrWhiteSpace(token) || token.Length < 3));

// Copy the tokens to a new list
// Count how many times each token occurs and add it only once, so we have no double entries
List<Token> tokenList = new List<Token>();
tokens.ForEach(delegate(string t)
{
// Continue only if token does not exist in tokenList
if (!tokenList.Exists(e => e.Value == t))
{
// Add token to list, including the count of how many times it occurred
tokenList.Add(new Token { Value = t, Count = tokens.Count<string>(c => c == t) });
}
});

// Sort the list on occurrance count
tokenList.Sort(delegate(Token a, Token b)
{
return b.Count.CompareTo(a.Count);
});

// At this point we have a list with unique tokens, sorted by most occurrances
// We convert it back to a string list and return it
tokens = new List<string>();
tokenList.ForEach(t => tokens.Add(t.Value));

return tokens;
}
}

Here is an example of it's usage:

// Dummy input string
string input = "Google-oprichters Larry Page en Sergey Brin willen af van hun gedeelde meerderheid aan aandelen van het bedrijf. Uit een bericht van de Amerikaanse beurswaakhond SEC willen de twee de komende vijf jaar tien miljoen van hun Google aandelen verkopen. Brin en Page, nu nog voor 59 procent eigenaar, bezitten dan nog maar 48 procent van de aandelen. Met de huidige koers levert dat hun in totaal 5,5 miljard euro op. De Google oprichters kiezen bewust voor een geleidelijke afbouw om de aandelen op de beurs niet teveel onder de druk te zetten. Ondanks de aandelenverkoop zullen Brin en Page nog aardig hun stempel op het beleid kunnen drukken. Naast henzelf zijn voor besluiten slechts krap twee procent van de overige aandeelhouders nodig.";

List<string> tokens = Tokenizer.TokenizeString(input);

This will result in 59 tokens with the first 5 being:

aandelen
google
brin
nog
procent


The list of stopwords that was loaded in Configuration.StopWords is: aan,naar,dat,nu,de,om,den,onder,der,ons,des,onze,deze,ook,die,op,dit,over,door,een,te,enige,tegen,enkele,ten,enz,ter,etc,tot,haar,uit,het,hierin,hoe,vanaf,hun,ik,vol,inzake,voor,is,wat,je,wie,na,zijn,u,uw,met,naar,jij,hij,zij,zonder,en,van,amp

Because i already had a list with dutch stopwords loaded, i have used a dutch text in the example (sorry english readers :)

/Ruud