在一个充满随机放置字符的列表中搜索单词

本文关键字：字符 列表 单词 搜索 满随机 一个 | 更新日期: 2023-09-27 18:07:57

我有一个问题:

如果我有一个字母列表，让我们用:

A
T
C

我希望算法能够根据我给它的单词列表找出哪些组合可以创建单词(它们不必与列表的长度相同)

那么从这里开始，它会像这样:

CAT, ACT, A etc etc.

我遇到的问题是理解算法的基础应该是什么。

有谁知道如何帮助我开始工作吗?

在一个充满随机放置字符的列表中搜索单词

当然，最简单的方法是使用蛮力。但是，当许多单词无法用现有的字母组成时，您不希望将随机字符串与整个字典进行比较。这里有一些技巧可以帮助你减少搜索空间。我假设你只看英语单词。如果是这样，您可以使用一些公共语言结构来进一步缩小搜索空间。现在，请记住，这些方法可能无法捕获英语中的所有单词，但是如果您正在编写自己的字典，则可以手动编写异常。

你要做的第一件事是通过删除给定搜索集不能生成的所有单词来缩减字典。循环遍历每个字母和字典单词，看看这个单词是否包含这个字母。如果不是，从字典中删除它(这是使用Parallel库的一个很好的候选)。

接下来，从元音开始。每个单词都至少有一个，而且它们可以被分组的方式也相当少。如果你不能用你的字母组成一个特定的元音组合，那就去掉任何包含这个元音组合的单词。还可以将蛮力生成器设置为只查看有效的元音组合。

以"h"开头的单词总是有一个元音作为第二个字母，所以除了A, e, i, o, u或y外，不要将h(1)与任何其他字母连接。

i在e之前，除了c之后，尽管这是一个很小的例子，我认为不值得添加它，除非你说的是很长的单词。

Q后面几乎总是u

这几条规则应该足以让你减少90%或更多的搜索空间。然后使用上面的语法规则只生成有效语法的组合，这将进一步减少您的空间。在那之后，即使有一个大字典(100,000个单词和16个字符)，你也应该有一个足够小的搜索空间来在一个合适的时间框架内运行一个蛮力算法。

不那么容易的方法

如果你真的想变得更花哨，你可以使用我上面提到的并行库来加速搜索空间的减少和蛮力算法本身。蛮力是令人尴尬的并行，所以如果你投入更多的内核，你将在运行时间上得到几乎线性的改进。

除此之外，你可以尝试使用一些贝叶斯统计分析或神经网络来指导你的组合选择，但这对于你所追求的可能是过度的:)

我不确定我是否理解了你的问题。如果你想知道列表中所有可能用这些字符写成的单词，你需要一个完整的单词列表。一个简单的规则似乎是，每个单词必须只使用字符列表中包含的字符。这样你就可以找到所有可以用字符列表写的字符串:

List<char> characters = new List<char>() { 'A', 'C', 'T', 'F', 'B', 'O' };
List<string> dictionary = new List<string>() { "CAT", "ACT", "A", "FISH", "BONE" };
List<string> possibleWords = new List<string>();
foreach (string word in dictionary)
{
   if (!(word.ToLower().Except(characters.ToString().ToLower()).Any()))
   {
      possibleWords.Add(word);
   }
}
// Result: "CAT", "ACT", "A"

这是一个起点。它表明，事实上，蛮力在这里是很好的。只有大约20万个单词需要检查。下面的算法对于整个Scrabble单词列表只需要几毫秒，查找字母表的前16个字母的匹配:

class Program
{
    static void Main(string[] args)
    {
        var validWords = new List<string>(File.ReadAllText("AllWords.txt").Split(' '));
        foreach (var result in validWords.Where(word => 
                     IsWordInString(word, "ABCDEFGHIJKLMNOP")))
        {
            Console.WriteLine(result);   
        }
    }
    static bool IsWordInString(string word, string source)
    {
        var letterList = source.ToList();
        return word.All(letterList.Remove);
    }
}

算法为:

  • 遍历有效单词的完整列表
  • 检查一个单词中的每个字符都可以成功地从有效字符列表中"剔除"
  • 如果可以，就是匹配。否则将被拒绝。

注意-这可能是最简单的方法，并且没有应用优化。有很多方法可以让它更快。但是因为它的性能主要取决于单词列表的长度(这是恒定的)，所以增加字母列表对速度的影响很小。

作为一个好奇，如果你运行这个(使用整个字母表):

var longest = validWords.Where(word => 
    IsWordInString(word, "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
            .OrderByDescending(i => i.Length).First();

立即返回"DERMATOGLYPHICS"——这是英语中没有重复字母的正确最长单词。在我的调试器中没有明显的执行时间。

(从这里的单词列表)

我认为蛮力方法是最简单的。这个算法基本上会找到你的字母集合的每个子集并检查它是否在字典中。对于每个字母，它将检查它在单词中或不在单词中的可能性。

您的字典数据结构应该排序，以便可以使用二进制搜索(或者您可以使用哈希集)快速检查是否包含单词。

伪代码看起来像这样:

A = array of letters
S = empty list
IS_VALID(word, i)
    //base case: reached the end of the letters
    if i > length(A) - 1
        return
    if dictionary contains word
        add word to S
    //check for all words containing A[i]
    IS_VALID(w + A[i], i+1)
    //check for all words excluding A[i]
    IS_VALID(w, i+1);
//initialization
IS_VALID("", 0)

其中word是您当前正在查看的字符串，i是您当前正在考虑附加到word末尾的A中字母的索引

    private static bool b;
    /// <summary>
    /// Word with Random Characters
    /// </summary>
    /// <param name="characterList"></param>
    /// <param name="wordList"></param>
    public static void WordWithRandomCharacters(List<char> characterList, List<string> wordList)
    {
        var resultWords = new List<string>();
        foreach (var word in wordList)
        {
            foreach (char c in word.ToCharArray())
            {
                b = false;
                if (characterList.Contains(c)) b = true;
                if (!b) break;
            }
            if (b) resultWords.Add(word);
        }
        foreach (var word in resultWords)
        {
            Console.WriteLine(word);
        }
    }
相关文章：