Python RegEx-刽子手算法

Question

我正在尝试编写刽子手算法。我的想法是这样的:

• 预处理字典，根据单词的长度包含单词的相对字母频率。步骤完成。

例子:

#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)

• 这个特别的游戏会免费给你最后一个元音。例如，如果这个词是土的， 用户将获得以下板:e----e- 猜测。所以，我想找到一种方法来创建一个新的生成器或列表 删除所有不符合 e----e- 模板的词。

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

所以我的第一个问题是:

1. 我如何确保“e”是 仅位于第一个和 倒数第二个位置
2. 我如何创建一个智能函数，在拼图更新和计算机不断猜测时使用新的正则表达式？

例如，如果单词是 monkey，计算机将只给出 ----e- 第一步是从字典中删除所有不是 6 个字母的单词，以及所有不完全符合 '----e-' 模板的单词，并将其放入新列表中。 怎么做 我去做这个？

然后，它会根据其中单词的相对频率计算出一个新的 frequencyDict 新列表。

我目前的做法是这样的:

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

这是最有效的方法吗？

然后它会使用 newfrequencyDict 来猜测最常见的字母，假设它有 还没有被猜到。它会继续这样做，直到(希望)猜到这个词。

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

Answer 1

正则表达式并没有什么特别神奇的地方，将它们与整个字典进行匹配仍然需要 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% 单词中的字符，这意味着您可以通过任何一种方式消除最多的可能性。即使这样也不是最优的 - 可能某些字符更有可能在单词中出现两次，因此排除了更大比例的候选 - 但它更接近。