I am trying to classify a large-ish number of small strings (millions) into about 10 disjunct categories. Examples of classes and strings for each class include:email: foo@bar.comphone: 55, 22334455personName: John, Q., PublicorganizationName: Reuters, IBMdate: Dec., 22.10.2010nameAndEmail: Larsonlarson@gmail.com (a last name has been concatenated with an email address.)phoneAndEmail: 55larson@gmail.com (part of a phone number has been concatenated with an emal address)separator: ,, and, orother: stuff that does not fit in other categories.Carrying out classification via a set of heuristics seems tedious, so I have been experimenting with an SVM. I'm not able to get more than about 80% accuracy without doing a lot of work manually encoding features like has an ampersand, is uppercase, is mostly numeric, has a colon in the middle, etc., which sort of defeats the purpose.I'm wondering whether part of the challenge with using an SVM is that the salient features of a given string, like the '@' character, are not in a fixed position in the string, so it will not get the same feature index for each string.Does anyone have suggestions for a more appropriate approach to this task, or can anyone recommend further reading?
Appropriate algorithm for string (not document) classification?
machine learning;classification;text mining;multiclass classification
You might find it useful to treat n-grams of characters as your feature space. Then you could represent a string as a bag of substrings.  With N = 4 or greater, you would capture things like .com in emails, ##.# in dates, etc.It might also help to encode all single digits as one reserved number-only-character.An easy way to to this might be to create all the n-gram substrings for each string in your dataset, then simply treat that list of words as a document.  Then you could use term frequency or tf-idf vectors in your supervised step.For example to create the substring uni-, bi-, and tri-grams for whatever@gmail.com:a = whatever@gmail.com b = set([a[x:x+y] for y in range(0,4) for x in range(0,len(a))]) set(['', 'co', 've', 'ai', 'eve', 'r@', 'at', '.co', 'gm', 'ev', 'tev', 'er', '@gm', 'ver', '@g', 'r@g', 'ail', 'il.', 'gma', '.', 'te', 'hat', '@', 'wha', 'om', 'wh', 'er@', 'mai', 'ma', 'ha', 'l.c', 'a', 'c', 'ate', 'e', 'g', 'i', 'h', '.c', 'm', 'l', 'o', 'l.', 'r', 't', 'w', 'v', 'com', 'il'])