Product Naming Algorithm

Question

I'm working on a new web site than can generate company/product names. Someone can come to the site and type in a bunch of words that you may want included in the meaning of the product somehow.

i.e. You go have just invented a robot that cleans an oil spill. You input a list of words: robot, oil, spill, autonomous, intelligent, etc. The code will take the words, find synonyms, prefixes and suffixes for all those words and try to mash them together in a cool manner.

Oil would yield the synonym petroleum and the prefix petro. Mashing that together with robot would give "Petrobot." Or, for a new version of of an alarm clock, the list: "intelligent, alarm, clock, aware, connected" could yield the product name "Cognizant Clock."

The site would present a list of mashed together words and you can pick from the best names.

My question is this. Any ideas on how to generate these mashed together words? Right now, I'm going to search for synonyms, prefixes and suffixes and store them in an array. Then I'm going to search for common letters between the words and overlap them as much as possible. i.e. Direct TV becomes DirecTV. This brute force search seems a bit inelegant.

Are there any other methods of generating product names you can think of or an easier approach to the one I suggested?

Just wanted to see if there was another method people can think of. Of course this site will be free and open and I'll link to this topic on the about page of the site, so please don't think of this post as me profiting off the community.

Answer 1

I would store all prefixes of the words in a multi-hashmaps. To check if one word starts with "bot" you'd only have to do one lookup in the prefix-map.

After that it's just a breadth-first traversal of the "graph" of "connectable" words.

Something like this:

import java.util.*;

public class WordMasher {

    int maxWordLen = 0;
    Set<String> words = new HashSet<String>();
    HashMap<String, Set<String>> prefixes = new HashMap<String, Set<String>>();

    public WordMasher(String... words) {
        for (String word : words) {
            this.words.add(word);
            maxWordLen = Math.max(maxWordLen, word.length());
            for (int i = 0; i < word.length() - 1; i++)
                putPrefix(word.substring(0, i), word);
        }
    }


    private void putPrefix(String pref, String word) {
        getPrefixSet(pref).add(word);
    }


    public Set<String> getMashes() {

        Set<String> mashes = new HashSet<String>();
        for (String word : words) {
            Set<String> newWordsLeft = new HashSet<String>(words);
            newWordsLeft.remove(word);
            mashes.addAll(getMashes(word, newWordsLeft));
        }

        return mashes;
    }

    private Set<String> getPrefixSet(String prefix) {
        if (!prefixes.containsKey(prefix))
            prefixes.put(prefix, new HashSet<String>());
        return prefixes.get(prefix);
    }


    private Set<String> getMashes(String prefix, Set<String> wordsLeft) {

        Set<String> mashes = new HashSet<String>();

        int prefLen = prefix.length();

        for (int n = Math.min(prefLen, maxWordLen); n >= 1; n--) {

            String toMatch = prefix.substring(prefLen - n, prefLen);
            List<String> alts = new ArrayList<String>(getPrefixSet(toMatch));
            alts.retainAll(wordsLeft);
            for (String alt : alts) {

                String newPrefix = prefix + alt.substring(n);
                mashes.add(newPrefix);

                Set<String> newWordsLeft = new HashSet<String>(wordsLeft);
                newWordsLeft.remove(alt);
                for (String tail : getMashes(newPrefix, newWordsLeft))
                    mashes.add(tail);
            }
        }
        return mashes;
    }


    public static void printProductNames(String... words) {
        System.out.println("Products for " + Arrays.toString(words) + ":");
        for (String product : new WordMasher(words).getMashes())
            System.out.println("    " + product);
        System.out.println();
    }

    public static void main(String[] args) {

        printProductNames("robot", "liquid", "oil", "cleaner", "spill", "turbo" );
        printProductNames("world", "domination", "yellow",
                "monkey", "donkey", "banana");
    }
}

Prints:

Products for [robot, liquid, oil, cleaner, spill, turbo]:
    turboiliquid
    oiliquid
    spilliquid
    cleanerobot
    roboturbo
    cleaneroboturboil
    roboturboiliquid
    cleaneroboturbo
    cleaneroboturboiliquid
    turboil
    roboturboil

Products for [world, domination, yellow, monkey, donkey, banana]:
    monkeyellow
    yelloworldonkey
    donkeyelloworld
    donkeyelloworldomination
    worldonkey
    monkeyelloworldomination
    yelloworldomination
    worldomination
    monkeyelloworldonkey
    yelloworld
    monkeyelloworld
    donkeyellow
    worldonkeyellow

If speed is an issue here, you may want to change the Strings to StringBuilders.

Answer 2

A suffix tree may be the data structure you are looking for to support your various operations efficiently:- http://en.wikipedia.org/wiki/Suffix_tree