Htykuut

I have an app that assists studying for Scrabble. Most searches are much faster than by desktop version in C#, except the Word Builder. This search shows all the words that can be formed from a given set of letters A-Z, or blanks.
What can I do to get it to run faster?
I've considered using a Trie, but haven't found a way to support the use of blanks.
I am using a SimpleCursorAdapter to populate the ListView, which is why I am returning a cursor.

    public Cursor getCursor_subanagrams(String term, String filters, String ordering) {

    if (term.trim() == "")

        return null;

    // only difference between this and anagram is changing the length filter

    char a = term.toCharArray(); // anagram



    int first = new int[26]; // letter count of anagram

    int c; // array position

    int blankcount = 0;



    // initialize word to anagram

    for (c = 0; c < a.length; c++) {

        if (a[c] == '?') {

            blankcount++;

            continue;

        }

        first[a[c] - 'A']++;

    }



// gets pool of words to search through

    String lenFilter = String.format("Length(Word) <= %1$s AND Length(Word) <= %2$s", LexData.getMaxLength(), term.length());

    Cursor cursor = database.rawQuery("SELECT WordID as _id, Word, WordID, FrontHooks, BackHooks, " +

            "InnerFront, InnerBack, Anagrams, ProbFactor, OPlayFactor, Score n" +

            "FROM     `" + LexData.getLexName() + "` n" +

            "WHERE (" + lenFilter +

            filters +

            " ) " + ordering, null);



// creates new cursor to add valid words to

    MatrixCursor matrixCursor = new MatrixCursor(new String{"_id", "Word", "WordID", "FrontHooks", "BackHooks", "InnerFront", "InnerBack",

            "Anagrams", "ProbFactor", "OPlayFactor", "Score"});



// THIS NEEDS TO BE FASTER

    while (cursor.moveToNext()) {

        String word = cursor.getString(1);

        char b = word.toCharArray();

        if (isAnagram(first, b, blankcount)) {

            matrixCursor.addRow(get_CursorRow(cursor));

        }

    }

    cursor.close();

    return matrixCursor;

}





private boolean isAnagram(int anagram, char word, int blankcount) {

    int matchcount = blankcount;

    int c; // each letter

    int second = {0,0,0,0,0, 0,0,0,0,0,  0,0,0,0,0,  0,0,0,0,0,  0,0,0,0,0, 0};



    for (c = 0; c < word.length; c++)

        second[word[c] - 'A']++;



    for (c = 0; c < 26; c++)

    {

        matchcount += (anagram[c]<second[c]) ? anagram[c]:second[c];

    }



    if (matchcount == word.length)

        return true;

    return false;

    }

Focus on speeding up the most typical case, which is where the word is not a (sub)anagram, and you return false. If you can identify as quickly as possible when it is not possible to make word out of anagram then you can avoid the expensive test.

One way to do this is using a bitmask of the letters in the words. You don't need to store letter counts, because if the number of unique letters in word that are not in anagram is greater than the number of blanks, then there is no way you can make it and you can quickly return false. If not then you can proceed to the more expensive test taking letter counts into account.

You can precompute the bitmasks like this:

private int letterMask(char word)

{

    int c, mask = 0;

    for (c = 0; c < word.length; c++)

        mask |= (1 << (word[c] - 'A'));

    return mask;

}

Add an extra column to your database to store the letter bitmask for each word, add it to your cursor, and compute the letter bitmask for the letters in term and store in termMask. Then inside your cursor loop you can do a test like this:

// compute mask of bits in mask that are not in term:

int missingLettersMask = cursor.getInt(8) & ~termMask;

if(missingLettersMask != 0)

{

    // check if we could possibly make up for these letters using blanks:

    int remainingBlanks = blankcount;

    while((remainingBlanks-- > 0) && (missingLettersMask != 0))

        missingLettersMask &= (missingLettersMask - 1); // remove one bit



    if(missingLettersMask != 0)

        continue; // move onto the next word

}



// word can potentially be made from anagram, call isAnagram:

There are ways to speed up your anagram checking function. Samgak has pointed out one. Another obvious optimisation is to return false if the word is longer than the number of available letters plus blanks. In the end, these are all micro-optimisations and you will end up checking your whole dictionary.

You said you have considered using a trie. That's a good solution, in my opinion, because the structure of the trie will only make you check relevant words. Build it like this:

• Sort the letters of each word, so that "triangle" and "integral" will both become "aegilnrt".


• Insert the sorted word into the trie.


• Where you would place the end-marker in a normal trie, you place a list of possible words.

If you were looking for exact anagrams, you would sort the word to check, traverse the trie and print out the list of possible anagrams at the end. But here, you have to deal with partial anagrams and with blanks:

• Regular traversal means you take the next letter of the word and then descent the corresponding link in the tree,if it exists.


• Partial anagrams can be found by ignoring the next letter without descending in the trie.


• Blanks can be dealt with by descending all possible branches of a trie and decreasing the number of blanks.

When you have blanks, you will end up with duplicates. For example, if you have the letters A, B and C and a blank tile, you can make the word CAB, but you can get there on four different ways: CAB, _AB, C_B, CA_.

You could get around this by storing the result list in a data structure that eliminates duplicates, such as a set or ordered set, but you would still go down the same paths several times in order to create the duplicates.

A better solution is to keep track of which trie nodes you have visited with which parameters, i.e. with with remaining unused letters and blanks. You can then cut such paths short. Here's an implementation in pseudocode:

function find_r(t, str, blanks, visited)

{

    // don't revisit explored paths

    key = make_key(t, str, blanks);



    if (key in visited) return ;

    visited ~= key;



    if (str.length == 0 and blanks == 0) {   

        // all resources have been used: return list of anagrams        

        return t.word;

    } else {

        res = ;

        c = 0;



        if (str.length > 0) {

            c = str[0];



            // regular traversal: use current letter and descend

            if (c in t.next) {

                res ~= find_r(t.next[c], str[1:], blanks, visited);

            }



            # partial anagrams: skip current letter and don't descend

            l = 1

            while (l < str.length and str[l] == c) l++;



            res ~= find_r(t, str[l:], blanks, visited);

        }



        if (blanks > 0) {

            // blanks: decrease blanks and descend

            for (i in t.next) {

                if (i < c) {

                    res ~= find_r(t.next[i], str, blanks - 1, visited);

                }

            }

        }



        return res;

    }

}

(Here, ~ denotes list concatenation or set insertion; [beg=0:end=length] denotes string slices; in tests whether a dictionary or set contains a key.)

Once you've built the tree, this solution is fast when there are no blanks, but it gets exponentially worse with each blank and with larger letter pools. Testing with one blank is still reasonably fast, but with two blanks, it is on par with your existing solution.

Now there are at most two blanks in a Scrabble game and the rack can hold only up to seven tiles, so it may not be as bad in practice. Another question is whether the search should consider words obtained with two blanks. The results list will be very long and it will contain all two-letter words. The player may be more interested in high-scoring words that can be played with a single blank.

I used samgak's recommendation to check for "mismatches".
Instead of going through the process of checking each letter before continuing, I exit during the process of checking each letter. I thought I could just check mismatches and ignore matchcounting, but couldn't get it to work accurately. More analysis must be needed.

This speeded things up about 20% according to initial tests with an emulator.
I may be able to speed things up even more by checking letters based on letter frequency; check most common letters(LNSTE) before others (ZQJ). Now to figure out how to sort an array by one field in the array, but that's another question.

    private boolean isAnagram(int anagram, char word, int blankcount) {

    // anagram is letters in term

    int matchcount = blankcount;

    int mismatchcount = 0;

    int c;

    int second = {0,0,0,0,0, 0,0,0,0,0,  0,0,0,0,0,  0,0,0,0,0,  0,0,0,0,0, 0};



    for (c = 0; c < word.length; c++)

        second[word[c] - 'A']++;



    for (c = 0; c < 26; c++)

    {

        mismatchcount += (anagram[c]<second[c] ? second[c] - anagram[c]:0);             

        if (mismatchcount > blankcount)

            return false;

        matchcount += (anagram[c]<second[c]) ? anagram[c]:second[c];

    }



    if (matchcount == word.length)

        return true;

    return false;

}

EDIT:
Here's an even more compact (faster?) version that counts mismatches as it builds the alternate word character array.

    private boolean isAnagram(int anagram, char word, int blankcount) {

    int mismatchcount = 0;

    int c;

    int second = {0,0,0,0,0, 0,0,0,0,0,  0,0,0,0,0,  0,0,0,0,0,  0,0,0,0,0, 0};

    int letter = 0;



    for (c = 0; c < word.length; c++) {

        letter = ++second[word[c] - 'A'];

        mismatchcount += (letter > anagram[word[c]-'A'] ? 1 : 0);

        if (mismatchcount > blankcount)

            return false;

    }

    return true;

}