我正在接管我的一个较旧的项目,其中有效性和效率是关键。我解析了100 GB的XML数据。对于每棵XML树(数百万棵树),使用一些XML属性,从中推导出模式。不过,对于这个问题,我将大大简化事情-但重要的是要记住,数据很多,而且快速处理以及将结果整齐地存储在XML中非常重要。另外,生成的XML树也将需要遍历。实际上,它将用作BaseX中使用的自定义索引机制,但我将在稍后再讨论。
从每棵树(及其子树,但现在并不重要)中创建一个基于根节点的直接子代的模式。作为一个基本示例,请使用以下XML树:
<node letter="X">
<node letter="A"/>
<node letter="B"/>
<node letter="C"/>
<node letter="D"/>
</node>
通过获取所有儿童的字母属性并将其排序并加入它们来创建模式。在这种情况下,模式将为
ABCD
。对于每棵树,还生成所有可能的子树(顺序不重要,最小组合2),即,生成所有子级的可能组合,并生成其模式。我没有包括组合树的XML,但是除了
ABCD
之外,可能的模式将是:AB
ABC
ABD
AC
ACD
AD
BC
BCD
BD
CD
在层次结构中,它们看起来像这样(请注意终端节点中的重复项)。
另外,应该以某种方式在生成的XML中指示我们从其开始的完整模式,以表明它是树中的“主要”模式。最终,我想恢复从给定模式派生的所有模式(请参阅稍后),然后仅将其过滤为“主要”模式。
从查询的角度来看,您可以
argue that I am doing a bottom-up look-up. If I am looking for a generalized pattern, e.g. AB, the more specific patterns should also be found because
AB is part of
ABCD。因此,如果我要使用上面的数据寻找模式AB
,我想找到ABCD
ABC
ABD
很明显,这里有两个步骤。首先,概括一个级别:
AB -> ABC,ABD
,然后是ABC->ABCD
(再次是ABD->ABDC
,但每个结果当然只能找到一次)。中间步骤ABC
和ABD
对我也很重要,不仅是最终的ABCD
结果。我面临的问题是如何有效地存储一棵树,例如图像中显示的树,这样一来就容易:1.以我所讨论的方式易于查询; 2.尽可能稀疏而不丢失任何节点; 3.高效建造。对于这个问题,后一点并不重要,因为我将自己实现构建脚本-这将在Python 3.6中完成。
到目前为止,我的想法是要有一个相当扁平的结构,可以通过“索引”直接父节点来工作。它看起来像这样:
<tree>
<node pattern="AB" index="1">
<parentnode coindex="7"/> <!-- ABC -->
<parentnode coindex="8"/> <!-- ABD -->
</node>
<node pattern="AC" index="2">
<parentnode coindex="7"/> <!-- ABC -->
<parentnode coindex="9"/> <!-- ACD-->
</node>
<node pattern="AD" index="3">
<parentnode coindex="8"/> <!-- ABD -->
<parentnode coindex="9"/> <!-- ACD -->
</node>
<node pattern="BC" index="4">
<parentnode coindex="7"/> <!-- ABC -->
<parentnode coindex="10"/> <!-- BCD -->
</node>
<node pattern="BD" index="5">
<parentnode coindex="8"/> <!-- ABD -->
<parentnode coindex="10"/> <!-- BCD -->
</node>
<node pattern="CD" index="6">
<parentnode coindex="9"/> <!-- ACD -->
<parentnode coindex="10"/> <!-- BCD -->
</node>
<node pattern="ABC" index="7">
<parentnode coindex="11"/> <!-- ABCD -->
</node>
<node pattern="ABD" index="8">
<parentnode coindex="11"/> <!-- ABCD -->
</node>
<node pattern="ACD" index="9">
<parentnode coindex="11"/> <!-- ABCD -->
</node>
<node pattern="BCD" index="10">
<parentnode coindex="11"/> <!-- ABCD -->
</node>
<node pattern="ABCD" index="11" isMain="true"/>
</tree>
通过这样做,我想一个人可以获得链接在一起的所有模式。例如,如果我现在寻找AB,我希望到达该节点的子节点(
parentnode
)并获取这些索引,并使用这些索引寻找直系 parent 。然后,该过程应重复进行,直到没有元素带有共索引(例如,在这种情况下为ABCD
)。想象一下,有成千上万个这样的XML元素,并且主要元素用
isMain
表示。请注意,isMain
不一定是没有父节点子级的模式!结果是所有原始XML树的累积。意味着在某些情况下,一种模式可能是主要模式,而在另一些情况下,它可能是组合的一部分。在这种情况下,node
用isMain
表示,因为在原始XML中,“有些树以该模式作为其主要模式”。到目前为止,这只是我的想法,但是我不确定是否有更好的方法,或者更重要的是,是否可以在BaseX中轻松查询。基本上,使用给定的
AB
输入,我想通过使用索引来检索所有相关的pattern
(ABC,ABD,ABCD),然后仅通过检索isMain="true"
的位置来过滤这些结果。我期待看到更好的主意,以及在BaseX中查询它们的方法。如果我的想法很好,那么我希望看到一种在单个xquery表达式中捕获查询的好方法。 最佳答案
我没有完全通过将层次结构数据放到平面结构中而仍然使用高效的XML处理器BaseX来实现。
我认为将数据放入它已经表示的逻辑结构中并使用索引来高效地查询数据是更自然(更快捷)的方法。
因此,您只需按原样使用分层结构即可,例如:
<tree>
<node pattern="ABCD">
<node pattern="ABC">
<node pattern="AB"/>
<node pattern="AC"/>
<node pattern="BC"/>
</node>
<node pattern="ABD">
<node pattern="AB"/>
<node pattern="AD"/>
<node pattern="BD"/>
</node>
</node>
</tree>
因此,我猜您是出于性能原因选择了这种格式。但是在构建数据库时,您应该创建一个属性索引,即所有属性值都将被索引。通常,对于更常见的查询,应将其重写,但是您可以直接使用属性索引。例如,我有一个50GB以上的数据库,其中包含英语维基百科的转储。例如,我选择搜索页面
List of Dragon Ball characters
:db:attribute("wikipedia", "List of Dragon Ball characters")/parent::*
在我的机器上执行大约需要20毫秒。
因此类似地,您可以简单地搜索模式并沿着树上走:
db:attribute("<YOUR_DB>", "AB")/ancestor::node/@pattern => distinct-values()
考虑到您首先使用索引,然后简单地向上移动 parent ,这应该尽可能快。
关于xml - 用XML存储带有共同 inode 的树的最有效方式,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50681347/