树匹配算法？

Question

树匹配算法？

5

我正在开发一个树库，其中所需功能的一部分是能够搜索符合模式的子节点。'模式'是指规定了子树中节点的结构和属性的规范（或条件）。例如，假设一棵树表示有关一种鸟类的数据。进一步假设这样的树的节点具有以下属性：位置、性别、翼展、体重、育雏量。给定一个父节点，我想用简单明了的语言发出搜索请求：“找到所有生活在XXX城市且体重大于100克的雄性鸟类的后代。任何找到的这样的鸟类都应该至少有2个兄弟和一个姐妹，并且本身必须至少有一个孩子”。

为了澄清，我并不希望像上面那样使用普通英语查询。我只是用“普通英语查询”来说明我想在树上执行的匹配类型。实际上，我完全打算使用符号进行匹配（而不是纯文本）。

< /note >

我在考虑可能使用类似正则表达式的模式匹配来匹配树。一种方法是拥有每个节点的字符串表示，这样我就可以使用普通的正则表达式。但是这可能会非常低效，因为会有很多重复的数据 - 即子节点的字符串表示将是父节点表示的超集，而父节点的表示将是其父节点的表示形式的超集，依此类推，递归地向上遍历树 - 这很容易变得难以处理，即使对于规模适中的树也是如此 - 必须有更好的方法。

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

尽管我要求一个通用算法，但我正在Python中实现它。如果有任何进一步说明这样的算法的代码片段（如果确实可以编写），那将非常有用。

- morpheous

你最好使用递归列表，实际上你只需要使用一个中间列表 ➔ 字符串 ➔ 正则表达式 ➔ 列表，这样做可能不值得开销。更具体的例子将有助于获得更好的答案。 - msw

你有两个问题：a）如何将树形模式匹配表示为正式可解释实体；b）将自由文本英语查询转换为这样的模式。a）是众所周知的，可以看看我的答案中提供的一个选项。b）仍然是研究课题，我怀疑你不想自己尝试。 - Ira Baxter

@Ira：只是为了明确，我只使用“普通英语查询”来说明我想在树上执行的匹配类型。实际上，我预计会使用符号进行匹配（而不是纯文本）-我认为我会编辑我的帖子以澄清这一点。 - morpheous

2个回答

3

这取决于您的树。如果您的树是有根和有序的，您应该能够在次线性时间内检查是否存在完全匹配，否则您应该能够在线性时间内检查是否存在匹配。还有一些更快的算法可用于近似匹配。

要查找此类主题的材料和算法，Google Scholar 是您的好朋友。搜索子树匹配或类似内容即可到达目的地。 编辑： 根据您更新的条目，我建议您查看XPath及其类似查询语言的实现方式。XML是一个有根树，XPath可以使用像您示例中那样的复杂匹配运算符在该树中搜索子树。

我还建议您不要自己实现此功能，而是使用现有库（如PyLucene或其他搜索引擎，考虑到您提出的示例，这似乎是合适的）。

- Håvard S

是的，我不相信重复造轮子。事实上，我一直在思考研究XPath的工作原理......传递给函数fetch_matching_subtrees()的节点就是该函数所关注的根节点。我之前没有考虑过Lucene引擎，这是一个值得深思的问题... - morpheous

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

如果用通配符编写一个Lisp Sexpression来描述树匹配，有什么问题？括号将节点分组。从左到右的元素匹配根节点，然后是子节点。子树匹配使用嵌套的S表达式来描述子树。

以下内容将匹配具有任意根节点的树，第一个子节点是叶子A，第三个子节点是以X为根的子树，第一个子节点是1，第三个子节点是A：

(?root A ? (X 1 A))

这个想法并不是我独有的；Lisp的人们自上世纪60年代初以来一直在编写这样的模式。

这里有一个LISP模式匹配器（作为你想要的示例），它只追溯到20年前： http://norvig.com/paip/patmatch.lisp

然而，自己编写这个程序非常容易。这通常被分配为学习LISP的人的家庭作业。