-1

我想在我的 [OWL] (http://www.w3.org/TR/owl-ref/) 文件中引入确定性排序，以便我可以将修改后的文件与原始文件进行比较，并更轻松地查看更改的位置. 该文件由工具（Protege）生成，元素的顺序是半随机变化的。

问题是排序不能基于简单的事情，比如给定元素的名称和属性。通常，差异仅出现在以下几个级别的子节点中。

例子：

  <owl:Class rdf:about="#SomeFooClass">
    <rdfs:subClassOf><!-- subclass definition 1 -->
      <owl:Restriction>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:ID="negate"/>
        </owl:onProperty>
      </owl:Restriction>
    </rdfs:subClassOf>
    <rdfs:subClassOf><!-- subclass definition 2 -->
      <owl:Restriction>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:about="#name"/>
        </owl:onProperty>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
      </owl:Restriction>
    </rdfs:subClassOf>

这里的子类定义 1 和 2（以及其中的其他子元素）按顺序变化，有时 1 是第一个，有时是 2。

我基于一些常见的直接属性（例如 about 和 ID）实现了排序，虽然这修复了许多模棱两可的排序，但它无法解决这个问题。XSLT：

<xsl:stylesheet version="2.0" 
 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>
    <xsl:strip-space  elements="*"/>

    <xsl:template match="@* | node()">
        <xsl:copy>
            <xsl:apply-templates select="@* | node()">
                <xsl:sort select="@rdf:about" data-type="text"/>
                <xsl:sort select="@rdf:ID" data-type="text"/>
            </xsl:apply-templates>
        </xsl:copy>
    </xsl:template>
</xsl:stylesheet>

我在想也许解决方案需要能够为每个元素计算某种“哈希码”，其中考虑到它的子元素的所有内容。这样子类定义 1 可以具有哈希码 3487631，子类定义 2 将具有 45612，并且它们之间的排序将是确定性的（如果它们的子元素未修改）。

编辑：刚刚意识到哈希码计算不应该关心子笔记的顺序来实现它想要做的事情。

我可以主要使用直接已知的属性值，然后使用哈希码，如果它们相等的话。我可能最终会得到类似的东西：

<xsl:stylesheet version="2.0" 
 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>
    <xsl:strip-space  elements="*"/>

    <xsl:template match="@* | node()">
        <xsl:copy>
            <xsl:apply-templates select="@* | node()">
                <xsl:sort select="@rdf:about" data-type="text"/>
                <xsl:sort select="@rdf:ID" data-type="text"/>
                <xsl:sort select="my:hashCode(.)" />
            </xsl:apply-templates>
        </xsl:copy>
    </xsl:template>

   <xsl:function name="my:hashCode" as="xs:string">
      ...
   </xsl:function>
</xsl:stylesheet>

但不知道如何实现 my:hashCode。

编辑：根据要求，举几个例子。保存相同数据时，该工具可能或多或少随机产生例如以下类型的结果 (1-3)：

1.

<owl:Class rdf:about="#SomeFooClass">
    <rdfs:subClassOf><!-- subclass definition 1 -->
      <owl:Restriction>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:ID="negate"/>
        </owl:onProperty>
      </owl:Restriction>
    </rdfs:subClassOf>
    <rdfs:subClassOf><!-- subclass definition 2 -->
      <owl:Restriction>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:about="#name"/>
        </owl:onProperty>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
      </owl:Restriction>
    </rdfs:subClassOf>
</owl:Class>

2.

<owl:Class rdf:about="#SomeFooClass">
    <rdfs:subClassOf><!-- subclass definition 2 -->
      <owl:Restriction>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:about="#name"/>
        </owl:onProperty>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
      </owl:Restriction>
    </rdfs:subClassOf>
    <rdfs:subClassOf><!-- subclass definition 1 -->
      <owl:Restriction>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:ID="negate"/>
        </owl:onProperty>
      </owl:Restriction>
    </rdfs:subClassOf>
</owl:Class>

3.

<owl:Class rdf:about="#SomeFooClass">
    <rdfs:subClassOf><!-- subclass definition 2 -->
      <owl:Restriction>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:about="#name"/>
        </owl:onProperty>
      </owl:Restriction>
    </rdfs:subClassOf>
    <rdfs:subClassOf><!-- subclass definition 1 -->
      <owl:Restriction>
        <owl:onProperty>
          <owl:DatatypeProperty rdf:ID="negate"/>
        </owl:onProperty>
        <owl:maxCardinality rdf:datatype="http://www.w3.org/2001/XMLSchema#int"
        >1</owl:maxCardinality>
      </owl:Restriction>
    </rdfs:subClassOf>
</owl:Class>

这些示例是结构的简化版本，但应该显示原理。我想实现一个 XSLT 排序，它将为所有 3 个示例产生相同的输出。转换后的结果是否看起来像版本 1、2 或 3（或其他排序）并不那么重要。

4

2 回答 2

0

毕竟，我最终在 Java 中实现了排序。

基本上我从孩子开始递归地对DOM进行排序：

private Element sort(Element e) {
    // first, sort children's contents recursively
    List<Element> elementNodes = removeElementChildNodes(e);
    for (Element child: elementNodes) {
        sort(child);
    }
    // after that, sort the order of these children
    List<Element> sortedElementNodes = sortElements(elementNodes);
    // add them back
    for (Element child: sortedElementNodes) {
        e.appendChild(child);
    }
    return e;
}

实际排序首先比较元素名称和几个重要的属性名称，如果都相等，比较节点的规范化字符串转换和它的孩子（孩子的内容此时保证已经排序）

private class ElementSortingComparator implements Comparator<Element> {

    public int compare(Element o1, Element o2) {
        CompareToBuilder c = new CompareToBuilder(); 
        c.append(o1.getTagName(), o2.getTagName());
        c.append(o1.getAttribute(ID_ATTRIBUTE),
                o2.getAttribute(ID_ATTRIBUTE));
        c.append(o1.getAttribute(ABOUT_ATTRIBUTE),
                o2.getAttribute(ABOUT_ATTRIBUTE));
        int result = c.toComparison();
        if (result == 0) {
            String node1 = partialNodeToString(o1);
            String node2 = partialNodeToString(o2);
            result = node1.compareTo(node2);
        }
        return result;
    }
}
于 2012-06-26T08:05:12.307 回答
0

我假设两个节点相等，如果节点名称相同且文本内容相同，则出于排序目的。据我了解，输入文档需要以某种确定性的方式进行排序，但排序是什么并不重要，只要它是确定性的。因此，我建议对节点名称和直接文本子项的组合进行排序。不需要散列。

试试这个样式表：

<xsl:stylesheet version="2.0" 
 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>
    <xsl:strip-space  elements="*"/>

    <xsl:template match="@*|node()">
        <xsl:copy>
          <xsl:apply-templates select="@*" />
          <xsl:apply-templates select="node()">
            <xsl:sort select="namespace-uri()" data-type="text" />
            <xsl:sort select="local-name()" data-type="text"/>
            <xsl:sort select="string-join(./text(),' ')" data-type="text"/>
          </xsl:apply-templates>
        </xsl:copy>
    </xsl:template>

</xsl:stylesheet>
于 2012-06-20T13:49:47.793 回答