Python中的树遍历和字谜

本文包含附属链接。有关更多信息，请参阅我的附属公司披露。

我知道这只是语言的一个意外，但是你可以将“眼睛”中的字母重新排列成“他们看到”的事实感觉……很神奇。

从我还是个孩子的时候起，我就喜欢字谜。所以，我想我会尝试在 Python 中构建一个字谜生成器。它变成了一个有趣的周末小项目，带有一些树遍历和递归。

这就是我想出的。

如何检查两个字符串是否是字谜

如果string1中的字符是string2中字符的重新排列，则string1是string2的变位词。

不过，字符的顺序并不重要。重要的是string1中每个字符的计数与string2中每个字符的计数相同。如果每个字符在每个字符串中出现的次数相同，则这两个字符串是彼此的字谜。

Python 的collections.Counter可以计算：

 from collections import Counter string1 = "the eyes" string2 = "they see" Counter(string1) # Counter({ # 'e': 3, # 't': 1, # 'h': 1, # ' ': 1, # 'y': 1, # 's': 1 # }) Counter(string1) == Counter(string2) # True ✅

看到Counter对象中的空字符串' '了吗？那是个问题。 “剧院”和“眼泪”是字谜，即使一个有空格而另一个没有。字谜不区分大小写。它们也可能有不同的标点符号，例如“vitalise”和“IT’S ALIVE！”。

一个强大的解决方案需要将所有这些都考虑在内，因此collections.Counter不会在没有一些预处理的情况下削减它：

 string1 = "vitalise" string2 = "IT'S ALIVE!" Counter(string1) == Counter(string2) # False ❌

像大多数问题一样，有很多方法可以解决这个问题。

我想要一个易于理解且易于更改的解决方案，以防它无法处理应有的所有情况。我使用了字符串.translate()方法，它根据翻译字典替换字符串中的每个字符。映射到None的字符将从字符串中删除。另外，我可以使用str.maketrans()轻松创建翻译词典。

这使我可以细粒度地控制字符串在传递给Counter()之前的处理方式：

 from collections import Counter from string import punctuation, whitespace from typing import Callable def process(string_: str) -> str: chars_to_remove = punctuation + whitespace translation = str.maketrans("", "", chars_to_remove) return string_.translate(translation).lower() def are_anagrams( string1: str, string2: str, process: Callable = process ) -> bool: processed1 = process(string1) processed2 = process(string2) return Counter(processed1) == Counter(processed2)

在process()函数中使用.casefold()而不是.lower()可能会更好。但总的来说，这是一个强大的解决方案。只要您了解Counter 、 .translate()和str.maketrans() ，就很容易理解。如果需要，可以轻松更换处理功能。

但是如何为特定字符串查找字谜呢？

如何生成字谜

这比检查两个字符串是否是彼此的字谜更难。

仅仅生成所有可能的字符串重排是不够的。您必须在有意义的地方插入空格和标点符号。字符串中的结果单词需要是实际的字典单词。

我们需要一种方法来有效地生成使用字符串中的字母的单词。

在纸上解决它

抛开获取单词列表的问题，从简单的开始：

 eyes the they see sea

过程是这样的：

1. 写下要为其生成字谜的短语，例如“眼睛”。
2. 从短语中选择一个字母（比如“t”）并扫描列表以查找以该字母开头的单词（单词 =“the”和“they”）。划掉短语中字母的一个实例，并将该字母写为字谜的第一个字母（字谜 =“t”）。
3. 从尚未被划掉的短语中选择一个字母（例如，“h”），然后将在最后一步中选择的单词过滤到第二个字母是您选择的新字母的那些单词（words = “the”和“他们”）。划掉短语中的字母并将其添加到您的字谜（字谜 =“th”）中。
4. 继续选择未使用的字母并过滤单词列表的过程。当您到达单词的末尾时，请检查您目前生成的短语是否是原始短语的字谜。如果是，你就完成了。如果没有，请从完整的单词列表重新开始，但只使用尚未被划掉的字母。
5. 使用短语中不同的首字母重复整个过程。

如果你在上面的小单词列表上一步一步地遵循这个算法，你最终会得到四个字谜：

• 眼睛
• 眼睛
• 他们看
• 看到他们

当然，“眼睛”是您开始使用的短语。没关系。只是丢弃它。

如果我们可以直接跳到它们而不是扫描整个列表以查找所有以字母 T 开头的单词，那不是很好吗？或者跳转到所有以 TH 开头的单词？还是从 THE 开始？

听起来我们需要一个哈希表！

我们真正想要的是哈希表的哈希表。

哈希表的哈希表是表示树的一种方式。而且，如果你停下来想一想，我所描述的生成字谜的方法感觉很像深度优先搜索。这是如何实现算法的重要线索。

Python 拥有我们需要的所有部分。

构建字典树

我们要构建的树看起来像这样：

Python 字典是哈希表，因此它们是我们树的基础的自然选择。每个字典的键是包含单个字母的字符串，值是更多的字典。我们需要知道我们何时处于单词的末尾，因此我们将使用字典{" ": {}}标记这些位置。

单词 eye、the、they、see 和 sea 的字典树如下所示：

 {'e': {'y': {'e': {'s': {' ': {}}}}}, 's': {'e': {'a': {' ': {}}, 'e': {' ': {}}}}, 't': {'h': {'e': {' ': {}, 'y': {' ': {}}}}}}

但是你如何构建这样的字典呢？

关键观察是您可以递归地将单词添加到字典中。从空字典开始。对于每个单词，弹出第一个字母——称之为char 。如果char是字典中的键，则获取它的值。否则，将字典中的键char设置为空字典作为其值。然后重复这个过程，使用映射到char的字典和没有第一个字符的单词。

假设word没有空格并将字符串" "添加到末尾，以便我们得到正确的终端词典。

这是代码：

 from typing import Iterable def add_word(tree: dict, word: str) -> None: if word != "": char = word[0] branch = tree.get(char, {}) tree[char] = branch _add_word(branch, word[1:]) def build_word_tree(words: Iterable[str]) -> dict: word_tree = {} for word in words: add_word(word_tree, word + " ") return word_tree

递归很好，因为它可以紧凑地描述重复的过程。但是如果不手动推理这些步骤，可能很难理解递归算法的作用。带有一些好的示例的文档可以帮助读者（包括你未来的自己！）理解递归函数。

现在我们已经有了可以使用的树，我们可以开始生成字谜了。

遍历树制作字谜

您可以将 anagram 算法实现为遍历单词树中的节点。

我们选择一个初始节点——我们想要变位词的短语中的一个字符——并在数组中将该节点标记为已访问。然后移动到以该节点为根的树中的分支。继续重复此操作，直到您访问短语中的所有字符或到达单词的末尾。更多递归！

它本质上是一种深度优先搜索算法，除了可步行到的节点受到树中的节点和短语中尚未访问的字符的限制。

这是在以下 Python 代码中捕获的：

 from typing import Generator def walks( tree: dict, filter_: Callable, _visited: tuple = () ) -> Generator: if tree == {}: yield _visited else: for node in filter_(tree, _visited): yield from walks( tree[node], filter_, (*_visited, node) )

filter_()函数应该返回一个可以步行到的节点元组。这对于查找字谜的确切工作方式存在一些细微差别。我们稍后会谈到这一点，现在暂不定义过滤器函数。

我们还没有完成 anagram 算法的 walk。

walks()产生一个 walk 访问的节点的元组——在这种情况下是一个短语中的字符——但是当它们到达一个单词的末尾时，walk 就结束了。

要生成多字字谜，您需要绕着树转一圈，然后继续从根部开始遍历树。我把这称为“走动”树。你不停地走来走去，收集单词，直到走完为止。

这是代码：

 def walk_around( tree: dict, done: Callable, filter_: Callable, _visited: tuple = (), ) -> Generator: for walk in walks(tree, filter_, _visited): if done(walk): yield walk else: yield from walk_around( tree, done, filter_, walk )

我们需要实现done和filter函数以传递给walk_around() ，这两者都取决于我们为其生成字谜的短语。

当walk 中访问的字符串是短语的变位词时，就完成了walk。我们已经知道该怎么做！我们可以使用are_anagrams()函数：

 def done(phrase: str, walk: tuple) -> bool: return are_anagrams(phrase, "".join(walk))

现在我们需要定义filter_() 。

我说这有一些细微差别。

在步行的每一步，我们只需要移动到我们还没有访问过的短语中的一个字符。或者一个标点符号，因为我们想要包含诸如缩写之类的词。哦，我们也可以移动到一个" "字符，因为这是我们知道我们在一个单词的末尾的方式。

我们可以使用sets清晰地表达这些规则：

 def filter_( phrase: str, tree: dict, _visited: tuple ) -> tuple: remaining = set(Counter(phrase) - Counter(_visited)) _punctuation = set(punctuation) end_of_word = {" "} allowed = remaining | _punctuation | end_of_word nodes = set(tree.keys()) anagram_nodes = nodes.intersection(allowed) return tuple(anagram_nodes)

Counter可以轻松计算短语中尚未访问的字符。

从另一个计数器中减去一个Counter会返回一个减去计数的Counter 。计数为零的字符将被删除。例如， Counter("tea") - Counter("e")返回Counter({'t': 1, 'a': 1}) 。

该|是自 Python 3.9 起可用的字典合并运算符。

我们已经准备好编写一个字谜生成器：

 from functools import partial def anagrams(phrase: str, words: Iterable) -> Generator: tree = build_word_tree(words) _done = partial(done, phrase) _filter = partial(filter_, phrase) for walk in walk_around(tree, _done, _filter): anagram = "".join(walk).rstrip() if anagram != phrase: yield "".join(walk).rstrip()

functools.partial()在这里用于“填写” done()和filter_()函数的phrase参数。我们必须这样做，因为walk_around()的done和filter_参数需要没有phrase参数的函数。 .rstrip() walk_around()的步行以空格结尾。

让我们使用anagrams()来了解一小部分单词：

 words = ["eyes", "the", "they", "see", "sea"] phrase = "the eyes" for anagram in anagrams(phrase, words): print(anagram.rstrip()) # eyes the # they see # see they

嘿，它有效！

测试大量单词

如果您的计算机具有类 Unix 操作系统，那么您现在有大量可用的单词。

在大多数机器上，有一个words文件位于/usr/share/dict/words或/usr/dict/words 。这是一个以换行符分隔的字典单词列表。如果您有一台 Windows 机器或没有words文件，您可以在 GNU 网站上以您的语言找到该文件的tarball 。

让我们试一试：

 from pathlib import Path words_path = Path("/usr/share/dict/words") words = words_path.read_text() # The words file ends with a blank line so we # need to remove trailing whitespace words = words.lower().strip().split("\n") phrase = "tea" for anagram in anagrams(phrase, words): print(anagram) # ate # a te # aet # at e # ate # ae t # tae # ...

它工作得很好，但是words文件包含单个字母和两个字母的单词，例如“te”。这给我们的字谜增加了一堆噪音。我们可能应该清理它。

让我们过滤掉一些我们知道我们不想要的词：

 from string import ascii_lowercase SINGLE_LETTERS = set(ascii_lowercase) - {"a", "i"} TWO_LETTER_WORDS = {"te", "ae", "ea"} FORBIDDEN = SINGLE_LETTERS | TWO_LETTER_WORDS words_path = Path("/usr/share/dict/words") words = words_path.read_text() words = words.lower().strip().split("\n") words = (word for word in words if word not in FORBIDDEN) phrase = "tea" for anagram in anagrams(phrase, words): print(anagram) # eat # eta # ate # tae

这肯定会给我们带来更好的结果。对于一个非常好的字谜生成器，您需要花一些时间来整理单词。 words文件不一定是最好的单词集，因为它不包含任何缩写。

您可以使用 aspell 的SCOWL 工具生成更多有趣的单词列表。

快乐字谜狩猎！

---

原文： https://davidamos.dev/tree-traversals-and-anagrams-python/