树匹配算法？

Question

我正在开发一个树形结构的库，其中一个重要功能是能够搜索某个节点下符合特定模式的子节点。

这里的“模式”是指一种规范或标准，用来描述子树中节点的结构和属性。

举个例子，假设这棵树代表某种鸟类的数据。再假设这棵树的节点有以下属性：

• 位置
• 性别
• 翼展
• 体重
• 窝里有多少小鸟

给定一个父节点，我想用简单的语言进行搜索，比如：

“帮我找出所有这个鸟的后代中，生活在XXX城市的雄性鸟，体重超过100克。找到的每只鸟还必须至少有两个兄弟和一个姐妹，并且它自己至少要有一个孩子。”

< 注意 >

为了澄清一下，我并不指望能用上面那种简单的英语来进行查询。我只是用“简单英语查询”来说明我希望在树上进行的匹配类型。实际上，我完全预期会使用符号来进行匹配，而不是简单的文本。

< /注意 >

我在考虑可能使用类似正则表达式的模式匹配来匹配树。一个方法是为每个节点创建一个字符串表示，这样我就可以使用普通的正则表达式，但这可能效率不高，因为会有很多重复的数据。也就是说，子节点的字符串表示会是其父节点表示的超集，而父节点的表示又会是其祖父节点表示的超集，依此类推，这样在树的结构上可能会变得非常复杂，甚至对于中等大小的树也会显得难以处理——肯定有更好的方法。

有没有人知道一种算法，可以让我根据模式选择节点（子树）？

虽然我问的是一个通用算法，但我是在用Python实现这个功能。如果有任何代码片段能进一步说明这样的算法（如果确实可以编写的话），那将非常有帮助。

Answer 1

用通配符写一个Lisp的S表达式来描述树的匹配有什么问题呢？括号用来表示一个节点。元素从左到右匹配根节点，然后是它的孩子节点。子树的匹配则使用嵌套的S表达式来描述。

下面这个例子可以匹配一个树，根节点可以是任意的，第一个孩子是一个叶子节点A，第三个孩子是一个以X为根的子树，子树的第一个孩子是1，第三个孩子是A：

(?root A ? (X 1 A))

这个想法并不是我独创的；Lisp的开发者们从六十年代初就开始写这样的模式了。

这里有一个LISP模式匹配器（就像你想要的那样），它的历史大约有20年： http://norvig.com/paip/patmatch.lisp

不过，自己编写这个其实很简单。这通常被作为学习LISP的人们的作业练习。

Answer 2

这要看你的树的结构。如果你的树是有根的并且是有序的，你应该能在比线性时间更快的时间内找到完全匹配的结果。如果不是，你也能在线性时间内找到匹配的结果。此外，还有一些更快的算法可以用来进行近似匹配。

如果你想找相关的资料和算法，Google Scholar 是个不错的选择。搜索“子树匹配”或者类似的关键词应该能找到你需要的内容。

编辑：根据你更新的内容，我建议你看看 XPath 和类似的查询语言是怎么实现的。XML 是一种有根的树结构，而 XPath 可以用复杂的匹配操作符在这棵树中搜索子树，就像你例子中的那样。

我还建议你不要自己去实现这个，而是使用现有的库（比如 PyLucene 或者其他合适的搜索引擎，这样更符合你给出的例子）。