Finding and counting equal substrings in a set of strings

Question

I'm thinking about a way of finding similar parts in Strings. I have a set of strings of varying length i.e:

• The quick brown fox jumps
• fox force five
• the bunny is much quicker than the fox
• is

First, i thought of just tokenizing the strings and count the tokens but in the case of "quick" here I also need to match "quicker".

So the output should be something like this (a mapping of tokens to the count, if the count is 1 it is omitted):

{
  "the": 3,
  "fox": 3,
  "quick": 2,
  "is": 2
}

The use case is as follows:

The user groups together Strings to categories, the goal is to make suggestions for a new string to which category it might belong. So the idea was to search all current strings in a category for keywords like this.

Answer 1

As counting identical strings is trivial, I'll address the portion of your question about making "quicker" count as "quick". As mentioned in the comments this is called stemming. Note that stemming is language-specific so you'll have to know what language your terms are in.

I will post an example for Java as you didn't specify a programming language. The lucene-analyzers-common library has stemmers in many languages. Assuming English (other languages are similar), you'd want to do something like:

SnowballProgram stemmer = new EnglishStemmer();
// for each term:
stemmer.setCurrent(term);
stemmer.stem();
String stemmedTerm = stemmer.getCurrent();
// count terms

Note that creating an EnglishStemmer is not so fast so you want to reuse the same stemmer if performance matters.

Answer 2

This solution assumes that your words will be separated by spaces. In order to consider any punctuation marks you would also att them to the string input to the temp.split() call. Obviously if you want to work on multiple strings then it would be best to move the split and loop into a method and call it for every input string that you would like to be included in the count.

Hashmap<String,Integer> wordFrequency = new Hashmap<String,Integer>();
String temp = "whatever string thing is being checked"
String[] stringList = temp.split(" ");
for (string s : stringList){
    if (!wordFrequency.keySet().contains(s)){
        wordFrequency.put(s,1);
    }
    else{
        wordFrequency.put(s,wordFrequency.get(s)++);
    }
}
System.out.println(wordFrequency.entrySet()); 
//I believe that Set has a well defined toString() implementation