mor*_*ous 5 python algorithm tree
我正在处理树库,并且所需功能的一部分是能够在节点中搜索与模式匹配的子节点.
"模式"是规范(或标准),其规定了结构,以及要匹配的子树中的节点的属性.
例如,假设树代表关于特定鸟类的数据.进一步假设这种树的节点具有以下属性:
鉴于父节点,我想用简单的英语发出搜索:
"把我这只鸟的后代的所有雄性鸟取出来,住在XXX城市,体重> 100g.发现任何这样的鸟也应该至少有2个兄弟和1个妹妹,并且本身必须至少有一个孩子"
<note>
只是为了澄清,我不希望能够像上面所做的那样使用普通英语进行查询.我只使用"普通英语查询"来说明我想在树上执行的匹配类型.我完全希望在实践中使用符号进行匹配(而不是纯文本).
</ note>
我想可能使用正则表达式模式匹配来匹配树.一种方法是使用每个节点的字符串表示,所以我可以使用普通的正则表达式 - 但这可能是非常低效的,因为会有很多重复的数据 - 即子节点的字符串表示将是超集他们的父表示,将是他们的父母代表字符串的超集,依此类推,递归地,在树上 - 这对于事件适度大小的树很容易变得笨重 - 必须有更好的方法.
是否有人知道一种算法,它允许我根据模式选择节点中的节点(子树)？
虽然我要求使用通用算法,但我在Python中实现了这一点.任何进一步说明这种算法的片段(如果确实可以写一个),将是非常有用的.
用通配符编写Lisp Sexpression来描述树匹配有什么问题？括号将节点分组。从左到右的元素匹配根后跟子元素。子树匹配使用嵌套的 S 表达式来描述子树。
以下将匹配具有任意根节点的树，第一个子节点是叶子 A，第三个子节点是以 X 为根的子树，第一个子节点 1 和第三个子节点 A：
(?root A ? (X 1 A))
这个想法不是我独有的。从 60 年代初开始，Lisp 人就一直在编写这样的模式。
这是一个仅可追溯到 20 年前的 LISP 模式匹配器（作为您想要的示例）：http : //norvig.com/paip/patmatch.lisp
但是，自己编写代码非常简单。这通常被指定为学习 LISP 的人的家庭作业。
这取决于你的树。如果您的树是有根且有序的，您应该能够检查亚线性时间中的精确匹配，如果不是，您应该能够检查线性时间中的匹配。还存在几种更快的近似匹配算法。
要查找此类主题的材料和算法，Google 学术搜索是您的朋友。搜索子树匹配或类似的内容应该可以到达那里。
编辑：从您更新的条目来看，我建议您看看 XPath 和类似的查询语言是如何实现的。XML 是一棵有根树，XPath 可以使用复杂的匹配运算符（如示例中的运算符）搜索该树中的子树。
我还建议您不要自己实现这一点，而是使用现有的库（例如PyLucene或其他一些搜索引擎，考虑到您给出的示例，这似乎很合适）。