diff --git a/java/src/com/android/inputmethod/latin/BinaryDictionary.java b/java/src/com/android/inputmethod/latin/BinaryDictionary.java
index b8cf3f8..e7ab02a 100644
--- a/java/src/com/android/inputmethod/latin/BinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/BinaryDictionary.java
@@ -359,14 +359,16 @@
     }
 
     @UsedForTesting
-    public boolean isValidBigram(final String word0, final String word1) {
-        return getBigramProbability(word0, word1) != NOT_A_PROBABILITY;
+    public boolean isValidNgram(final PrevWordsInfo prevWordsInfo, final String word) {
+        return getNgramProbability(prevWordsInfo, word) != NOT_A_PROBABILITY;
     }
 
-    public int getBigramProbability(final String word0, final String word1) {
-        if (TextUtils.isEmpty(word0) || TextUtils.isEmpty(word1)) return NOT_A_PROBABILITY;
-        final int[] codePoints0 = StringUtils.toCodePointArray(word0);
-        final int[] codePoints1 = StringUtils.toCodePointArray(word1);
+    public int getNgramProbability(final PrevWordsInfo prevWordsInfo, final String word) {
+        if (TextUtils.isEmpty(prevWordsInfo.mPrevWord) || TextUtils.isEmpty(word)) {
+            return NOT_A_PROBABILITY;
+        }
+        final int[] codePoints0 = StringUtils.toCodePointArray(prevWordsInfo.mPrevWord);
+        final int[] codePoints1 = StringUtils.toCodePointArray(word);
         return getBigramProbabilityNative(mNativeDict, codePoints0, codePoints1);
     }
 
@@ -417,7 +419,7 @@
     }
 
     // Add a unigram entry to binary dictionary with unigram attributes in native code.
-    public void addUnigramWord(final String word, final int probability,
+    public void addUnigramEntry(final String word, final int probability,
             final String shortcutTarget, final int shortcutProbability, final boolean isNotAWord,
             final boolean isBlacklisted, final int timestamp) {
         if (TextUtils.isEmpty(word)) {
@@ -431,25 +433,26 @@
         mHasUpdated = true;
     }
 
-    // Add a bigram entry to binary dictionary with timestamp in native code.
-    public void addBigramWords(final String word0, final String word1, final int probability,
+    // Add an n-gram entry to the binary dictionary with timestamp in native code.
+    public void addNgramEntry(final PrevWordsInfo prevWordsInfo, final String word,
+            final int probability,
             final int timestamp) {
-        if (TextUtils.isEmpty(word0) || TextUtils.isEmpty(word1)) {
+        if (TextUtils.isEmpty(prevWordsInfo.mPrevWord) || TextUtils.isEmpty(word)) {
             return;
         }
-        final int[] codePoints0 = StringUtils.toCodePointArray(word0);
-        final int[] codePoints1 = StringUtils.toCodePointArray(word1);
+        final int[] codePoints0 = StringUtils.toCodePointArray(prevWordsInfo.mPrevWord);
+        final int[] codePoints1 = StringUtils.toCodePointArray(word);
         addBigramWordsNative(mNativeDict, codePoints0, codePoints1, probability, timestamp);
         mHasUpdated = true;
     }
 
-    // Remove a bigram entry form binary dictionary in native code.
-    public void removeBigramWords(final String word0, final String word1) {
-        if (TextUtils.isEmpty(word0) || TextUtils.isEmpty(word1)) {
+    // Remove an n-gram entry from the binary dictionary in native code.
+    public void removeNgramEntry(final PrevWordsInfo prevWordsInfo, final String word) {
+        if (TextUtils.isEmpty(prevWordsInfo.mPrevWord) || TextUtils.isEmpty(word)) {
             return;
         }
-        final int[] codePoints0 = StringUtils.toCodePointArray(word0);
-        final int[] codePoints1 = StringUtils.toCodePointArray(word1);
+        final int[] codePoints0 = StringUtils.toCodePointArray(prevWordsInfo.mPrevWord);
+        final int[] codePoints1 = StringUtils.toCodePointArray(word);
         removeBigramWordsNative(mNativeDict, codePoints0, codePoints1);
         mHasUpdated = true;
     }
diff --git a/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java
index e04fcda..3fb76b1 100644
--- a/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java
@@ -142,7 +142,7 @@
                 Log.d(TAG, "loadAccountVocabulary: " + word);
             }
             runGCIfRequiredLocked(true /* mindsBlockByGC */);
-            addWordDynamicallyLocked(word, FREQUENCY_FOR_CONTACTS, null /* shortcut */,
+            addUnigramLocked(word, FREQUENCY_FOR_CONTACTS, null /* shortcut */,
                     0 /* shortcutFreq */, false /* isNotAWord */, false /* isBlacklisted */,
                     BinaryDictionary.NOT_A_VALID_TIMESTAMP);
         }
@@ -224,7 +224,7 @@
      */
     private void addNameLocked(final String name) {
         int len = StringUtils.codePointCount(name);
-        String prevWord = null;
+        PrevWordsInfo prevWordsInfo = new PrevWordsInfo(null);
         // TODO: Better tokenization for non-Latin writing systems
         for (int i = 0; i < len; i++) {
             if (Character.isLetter(name.codePointAt(i))) {
@@ -239,19 +239,19 @@
                 final int wordLen = StringUtils.codePointCount(word);
                 if (wordLen < MAX_WORD_LENGTH && wordLen > 1) {
                     if (DEBUG) {
-                        Log.d(TAG, "addName " + name + ", " + word + ", " + prevWord);
+                        Log.d(TAG, "addName " + name + ", " + word + ", "
+                                + prevWordsInfo.mPrevWord);
                     }
                     runGCIfRequiredLocked(true /* mindsBlockByGC */);
-                    addWordDynamicallyLocked(word, FREQUENCY_FOR_CONTACTS,
+                    addUnigramLocked(word, FREQUENCY_FOR_CONTACTS,
                             null /* shortcut */, 0 /* shortcutFreq */, false /* isNotAWord */,
                             false /* isBlacklisted */, BinaryDictionary.NOT_A_VALID_TIMESTAMP);
-                    if (!TextUtils.isEmpty(prevWord) && mUseFirstLastBigrams) {
+                    if (!TextUtils.isEmpty(prevWordsInfo.mPrevWord) && mUseFirstLastBigrams) {
                         runGCIfRequiredLocked(true /* mindsBlockByGC */);
-                        addBigramDynamicallyLocked(prevWord, word,
-                                FREQUENCY_FOR_CONTACTS_BIGRAM,
+                        addNgramEntryLocked(prevWordsInfo, word, FREQUENCY_FOR_CONTACTS_BIGRAM,
                                 BinaryDictionary.NOT_A_VALID_TIMESTAMP);
                     }
-                    prevWord = word;
+                    prevWordsInfo = new PrevWordsInfo(word);
                 }
             }
         }
diff --git a/java/src/com/android/inputmethod/latin/DictionaryFacilitatorForSuggest.java b/java/src/com/android/inputmethod/latin/DictionaryFacilitatorForSuggest.java
index 14c8bb6..301b832 100644
--- a/java/src/com/android/inputmethod/latin/DictionaryFacilitatorForSuggest.java
+++ b/java/src/com/android/inputmethod/latin/DictionaryFacilitatorForSuggest.java
@@ -370,22 +370,23 @@
     }
 
     public void addToUserHistory(final String suggestion, final boolean wasAutoCapitalized,
-            final String previousWord, final int timeStampInSeconds,
+            final PrevWordsInfo prevWordsInfo, final int timeStampInSeconds,
             final boolean blockPotentiallyOffensive) {
         final Dictionaries dictionaries = mDictionaries;
         final String[] words = suggestion.split(Constants.WORD_SEPARATOR);
         for (int i = 0; i < words.length; i++) {
             final String currentWord = words[i];
-            final String prevWord = (i == 0) ? previousWord : words[i - 1];
+            final PrevWordsInfo prevWordsInfoForCurrentWord =
+                    (i == 0) ? prevWordsInfo : new PrevWordsInfo(words[i - 1]);
             final boolean wasCurrentWordAutoCapitalized = (i == 0) ? wasAutoCapitalized : false;
-            addWordToUserHistory(dictionaries, prevWord, currentWord,
+            addWordToUserHistory(dictionaries, prevWordsInfoForCurrentWord, currentWord,
                     wasCurrentWordAutoCapitalized, timeStampInSeconds, blockPotentiallyOffensive);
         }
     }
 
-    private void addWordToUserHistory(final Dictionaries dictionaries, final String prevWord,
-            final String word, final boolean wasAutoCapitalized, final int timeStampInSeconds,
-            final boolean blockPotentiallyOffensive) {
+    private void addWordToUserHistory(final Dictionaries dictionaries,
+            final PrevWordsInfo prevWordsInfo, final String word, final boolean wasAutoCapitalized,
+            final int timeStampInSeconds, final boolean blockPotentiallyOffensive) {
         final ExpandableBinaryDictionary userHistoryDictionary =
                 dictionaries.getSubDict(Dictionary.TYPE_USER_HISTORY);
         if (userHistoryDictionary == null) {
@@ -430,15 +431,16 @@
         // We demote unrecognized words (frequency < 0, below) by specifying them as "invalid".
         // We don't add words with 0-frequency (assuming they would be profanity etc.).
         final boolean isValid = maxFreq > 0;
-        UserHistoryDictionary.addToDictionary(userHistoryDictionary, prevWord, secondWord,
+        UserHistoryDictionary.addToDictionary(userHistoryDictionary, prevWordsInfo, secondWord,
                 isValid, timeStampInSeconds);
     }
 
-    public void cancelAddingUserHistory(final String previousWord, final String committedWord) {
+    public void cancelAddingUserHistory(final PrevWordsInfo prevWordsInfo,
+            final String committedWord) {
         final ExpandableBinaryDictionary userHistoryDictionary =
                 mDictionaries.getSubDict(Dictionary.TYPE_USER_HISTORY);
         if (userHistoryDictionary != null) {
-            userHistoryDictionary.removeBigramDynamically(previousWord, committedWord);
+            userHistoryDictionary.removeNgramDynamically(prevWordsInfo, committedWord);
         }
     }
 
diff --git a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
index 629f3fd..d67253c 100644
--- a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
@@ -269,9 +269,9 @@
     }
 
     /**
-     * Dynamically adds a word unigram to the dictionary. May overwrite an existing entry.
+     * Adds unigram information of a word to the dictionary. May overwrite an existing entry.
      */
-    public void addWordDynamically(final String word, final int frequency,
+    public void addUnigramEntry(final String word, final int frequency,
             final String shortcutTarget, final int shortcutFreq, final boolean isNotAWord,
             final boolean isBlacklisted, final int timestamp) {
         reloadDictionaryIfRequired();
@@ -282,23 +282,23 @@
                     return;
                 }
                 runGCIfRequiredLocked(true /* mindsBlockByGC */);
-                addWordDynamicallyLocked(word, frequency, shortcutTarget, shortcutFreq,
+                addUnigramLocked(word, frequency, shortcutTarget, shortcutFreq,
                         isNotAWord, isBlacklisted, timestamp);
             }
         });
     }
 
-    protected void addWordDynamicallyLocked(final String word, final int frequency,
+    protected void addUnigramLocked(final String word, final int frequency,
             final String shortcutTarget, final int shortcutFreq, final boolean isNotAWord,
             final boolean isBlacklisted, final int timestamp) {
-        mBinaryDictionary.addUnigramWord(word, frequency, shortcutTarget, shortcutFreq,
+        mBinaryDictionary.addUnigramEntry(word, frequency, shortcutTarget, shortcutFreq,
                 isNotAWord, isBlacklisted, timestamp);
     }
 
     /**
-     * Dynamically adds a word bigram in the dictionary. May overwrite an existing entry.
+     * Adds n-gram information of a word to the dictionary. May overwrite an existing entry.
      */
-    public void addBigramDynamically(final String word0, final String word1,
+    public void addNgramEntry(final PrevWordsInfo prevWordsInfo, final String word,
             final int frequency, final int timestamp) {
         reloadDictionaryIfRequired();
         asyncExecuteTaskWithWriteLock(new Runnable() {
@@ -308,20 +308,20 @@
                     return;
                 }
                 runGCIfRequiredLocked(true /* mindsBlockByGC */);
-                addBigramDynamicallyLocked(word0, word1, frequency, timestamp);
+                addNgramEntryLocked(prevWordsInfo, word, frequency, timestamp);
             }
         });
     }
 
-    protected void addBigramDynamicallyLocked(final String word0, final String word1,
+    protected void addNgramEntryLocked(final PrevWordsInfo prevWordsInfo, final String word,
             final int frequency, final int timestamp) {
-        mBinaryDictionary.addBigramWords(word0, word1, frequency, timestamp);
+        mBinaryDictionary.addNgramEntry(prevWordsInfo, word, frequency, timestamp);
     }
 
     /**
-     * Dynamically remove a word bigram in the dictionary.
+     * Dynamically remove the n-gram entry in the dictionary.
      */
-    public void removeBigramDynamically(final String word0, final String word1) {
+    public void removeNgramDynamically(final PrevWordsInfo prevWordsInfo, final String word1) {
         reloadDictionaryIfRequired();
         asyncExecuteTaskWithWriteLock(new Runnable() {
             @Override
@@ -330,7 +330,7 @@
                     return;
                 }
                 runGCIfRequiredLocked(true /* mindsBlockByGC */);
-                mBinaryDictionary.removeBigramWords(word0, word1);
+                mBinaryDictionary.removeNgramEntry(prevWordsInfo, word1);
             }
         });
     }
@@ -428,9 +428,9 @@
         return mBinaryDictionary.isValidWord(word);
     }
 
-    protected boolean isValidBigramLocked(final String word1, final String word2) {
+    protected boolean isValidNgramLocked(final PrevWordsInfo prevWordsInfo, final String word) {
         if (mBinaryDictionary == null) return false;
-        return mBinaryDictionary.isValidBigram(word1, word2);
+        return mBinaryDictionary.isValidNgram(prevWordsInfo, word);
     }
 
     /**
diff --git a/java/src/com/android/inputmethod/latin/LastComposedWord.java b/java/src/com/android/inputmethod/latin/LastComposedWord.java
index 232bf74..9caec3e 100644
--- a/java/src/com/android/inputmethod/latin/LastComposedWord.java
+++ b/java/src/com/android/inputmethod/latin/LastComposedWord.java
@@ -48,7 +48,7 @@
     public final String mTypedWord;
     public final CharSequence mCommittedWord;
     public final String mSeparatorString;
-    public final String mPrevWord;
+    public final PrevWordsInfo mPrevWordsInfo;
     public final int mCapitalizedMode;
     public final InputPointers mInputPointers =
             new InputPointers(Constants.DICTIONARY_MAX_WORD_LENGTH);
@@ -64,7 +64,7 @@
     public LastComposedWord(final ArrayList<Event> events,
             final InputPointers inputPointers, final String typedWord,
             final CharSequence committedWord, final String separatorString,
-            final String prevWord, final int capitalizedMode) {
+            final PrevWordsInfo prevWordsInfo, final int capitalizedMode) {
         if (inputPointers != null) {
             mInputPointers.copy(inputPointers);
         }
@@ -73,7 +73,7 @@
         mCommittedWord = committedWord;
         mSeparatorString = separatorString;
         mActive = true;
-        mPrevWord = prevWord;
+        mPrevWordsInfo = prevWordsInfo;
         mCapitalizedMode = capitalizedMode;
     }
 
diff --git a/java/src/com/android/inputmethod/latin/UserBinaryDictionary.java b/java/src/com/android/inputmethod/latin/UserBinaryDictionary.java
index c8ffbe4..b89ab84 100644
--- a/java/src/com/android/inputmethod/latin/UserBinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/UserBinaryDictionary.java
@@ -258,12 +258,12 @@
                 // Safeguard against adding really long words.
                 if (word.length() < MAX_WORD_LENGTH) {
                     runGCIfRequiredLocked(true /* mindsBlockByGC */);
-                    addWordDynamicallyLocked(word, adjustedFrequency, null /* shortcutTarget */,
+                    addUnigramLocked(word, adjustedFrequency, null /* shortcutTarget */,
                             0 /* shortcutFreq */, false /* isNotAWord */,
                             false /* isBlacklisted */, BinaryDictionary.NOT_A_VALID_TIMESTAMP);
                     if (null != shortcut && shortcut.length() < MAX_WORD_LENGTH) {
                         runGCIfRequiredLocked(true /* mindsBlockByGC */);
-                        addWordDynamicallyLocked(shortcut, adjustedFrequency, word,
+                        addUnigramLocked(shortcut, adjustedFrequency, word,
                                 USER_DICT_SHORTCUT_FREQUENCY, true /* isNotAWord */,
                                 false /* isBlacklisted */, BinaryDictionary.NOT_A_VALID_TIMESTAMP);
                     }
diff --git a/java/src/com/android/inputmethod/latin/WordComposer.java b/java/src/com/android/inputmethod/latin/WordComposer.java
index 227b42b..09e9054 100644
--- a/java/src/com/android/inputmethod/latin/WordComposer.java
+++ b/java/src/com/android/inputmethod/latin/WordComposer.java
@@ -294,11 +294,10 @@
      * This will register NOT_A_COORDINATE for X and Ys, and use the passed keyboard for proximity.
      * @param codePoints the code points to set as the composing word.
      * @param coordinates the x, y coordinates of the key in the CoordinateUtils format
-     * @param previousWord the previous word, to use as context for suggestions. Can be null if
-     *   the context is nil (typically, at start of text).
+     * @param prevWordsInfo the information of previous words, to use as context for suggestions
      */
     public void setComposingWord(final int[] codePoints, final int[] coordinates,
-            final CharSequence previousWord) {
+            final PrevWordsInfo prevWordsInfo) {
         reset();
         final int length = codePoints.length;
         for (int i = 0; i < length; ++i) {
@@ -307,7 +306,7 @@
                     CoordinateUtils.yFromArray(coordinates, i)));
         }
         mIsResumed = true;
-        mPrevWordsInfo = new PrevWordsInfo(null == previousWord ? null : previousWord.toString());
+        mPrevWordsInfo = prevWordsInfo;
     }
 
     /**
@@ -413,13 +412,13 @@
     // `type' should be one of the LastComposedWord.COMMIT_TYPE_* constants above.
     // committedWord should contain suggestion spans if applicable.
     public LastComposedWord commitWord(final int type, final CharSequence committedWord,
-            final String separatorString, final String prevWord) {
+            final String separatorString, final PrevWordsInfo prevWordsInfo) {
         // Note: currently, we come here whenever we commit a word. If it's a MANUAL_PICK
         // or a DECIDED_WORD we may cancel the commit later; otherwise, we should deactivate
         // the last composed word to ensure this does not happen.
         final LastComposedWord lastComposedWord = new LastComposedWord(mEvents,
                 mInputPointers, mTypedWordCache.toString(), committedWord, separatorString,
-                prevWord, mCapitalizedMode);
+                prevWordsInfo, mCapitalizedMode);
         mInputPointers.reset();
         if (type != LastComposedWord.COMMIT_TYPE_DECIDED_WORD
                 && type != LastComposedWord.COMMIT_TYPE_MANUAL_PICK) {
diff --git a/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java b/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java
index ea58abc..58b1012 100644
--- a/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java
+++ b/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java
@@ -37,6 +37,7 @@
 import com.android.inputmethod.latin.LastComposedWord;
 import com.android.inputmethod.latin.LatinIME;
 import com.android.inputmethod.latin.LatinImeLogger;
+import com.android.inputmethod.latin.PrevWordsInfo;
 import com.android.inputmethod.latin.RichInputConnection;
 import com.android.inputmethod.latin.Suggest;
 import com.android.inputmethod.latin.Suggest.OnGetSuggestedWordsCallback;
@@ -1233,7 +1234,7 @@
     }
 
     private void performAdditionToUserHistoryDictionary(final SettingsValues settingsValues,
-            final String suggestion, final String prevWord) {
+            final String suggestion, final PrevWordsInfo prevWordsInfo) {
         // If correction is not enabled, we don't add words to the user history dictionary.
         // That's to avoid unintended additions in some sensitive fields, or fields that
         // expect to receive non-words.
@@ -1244,8 +1245,8 @@
                 mWordComposer.wasAutoCapitalized() && !mWordComposer.isMostlyCaps();
         final int timeStampInSeconds = (int)TimeUnit.MILLISECONDS.toSeconds(
                 System.currentTimeMillis());
-        mSuggest.mDictionaryFacilitator.addToUserHistory(suggestion, wasAutoCapitalized, prevWord,
-                timeStampInSeconds, settingsValues.mBlockPotentiallyOffensive);
+        mSuggest.mDictionaryFacilitator.addToUserHistory(suggestion, wasAutoCapitalized,
+                prevWordsInfo, timeStampInSeconds, settingsValues.mBlockPotentiallyOffensive);
     }
 
     public void performUpdateSuggestionStripSync(final SettingsValues settingsValues) {
@@ -1370,13 +1371,15 @@
             }
         }
         final int[] codePoints = StringUtils.toCodePointArray(typedWord);
+        // We want the previous word for suggestion. If we have chars in the word
+        // before the cursor, then we want the word before that, hence 2; otherwise,
+        // we want the word immediately before the cursor, hence 1.
+        final String prevWord = getNthPreviousWordForSuggestion(
+                settingsValues.mSpacingAndPunctuations,
+                0 == numberOfCharsInWordBeforeCursor ? 1 : 2).toString();
         mWordComposer.setComposingWord(codePoints,
                 mLatinIME.getCoordinatesForCurrentKeyboard(codePoints),
-                getNthPreviousWordForSuggestion(settingsValues.mSpacingAndPunctuations,
-                        // We want the previous word for suggestion. If we have chars in the word
-                        // before the cursor, then we want the word before that, hence 2; otherwise,
-                        // we want the word immediately before the cursor, hence 1.
-                        0 == numberOfCharsInWordBeforeCursor ? 1 : 2));
+                new PrevWordsInfo(prevWord));
         mWordComposer.setCursorPositionWithinWord(
                 typedWord.codePointCount(0, numberOfCharsInWordBeforeCursor));
         mConnection.setComposingRegion(expectedCursorPosition - numberOfCharsInWordBeforeCursor,
@@ -1431,7 +1434,7 @@
      * @param inputTransaction The transaction in progress.
      */
     private void revertCommit(final InputTransaction inputTransaction) {
-        final String previousWord = mLastComposedWord.mPrevWord;
+        final PrevWordsInfo prevWordsInfo = mLastComposedWord.mPrevWordsInfo;
         final CharSequence originallyTypedWord = mLastComposedWord.mTypedWord;
         final CharSequence committedWord = mLastComposedWord.mCommittedWord;
         final String committedWordString = committedWord.toString();
@@ -1453,9 +1456,9 @@
             }
         }
         mConnection.deleteSurroundingText(deleteLength, 0);
-        if (!TextUtils.isEmpty(previousWord) && !TextUtils.isEmpty(committedWord)) {
+        if (!TextUtils.isEmpty(prevWordsInfo.mPrevWord) && !TextUtils.isEmpty(committedWord)) {
             mSuggest.mDictionaryFacilitator.cancelAddingUserHistory(
-                    previousWord, committedWordString);
+                    prevWordsInfo, committedWordString);
         }
         final String stringToCommit = originallyTypedWord + mLastComposedWord.mSeparatorString;
         final SpannableString textToCommit = new SpannableString(stringToCommit);
@@ -1504,7 +1507,7 @@
             // with the typed word, so we need to resume suggestions right away.
             final int[] codePoints = StringUtils.toCodePointArray(stringToCommit);
             mWordComposer.setComposingWord(codePoints,
-                    mLatinIME.getCoordinatesForCurrentKeyboard(codePoints), previousWord);
+                    mLatinIME.getCoordinatesForCurrentKeyboard(codePoints), prevWordsInfo);
             mConnection.setComposingText(textToCommit, 1);
         }
         if (inputTransaction.mSettingsValues.mIsInternal) {
@@ -1968,17 +1971,17 @@
                         suggestedWords);
         // Use the 2nd previous word as the previous word because the 1st previous word is the word
         // to be committed.
-        final String prevWord = mConnection.getNthPreviousWord(
-                settingsValues.mSpacingAndPunctuations, 2);
+        final PrevWordsInfo prevWordsInfo = new PrevWordsInfo(mConnection.getNthPreviousWord(
+                settingsValues.mSpacingAndPunctuations, 2));
         mConnection.commitText(chosenWordWithSuggestions, 1);
         // Add the word to the user history dictionary
-        performAdditionToUserHistoryDictionary(settingsValues, chosenWord, prevWord);
+        performAdditionToUserHistoryDictionary(settingsValues, chosenWord, prevWordsInfo);
         // TODO: figure out here if this is an auto-correct or if the best word is actually
         // what user typed. Note: currently this is done much later in
         // LastComposedWord#didCommitTypedWord by string equality of the remembered
         // strings.
         mLastComposedWord = mWordComposer.commitWord(commitType,
-                chosenWordWithSuggestions, separatorString, prevWord);
+                chosenWordWithSuggestions, separatorString, prevWordsInfo);
         final boolean shouldDiscardPreviousWordForSuggestion;
         if (0 == StringUtils.codePointCount(separatorString)) {
             // Separator is 0-length, we can keep the previous word for suggestion. Either this
diff --git a/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java b/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java
index 818cd9a..f89caf9 100644
--- a/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java
@@ -22,6 +22,7 @@
 import com.android.inputmethod.latin.Constants;
 import com.android.inputmethod.latin.Dictionary;
 import com.android.inputmethod.latin.ExpandableBinaryDictionary;
+import com.android.inputmethod.latin.PrevWordsInfo;
 
 import java.io.File;
 import java.util.Locale;
@@ -52,29 +53,32 @@
     }
 
     /**
-     * Pair will be added to the user history dictionary.
+     * Add a word to the user history dictionary.
      *
-     * The first word may be null. That means we don't know the context, in other words,
-     * it's only a unigram. The first word may also be an empty string : this means start
-     * context, as in beginning of a sentence for example.
-     * The second word may not be null (a NullPointerException would be thrown).
+     * @param userHistoryDictionary the user history dictionary
+     * @param prevWordsInfo the information of previous words
+     * @param word the word the user inputted
+     * @param isValid whether the word is valid or not
+     * @param timestamp the timestamp when the word has been inputted
      */
     public static void addToDictionary(final ExpandableBinaryDictionary userHistoryDictionary,
-            final String word0, final String word1, final boolean isValid, final int timestamp) {
-        if (word1.length() >= Constants.DICTIONARY_MAX_WORD_LENGTH ||
-                (word0 != null && word0.length() >= Constants.DICTIONARY_MAX_WORD_LENGTH)) {
+            final PrevWordsInfo prevWordsInfo, final String word, final boolean isValid,
+            final int timestamp) {
+        final String prevWord = prevWordsInfo.mPrevWord;
+        if (word.length() >= Constants.DICTIONARY_MAX_WORD_LENGTH ||
+                (prevWord != null && prevWord.length() >= Constants.DICTIONARY_MAX_WORD_LENGTH)) {
             return;
         }
         final int frequency = isValid ?
                 FREQUENCY_FOR_WORDS_IN_DICTS : FREQUENCY_FOR_WORDS_NOT_IN_DICTS;
-        userHistoryDictionary.addWordDynamically(word1, frequency, null /* shortcutTarget */,
+        userHistoryDictionary.addUnigramEntry(word, frequency, null /* shortcutTarget */,
                 0 /* shortcutFreq */, false /* isNotAWord */, false /* isBlacklisted */, timestamp);
         // Do not insert a word as a bigram of itself
-        if (word1.equals(word0)) {
+        if (word.equals(prevWord)) {
             return;
         }
-        if (null != word0) {
-            userHistoryDictionary.addBigramDynamically(word0, word1, frequency, timestamp);
+        if (null != prevWord) {
+            userHistoryDictionary.addNgramEntry(prevWordsInfo, word, frequency, timestamp);
         }
     }
 }
diff --git a/java/src/com/android/inputmethod/latin/utils/DistracterFilter.java b/java/src/com/android/inputmethod/latin/utils/DistracterFilter.java
index a219532..9ea7e21 100644
--- a/java/src/com/android/inputmethod/latin/utils/DistracterFilter.java
+++ b/java/src/com/android/inputmethod/latin/utils/DistracterFilter.java
@@ -114,7 +114,7 @@
         final int[] codePoints = StringUtils.toCodePointArray(testedWord);
         final int[] coordinates;
         coordinates = mKeyboard.getCoordinates(codePoints);
-        composer.setComposingWord(codePoints, coordinates, prevWordsInfo.mPrevWord);
+        composer.setComposingWord(codePoints, coordinates, prevWordsInfo);
 
         final int trailingSingleQuotesCount = StringUtils.getTrailingSingleQuotesCount(testedWord);
         final String consideredWord = trailingSingleQuotesCount > 0 ?
diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
index 90b90ff..2c2fed3 100644
--- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
+++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
@@ -65,7 +65,7 @@
 
     private void addUnigramWord(final BinaryDictionary binaryDictionary, final String word,
             final int probability) {
-        binaryDictionary.addUnigramWord(word, probability, "" /* shortcutTarget */,
+        binaryDictionary.addUnigramEntry(word, probability, "" /* shortcutTarget */,
                 BinaryDictionary.NOT_A_PROBABILITY /* shortcutProbability */,
                 false /* isNotAWord */, false /* isBlacklisted */,
                 mCurrentTime /* timestamp */);
@@ -73,10 +73,15 @@
 
     private void addBigramWords(final BinaryDictionary binaryDictionary, final String word0,
             final String word1, final int probability) {
-        binaryDictionary.addBigramWords(word0, word1, probability,
+        binaryDictionary.addNgramEntry(new PrevWordsInfo(word0), word1, probability,
                 mCurrentTime /* timestamp */);
     }
 
+    private static boolean isValidBigram(final BinaryDictionary binaryDictionary,
+            final String word0, final String word1) {
+        return binaryDictionary.isValidNgram(new PrevWordsInfo(word0), word1);
+    }
+
     private void forcePassingShortTime(final BinaryDictionary binaryDictionary) {
         // 30 days.
         final int timeToElapse = (int)TimeUnit.SECONDS.convert(30, TimeUnit.DAYS);
@@ -224,19 +229,19 @@
         assertTrue(binaryDictionary.isValidWord("b"));
 
         addBigramWords(binaryDictionary, "a", "b", Dictionary.NOT_A_PROBABILITY);
-        assertFalse(binaryDictionary.isValidBigram("a", "b"));
+        assertFalse(isValidBigram(binaryDictionary, "a", "b"));
         addBigramWords(binaryDictionary, "a", "b", Dictionary.NOT_A_PROBABILITY);
-        assertTrue(binaryDictionary.isValidBigram("a", "b"));
+        assertTrue(isValidBigram(binaryDictionary, "a", "b"));
 
         addUnigramWord(binaryDictionary, "c", DUMMY_PROBABILITY);
         addBigramWords(binaryDictionary, "a", "c", DUMMY_PROBABILITY);
-        assertTrue(binaryDictionary.isValidBigram("a", "c"));
+        assertTrue(isValidBigram(binaryDictionary, "a", "c"));
 
         // Add bigrams of not valid unigrams.
         addBigramWords(binaryDictionary, "x", "y", Dictionary.NOT_A_PROBABILITY);
-        assertFalse(binaryDictionary.isValidBigram("x", "y"));
+        assertFalse(isValidBigram(binaryDictionary, "x", "y"));
         addBigramWords(binaryDictionary, "x", "y", DUMMY_PROBABILITY);
-        assertFalse(binaryDictionary.isValidBigram("x", "y"));
+        assertFalse(isValidBigram(binaryDictionary, "x", "y"));
 
         binaryDictionary.close();
         dictFile.delete();
@@ -276,9 +281,9 @@
         addUnigramWord(binaryDictionary, "a", DUMMY_PROBABILITY);
         addUnigramWord(binaryDictionary, "b", DUMMY_PROBABILITY);
         addBigramWords(binaryDictionary, "a", "b", DUMMY_PROBABILITY);
-        assertTrue(binaryDictionary.isValidBigram("a", "b"));
+        assertTrue(isValidBigram(binaryDictionary, "a", "b"));
         forcePassingShortTime(binaryDictionary);
-        assertFalse(binaryDictionary.isValidBigram("a", "b"));
+        assertFalse(isValidBigram(binaryDictionary, "a", "b"));
 
         addUnigramWord(binaryDictionary, "a", DUMMY_PROBABILITY);
         addUnigramWord(binaryDictionary, "b", DUMMY_PROBABILITY);
@@ -289,11 +294,11 @@
         addUnigramWord(binaryDictionary, "a", DUMMY_PROBABILITY);
         addUnigramWord(binaryDictionary, "b", DUMMY_PROBABILITY);
         addBigramWords(binaryDictionary, "a", "b", DUMMY_PROBABILITY);
-        assertTrue(binaryDictionary.isValidBigram("a", "b"));
+        assertTrue(isValidBigram(binaryDictionary, "a", "b"));
         forcePassingShortTime(binaryDictionary);
-        assertTrue(binaryDictionary.isValidBigram("a", "b"));
+        assertTrue(isValidBigram(binaryDictionary, "a", "b"));
         forcePassingLongTime(binaryDictionary);
-        assertFalse(binaryDictionary.isValidBigram("a", "b"));
+        assertFalse(isValidBigram(binaryDictionary, "a", "b"));
 
         binaryDictionary.close();
         dictFile.delete();
@@ -549,8 +554,8 @@
         for (int j = 0; j < weakBigramTypedCount; j++) {
             addBigramWords(binaryDictionary, weak, target, DUMMY_PROBABILITY);
         }
-        assertTrue(binaryDictionary.isValidBigram(strong, target));
-        assertTrue(binaryDictionary.isValidBigram(weak, target));
+        assertTrue(isValidBigram(binaryDictionary, strong, target));
+        assertTrue(isValidBigram(binaryDictionary, weak, target));
 
         for (int i = 0; i < bigramCount; i++) {
             final int word0Index = random.nextInt(words.size());
@@ -571,8 +576,8 @@
                         Integer.parseInt(binaryDictionary.getPropertyForTest(
                                 BinaryDictionary.BIGRAM_COUNT_QUERY));
                 assertTrue(bigramCountBeforeGC > bigramCountAfterGC);
-                assertTrue(binaryDictionary.isValidBigram(strong, target));
-                assertFalse(binaryDictionary.isValidBigram(weak, target));
+                assertTrue(isValidBigram(binaryDictionary, strong, target));
+                assertFalse(isValidBigram(binaryDictionary, weak, target));
                 break;
             }
         }
@@ -606,9 +611,9 @@
         addUnigramWord(binaryDictionary, "ccc", DUMMY_PROBABILITY);
         addUnigramWord(binaryDictionary, "abc", DUMMY_PROBABILITY);
         addBigramWords(binaryDictionary, "aaa", "abc", DUMMY_PROBABILITY);
-        assertTrue(binaryDictionary.isValidBigram("aaa", "abc"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "abc"));
         addBigramWords(binaryDictionary, "aaa", "bbb", Dictionary.NOT_A_PROBABILITY);
-        assertFalse(binaryDictionary.isValidBigram("aaa", "bbb"));
+        assertFalse(isValidBigram(binaryDictionary, "aaa", "bbb"));
 
         assertEquals(fromFormatVersion, binaryDictionary.getFormatVersion());
         assertTrue(binaryDictionary.migrateTo(toFormatVersion));
@@ -619,10 +624,10 @@
         assertTrue(binaryDictionary.getFrequency("aaa") < binaryDictionary.getFrequency("ccc"));
         addUnigramWord(binaryDictionary, "bbb", Dictionary.NOT_A_PROBABILITY);
         assertTrue(binaryDictionary.isValidWord("bbb"));
-        assertTrue(binaryDictionary.isValidBigram("aaa", "abc"));
-        assertFalse(binaryDictionary.isValidBigram("aaa", "bbb"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "abc"));
+        assertFalse(isValidBigram(binaryDictionary, "aaa", "bbb"));
         addBigramWords(binaryDictionary, "aaa", "bbb", Dictionary.NOT_A_PROBABILITY);
-        assertTrue(binaryDictionary.isValidBigram("aaa", "bbb"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "bbb"));
         binaryDictionary.close();
         dictFile.delete();
     }
diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
index c87c2a9..2b82e54 100644
--- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
+++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
@@ -170,7 +170,7 @@
         addUnigramWord(binaryDictionary, validLongWord, probability);
         addUnigramWord(binaryDictionary, invalidLongWord, probability);
         // Too long short cut.
-        binaryDictionary.addUnigramWord("a", probability, invalidLongWord,
+        binaryDictionary.addUnigramEntry("a", probability, invalidLongWord,
                 10 /* shortcutProbability */, false /* isNotAWord */, false /* isBlacklisted */,
                 BinaryDictionary.NOT_A_VALID_TIMESTAMP);
         addUnigramWord(binaryDictionary, "abc", probability);
@@ -188,20 +188,35 @@
         dictFile.delete();
     }
 
-    private void addUnigramWord(final BinaryDictionary binaryDictionary, final String word,
+    private static void addUnigramWord(final BinaryDictionary binaryDictionary, final String word,
             final int probability) {
-        binaryDictionary.addUnigramWord(word, probability, "" /* shortcutTarget */,
+        binaryDictionary.addUnigramEntry(word, probability, "" /* shortcutTarget */,
                 BinaryDictionary.NOT_A_PROBABILITY /* shortcutProbability */,
                 false /* isNotAWord */, false /* isBlacklisted */,
                 BinaryDictionary.NOT_A_VALID_TIMESTAMP /* timestamp */);
     }
 
-    private void addBigramWords(final BinaryDictionary binaryDictionary, final String word0,
+    private static void addBigramWords(final BinaryDictionary binaryDictionary, final String word0,
             final String word1, final int probability) {
-        binaryDictionary.addBigramWords(word0, word1, probability,
+        binaryDictionary.addNgramEntry(new PrevWordsInfo(word0), word1, probability,
                 BinaryDictionary.NOT_A_VALID_TIMESTAMP /* timestamp */);
     }
 
+    private static boolean isValidBigram(final BinaryDictionary binaryDictionary,
+            final String word0, final String word1) {
+        return binaryDictionary.isValidNgram(new PrevWordsInfo(word0), word1);
+    }
+
+    private static void removeBigramEntry(final BinaryDictionary binaryDictionary,
+            final String word0, final String word1) {
+        binaryDictionary.removeNgramEntry(new PrevWordsInfo(word0), word1);
+    }
+
+    private static int getBigramProbability(final BinaryDictionary binaryDictionary,
+            final String word0,  final String word1) {
+        return binaryDictionary.getNgramProbability(new PrevWordsInfo(word0), word1);
+    }
+
     public void testAddUnigramWord() {
         for (final int formatVersion : DICT_FORMAT_VERSIONS) {
             testAddUnigramWord(formatVersion);
@@ -312,32 +327,32 @@
         addBigramWords(binaryDictionary, "abb", "aaa", bigramProbability);
         addBigramWords(binaryDictionary, "abb", "bcc", bigramProbability);
 
-        assertTrue(binaryDictionary.isValidBigram("aaa", "abb"));
-        assertTrue(binaryDictionary.isValidBigram("aaa", "bcc"));
-        assertTrue(binaryDictionary.isValidBigram("abb", "aaa"));
-        assertTrue(binaryDictionary.isValidBigram("abb", "bcc"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "abb"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "bcc"));
+        assertTrue(isValidBigram(binaryDictionary, "abb", "aaa"));
+        assertTrue(isValidBigram(binaryDictionary, "abb", "bcc"));
         if (canCheckBigramProbability(formatVersion)) {
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("aaa", "abb"));
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("aaa", "bcc"));
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("abb", "aaa"));
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("abb", "bcc"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "aaa", "abb"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "aaa", "bcc"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "abb", "aaa"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "abb", "bcc"));
         }
 
         addBigramWords(binaryDictionary, "aaa", "abb", updatedBigramProbability);
         if (canCheckBigramProbability(formatVersion)) {
             assertEquals(updatedBigramProbability,
-                    binaryDictionary.getBigramProbability("aaa", "abb"));
+                    getBigramProbability(binaryDictionary, "aaa", "abb"));
         }
 
-        assertFalse(binaryDictionary.isValidBigram("bcc", "aaa"));
-        assertFalse(binaryDictionary.isValidBigram("bcc", "bbc"));
-        assertFalse(binaryDictionary.isValidBigram("aaa", "aaa"));
+        assertFalse(isValidBigram(binaryDictionary, "bcc", "aaa"));
+        assertFalse(isValidBigram(binaryDictionary, "bcc", "bbc"));
+        assertFalse(isValidBigram(binaryDictionary, "aaa", "aaa"));
         assertEquals(Dictionary.NOT_A_PROBABILITY,
-                binaryDictionary.getBigramProbability("bcc", "aaa"));
+                getBigramProbability(binaryDictionary, "bcc", "aaa"));
         assertEquals(Dictionary.NOT_A_PROBABILITY,
-                binaryDictionary.getBigramProbability("bcc", "bbc"));
+                getBigramProbability(binaryDictionary, "bcc", "bbc"));
         assertEquals(Dictionary.NOT_A_PROBABILITY,
-                binaryDictionary.getBigramProbability("aaa", "aaa"));
+                getBigramProbability(binaryDictionary, "aaa", "aaa"));
 
         // Testing bigram link.
         addUnigramWord(binaryDictionary, "abcde", unigramProbability);
@@ -349,14 +364,14 @@
 
         if (canCheckBigramProbability(formatVersion)) {
             assertEquals(bigramProbability,
-                    binaryDictionary.getBigramProbability("abcde", "fghij"));
+                    getBigramProbability(binaryDictionary, "abcde", "fghij"));
         }
         assertEquals(Dictionary.NOT_A_PROBABILITY,
-                binaryDictionary.getBigramProbability("abcde", "fgh"));
+                getBigramProbability(binaryDictionary, "abcde", "fgh"));
         addBigramWords(binaryDictionary, "abcde", "fghij", updatedBigramProbability);
         if (canCheckBigramProbability(formatVersion)) {
             assertEquals(updatedBigramProbability,
-                    binaryDictionary.getBigramProbability("abcde", "fghij"));
+                    getBigramProbability(binaryDictionary, "abcde", "fghij"));
         }
 
         dictFile.delete();
@@ -418,10 +433,10 @@
         for (final Pair<String, String> bigram : bigramWords) {
             final int bigramProbability = bigramProbabilities.get(bigram);
             assertEquals(bigramProbability != Dictionary.NOT_A_PROBABILITY,
-                    binaryDictionary.isValidBigram(bigram.first, bigram.second));
+                    isValidBigram(binaryDictionary, bigram.first, bigram.second));
             if (canCheckBigramProbability(formatVersion)) {
                 assertEquals(bigramProbability,
-                        binaryDictionary.getBigramProbability(bigram.first, bigram.second));
+                        getBigramProbability(binaryDictionary, bigram.first, bigram.second));
             }
         }
 
@@ -454,28 +469,28 @@
         addBigramWords(binaryDictionary, "abb", "aaa", bigramProbability);
         addBigramWords(binaryDictionary, "abb", "bcc", bigramProbability);
 
-        assertTrue(binaryDictionary.isValidBigram("aaa", "abb"));
-        assertTrue(binaryDictionary.isValidBigram("aaa", "bcc"));
-        assertTrue(binaryDictionary.isValidBigram("abb", "aaa"));
-        assertTrue(binaryDictionary.isValidBigram("abb", "bcc"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "abb"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "bcc"));
+        assertTrue(isValidBigram(binaryDictionary, "abb", "aaa"));
+        assertTrue(isValidBigram(binaryDictionary, "abb", "bcc"));
 
-        binaryDictionary.removeBigramWords("aaa", "abb");
-        assertFalse(binaryDictionary.isValidBigram("aaa", "abb"));
+        removeBigramEntry(binaryDictionary, "aaa", "abb");
+        assertFalse(isValidBigram(binaryDictionary, "aaa", "abb"));
         addBigramWords(binaryDictionary, "aaa", "abb", bigramProbability);
-        assertTrue(binaryDictionary.isValidBigram("aaa", "abb"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "abb"));
 
 
-        binaryDictionary.removeBigramWords("aaa", "bcc");
-        assertFalse(binaryDictionary.isValidBigram("aaa", "bcc"));
-        binaryDictionary.removeBigramWords("abb", "aaa");
-        assertFalse(binaryDictionary.isValidBigram("abb", "aaa"));
-        binaryDictionary.removeBigramWords("abb", "bcc");
-        assertFalse(binaryDictionary.isValidBigram("abb", "bcc"));
+        removeBigramEntry(binaryDictionary, "aaa", "bcc");
+        assertFalse(isValidBigram(binaryDictionary, "aaa", "bcc"));
+        removeBigramEntry(binaryDictionary, "abb", "aaa");
+        assertFalse(isValidBigram(binaryDictionary, "abb", "aaa"));
+        removeBigramEntry(binaryDictionary, "abb", "bcc");
+        assertFalse(isValidBigram(binaryDictionary, "abb", "bcc"));
 
-        binaryDictionary.removeBigramWords("aaa", "abb");
+        removeBigramEntry(binaryDictionary, "aaa", "abb");
         // Test remove non-existing bigram operation.
-        binaryDictionary.removeBigramWords("aaa", "abb");
-        binaryDictionary.removeBigramWords("bcc", "aaa");
+        removeBigramEntry(binaryDictionary, "aaa", "abb");
+        removeBigramEntry(binaryDictionary, "bcc", "aaa");
 
         dictFile.delete();
     }
@@ -570,14 +585,14 @@
         assertEquals(unigramProbability, binaryDictionary.getFrequency("abb"));
         assertEquals(unigramProbability, binaryDictionary.getFrequency("bcc"));
         if (canCheckBigramProbability(formatVersion)) {
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("aaa", "abb"));
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("aaa", "bcc"));
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("abb", "aaa"));
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("abb", "bcc"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "aaa", "abb"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "aaa", "bcc"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "abb", "aaa"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "abb", "bcc"));
         }
-        assertFalse(binaryDictionary.isValidBigram("bcc", "aaa"));
-        assertFalse(binaryDictionary.isValidBigram("bcc", "bbc"));
-        assertFalse(binaryDictionary.isValidBigram("aaa", "aaa"));
+        assertFalse(isValidBigram(binaryDictionary, "bcc", "aaa"));
+        assertFalse(isValidBigram(binaryDictionary, "bcc", "bbc"));
+        assertFalse(isValidBigram(binaryDictionary, "aaa", "aaa"));
         binaryDictionary.flushWithGC();
         binaryDictionary.close();
 
@@ -649,10 +664,10 @@
         for (final Pair<String, String> bigram : bigramWords) {
             final int bigramProbability = bigramProbabilities.get(bigram);
             assertEquals(bigramProbability != Dictionary.NOT_A_PROBABILITY,
-                    binaryDictionary.isValidBigram(bigram.first, bigram.second));
+                    isValidBigram(binaryDictionary, bigram.first, bigram.second));
             if (canCheckBigramProbability(formatVersion)) {
                 assertEquals(bigramProbability,
-                        binaryDictionary.getBigramProbability(bigram.first, bigram.second));
+                        getBigramProbability(binaryDictionary, bigram.first, bigram.second));
             }
         }
 
@@ -742,7 +757,7 @@
                     final Pair<String, String> bigram = bigramWords.get(bigramIndex);
                     bigramWords.remove(bigramIndex);
                     bigramProbabilities.remove(bigram);
-                    binaryDictionary.removeBigramWords(bigram.first, bigram.second);
+                    removeBigramEntry(binaryDictionary, bigram.first, bigram.second);
                 }
             }
 
@@ -765,10 +780,10 @@
 
                 if (canCheckBigramProbability(formatVersion)) {
                     assertEquals(probability,
-                            binaryDictionary.getBigramProbability(bigram.first, bigram.second));
+                            getBigramProbability(binaryDictionary, bigram.first, bigram.second));
                 }
                 assertEquals(probability != Dictionary.NOT_A_PROBABILITY,
-                        binaryDictionary.isValidBigram(bigram.first, bigram.second));
+                        isValidBigram(binaryDictionary, bigram.first, bigram.second));
             }
             binaryDictionary.flushWithGC();
             binaryDictionary.close();
@@ -946,10 +961,10 @@
             final String word1 = entry.getKey().second;
             final int bigramProbability = entry.getValue();
             assertEquals(bigramProbability != Dictionary.NOT_A_PROBABILITY,
-                    binaryDictionary.isValidBigram(word0, word1));
+                    isValidBigram(binaryDictionary, word0, word1));
             if (canCheckBigramProbability(formatVersion)) {
                 assertEquals(bigramProbability,
-                        binaryDictionary.getBigramProbability(word0, word1));
+                        getBigramProbability(binaryDictionary, word0, word1));
             }
         }
     }
@@ -993,7 +1008,7 @@
             final boolean isNotAWord = random.nextBoolean();
             final boolean isBlacklisted = random.nextBoolean();
             // TODO: Add tests for historical info.
-            binaryDictionary.addUnigramWord(word, unigramProbability,
+            binaryDictionary.addUnigramEntry(word, unigramProbability,
                     null /* shortcutTarget */, BinaryDictionary.NOT_A_PROBABILITY,
                     isNotAWord, isBlacklisted, BinaryDictionary.NOT_A_VALID_TIMESTAMP);
             if (binaryDictionary.needsToRunGC(false /* mindsBlockByGC */)) {
@@ -1023,8 +1038,7 @@
             final int unigramProbability = wordProbabilities.get(word1);
             final int bigramProbability =
                     unigramProbability + random.nextInt(0xFF - unigramProbability);
-            binaryDictionary.addBigramWords(word0, word1, bigramProbability,
-                    BinaryDictionary.NOT_A_VALID_TIMESTAMP);
+            addBigramWords(binaryDictionary, word0, word1, bigramProbability);
             if (binaryDictionary.needsToRunGC(false /* mindsBlockByGC */)) {
                 binaryDictionary.flushWithGC();
             }
@@ -1112,8 +1126,7 @@
             final int unigramProbability = wordProbabilitiesToCheckLater.get(word1);
             final int bigramProbability =
                     unigramProbability + random.nextInt(0xFF - unigramProbability);
-            binaryDictionary.addBigramWords(word0, word1, bigramProbability,
-                    BinaryDictionary.NOT_A_VALID_TIMESTAMP);
+            addBigramWords(binaryDictionary, word0, word1, bigramProbability);
             if (binaryDictionary.needsToRunGC(false /* mindsBlockByGC */)) {
                 binaryDictionary.flushWithGC();
             }
@@ -1174,7 +1187,7 @@
 
         final int unigramProbability = 100;
         final int shortcutProbability = 10;
-        binaryDictionary.addUnigramWord("aaa", unigramProbability, "zzz",
+        binaryDictionary.addUnigramEntry("aaa", unigramProbability, "zzz",
                 shortcutProbability, false /* isNotAWord */, false /* isBlacklisted */,
                 0 /* timestamp */);
         WordProperty wordProperty = binaryDictionary.getWordProperty("aaa");
@@ -1182,7 +1195,7 @@
         assertEquals("zzz", wordProperty.mShortcutTargets.get(0).mWord);
         assertEquals(shortcutProbability, wordProperty.mShortcutTargets.get(0).getProbability());
         final int updatedShortcutProbability = 2;
-        binaryDictionary.addUnigramWord("aaa", unigramProbability, "zzz",
+        binaryDictionary.addUnigramEntry("aaa", unigramProbability, "zzz",
                 updatedShortcutProbability, false /* isNotAWord */, false /* isBlacklisted */,
                 0 /* timestamp */);
         wordProperty = binaryDictionary.getWordProperty("aaa");
@@ -1190,7 +1203,7 @@
         assertEquals("zzz", wordProperty.mShortcutTargets.get(0).mWord);
         assertEquals(updatedShortcutProbability,
                 wordProperty.mShortcutTargets.get(0).getProbability());
-        binaryDictionary.addUnigramWord("aaa", unigramProbability, "yyy",
+        binaryDictionary.addUnigramEntry("aaa", unigramProbability, "yyy",
                 shortcutProbability, false /* isNotAWord */, false /* isBlacklisted */,
                 0 /* timestamp */);
         final HashMap<String, Integer> shortcutTargets = new HashMap<String, Integer>();
@@ -1261,7 +1274,7 @@
             final int shortcutProbability = random.nextInt(0xF);
             final String word = words.get(random.nextInt(words.size()));
             final int unigramProbability = unigramProbabilities.get(word);
-            binaryDictionary.addUnigramWord(word, unigramProbability, shortcutTarget,
+            binaryDictionary.addUnigramEntry(word, unigramProbability, shortcutTarget,
                     shortcutProbability, false /* isNotAWord */, false /* isBlacklisted */,
                     0 /* timestamp */);
             if (shortcutTargets.containsKey(word)) {
@@ -1317,14 +1330,14 @@
         final int bigramProbability = 150;
         addBigramWords(binaryDictionary, "aaa", "bbb", bigramProbability);
         final int shortcutProbability = 10;
-        binaryDictionary.addUnigramWord("ccc", unigramProbability, "xxx", shortcutProbability,
+        binaryDictionary.addUnigramEntry("ccc", unigramProbability, "xxx", shortcutProbability,
                 false /* isNotAWord */, false /* isBlacklisted */, 0 /* timestamp */);
-        binaryDictionary.addUnigramWord("ddd", unigramProbability, null /* shortcutTarget */,
+        binaryDictionary.addUnigramEntry("ddd", unigramProbability, null /* shortcutTarget */,
                 Dictionary.NOT_A_PROBABILITY, true /* isNotAWord */,
                 true /* isBlacklisted */, 0 /* timestamp */);
         assertEquals(unigramProbability, binaryDictionary.getFrequency("aaa"));
         assertEquals(unigramProbability, binaryDictionary.getFrequency("bbb"));
-        assertTrue(binaryDictionary.isValidBigram("aaa", "bbb"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "bbb"));
         assertEquals(fromFormatVersion, binaryDictionary.getFormatVersion());
         assertTrue(binaryDictionary.migrateTo(toFormatVersion));
         assertTrue(binaryDictionary.isValidDictionary());
@@ -1332,9 +1345,9 @@
         assertEquals(unigramProbability, binaryDictionary.getFrequency("aaa"));
         assertEquals(unigramProbability, binaryDictionary.getFrequency("bbb"));
         if (canCheckBigramProbability(toFormatVersion)) {
-            assertEquals(bigramProbability, binaryDictionary.getBigramProbability("aaa", "bbb"));
+            assertEquals(bigramProbability, getBigramProbability(binaryDictionary, "aaa", "bbb"));
         }
-        assertTrue(binaryDictionary.isValidBigram("aaa", "bbb"));
+        assertTrue(isValidBigram(binaryDictionary, "aaa", "bbb"));
         WordProperty wordProperty = binaryDictionary.getWordProperty("ccc");
         assertEquals(1, wordProperty.mShortcutTargets.size());
         assertEquals("xxx", wordProperty.mShortcutTargets.get(0).mWord);
@@ -1395,8 +1408,7 @@
             final int unigramProbability = unigramProbabilities.get(word1);
             final int bigramProbability =
                     random.nextInt(0xFF - unigramProbability) + unigramProbability;
-            binaryDictionary.addBigramWords(word0, word1, bigramProbability,
-                    BinaryDictionary.NOT_A_VALID_TIMESTAMP);
+            addBigramWords(binaryDictionary, word0, word1, bigramProbability);
             if (binaryDictionary.needsToRunGC(true /* mindsBlockByGC */)) {
                 binaryDictionary.flushWithGC();
             }
@@ -1415,9 +1427,9 @@
         for (final Pair<String, String> bigram : bigrams) {
             if (canCheckBigramProbability(toFormatVersion)) {
                 assertEquals((int)bigramProbabilities.get(bigram),
-                        binaryDictionary.getBigramProbability(bigram.first, bigram.second));
+                        getBigramProbability(binaryDictionary, bigram.first, bigram.second));
             }
-            assertTrue(binaryDictionary.isValidBigram(bigram.first, bigram.second));
+            assertTrue(isValidBigram(binaryDictionary, bigram.first, bigram.second));
         }
         assertEquals(bigramProbabilities.size(), Integer.parseInt(
                 binaryDictionary.getPropertyForTest(BinaryDictionary.BIGRAM_COUNT_QUERY)));
diff --git a/tests/src/com/android/inputmethod/latin/WordComposerTests.java b/tests/src/com/android/inputmethod/latin/WordComposerTests.java
index 16e8b36..17e7185 100644
--- a/tests/src/com/android/inputmethod/latin/WordComposerTests.java
+++ b/tests/src/com/android/inputmethod/latin/WordComposerTests.java
@@ -40,8 +40,8 @@
         final int[] COORDINATES_WITHIN_BMP =
                 CoordinateUtils.newCoordinateArray(CODEPOINTS_WITHIN_BMP.length,
                         Constants.NOT_A_COORDINATE, Constants.NOT_A_COORDINATE);
-        final String PREVWORD = "prevword";
-        wc.setComposingWord(CODEPOINTS_WITHIN_BMP, COORDINATES_WITHIN_BMP, PREVWORD);
+        final PrevWordsInfo PREV_WORDS_INFO = new PrevWordsInfo("prevword");
+        wc.setComposingWord(CODEPOINTS_WITHIN_BMP, COORDINATES_WITHIN_BMP, PREV_WORDS_INFO);
         assertEquals(wc.size(), STR_WITHIN_BMP.codePointCount(0, STR_WITHIN_BMP.length()));
         assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
         wc.setCursorPositionWithinWord(2);
@@ -57,7 +57,7 @@
         assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(1));
         assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
         // Check the previous word is still there
-        assertEquals(PREVWORD, wc.getPrevWordsInfoForSuggestion().mPrevWord);
+        assertEquals(PREV_WORDS_INFO, wc.getPrevWordsInfoForSuggestion());
         // Move the cursor past the end of the word
         assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(1));
         assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(15));
@@ -74,7 +74,7 @@
                 CoordinateUtils.newCoordinateArray(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR.length,
                         Constants.NOT_A_COORDINATE, Constants.NOT_A_COORDINATE);
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                null /* previousWord */);
+                new PrevWordsInfo(null));
         assertEquals(wc.size(), CODEPOINTS_WITH_SUPPLEMENTARY_CHAR.length);
         assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
         wc.setCursorPositionWithinWord(3);
@@ -85,46 +85,53 @@
         assertFalse(wc.isCursorFrontOrMiddleOfComposingWord());
         assertNull(wc.getPrevWordsInfoForSuggestion().mPrevWord);
 
+        final PrevWordsInfo PREV_WORDS_INFO_STR_WITHIN_BMP = new PrevWordsInfo(STR_WITHIN_BMP);
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                STR_WITHIN_BMP);
+                PREV_WORDS_INFO_STR_WITHIN_BMP);
         wc.setCursorPositionWithinWord(3);
         assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(7));
-        assertEquals(STR_WITHIN_BMP, wc.getPrevWordsInfoForSuggestion().mPrevWord);
+        assertEquals(PREV_WORDS_INFO_STR_WITHIN_BMP, wc.getPrevWordsInfoForSuggestion());
 
+        final PrevWordsInfo PREV_WORDS_INFO_STR_WITH_SUPPLEMENTARY_CHAR =
+                new PrevWordsInfo(STR_WITH_SUPPLEMENTARY_CHAR);
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                STR_WITH_SUPPLEMENTARY_CHAR);
+                PREV_WORDS_INFO_STR_WITH_SUPPLEMENTARY_CHAR);
         wc.setCursorPositionWithinWord(3);
         assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(7));
-        assertEquals(STR_WITH_SUPPLEMENTARY_CHAR, wc.getPrevWordsInfoForSuggestion().mPrevWord);
+        assertEquals(PREV_WORDS_INFO_STR_WITH_SUPPLEMENTARY_CHAR,
+                wc.getPrevWordsInfoForSuggestion());
 
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                STR_WITHIN_BMP);
+                PREV_WORDS_INFO_STR_WITHIN_BMP);
         wc.setCursorPositionWithinWord(3);
         assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(-3));
         assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(-1));
-        assertEquals(STR_WITHIN_BMP, wc.getPrevWordsInfoForSuggestion().mPrevWord);
+        assertEquals(PREV_WORDS_INFO_STR_WITHIN_BMP, wc.getPrevWordsInfoForSuggestion());
 
+
+        final PrevWordsInfo PREV_WORDS_INFO_NULL = new PrevWordsInfo(null);
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                null /* previousWord */);
+                PREV_WORDS_INFO_NULL);
         wc.setCursorPositionWithinWord(3);
         assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(-9));
         assertNull(wc.getPrevWordsInfoForSuggestion().mPrevWord);
 
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                STR_WITH_SUPPLEMENTARY_CHAR);
+                PREV_WORDS_INFO_STR_WITH_SUPPLEMENTARY_CHAR);
         assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(-10));
-        assertEquals(STR_WITH_SUPPLEMENTARY_CHAR, wc.getPrevWordsInfoForSuggestion().mPrevWord);
+        assertEquals(PREV_WORDS_INFO_STR_WITH_SUPPLEMENTARY_CHAR,
+                wc.getPrevWordsInfoForSuggestion());
 
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                null /* previousWord */);
+                PREV_WORDS_INFO_NULL);
         assertFalse(wc.moveCursorByAndReturnIfInsideComposingWord(-11));
 
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                null /* previousWord */);
+                PREV_WORDS_INFO_NULL);
         assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(0));
 
         wc.setComposingWord(CODEPOINTS_WITH_SUPPLEMENTARY_CHAR, COORDINATES_WITH_SUPPLEMENTARY_CHAR,
-                null /* previousWord */);
+                PREV_WORDS_INFO_NULL);
         wc.setCursorPositionWithinWord(2);
         assertTrue(wc.moveCursorByAndReturnIfInsideComposingWord(0));
     }
diff --git a/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java
index dab9a43..a04b810 100644
--- a/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java
+++ b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java
@@ -19,6 +19,7 @@
 import com.android.inputmethod.annotations.UsedForTesting;
 import com.android.inputmethod.latin.BinaryDictionary;
 import com.android.inputmethod.latin.Dictionary;
+import com.android.inputmethod.latin.PrevWordsInfo;
 import com.android.inputmethod.latin.makedict.FormatSpec.FormatOptions;
 import com.android.inputmethod.latin.makedict.FusionDictionary.PtNode;
 import com.android.inputmethod.latin.utils.BinaryDictionaryUtils;
@@ -74,13 +75,13 @@
         for (final WordProperty wordProperty : dict) {
             // TODO: switch to addMultipleDictionaryEntries when they support shortcuts
             if (null == wordProperty.mShortcutTargets || wordProperty.mShortcutTargets.isEmpty()) {
-                binaryDict.addUnigramWord(wordProperty.mWord, wordProperty.getProbability(),
+                binaryDict.addUnigramEntry(wordProperty.mWord, wordProperty.getProbability(),
                         null /* shortcutTarget */, 0 /* shortcutProbability */,
                         wordProperty.mIsNotAWord, wordProperty.mIsBlacklistEntry,
                         0 /* timestamp */);
             } else {
                 for (final WeightedString shortcutTarget : wordProperty.mShortcutTargets) {
-                    binaryDict.addUnigramWord(wordProperty.mWord, wordProperty.getProbability(),
+                    binaryDict.addUnigramEntry(wordProperty.mWord, wordProperty.getProbability(),
                             shortcutTarget.mWord, shortcutTarget.getProbability(),
                             wordProperty.mIsNotAWord, wordProperty.mIsBlacklistEntry,
                             0 /* timestamp */);
@@ -93,8 +94,8 @@
         for (final WordProperty word0Property : dict) {
             if (null == word0Property.mBigrams) continue;
             for (final WeightedString word1 : word0Property.mBigrams) {
-                binaryDict.addBigramWords(word0Property.mWord, word1.mWord, word1.getProbability(),
-                        0 /* timestamp */);
+                binaryDict.addNgramEntry(new PrevWordsInfo(word0Property.mWord), word1.mWord,
+                        word1.getProbability(), 0 /* timestamp */);
                 if (binaryDict.needsToRunGC(true /* mindsBlockByGC */)) {
                     binaryDict.flushWithGC();
                 }
diff --git a/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
index f2d7b76..bc86864 100644
--- a/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
+++ b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
@@ -21,6 +21,7 @@
 import android.util.Log;
 
 import com.android.inputmethod.latin.ExpandableBinaryDictionary;
+import com.android.inputmethod.latin.PrevWordsInfo;
 import com.android.inputmethod.latin.utils.BinaryDictionaryUtils;
 import com.android.inputmethod.latin.utils.CollectionUtils;
 import com.android.inputmethod.latin.utils.FileUtils;
@@ -109,11 +110,11 @@
     }
 
     private static void addToDict(final UserHistoryDictionary dict, final List<String> words) {
-        String prevWord = null;
+        PrevWordsInfo prevWordsInfo = new PrevWordsInfo(null);
         for (String word : words) {
-            UserHistoryDictionary.addToDictionary(dict, prevWord, word, true,
+            UserHistoryDictionary.addToDictionary(dict, prevWordsInfo, word, true,
                     (int)TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis()));
-            prevWord = word;
+            prevWordsInfo = new PrevWordsInfo(word);
         }
     }
 
@@ -260,10 +261,10 @@
         final UserHistoryDictionary dict =
                 PersonalizationHelper.getUserHistoryDictionary(getContext(), dummyLocale);
         dict.waitAllTasksForTests();
-        String prevWord = null;
+        PrevWordsInfo prevWordsInfo = new PrevWordsInfo(null);
         for (final String word : words) {
-            UserHistoryDictionary.addToDictionary(dict, prevWord, word, true, mCurrentTime);
-            prevWord = word;
+            UserHistoryDictionary.addToDictionary(dict, prevWordsInfo, word, true, mCurrentTime);
+            prevWordsInfo = new PrevWordsInfo(word);
             dict.waitAllTasksForTests();
             assertTrue(dict.isInUnderlyingBinaryDictionaryForTests(word));
         }