diff options
Diffstat (limited to 'java/src/com/android/inputmethod/latin')
6 files changed, 333 insertions, 40 deletions
diff --git a/java/src/com/android/inputmethod/latin/BinaryDictionary.java b/java/src/com/android/inputmethod/latin/BinaryDictionary.java index a644ec0d9..cc20f4294 100644 --- a/java/src/com/android/inputmethod/latin/BinaryDictionary.java +++ b/java/src/com/android/inputmethod/latin/BinaryDictionary.java @@ -17,6 +17,7 @@ package com.android.inputmethod.latin; import android.content.Context; +import android.text.TextUtils; import com.android.inputmethod.keyboard.ProximityInfo; @@ -84,6 +85,7 @@ public class BinaryDictionary extends Dictionary { int typedLetterMultiplier, int fullWordMultiplier, int maxWordLength, int maxWords); private native void closeNative(long dict); private native boolean isValidWordNative(long dict, int[] word, int wordLength); + private native boolean isValidBigramNative(long dict, int[] word1, int[] word2); private native int getSuggestionsNative(long dict, long proximityInfo, int[] xCoordinates, int[] yCoordinates, int[] inputCodes, int codesSize, int[] prevWordForBigrams, boolean useFullEditDistance, char[] outputChars, int[] scores); @@ -204,6 +206,15 @@ public class BinaryDictionary extends Dictionary { return isValidWordNative(mNativeDict, chars, chars.length); } + // TODO: Add a batch process version (isValidBigramMultiple?) to avoid excessive numbers of jni + // calls when checking for changes in an entire dictionary. + public boolean isValidBigram(CharSequence word1, CharSequence word2) { + if (TextUtils.isEmpty(word1) || TextUtils.isEmpty(word2)) return false; + int[] chars1 = StringUtils.toCodePointArray(word1.toString()); + int[] chars2 = StringUtils.toCodePointArray(word2.toString()); + return isValidBigramNative(mNativeDict, chars1, chars2); + } + @Override public synchronized void close() { closeInternal(); diff --git a/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java index 65f97e987..22787c218 100644 --- a/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java +++ b/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java @@ -18,6 +18,7 @@ import android.content.ContentResolver; import android.content.Context; import android.database.ContentObserver; import android.database.Cursor; +import android.os.SystemClock; import android.provider.BaseColumns; import android.provider.ContactsContract.Contacts; import android.text.TextUtils; @@ -30,18 +31,27 @@ import java.util.Locale; public class ContactsBinaryDictionary extends ExpandableBinaryDictionary { private static final String[] PROJECTION = {BaseColumns._ID, Contacts.DISPLAY_NAME,}; + private static final String[] PROJECTION_ID_ONLY = {BaseColumns._ID}; private static final String TAG = ContactsBinaryDictionary.class.getSimpleName(); private static final String NAME = "contacts"; + private static boolean DEBUG = false; + /** * Frequency for contacts information into the dictionary */ private static final int FREQUENCY_FOR_CONTACTS = 40; private static final int FREQUENCY_FOR_CONTACTS_BIGRAM = 90; + /** The maximum number of contacts that this dictionary supports. */ + private static final int MAX_CONTACT_COUNT = 10000; + private static final int INDEX_NAME = 1; + /** The number of contacts in the most recent dictionary rebuild. */ + static private int sContactCountAtLastRebuild = 0; + private ContentObserver mObserver; /** @@ -98,6 +108,7 @@ public class ContactsBinaryDictionary extends ExpandableBinaryDictionary { if (cursor != null) { try { if (cursor.moveToFirst()) { + sContactCountAtLastRebuild = getContactCount(); addWords(cursor); } } finally { @@ -125,15 +136,28 @@ public class ContactsBinaryDictionary extends ExpandableBinaryDictionary { private void addWords(Cursor cursor) { clearFusionDictionary(); - while (!cursor.isAfterLast()) { + int count = 0; + while (!cursor.isAfterLast() && count < MAX_CONTACT_COUNT) { String name = cursor.getString(INDEX_NAME); - if (name != null && -1 == name.indexOf('@')) { + if (isValidName(name)) { addName(name); + ++count; } cursor.moveToNext(); } } + private int getContactCount() { + // TODO: consider switching to a rawQuery("select count(*)...") on the database if + // performance is a bottleneck. + final Cursor cursor = mContext.getContentResolver().query( + Contacts.CONTENT_URI, PROJECTION_ID_ONLY, null, null, null); + if (cursor != null) { + return cursor.getCount(); + } + return 0; + } + /** * Adds the words in a name (e.g., firstname/lastname) to the binary dictionary along with their * bigrams depending on locale. @@ -144,16 +168,9 @@ public class ContactsBinaryDictionary extends ExpandableBinaryDictionary { // TODO: Better tokenization for non-Latin writing systems for (int i = 0; i < len; i++) { if (Character.isLetter(name.codePointAt(i))) { - int j; - for (j = i + 1; j < len; j++) { - final int codePoint = name.codePointAt(j); - if (!(codePoint == Keyboard.CODE_DASH || codePoint == Keyboard.CODE_SINGLE_QUOTE - || Character.isLetter(codePoint))) { - break; - } - } - String word = name.substring(i, j); - i = j - 1; + int end = getWordEndPosition(name, len, i); + String word = name.substring(i, end); + i = end - 1; // Don't add single letter words, possibly confuses // capitalization of i. final int wordLen = word.codePointCount(0, word.length()); @@ -169,4 +186,100 @@ public class ContactsBinaryDictionary extends ExpandableBinaryDictionary { } } } + + /** + * Returns the index of the last letter in the word, starting from position startIndex. + */ + private static int getWordEndPosition(String string, int len, int startIndex) { + int end; + int cp = 0; + for (end = startIndex + 1; end < len; end += Character.charCount(cp)) { + cp = string.codePointAt(end); + if (!(cp == Keyboard.CODE_DASH || cp == Keyboard.CODE_SINGLE_QUOTE + || Character.isLetter(cp))) { + break; + } + } + return end; + } + + @Override + protected boolean hasContentChanged() { + final long startTime = SystemClock.uptimeMillis(); + final int contactCount = getContactCount(); + if (contactCount > MAX_CONTACT_COUNT) { + // If there are too many contacts then return false. In this rare case it is impossible + // to include all of them anyways and the cost of rebuilding the dictionary is too high. + // TODO: Sort and check only the MAX_CONTACT_COUNT most recent contacts? + return false; + } + if (contactCount != sContactCountAtLastRebuild) { + return true; + } + // Check all contacts since it's not possible to find out which names have changed. + // This is needed because it's possible to receive extraneous onChange events even when no + // name has changed. + Cursor cursor = mContext.getContentResolver().query( + Contacts.CONTENT_URI, PROJECTION, null, null, null); + if (cursor != null) { + try { + if (cursor.moveToFirst()) { + while (!cursor.isAfterLast()) { + String name = cursor.getString(INDEX_NAME); + if (isValidName(name) && !isNameInDictionary(name)) { + if (DEBUG) { + Log.d(TAG, "Contact name missing: " + name + " (runtime = " + + (SystemClock.uptimeMillis() - startTime) + " ms)"); + } + return true; + } + cursor.moveToNext(); + } + } + } finally { + cursor.close(); + } + } + if (DEBUG) { + Log.d(TAG, "No contacts changed. (runtime = " + (SystemClock.uptimeMillis() - startTime) + + " ms)"); + } + return false; + } + + private static boolean isValidName(String name) { + if (name != null && -1 == name.indexOf('@')) { + return true; + } + return false; + } + + /** + * Checks if the words in a name are in the current binary dictionary. + */ + private boolean isNameInDictionary(String name) { + int len = name.codePointCount(0, name.length()); + String prevWord = null; + for (int i = 0; i < len; i++) { + if (Character.isLetter(name.codePointAt(i))) { + int end = getWordEndPosition(name, len, i); + String word = name.substring(i, end); + i = end - 1; + final int wordLen = word.codePointCount(0, word.length()); + if (wordLen < MAX_WORD_LENGTH && wordLen > 1) { + if (!TextUtils.isEmpty(prevWord) && mUseFirstLastBigrams) { + if (!super.isValidBigramLocked(prevWord, word)) { + return false; + } + } else { + if (!super.isValidWordLocked(word)) { + return false; + } + } + prevWord = word; + } + } + } + return true; + } } diff --git a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java index 3d89226c0..22d8f24f1 100644 --- a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java +++ b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java @@ -96,6 +96,13 @@ abstract public class ExpandableBinaryDictionary extends Dictionary { protected abstract void loadDictionaryAsync(); /** + * Indicates that the source dictionary content has changed and a rebuild of the binary file is + * required. If it returns false, the next reload will only read the current binary dictionary + * from file. Note that the shared binary dictionary is locked when this is called. + */ + protected abstract boolean hasContentChanged(); + + /** * Gets the shared dictionary controller for the given filename. */ private static synchronized DictionaryController getSharedDictionaryController( @@ -148,8 +155,9 @@ abstract public class ExpandableBinaryDictionary extends Dictionary { * the native side. */ public void clearFusionDictionary() { - mFusionDictionary = new FusionDictionary(new Node(), new FusionDictionary.DictionaryOptions( - new HashMap<String, String>(), false, false)); + mFusionDictionary = new FusionDictionary(new Node(), + new FusionDictionary.DictionaryOptions(new HashMap<String, String>(), false, + false)); } /** @@ -224,9 +232,7 @@ abstract public class ExpandableBinaryDictionary extends Dictionary { protected boolean isValidWordInner(final CharSequence word) { if (mLocalDictionaryController.tryLock()) { try { - if (mBinaryDictionary != null) { - return mBinaryDictionary.isValidWord(word); - } + return isValidWordLocked(word); } finally { mLocalDictionaryController.unlock(); } @@ -234,6 +240,32 @@ abstract public class ExpandableBinaryDictionary extends Dictionary { return false; } + protected boolean isValidWordLocked(final CharSequence word) { + if (mBinaryDictionary == null) return false; + return mBinaryDictionary.isValidWord(word); + } + + protected boolean isValidBigram(final CharSequence word1, final CharSequence word2) { + if (mBinaryDictionary == null) return false; + return mBinaryDictionary.isValidBigram(word1, word2); + } + + protected boolean isValidBigramInner(final CharSequence word1, final CharSequence word2) { + if (mLocalDictionaryController.tryLock()) { + try { + return isValidBigramLocked(word1, word2); + } finally { + mLocalDictionaryController.unlock(); + } + } + return false; + } + + protected boolean isValidBigramLocked(final CharSequence word1, final CharSequence word2) { + if (mBinaryDictionary == null) return false; + return mBinaryDictionary.isValidBigram(word1, word2); + } + /** * Load the current binary dictionary from internal storage in a background thread. If no binary * dictionary exists, this method will generate one. @@ -315,12 +347,16 @@ abstract public class ExpandableBinaryDictionary extends Dictionary { } /** - * Sets whether or not the dictionary is out of date and requires a reload. + * Marks that the dictionary is out of date and requires a reload. + * + * @param requiresRebuild Indicates that the source dictionary content has changed and a rebuild + * of the binary file is required. If not true, the next reload process will only read + * the current binary dictionary from file. */ - protected void setRequiresReload(final boolean reload) { - final long time = reload ? SystemClock.uptimeMillis() : 0; - mSharedDictionaryController.mLastUpdateRequestTime = time; + protected void setRequiresReload(final boolean requiresRebuild) { + final long time = SystemClock.uptimeMillis(); mLocalDictionaryController.mLastUpdateRequestTime = time; + mSharedDictionaryController.mLastUpdateRequestTime = time; if (DEBUG) { Log.d(TAG, "Reload request: request=" + time + " update=" + mSharedDictionaryController.mLastUpdateTime); @@ -351,21 +387,30 @@ abstract public class ExpandableBinaryDictionary extends Dictionary { if (mSharedDictionaryController.isOutOfDate() || !dictionaryFileExists()) { // If the shared dictionary file does not exist or is out of date, the first // instance that acquires the lock will generate a new one. - mSharedDictionaryController.mLastUpdateTime = time; - mLocalDictionaryController.mLastUpdateTime = time; - generateBinaryDictionary(); - loadBinaryDictionary(); - } else if (mLocalDictionaryController.isOutOfDate()) { - // Otherwise, if only the local dictionary for this instance is out of date, load - // the shared dictionary from file. - mLocalDictionaryController.mLastUpdateTime = time; + if (hasContentChanged()) { + // If the source content has changed, rebuild the binary dictionary. + mSharedDictionaryController.mLastUpdateTime = time; + generateBinaryDictionary(); + loadBinaryDictionary(); + } else { + // If not, the reload request was unnecessary so revert LastUpdateRequestTime + // to LastUpdateTime. + mSharedDictionaryController.mLastUpdateRequestTime = + mSharedDictionaryController.mLastUpdateTime; + } + } else if (mBinaryDictionary == null || mLocalDictionaryController.mLastUpdateTime + < mSharedDictionaryController.mLastUpdateTime) { + // Otherwise, if the local dictionary is older than the shared dictionary, load the + // shared dictionary. loadBinaryDictionary(); } + mLocalDictionaryController.mLastUpdateTime = time; } finally { mSharedDictionaryController.unlock(); } } + // TODO: cache the file's existence so that we avoid doing a disk access each time. private boolean dictionaryFileExists() { final File file = new File(mContext.getFilesDir(), mFilename); return file.exists(); diff --git a/java/src/com/android/inputmethod/latin/LatinIME.java b/java/src/com/android/inputmethod/latin/LatinIME.java index b7385ed21..70ff69a93 100644 --- a/java/src/com/android/inputmethod/latin/LatinIME.java +++ b/java/src/com/android/inputmethod/latin/LatinIME.java @@ -635,6 +635,12 @@ public class LatinIME extends InputMethodService implements KeyboardActionListen Log.d(TAG, "onStartInputView: editorInfo:" + String.format("inputType=0x%08x imeOptions=0x%08x", editorInfo.inputType, editorInfo.imeOptions)); + Log.d(TAG, "All caps = " + + ((editorInfo.inputType & InputType.TYPE_TEXT_FLAG_CAP_CHARACTERS) != 0) + + ", sentence caps = " + + ((editorInfo.inputType & InputType.TYPE_TEXT_FLAG_CAP_SENTENCES) != 0) + + ", word caps = " + + ((editorInfo.inputType & InputType.TYPE_TEXT_FLAG_CAP_WORDS) != 0)); } if (ProductionFlag.IS_EXPERIMENTAL) { ResearchLogger.latinIME_onStartInputViewInternal(editorInfo, mPrefs); diff --git a/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java b/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java index d82d503c4..3c818cc56 100644 --- a/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java +++ b/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java @@ -174,6 +174,7 @@ public class BinaryDictInputOutput { private static final int MAX_CHARGROUPS_IN_A_NODE = 0x7FFF; // 32767 private static final int MAX_TERMINAL_FREQUENCY = 255; + private static final int MAX_BIGRAM_FREQUENCY = 15; // Arbitrary limit to how much passes we consider address size compression should // terminate in. At the time of this writing, our largest dictionary completes @@ -722,15 +723,17 @@ public class BinaryDictInputOutput { } /** - * Makes the flag value for an attribute. + * Makes the flag value for a bigram. * - * @param more whether there are more attributes after this one. - * @param offset the offset of the attribute. - * @param frequency the frequency of the attribute, 0..15 + * @param more whether there are more bigrams after this one. + * @param offset the offset of the bigram. + * @param bigramFrequency the frequency of the bigram, 0..255. + * @param unigramFrequency the unigram frequency of the same word, 0..255. + * @param word the second bigram, for debugging purposes * @return the flags */ - private static final int makeAttributeFlags(final boolean more, final int offset, - final int frequency) { + private static final int makeBigramFlags(final boolean more, final int offset, + int bigramFrequency, final int unigramFrequency, final String word) { int bigramFlags = (more ? FLAG_ATTRIBUTE_HAS_NEXT : 0) + (offset < 0 ? FLAG_ATTRIBUTE_OFFSET_NEGATIVE : 0); switch (getByteSize(offset)) { @@ -746,7 +749,21 @@ public class BinaryDictInputOutput { default: throw new RuntimeException("Strange offset size"); } - bigramFlags += frequency & FLAG_ATTRIBUTE_FREQUENCY; + if (unigramFrequency > bigramFrequency) { + MakedictLog.e("Unigram freq is superior to bigram freq for \"" + word + + "\". Bigram freq is " + bigramFrequency + ", unigram freq for " + + word + " is " + unigramFrequency); + bigramFrequency = unigramFrequency; + } + // We compute the difference between 255 (which means probability = 1) and the + // unigram score. We split this into discrete 16 steps, and this is the value + // we store into the 4 bits of the bigrams frequency. + final float bigramRatio = (float)(bigramFrequency - unigramFrequency) + / (MAX_TERMINAL_FREQUENCY - unigramFrequency); + // TODO: if the bigram freq is very close to the unigram frequency, we don't want + // to include the bigram in the binary dictionary at all. + final int discretizedFrequency = Math.round(bigramRatio * MAX_BIGRAM_FREQUENCY); + bigramFlags += discretizedFrequency & FLAG_ATTRIBUTE_FREQUENCY; return bigramFlags; } @@ -854,11 +871,14 @@ public class BinaryDictInputOutput { final Iterator bigramIterator = group.mBigrams.iterator(); while (bigramIterator.hasNext()) { final WeightedString bigram = (WeightedString)bigramIterator.next(); - final int addressOfBigram = findAddressOfWord(dict, bigram.mWord); + final CharGroup target = + FusionDictionary.findWordInTree(dict.mRoot, bigram.mWord); + final int addressOfBigram = target.mCachedAddress; + final int unigramFrequencyForThisWord = target.mFrequency; ++groupAddress; final int offset = addressOfBigram - groupAddress; - int bigramFlags = makeAttributeFlags(bigramIterator.hasNext(), offset, - bigram.mFrequency); + int bigramFlags = makeBigramFlags(bigramIterator.hasNext(), offset, + bigram.mFrequency, unigramFrequencyForThisWord, bigram.mWord); buffer[index++] = (byte)bigramFlags; final int bigramShift = writeVariableAddress(buffer, index, Math.abs(offset)); index += bigramShift; diff --git a/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerService.java b/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerService.java index f41645283..6f7f0c333 100644 --- a/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerService.java +++ b/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerService.java @@ -23,6 +23,7 @@ import android.service.textservice.SpellCheckerService; import android.text.TextUtils; import android.util.Log; import android.util.LruCache; +import android.view.textservice.SentenceSuggestionsInfo; import android.view.textservice.SuggestionsInfo; import android.view.textservice.TextInfo; @@ -392,7 +393,10 @@ public class AndroidSpellCheckerService extends SpellCheckerService public DictAndProximity createDictAndProximity(final Locale locale) { final int script = getScriptFromLocale(locale); final ProximityInfo proximityInfo = ProximityInfo.createSpellCheckerProximityInfo( - SpellCheckerProximityInfo.getProximityForScript(script)); + SpellCheckerProximityInfo.getProximityForScript(script), + SpellCheckerProximityInfo.ROW_SIZE, + SpellCheckerProximityInfo.PROXIMITY_GRID_WIDTH, + SpellCheckerProximityInfo.PROXIMITY_GRID_HEIGHT); final DictionaryCollection dictionaryCollection = DictionaryFactory.createDictionaryFromManager(this, locale, true /* useFullEditDistance */); @@ -484,6 +488,10 @@ public class AndroidSpellCheckerService extends SpellCheckerService } mUnigramSuggestionsInfoCache.put(query, new SuggestionsParams(suggestions, flags)); } + + public void remove(String key) { + mUnigramSuggestionsInfoCache.remove(key); + } } AndroidSpellCheckerSession(final AndroidSpellCheckerService service) { @@ -566,6 +574,96 @@ public class AndroidSpellCheckerService extends SpellCheckerService return (letterCount * 4 < length * 3); } + private SentenceSuggestionsInfo fixWronglyInvalidatedWordWithSingleQuote( + TextInfo ti, SentenceSuggestionsInfo ssi) { + final String typedText = ti.getText(); + if (!typedText.contains(SINGLE_QUOTE)) { + return null; + } + final int N = ssi.getSuggestionsCount(); + final ArrayList<Integer> additionalOffsets = new ArrayList<Integer>(); + final ArrayList<Integer> additionalLengths = new ArrayList<Integer>(); + final ArrayList<SuggestionsInfo> additionalSuggestionsInfos = + new ArrayList<SuggestionsInfo>(); + for (int i = 0; i < N; ++i) { + final SuggestionsInfo si = ssi.getSuggestionsInfoAt(i); + final int flags = si.getSuggestionsAttributes(); + if ((flags & SuggestionsInfo.RESULT_ATTR_IN_THE_DICTIONARY) == 0) { + continue; + } + final int offset = ssi.getOffsetAt(i); + final int length = ssi.getLengthAt(i); + final String subText = typedText.substring(offset, offset + length); + if (!subText.contains(SINGLE_QUOTE)) { + continue; + } + final String[] splitTexts = subText.split(SINGLE_QUOTE, -1); + if (splitTexts == null || splitTexts.length <= 1) { + continue; + } + final int splitNum = splitTexts.length; + for (int j = 0; j < splitNum; ++j) { + final String splitText = splitTexts[j]; + if (TextUtils.isEmpty(splitText)) { + continue; + } + if (mSuggestionsCache.getSuggestionsFromCache(splitText) == null) { + continue; + } + final int newLength = splitText.length(); + // Neither RESULT_ATTR_IN_THE_DICTIONARY nor RESULT_ATTR_LOOKS_LIKE_TYPO + final int newFlags = 0; + final SuggestionsInfo newSi = new SuggestionsInfo(newFlags, EMPTY_STRING_ARRAY); + newSi.setCookieAndSequence(si.getCookie(), si.getSequence()); + if (DBG) { + Log.d(TAG, "Override and remove old span over: " + + splitText + ", " + offset + "," + newLength); + } + additionalOffsets.add(offset); + additionalLengths.add(newLength); + additionalSuggestionsInfos.add(newSi); + } + } + final int additionalSize = additionalOffsets.size(); + if (additionalSize <= 0) { + return null; + } + final int suggestionsSize = N + additionalSize; + final int[] newOffsets = new int[suggestionsSize]; + final int[] newLengths = new int[suggestionsSize]; + final SuggestionsInfo[] newSuggestionsInfos = new SuggestionsInfo[suggestionsSize]; + int i; + for (i = 0; i < N; ++i) { + newOffsets[i] = ssi.getOffsetAt(i); + newLengths[i] = ssi.getLengthAt(i); + newSuggestionsInfos[i] = ssi.getSuggestionsInfoAt(i); + } + for (; i < suggestionsSize; ++i) { + newOffsets[i] = additionalOffsets.get(i - N); + newLengths[i] = additionalLengths.get(i - N); + newSuggestionsInfos[i] = additionalSuggestionsInfos.get(i - N); + } + return new SentenceSuggestionsInfo(newSuggestionsInfos, newOffsets, newLengths); + } + + @Override + public SentenceSuggestionsInfo[] onGetSentenceSuggestionsMultiple( + TextInfo[] textInfos, int suggestionsLimit) { + final SentenceSuggestionsInfo[] retval = super.onGetSentenceSuggestionsMultiple( + textInfos, suggestionsLimit); + if (retval == null || retval.length != textInfos.length) { + return retval; + } + for (int i = 0; i < retval.length; ++i) { + final SentenceSuggestionsInfo tempSsi = + fixWronglyInvalidatedWordWithSingleQuote(textInfos[i], retval[i]); + if (tempSsi != null) { + retval[i] = tempSsi; + } + } + return retval; + } + // Note : this must be reentrant /** * Gets a list of suggestions for a specific string. This returns a list of possible |