11
\$\begingroup\$

I recently had a programming challenge, which was to create the N grams. The description is as follows:

Trigram analysis is very simple. Look at each set of three adjacent words in a document. Use the first two words of the set as a key, and remember the fact that the third word followed that key. Once you’ve finished, you know the list of individual words that can follow each two word sequence in the document. For example, given the input:

I wish I may I wish I might

You might generate:

"I wish" => ["I", "I"]
"wish I" => ["may", "might"]
"may I"  => ["wish"]
"I may"  => ["I"]

This says that the words "I wish" are twice followed by the word "I", the words "wish I" are followed once by "may" and once by "might" and so on. To generate new text from this analysis, choose an arbitrary word pair as a starting point. Use these to look up a random next word (using the table above) and append this new word to the text so far. This now gives you a new word pair at the end of the text, so look up a potential next word based on these. Add this to the list, and so on. In the previous example, we could start with "I may". The only possible next word is "I", so now we have:

I may I

The last two words are "may I", so the next word is "wish". We then look up "I wish", and find our choice is constrained to another "I".

I may I wish I

Now we look up "wish I", and find we have a choice. Let’s choose "may".

I may I wish I may

Now we’re back where we started from, with "I may." Following the same sequence, but choosing "might" this time, we get:

I may I wish I may I wish I might

At this point we stop, as no sequence starts "I might." Given a book, so the resulting output can be surprising.

I've implemented this idea in Java with generic Ngrams, whose value should be > 1. I want to know whether I can improve the efficiency of my code like runtime or space complexity.

public class Ngrams {

    private  String words[];  // List of words in Supplied String
    private  HashMap<String ,List<String> > nGramsMap; // Mapping of the Ngrams
    private int n; // Value for NGram

    Ngrams(String text, int n){

         if(n<1 || text==null || text.length()==0) 
            throw new IllegalArgumentException("Check the input Parameters : String Should not be null or empty and Ngram value should be > 1");

        words=text.split(" ");
        nGramsMap=new HashMap<String ,List<String>>();
        this.n=n;
    }

    public Map<String ,List<String>>  generateNgrams( ){

        // Filling the HashMap based on N value and using WOrds Array

        /*Look at each set of N adjacent words in a document. 
         Use the first N-1 words of the set as a key, 
        and remember the fact that the nth word followed that key. 
        Once you’ve finished, you know the list of individual words 
        that can follow each N-1 word sequence in the document. 
*/
        for(int i=0; i <= words.length-n ;i++  ){
                    StringBuilder sb=new StringBuilder();

                    int j=0;

                    while(j < n-1){
                        sb.append(words[i+j].trim());

                        j++ ;

                        if(j<n-1) sb.append(" ");
                    }

                    String key=sb.toString();

                    if(!nGramsMap.containsKey(key)){

                        ArrayList<String> list=new ArrayList<>();
                        list.add(words[i+j]);
                        nGramsMap.put(key, list);

                    }else{

                        List<String> list=nGramsMap.get(key);
                        list.add(words[i+j]);
                    }


//                  System.out.println("Key:  "+key+"       Value :   "+words[i+j]);
        }

        return nGramsMap;


    }

    public String  getNGramsText( ){

        /*          
        To generate new text from this analysis, 
        choose an arbitrary word pair as a starting point. 
        Use these to look up a random next word (using the table above)
        and append this new word to the text so far. 
        This now gives you a new word pair at the end of the text, 
        so look up a potential next word based on these. 
        Add this to the list, and so on.
        */
                    if(nGramsMap.size()==0)
                    generateNgrams( );

                    StringBuilder result= new StringBuilder();

                    Random gen=new Random();

                    int st= gen.nextInt(words.length-n);  //arbitrary word pair

                    StringBuilder startSb=new StringBuilder();

                    for(int i=0;i< n-1;i++){
                            startSb.append(words[st+i]);
                            if(i+1< n-1)startSb.append(" ");
                    }

                    String start= startSb.toString();

                    result.append(start+" ");

                    while(true){


                        int size=nGramsMap.get(start).size();
                        String next;
                        if(size>1){
                            st=gen.nextInt(size-1);
                            next=nGramsMap.get(start).remove(st);
                        }
                        else{
                            st=0;
                            next=nGramsMap.get(start).get(st);
                        }


                        String start_split[]=start.split(" ");
                        String nextKey;
                        if(start_split.length>1) {
                            nextKey=start.substring(start_split[0].length()+1);
                            start= nextKey+" "+next;
                        }
                        else {
                            start=next;
                        }

                        result.append(next);  //append this new word to the text so far

                        if(nGramsMap.containsKey(start)) result.append(" ");
                        else break;
        }



    return result.toString();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Can you include a main() method so that people can copy and paste this code, and immediately run it? It would help a lot in knowing whether I can improve the efficiency of the code (run-time or space complexity). \$\endgroup\$ – syb0rg Jan 4 '14 at 22:51
5
\$\begingroup\$

If text is null, you throw an IllegalArgumentException. It should throw a NullPointerException.

if (text == null) throw new NullPointerException("Check the input parameters: String should not be null");
if(n<1 || text.length()==0)  throw new IllegalArgumentException("Check the input parameters : String should not  empty and Ngram value should be > 1");

If the user is inputting the text directly I don't believe text can be null (I'm not completely sure on this), you can simplify your if condition test down a bit using the String method .equals().

if (n<1 || text.equals(""))

I included the upper example in the final code.


I am usually in support of using whitespace in programming. However, in this case I think you have a lot of superfluous whitespace in your program. Especially in between braces.

// There are only 4 real lines of code here, 5 if you include the comment.
// With your spacing scheme you have 10 (comment included).

                    }


//                  System.out.println("Key:  "+key+"       Value :   "+words[i+j]);
        }

        return nGramsMap;


    }

You comment what the variable n is, instead of giving it a more helpful name to begin with. It's good that you had the comment though, many people don't comment what obscure variables mean.

private int value; // Value for NGram

I don't see the imports you need. I assume you have all of these somewhere else in your program.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

Other than that, the program looks pretty good. You didn't include main(), so I couldn't do too much refining without making sure I wasn't breaking the program.

Final code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
public class Test
{

    private String words[]; // List of words in Supplied String
    private HashMap<String, List<String>> nGramsMap; // Mapping of the Ngrams
    private int value; // Value for NGram

    Test(String text, int n)
    {
        if (text == null) throw new NullPointerException("Check the input parameters: String should not be null");
        if(n<1 || text.length()==0)  throw new IllegalArgumentException("Check the input parameters : String should not  empty and Ngram value should be > 1");

        words = text.split(" ");
        nGramsMap = new HashMap<String, List<String>>();
        this.value = n;
    }

    public Map<String, List<String>> generateNgrams()
    {
        // Filling the HashMap based on N value and using WOrds Array

        /*
         * Look at each set of N adjacent words in a document. Use the first N-1 words of the set as a key, and remember the fact that the nth word
         * followed that key. Once you’ve finished, you know the list of individual words that can follow each N-1 word sequence in the document.
         */
        for (int i = 0; i <= words.length - value; i++)
        {
            StringBuilder sb = new StringBuilder();
            int j = 0;

            while (j < value - 1)
            {
                sb.append(words[i + j].trim());
                j++;
                if (j < value - 1) sb.append(" ");
            }

            String key = sb.toString();

            if (!nGramsMap.containsKey(key))
            {

                ArrayList<String> list = new ArrayList<>();
                list.add(words[i + j]);
                nGramsMap.put(key, list);

            }
            else
            {
                List<String> list = nGramsMap.get(key);
                list.add(words[i + j]);
            }
            // System.out.println("Key:  "+key+"       Value :   "+words[i+j]);
        }
        return nGramsMap;
    }

    public String getNGramsText()
    {
        /*
         * To generate new text from this analysis, choose an arbitrary word pair as a starting point. Use these to look up a random next word (using
         * the table above) and append this new word to the text so far. This now gives you a new word pair at the end of the text, so look up a
         * potential next word based on these. Add this to the list, and so on.
         */
        if (nGramsMap.size() == 0) generateNgrams();
        StringBuilder result = new StringBuilder();
        Random gen = new Random();
        int st = gen.nextInt(words.length - value); // arbitrary word pair
        StringBuilder startSb = new StringBuilder();

        for (int i = 0; i < value - 1; i++)
        {
            startSb.append(words[st + i]);
            if (i + 1 < value - 1) startSb.append(" ");
        }

        String start = startSb.toString();

        result.append(start + " ");

        while (true)
        {

            int size = nGramsMap.get(start).size();
            String next;
            if (size > 1)
            {
                st = gen.nextInt(size - 1);
                next = nGramsMap.get(start).remove(st);
            }
            else
            {
                st = 0;
                next = nGramsMap.get(start).get(st);
            }

            String start_split[] = start.split(" ");
            String nextKey;
            if (start_split.length > 1)
            {
                nextKey = start.substring(start_split[0].length() + 1);
                start = nextKey + " " + next;
            }
            else start = next;

            result.append(next); // append this new word to the text so far

            if (nGramsMap.containsKey(start)) result.append(" ");
            else break;
        }
        return result.toString();
    }
}
\$\endgroup\$
  • \$\begingroup\$ I would either keep the IllegalArgumentException or let it trigger NullPointerException naturally. Throwing NullPointerException deliberately is weird, in my opinion. \$\endgroup\$ – 200_success Jan 5 '14 at 10:07
  • 1
    \$\begingroup\$ IAE vs NPE and the debate goes on...! :P \$\endgroup\$ – Anirban Nag 'tintinmj' Jan 5 '14 at 10:34
  • \$\begingroup\$ Also, I think n is actually clearer than value. It is, after all, an n-gram, so n is self-documenting in this domain. \$\endgroup\$ – 200_success Jan 5 '14 at 12:21
2
\$\begingroup\$

I'm not a linguistics expert, but I believe n <= 1 should be illegal, because I have a hard time seeing how the n == 1 case should behave.

I think that an n-gram would be better represented as an n-level trie, as evidenced by all the work necessary to split and concatenate words to form the keys. Nevertheless, I'll continue this answer using maps of concatenated words to lists of words, since it would be hard to write a review incorporating such a radical change.

My biggest complaint is that getNGramsText() cheats by using the words array. Isn't the point of the exercise to reconstruct the text using only the n-gram data? To enforce discipline, I would recommend an interface like the following:

public class NGramAnalyzer {
    public NGramAnalyzer(int n) { ... }

    public Map<String, List<String>> fromText(String text) { ... }

    public static String toText(Map<String, List<String>> nGrams) { ... }
}

To arbitrarily pick the initial words for the reconstructed text, just use any key of the map. Also, I believe that the code to generate nextKey can be simplified to:

String nextKey = start.substring(1 + start.indexOf(" ")) + " " + next;

I recommend a few changes to generateNgrams(), noted in comments:

public Map<String, List<String>> fromText(String text) {
    // Use .isEmpty() instead of .length() == 0
    if (text == null || text.isEmpty()) {
        throw new IllegalArgumentException("null or empty text");
    }
    String[] words = text.split(" ");
    Map<String, List<String>> nGramsMap = new HashMap<String, List<String>>();

    for(int i = 0; i <= words.length-n ; i++) {
        // Renamed sb to give it purpose.  Use a for-loop.
        // Removed the special case within the loop.
        StringBuilder keyBuilder = new StringBuilder(words[i].trim());
        for (int j = 1; j < n - 1; j++) {
            keyBuilder.append(' ').append(words[i + j].trim());
        }
        String key = keyBuilder.toString();

        // Calling .containsKey() is redundant work; just call .get().
        // (The only reason to call .containsKey() would be to check for
        // an entry with a null value, which wouldn't be the case for us.)
        List<String> list = nGramsMap.get(key);
        if (list == null) {
            nGramsMap.put(key, list = new ArrayList<String>());
        }
        // Added benefit: we can write the following line just once.
        list.add(words[i + n - 1]);
    }
    return nGramsMap;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.