Python 正则表达式- 猜单词算法

3 投票

2 回答

1808 浏览

提问于 2025-04-16 19:31

我正在尝试编写一个猜字游戏的算法。我的想法是这样的：

首先处理一个字典，这个字典包含了不同长度单词中各个字母出现的频率。这个步骤已经完成。

举个例子：

#Each key corresponds to length of the word.   

frequencyDict = {2: ['a', 'o', 'e', 'i', 'm', 'h', 'n', 'u', 's', 't', 'y', 'b', 'd', 'l', 'p', 'x', 'f', 'r', 'w', 'g', 'k', 'j'], 
  3: ['a', 'e', 'o', 'i', 't', 's', 'u', 'p', 'r', 'n', 'd', 'b', 'm', 'g', 'y', 'l', 'h', 'w', 'f', 'c', 'k', 'x', 'v', 'j', 'z', 'q'], 
  4: ['e', 'a', 's', 'o', 'i', 'l', 'r', 't', 'n', 'u', 'd', 'p', 'm', 'h', 'b', 'c', 'g', 'k', 'y', 'f', 'w', 'v', 'j', 'z', 'x', 'q'],
  5: ['s', 'e', 'a', 'o', 'r', 'i', 'l', 't', 'n', 'd', 'u', 'c', 'p', 'y', 'm', 'h', 'g', 'b', 'k', 'f', 'w', 'v', 'z', 'x', 'j', 'q'],
  6: ['e', 's', 'a', 'r', 'i', 'o', 'l', 'n', 't', 'd', 'u', 'c', 'p', 'm', 'g', 'h', 'b', 'y', 'f', 'k', 'w', 'v', 'z', 'x', 'j', 'q'],
  7: ['e', 's', 'a', 'i', 'r', 'n', 'o', 't', 'l', 'd', 'u', 'c', 'g', 'p', 'm', 'h', 'b', 'y', 'f', 'k', 'w', 'v', 'z', 'x', 'j', 'q'],
  8: ['e', 's', 'i', 'a', 'r', 'n', 'o', 't', 'l', 'd', 'c', 'u', 'g', 'p', 'm', 'h', 'b', 'y', 'f', 'k', 'w', 'v', 'z', 'x', 'q', 'j']}

我还有一个生成单词的字典：

dictionary = word_reader('C:\\Python27\\dictionary.txt', len(letters))

这个字典是基于这个函数的：

#Strips dictionary of words that are too big or too small from the list
def word_reader(filename, L):
  L2 = L+2
  return (word.strip() for word in open(filename) \
          if len(word) < L2 and len(word) > 2)

在这个游戏中，玩家可以免费获得最后一个元音字母。如果单词是“earthen”，那么用户会看到这样的提示：e----e-，需要猜这个单词。所以，我想找一种方法，创建一个新的生成器或列表，把所有不符合这个“e----e-”格式的单词剔除掉。

p = re.compile('^e\D\D\D\De\D$', re.IGNORECASE)可以做到这一点，但它可能会找到其他地方也有'e'的单词，比如第一个字母和倒数第二个字母以外的地方。

所以我第一个问题是：

我怎么确保'e'只出现在第一个和倒数第二个位置？
我如何创建一个智能的函数，让它在谜题更新时生成新的正则表达式，并且电脑可以继续进行猜测？

举个例子，如果单词是“monkey”，电脑只会看到----e-。第一步是从字典中剔除所有不是6个字母的单词，以及所有不完全符合'----e-'格式的单词，并把这些放到一个新的列表中。我该怎么做呢？

接下来，它会根据新列表中的单词重新计算一个新的频率字典。

我目前的做法是这样的：

   cnt = Counter()
   for words in dictionary:
      for letters in words:
         cnt[letters]+=1

这样做是最有效的方法吗？

然后它会使用新的频率字典来猜测最常见的字母，前提是这个字母还没有被猜过。它会一直这样做，直到（希望）猜出这个单词。

这是一个有效的算法吗？有没有更好的实现方式？

正则表达式生成器数据过滤智能算法字典处理字符匹配字母频率猜字游戏

2 个回答

有很多问题，我会尽量回答几个。

你的正则表达式应该像这样：'^e[^e][^e][^e][^e]e[^e]$'。这里的 [^e] 表示“匹配任何不是'e'的字符”。注意，这个表达式会匹配非字母的字符，但如果你的字典里只有字母，那就没问题了。还有，一旦你找到了多个字母，就要把所有字母放到这些“不能匹配”的部分里。例如，如果猜到了'a'，那么字符串变成“ea---e-”，这时你就可以用正则表达式 '^ea[^ae][^ae][^ae]e[^ae]$' 来匹配。
你可以写一个函数，接收像“ea---e-”这样的字符串，然后从中构建一个正则表达式。这个函数需要做的事情是：a) 找到字符串中所有不是连字符的字母，形成一个集合（在这个例子中是 {'a', 'e'}），b) 把这个集合变成一个“匹配所有但不包括这些”的正则表达式片段（[^ae]）——注意顺序不重要，所以我用了集合，c) 把每个连字符替换成这些字母中的一个（ea[^ae][^ae][^ae]e[^ae]），最后 d) 在前面加个 '^'，在后面加个 '$'。
最后关于频率字典的问题——这个问题比较独立。要比线性搜索整个字典更高效是很难的。我建议你可能不应该多次计算同一个字母的出现次数。例如，你想让“earthen”这个词为字母'e'贡献2分吗？我猜在猜字游戏中，你只想让它算一次，因为“eeeeeeee”和“the”这两个词在猜字母'e'时的结果都是一样的（成功）。不过我可能错了。

回答于 2025-04-16 由 Python大师

分享举报

正则表达式其实并没有什么特别神奇的地方，检查它们是否匹配整个字典的过程仍然需要O(n)的时间。我的建议是，自己写一个函数来判断一个单词是否符合某个模板，然后用你目前的字典来测试这个函数。

下面是一个示例函数：

def matches_template(word, template):
  found_chars = set(x for x in template if x != '-')
  for char, template_char in zip(word, template):
    if template_char == '-':
      if char in found_chars: return False
    else:
      if template_char != char: return False
  return True

至于如何确定下一个要猜的字符，你可能不想选择出现频率最高的字符。相反，你应该选择那个在50%的单词中出现的字符，这样可以最大程度地排除其他可能性。即使这样也不是最优的——因为某些字符可能在单词中出现两次的概率更高，从而排除更多的候选字符——但这样做会更接近理想情况。

回答于 2025-04-16 由 Python大师

分享举报

Python 正则表达式- 猜单词算法

2 个回答

撰写回答