在 java 中创建单词的高效算法

Question

我正在使用 libGDX 框架开发一个文字游戏，我想实现一个基本的提示功能，系统可以根据该功能从棋盘上提供的 17 个字母中生成一个有效的 7 个字母的单词。现在，船上 17 个字母（可供选择）的设置是完全随机的，所以我不能使用预先确定的提示词来提示（比如 4 图片 1 个单词）。

我的解决方案是通过从提供的 17 个字母中找到所有可能的 7 个字母组合来进行一些组合。接下来，我排列了每个组合并使用 wordSet English Lexicon 对它们进行了交叉检查，我获得的第一个有效单词将是提示词。

正如您已经猜到的那样，这个过程的任务是知道 17 排列 7 已经等于 9800 万种可能的排列。为了掩盖这一点，我使用 FixedThreadPool 来拆分排列任务（分成大约 20 个工作线程），现在我的单词搜索速度相对较快，但缺点是，这会导致低端设备严重滞后.

任何关于如何制作更好的提示词搜索算法或改进我上面解释的方法的建议都将不胜感激。

Answer 1

关于速度，我现在无法真正测试任何东西，但如果你保持你的词典排序，你可以在它上面使用搜索算法：你首先找到所有位置，其中单词列表以以下之一开头您的 17 个可用字母。然后，您查看每个列表，寻找以其他 16 个字母之一开头的列表，并继续此操作，直到出现任何具有允许长度的单词。

作为一个简单的例子，请考虑以下内容：

String[] lexicon = {"parrot", "postal", "office", "spam"};
char[] letters = {'p', 'o', 's', 't', 'a', 'l'};

这将产生中间可能性：

{"parrot", "postal", "office", "spam"}  (1 letter  matched)
{"parrot", "postal", "spam"}            (2 letters matched)
{"postal", "spam"}                      (3 letters matched)
{"parrot"}                              (4 letters matched)

此时您可以继续您的搜索算法，或者注意只剩下一个选项并使用不同的测试来查看它是否被允许。

此算法要求您最多使用 C(17, 7) = 19,448 次搜索。您也可以改进对每个字母使用完全二进制搜索的成本。

Answer 2

使用您的单词列表构建一个 trie / 前缀树：

您可以从 17 个可用字母中随机选择一个字母，并开始仅使用 17 个字母中的字母进行遍历。第一个带有标记表示单词结束的标志的节点可以是一个建议。

很多预测性文本程序都使用这样的结构来猜测您正在输入的单词，或者如果您在图表中距离标记单词结尾的节点不太远，则可以帮助您打错字。在 space 上更好，因为树的深度由最长的单词决定。但是，您不会在以下情况上浪费 space：

do
dog
doggy
done
dunce

您只存储：

                d
               / \
             *o   u
             / \   \
           *g   n   n
           /     \   \
          g      *e   c
         /             \
       *y              *e

其中 * 是一个布尔标志，指示单词结束的位置。

时间复杂度：

判断一个文本字符串是否是一个单词将通过 O(n) 其中 n 是单词的长度。

这个网站似乎有一些优化：https://www.geeksforgeeks.org/trie-insert-and-search/

Space，取决于您是使用数组、指针还是哈希图来实现。

Answer 3

这里有几种优化方法：

与其生成数百万个组合并对其进行测试，不如遍历英语单词列表并针对您的 17 个字母进行测试。您将进行数千次测试，而不是进行数百万次测试。
测试是否可以使用字母计数从 17 个字母组成单词，而不是实际生成特定顺序的字母串并与单词进行比较。这意味着您不必生成每个可能的字母顺序。

要实现第二个优化，有必要以一种可以轻松比较字母计数的方式将单词存储在单词列表中。一种简单的方法是将每个单词与另一个字符串一起存储，该字符串由按字母顺序排序的所有字母组成。例如，您将 "cheese" 和 "ceeehs" 成对存储。您可以计算字母的运行次数，看看每个字母是否足够。

在流程开始时，您可以计算 17 中每个字母的数量，并将它们存储在一个数组中。然后浏览你的单词列表并测试每个单词，如下所示：

int[] letter_counts = new int[26]; // how many of each letter of the
                                   // alphabet you have in your 17 letters

boolean test_word(String word)  // pass in the sorted string e.g "ceeehs"
{
    char prev = '[=10=]'; // use this for detecting repeating letters
    int count = 0;
    for(int i = 0; i < word.length(); i++)
    {
        char c = word.charAt(i);
        if(c != prev)
        {
            prev = c;
            count = 0;
        }
        count++;
        if(letter_counts[(int)c - 'a'] < count)
            return false; // not enough letters
    }
    return true;
}

为了避免偏向单词列表中较早的单词（因为一找到就停下来），您可以从单词列表中的随机位置开始，然后循环到开头。

这种方法绝不是最优的，但可能足够快并且易于实施。

在 java 中创建单词的高效算法

Efficient algorithm for word creation in java

java

algorithm

performance

permutation

libgdx