3
我有一個使用XSLT中的xsl：key結構構造的節點集。我想找到這個節點集中所有節點的最低共同祖先（LCA） - 有什麼想法？查找XML節點集的最低公共祖先
我知道Kaysian相交和XPath的相交函數，但是這些似乎適合尋找只有一對元素的LCA：我不知道每個節點集中有多少項目。
我想知道是否有可能使用'every'和'intersect'表達式組合的解決方案，但我還沒有想到一個！
由於提前， 湯姆
A
回答
1
這裏是一個底向上的方法：
<xsl:function name="my:lca" as="node()?">
<xsl:param name="pSet" as="node()*"/>
<xsl:sequence select=
"if(not($pSet))
then()
else
if(not($pSet[2]))
then $pSet[1]
else
if($pSet intersect $pSet/ancestor::node())
then
my:lca($pSet[not($pSet intersect ancestor::node())])
else
my:lca($pSet/..)
"/>
</xsl:function>
測試：
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:my="my:my">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:variable name="vSet1" select=
"//*[self::A.1.1 or self::A.2.1]"/>
<xsl:variable name="vSet2" select=
"//*[self::B.2.2.1 or self::B.1]"/>
<xsl:variable name="vSet3" select=
"$vSet1 | //B.2.2.2"/>
<xsl:template match="/">
<!---->
<xsl:sequence select="my:lca($vSet1)/name()"/>
=========
<xsl:sequence select="my:lca($vSet2)/name()"/>
=========
<xsl:sequence select="my:lca($vSet3)/name()"/>
</xsl:template>
<xsl:function name="my:lca" as="node()?">
<xsl:param name="pSet" as="node()*"/>
<xsl:sequence select=
"if(not($pSet))
then()
else
if(not($pSet[2]))
then $pSet[1]
else
if($pSet intersect $pSet/ancestor::node())
then
my:lca($pSet[not($pSet intersect ancestor::node())])
else
my:lca($pSet/..)
"/>
</xsl:function>
</xsl:stylesheet>
當在下面的XML文檔施加這種轉變：
<t>
<A>
<A.1>
<A.1.1/>
<A.1.2/>
</A.1>
<A.2>
<A.2.1/>
</A.2>
<A.3/>
</A>
<B>
<B.1/>
<B.2>
<B.2.1/>
<B.2.2>
<B.2.2.1/>
<B.2.2.2/>
</B.2.2>
</B.2>
</B>
</t>
的希望，正確的結果產生了三種情況下：
A
=========
B
=========
t
更新：我有什麼，我認爲可能是最有效的算法。
這個想法是，一個節點集的LCA和這個節點集的兩個節點的LCA相同：「最左邊」和「最右邊」的那個。證明這是正確的就留給讀者做練習:)
下面是一個完整的XSLT 2.0實現：
<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:my="my:my">
<xsl:output omit-xml-declaration="yes" indent="yes"/>
<xsl:variable name="vSet1" select=
"//*[self::A.1.1 or self::A.2.1]"/>
<xsl:variable name="vSet2" select=
"//*[self::B.2.2.1 or self::B.1]"/>
<xsl:variable name="vSet3" select=
"$vSet1 | //B.2.2.2"/>
<xsl:template match="/">
<xsl:sequence select="my:lca($vSet1)/name()"/>
=========
<xsl:sequence select="my:lca($vSet2)/name()"/>
=========
<xsl:sequence select="my:lca($vSet3)/name()"/>
</xsl:template>
<xsl:function name="my:lca" as="node()?">
<xsl:param name="pSet" as="node()*"/>
<xsl:sequence select=
"if(not($pSet))
then()
else
if(not($pSet[2]))
then $pSet[1]
else
for $n1 in $pSet[1],
$n2 in $pSet[last()]
return my:lca2nodes($n1, $n2)
"/>
</xsl:function>
<xsl:function name="my:lca2nodes" as="node()?">
<xsl:param name="pN1" as="node()"/>
<xsl:param name="pN2" as="node()"/>
<xsl:variable name="n1" select=
"($pN1 | $pN2)
[count(ancestor-or-self::node())
eq
min(($pN1 | $pN2)/count(ancestor-or-self::node()))
]
[1]"/>
<xsl:variable name="n2" select="($pN1 | $pN2) except $n1"/>
<xsl:sequence select=
"$n1/ancestor-or-self::node()
[exists(. intersect $n2/ancestor-or-self::node())]
[1]"/>
</xsl:function>
</xsl:stylesheet>
當在同一個XML文檔進行這種轉變（以上），同樣正確的結果產生，但要快得多 - 特別是如果節點集的規模是大：
A
=========
B
=========
t
+0
輝煌。它看起來像馬丁的代碼也可以工作，但這樣可以更好地擴展，並且將會被未來的同事更容易地閱讀。非常感謝，現在就去測試吧！ – 2012-01-05 14:29:59
+0
@yamahito：不客氣。我用略微改變的解決方案（不再使用'descendant ::'axis）編輯我的答案，這可能更有效率，因爲祖先集是「線性的」，而一組degendents可能是「二次的」。 – 2012-01-05 14:43:11
+0
Gotcha。發揮魅力。 – 2012-01-05 14:45:59
1
我試過如下：
<xsl:stylesheet
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:mf="http://example.com/mf"
exclude-result-prefixes="xs mf"
version="2.0">
<xsl:output method="html" indent="yes"/>
<xsl:function name="mf:lca" as="node()?">
<xsl:param name="nodes" as="node()*"/>
<xsl:variable name="all-ancestors" select="$nodes/ancestor::node()"/>
<xsl:sequence
select="$all-ancestors[every $n in $nodes satisfies exists($n/ancestor::node() intersect .)][last()]"/>
</xsl:function>
<xsl:template match="/">
<xsl:sequence select="mf:lca(//foo)"/>
</xsl:template>
</xsl:stylesheet>
與樣品
<root>
<anc1>
<anc2>
<foo/>
<bar>
<foo/>
</bar>
<bar>
<baz>
<foo/>
</baz>
</bar>
</anc2>
</anc1>
</root>
我得到的anc2元素，但我還沒有更多的測試，測試複雜的設置，現在沒有時間了。也許你可以嘗試使用你的樣本數據，並報告你是否得到你想要的結果。
+0
這看起來不錯，但我想我還沒有滿足自己爲什麼它是[last（）]而不是[1] - 如果直接使用$ nodes/ancestor :: *而不是$所有的祖先？ – 2012-01-05 14:26:41
+0
這個答案的好處在於它是純XPath - 即使我在XSLT中使用Dimitre的解決方案，也可能派上用場進行QA測試。 – 2012-01-05 15:33:11
+0
Martin，您可能對更快的算法感興趣 - 我用我認爲是LCA的最佳算法更新了我的答案。 – 2012-01-06 03:50:57
0
馬丁的解決方案將工作，但我認爲在某些情況下，這可能會非常昂貴，並且會消除重複。我傾向於用一種方法找到兩個節點的LCA，然後遞歸地使用LCA（x，y，z）= LCA（LCA（x，y），z）理論[理論我讓讀者證明......]。
現在通過查看序列x/ancestor-or-self :: node（）和y/ancestor-or-self :: node（），可以非常有效地找到LCA（x，y）以較短的長度，然後找到最後一個節點是在兩個：XQuery中的符號：
(let $ax := $x/ancestor-or-self::node()
let $ay := $y/ancestor-or-self::node()
let $len := min((count($ax), count($ay))
for $i in reverse($len to 1)
where $ax[$i] is $ay[$i]
return $ax[$i]
)[1]
+0
嗨邁克爾，感謝您花時間看看這個。但我不確定在這種情況下如何應用您的答案，因爲我不知道節點集中會有多少個節點（實際上絕大多數情況下只有一個節點），因此我不確定如何在該節點集內的節點對之間進行遞歸（如果有的話）。也爲在這個問題中Kaysian錯誤拼寫道歉！ – 2012-01-05 14:24:09
+0
@Michael Kay：您可能對更快的算法感興趣 - 我用我認爲是LCA的最佳算法更新了我的答案。 – 2012-01-06 03:51:29
相關問題
- 1. 給定節點對的最低公共祖先
- 2. 最低公共祖先（升壓圖）
- 3. 最低公共祖先 - 代碼說明
- 4. python最低共同祖先
- 5. 在neo4j中查找最低共同祖先（LCA）
- 6. 最低公共祖先算法的實際應用是什麼？
- 7. 使用lxml查找所有xml節點python的祖先
- 8. 如何找到一棵樹的最低共同祖先？
- 9. jQuery中最近的祖先節點
- 10. BST的最低公共祖先（返回值中的陌生人行爲）
- 11. 二叉樹的最低公共祖先（不是二叉搜索樹）
- 12. 二叉樹中的最低公共祖先，閱讀輸入和算法
- 13. 如何查找二叉樹中節點的第一個共同祖先？
- 14. 查找兩個Git分支的最新共同祖先
- 15. 有沒有更好的方法找到最低的共同祖先？
- 16. XPath查找包含CSS類的祖先節點
- 17. 節點集（）是否有一個祖先節點？
- 18. 如何使用XPath找到一個祖先或自身的最近的祖先節點列表
- 19. 獲取祖先節點+的XQuery-SQL
- 20. 用它的祖先節點/標籤包裝一個XML元素
- 21. 獲取沒有特定祖先的節點xml xpath
- 22. 在遞歸SQL表中查找最低公共父項
- 23. 獲取最遙遠的祖先節點-Xpath，XSLT
- 24. 遞歸樹，印刷祖先節點
- 25. 最低的共同祖先破解代碼採訪解決方案
- 26. 父母/小孩isa中最低的共同祖先？層次Clojure中
- 27. 根據子節點中的值選擇父/祖先節點
- 28. 如何查找類型類的祖先？
- 29. 查找XML子節點
- 30. 查找兩組最大公共子集的有效算法？
如果有人想知道這裏的大局觀，我在一本書在移動腳註從一個疙瘩結束到文本中引用它們的最低級別。 – 2012-01-05 12:30:52