java - 需要更快的 Word Builder 算法

Question

我有一个应用程序可以帮助学习拼字游戏。除了 Word Builder 之外，大多数搜索都比 C# 中的桌面版本快得多。此搜索显示可以由一组给定的字母 A-Z 或空格组成的所有单词。 我该怎么做才能让它运行得更快？ 我考虑过使用 Trie，但还没有找到支持使用空格的方法。 我正在使用 SimpleCursorAdapter 来填充 ListView，这就是我返回游标的原因。

    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;
    }

Answer 1

专注于加速最典型的情况，即单词不是(子)字谜，您返回 false。如果您可以在无法从 anagram 中生成 word 时尽快识别，那么您就可以避免昂贵的测试。

一种方法是使用单词中字母的位掩码。您不需要存储字母数，因为如果 word 中不在 anagram 中的唯一字母数大于空格数，则没有你可以做到的方式，你可以快速返回 false。如果没有，那么您可以继续进行更昂贵的测试，并将字母计数考虑在内。

您可以像这样预先计算位掩码:

private int letterMask(char[] word)
{
    int c, mask = 0;
    for (c = 0; c < word.length; c++)
        mask |= (1 << (word[c] - 'A'));
    return mask;
}

在您的数据库中添加一个额外的列来存储每个单词的字母位掩码，将其添加到您的游标中，并为 term 中的字母计算字母位掩码并存储在 termMask。然后在你的光标循环中你可以做这样的测试:

// 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: