计算每个节点的 Strahler 数

Question

一个节点的Strahler number 在树中是节点高度概念的概括。

目标是定义一个转换，将数字属性（例如 strahler）添加到 XML 文档的每个节点。

归纳地，节点n的斯特拉勒数表示为Stn(n)，定义如下：

如果n是一片叶子，那么Stn(n)=0
else（n 不是叶子）通过降序 Strahler 值对其 children（n1，...，nd）进行排序：Stn(n1)≥Stn(n2)≥ ... ≥ Stn(nd)。如果 Stn(n1) = Stn(n2) 那么 Stn(n)=n1+1；否则 Stn(n)=Stn(n1)。

例如对于节点 n 和 children n1 n2 n3 和 Stn 1 2 3 分别，Stn n 是 3（因为最大值只出现一次）。对于节点 n with children n1 n2 n3 with Stn 1 2 2，分别将 Stn n 又是 3（因为最大值出现不止一次）。

示例输入:

<root field="4">
<a>
    <aa x="1"/>
    <ab>
        <aba number="36" usefulness="useful">
            <abaa>text1</abaa>
            <abab>
                <ababa>text2</ababa>
            </abab>
        </aba>
        <abb number="37" usefulness="useful">
            <abba>text3</abba>
            <abbb>
                <abbba>text4</abbba>
                <abbbb>text5</abbbb>
            </abbb>
        </abb>
    </ab>
</a>
</root>

输出:

<root strahler="2" field="4">
<a strahler="2">
    <aa strahler="0" x="1"/>
    <ab strahler="2">
        <aba strahler="1" number="36" usefulness="useful">
            <abaa strahler="0">text1</abaa>
            <abab strahler="0">
                <ababa strahler="0">text2</ababa>
            </abab>
        </aba>
        <abb strahler="1" number="37" usefulness="useful">
            <abba strahler="0">text3</abba>
            <abbb strahler="1">
                <abbba strahler="0">text4</abbba>
                <abbbb strahler="0">text5</abbbb>
            </abbb>
        </abb>
    </ab>
</a>
</root>

Answer 1

XSLT 不太可能是这方面的最佳工具，主要是因为它不能真正自下而上地遍历树。可以将 Strahler 数一次添加到树的一层，从最深的一层开始 - 但每次都必须重新处理整个树，从而导致算法效率非常低。

不过，如果没有其他方法可用，您可以尝试这样的操作：

XSLT 2.0

<xsl:stylesheet version="2.0" 
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>

<xsl:variable name="max-depth" select="max(//*/count(ancestor::node()))"/>

<xsl:template match="/">
    <xsl:call-template name="strahler">
        <xsl:with-param name="node-set" select="*"/>
        <xsl:with-param name="current-level" select="$max-depth"/>
    </xsl:call-template>
</xsl:template>

<xsl:template name="strahler">
    <xsl:param name="node-set" select="*"/>
    <xsl:param name="current-level"/>

    <xsl:variable name="next-set">
        <xsl:apply-templates select="$node-set" mode="strahler">
            <xsl:with-param name="current-level" select="$current-level"/>
        </xsl:apply-templates>
    </xsl:variable>

    <xsl:choose>
        <xsl:when test="$current-level > 1">
            <!-- recursive call -->
            <xsl:call-template name="strahler">
                <xsl:with-param name="node-set" select="$next-set"/>
                <xsl:with-param name="current-level" select="$current-level - 1"/>
            </xsl:call-template>
        </xsl:when>
        <xsl:otherwise>
            <xsl:copy-of select="$next-set"/>
        </xsl:otherwise>
    </xsl:choose>
</xsl:template>

<xsl:template match="*" mode="strahler">
    <xsl:param name="current-level"/>
    <xsl:copy>
        <xsl:if test="count(ancestor::node()) = $current-level">
            <xsl:attribute name="strahler">
                <xsl:variable name="max-strahler" select="max(*/@strahler)" />
                <xsl:choose>
                    <xsl:when test="not(*)">
                        <xsl:value-of select="1"/>
                    </xsl:when>
                    <xsl:when test="count(*[@strahler=$max-strahler]) > 1">
                        <xsl:value-of select="$max-strahler + 1"/>
                    </xsl:when>
                    <xsl:otherwise>
                        <xsl:value-of select="$max-strahler"/>
                    </xsl:otherwise>
                </xsl:choose>
            </xsl:attribute>
        </xsl:if>
        <xsl:copy-of select="@*"/>
        <xsl:apply-templates mode="strahler">
            <xsl:with-param name="current-level" select="$current-level"/>
        </xsl:apply-templates>
    </xsl:copy>
</xsl:template>

</xsl:stylesheet>

应用于您的输入示例，结果将是：

<?xml version="1.0" encoding="UTF-8"?>
<root strahler="3" field="4">
   <a strahler="3">
      <aa strahler="1" x="1"/>
      <ab strahler="3">
        <aba strahler="2" number="36" usefulness="useful">
            <abaa strahler="1">text1</abaa>
            <abab strahler="1">
                <ababa strahler="1">text2</ababa>
            </abab>
        </aba>
        <abb strahler="2" number="37" usefulness="useful">
            <abba strahler="1">text3</abba>
            <abbb strahler="2">
                <abbba strahler="1">text4</abbba>
                <abbbb strahler="1">text5</abbbb>
            </abbb>
        </abb>
      </ab>
   </a>
</root>

这与您发布的结果不同，但根据您链接到的维基百科文章中的规则，我相信它是正确的。

请注意，"height" 在这里没有用。

Answer 2

这个更短、更高效的 XSLT 2.0 转换:

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="my:f">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

  <xsl:template match="node()|@*">
    <xsl:copy>
      <xsl:apply-templates select="node()|@*"/>
    </xsl:copy>
  </xsl:template>

  <xsl:template match="*[true()]">
    <xsl:copy>
      <xsl:apply-templates select="@*"/>
      <xsl:attribute name="strahler" select="f:strahler(.)"/>
      <xsl:apply-templates/>
    </xsl:copy>
  </xsl:template>

  <xsl:function name="f:strahler" as="xs:integer" saxon:memo-function="yes">
    <xsl:param name="pElem" as="element()"/>

    <xsl:sequence select=
     "if(not($pElem/*))
        then 1
        else 
           if(not($pElem/*[2]))
             then f:strahler($pElem/*[1])
             else for $maxVal in max($pElem/*/f:strahler(.)),
                      $twoWithMax in 
                           (($pElem/*[f:strahler(.) eq $maxVal])[2]/1, 0)[1]
                    return $maxVal+$twoWithMax
     "/>
  </xsl:function>
</xsl:stylesheet>

应用于所提供的 XML 文档时:

<root field="4">
    <a>
        <aa x="1"/>
        <ab>
            <aba number="36" usefulness="useful">
                <abaa>text1</abaa>
                <abab>
                    <ababa>text2</ababa>
                </abab>
            </aba>
            <abb number="37" usefulness="useful">
                <abba>text3</abba>
                <abbb>
                    <abbba>text4</abbba>
                    <abbbb>text5</abbbb>
                </abbb>
            </abb>
        </ab>
    </a>
</root>

产生正确的结果（注意官方定义的Strahler number 给叶节点 1 -- 不是 0):

<root field="4" strahler="3">
      <a strahler="3">
            <aa x="1" strahler="1"/>
            <ab strahler="3">
                  <aba number="36" usefulness="useful" strahler="2">
                        <abaa strahler="1">text1</abaa>
                        <abab strahler="1">
                              <ababa strahler="1">text2</ababa>
                        </abab>
                  </aba>
                  <abb number="37" usefulness="useful" strahler="2">
                        <abba strahler="1">text3</abba>
                        <abbb strahler="2">
                              <abbba strahler="1">text4</abbba>
                              <abbbb strahler="1">text5</abbbb>
                        </abbb>
                  </abb>
            </ab>
      </a>
</root>

使用 XSLT 3.0 / XPath 3.0 的更紧凑和高效的解决方案:

<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:f="my:f">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>

    <xsl:template match="node()|@*">
        <xsl:copy>
            <xsl:apply-templates select="node()|@*"/>
        </xsl:copy>
    </xsl:template>

    <xsl:template match="*[true()]">
        <xsl:copy>
            <xsl:apply-templates select="@*"/>
            <xsl:attribute name="strahler" select="f:strahler(.)"/>
            <xsl:apply-templates/>
        </xsl:copy>
    </xsl:template>

    <xsl:function name="f:strahler" as="xs:integer" cache="full">
        <xsl:param name="pElem" as="element()"/>

        <xsl:sequence select=
         "let $children := $pElem/*
           return
              if(not($children))
                then 1
                else 
                  if(not($children[2]))
                    then f:strahler($children[1])
                    else 
                      let $childrenStrahler := $children/f:strahler(.),
                          $maxVal := max($childrenStrahler),
                          $twoWithMax := ($childrenStrahler[. eq $maxVal][2]!1, 0)[1]
                        return $maxVal +$twoWithMax 
            "/>
    </xsl:function>
</xsl:stylesheet>

效率:

XSLT is not likely the optimal tool for this ...

如果有人告诉你这个，不要相信他们。

两种提出的解决方案都是有效的，通过使用记忆。

事实上，f:stahler($aNode)对每个不同的元素只计算一次。

请注意使用：

saxon:memo-function="yes"
cache="full"

第一个是Saxon's extension attributes. As per the documentation of saxon:memo-function之一：

Specifying "yes" indicates that Saxon should remember the results of calling the function in a cache, and if the function is called again with the same arguments, the result is retrieved from the cache rather than being recalculated.

第二个是standard feature of XSLT 3.0:

The value cache="full" encourages the processor to retain memory of all previous calls of this function during the same transformation and to reuse results from this memory whenever possible. The value cache="partial" encourages the processor to retain such memory but to discard results if necessary to keep the amount of memory used within bounds. The default value cache="no" encourages the processor not to retain memory of previous calls.

Answer 3

XSLT 非常适合这项工作，Dimitre 的解决方案非常完美 (+1)。

XQuery 1.0 中的替代实现可能如下所示：

declare function local:strahler($nodes as node()*) as node()*
{
  for $node in $nodes
  return
    typeswitch ($node)
    case document-node() return
      document {local:strahler($node/node())}
    case element() return
      element {node-name($node)}
      {
        let $children := local:strahler($node/node())
        let $max := (max($children/@strahler), 1)[1]
        return
        (
          $node/@*,
          attribute strahler {$max + (($children/@strahler[. = $max])[2]/1, 0)[1]},
          $children
        )
      }
    default return
      $node
};

local:strahler(.)

在文件 strahler.xq 中输入 sample.xml 时，可以从命令行运行使用 Saxon，使用以下命令：

java net.sf.saxon.Query strahler.xq -s:sample.xml

与 XSLT 变体一样，它在自下而上添加新属性的同时重写了文档。此处的重写比使用 XSLT 更明显，但在这种情况下已经足够了。

计算每个节点的 Strahler 数

Compute the Strahler number of each node

xslt

xquery