XQuery/查找重复文档

动机

您有一组文档，其中可能包含某些文档的完全相同的副本。您希望检测并删除所有重复的文档。

方法

有两种方法。一种是编写一个“比较”函数，该函数将比较列表中的每个元素和节点与列表中的其他每个项目。这种方法的问题在于它将在大致 n 平方的时间内运行，对于较大的数据集而言，这可能会非常慢。当您的数据集非常小时，“成对比较”是最好的。

在这个示例中，我们将为每个文档创建一个唯一的“哈希”值。然后，您可以删除所有具有相同哈希值的文档。哈希至关重要，因为创建哈希后，它可以被存储并用于将来的比较。因此，您拥有了一种非常一致的方法来找出新文档是否唯一。比较文档的哈希值会给用户一个非常快速的问题答案——*我们以前见过这个文档吗？*

关于哈希函数

哈希函数接受一个输入字符串，并对其执行数学函数，这将产生一个相当短的字符串，从实际意义上讲，它是唯一的，这使得两个不同文档具有相同哈希值的概率非常非常低。例如，如果您每秒计算一百万个哈希，则重复项每百亿年才会出现一次。这对大多数商业应用程序来说已经足够好了。关键点是，如果文档中的一个字符不同，则哈希将完全不同。

我们使用哈希函数的方式是使用 XQuery 函数，例如

  util:hash($input, $algorithm) (see eXist documentation)

其中 $input 是您的输入文档，$algorithm 是一个标识您将使用哪个哈希函数的字符串。常见的算法包括“md5”、“sha1”和“sha256”。哈希函数始终返回一个称为哈希值、哈希码、哈希和、校验和或简称为哈希的单个字符串。

以下是如何使用 md5 哈希函数的示例。

xquery version "1.0";
let $input := 'Hello World!'
let $hash := util:hash($input, 'md5')
return
<results>
  The MD5 hash for '{$input}'={$hash}
</results>

返回

<results>
  The MD5 hash for 'Hello World!'=ed076287532e86365e841e92bfc50d8c
</results>

计时您的哈希函数

MD5 是哈希算法中最受欢迎的版本之一，因为它非常快，并且始终返回易于存储、用作 REST 参数以及比较值的长度一致的字符串。以下是一个计算“哈姆雷特”整个 XML 文件（大约 7,842 行 XML）哈希的 XQuery 示例。

xquery version "1.0";
let $file-path := '/db/shakespeare/plays/hamlet.xml'
let $input := doc($file-path)/PLAY
let $start-time := util:system-time()
let $hash := util:hash($input, 'md5')
let $end-time := util:system-time()
return
<results>
  <input-file>{$file-path}</input-file>
  <hash>{$hash}</hash>
  <execution-time>{(($end-time - $start-time) div xs:dayTimeDuration('PT1S'))  * 1000} milliseconds</execution-time>
</results>

此程序使用“系统计时器”并返回以下结果

<results>
   <input-file>/db/shakespeare/plays/hamlet.xml</input-file>
   <hash>00f1bf99e42afb434dca712f9625aeac</hash>
   <execution-time>15 milliseconds</execution-time>
</results>

上面的示例在本地系统上多次运行时，要么返回 0，要么返回 15 毫秒。这表明时间反映了磁盘 I/O，因此哈希运行非常快，即使在慢速计算机上处理大型文件，通常也低于 10 毫秒。

请注意，哈希函数对文档的“序列化”方式非常敏感，默认行为可能不是您预期的。默认哈希仅适用于文档的 string() 值或元素“content”。请注意，XML 节点的 string() 值不包含文档的属性或元素名称。这不是错误，因为哈希函数被设计为对字符串而不是 XML 文档进行操作。以下有两个文件，它们具有相同的内容，但元素名称不同

xquery version "1.0";
let $input1 := <x a="1">Hello <b>World!</b></x>
let $input2 := <y b="2">Hello <i>World!</i></y>
let $hash1 := util:hash($input1, 'md5')
let $hash2 := util:hash($input2, 'md5')
return
<results>
  <compare>
    <input1>{$input1}</input1>
    <input2>{$input2}</input2>
    <hash1>{$hash1}</hash1>
    <hash2>{$hash2}</hash2>
    {if ($hash1=$hash2)
       then "same"
       else "different"
     }</compare>
</results>

返回以下内容

<results>
    <input1>
        <x a="1">Hello <b>World!</b>
        </x>
    </input1>
    <input2>
        <y b="2">Hello <b>World!</b>

        </y>
    </input2>
    <hash1>ed076287532e86365e841e92bfc50d8c</hash1>
    <hash2>ed076287532e86365e841e92bfc50d8c</hash2>
    <compare>same</compare>
</results>

仔细定义文档相等性

当我们问“我已经有这个文档的副本了吗？”时，我们需要首先定义重复文档的含义。在本例中，我们将将其定义为具有完全相同的属性和元素，并且顺序完全相同的 XML 文档。从技术上讲，XML 可能具有不同顺序的属性，它们可能被认为是相同的，也可能被认为是重复文档。元素的前后空格可能很重要，也可能不重要。无论您的方法如何，都应该仔细定义适合您情况的“相同性”概念。

为每个文档创建一致的序列化

我们希望有一个函数可以将每个 XML 文档转换为一个字符串，该字符串删除所有缩进。这有时被称为 XML 文档的“规范”版本。以下函数为每个 XML 文档创建一个字符串

如果您运行的是 eXist 1.5，则 util 模块有一个“serialize”函数，该函数可以将整个 XML 文档转换为一个字符串。

 let $string-version-of-xml-file := util:serialize($input-xml-file, ())

在以下示例中，文件是相同的，除了一个属性的名称。

xquery version "1.0";
let $input1 := <x a="1">Hello <b>World!</b></x>
let $input2 := <y b="1">Hello <b>World!</b></y>
let $hash1 := util:hash(util:serialize($input1, ()), 'md5')
let $hash2 := util:hash(util:serialize($input2, ()), 'md5')
return
<results>
  
    <input1>{$input1}</input1>
    <input2>{$input2}</input2>
    <hash1>{$hash1}</hash1>
    <hash2>{$hash2}</hash2>
    <compare>
     {if ($hash1=$hash2)
       then "same"
       else "different"
     }</compare>
</results>

如果您的系统没有序列化函数，您可以使用简单的递归函数创建自己的函数。

将 XML 文档转换为字符串

以下函数可用于以一致的格式复制 XML 文件。

declare function local:copy($element as element()) {
  element {node-name($element)}
    {$element/@*,
     for $child in $element/node()
        return if ($child instance of element())
          then local:copy($child)
          else $child
    }
};

这样做的优势在于，所有属性都将以一致的顺序出现。

此函数还可以修改以添加和删除与您的比较无关的元素或属性。请参阅：使用 XQuery 的标识转换

比较集合中的所有文件

以下程序将计算集合中所有文件的哈希值。然后，它将报告哪些哈希值相同。

xquery version "1.0";

let $title := 'Find Duplicate Documents'

let $input-collection := '/db/test/hash/docs'
let $file-names := xmldb:get-child-resources($input-collection)

let $hashes :=
<hashes>
   {for $file in $file-names
        let $file-path := concat($input-collection, '/', $file)
        let $doc := doc($file-path)
        let $string-of-doc := util:serialize($doc, ())
        let $md5-hash-of-string-of-doc := util:hash($string-of-doc, 'md5')
        return
        <file>
           <file-name>{$file}</file-name>
           <hash>{$md5-hash-of-string-of-doc}</hash>
        </file>
   }
</hashes>

return
<results>
  <title>{$title}</title>
  <input-collection>{$input-collection}</input-collection>
  {$hashes}
  {for $file1 in $file-names
    let $hash-for-file1 := $hashes/file[file-name=$file1]/hash/text()
    return
    <result>
       <file>{$file1}</file>
       <same-as>{
          for $file2 in $file-names
          let $hash-for-file2 := $hashes/file[file-name=$file2]/hash/text()
          return
            if ($file1 ne $file2 and $hash-for-file1 = $hash-for-file2)
             then $file2
             else 
               ()
          }
       </same-as>
    </result>
   }
</results>

示例输出

<results>
    <title>Find Duplicate Documents</title>
    <input-collection>/db/test/hash/docs</input-collection>
    <hashes>
        <file>
            <file-name>1.xml</file-name>
            <hash>a1facfc0b442306b3cd3d29dd3494108</hash>
        </file>
        <file>
            <file-name>2.xml</file-name>
            <hash>70b78ba529fdcb44ea22b02257385ea0</hash>
        </file>
        <file>
            <file-name>3.xml</file-name>          
            <hash>df13cee105164d50eeda912943391d0b</hash>
        </file>
        <file>
            <file-name>4.xml</file-name>
            <hash>a1facfc0b442306b3cd3d29dd3494108</hash>
        </file>
    </hashes>
    <result>
        <file>1.xml</file>
        <same-as>4.xml</same-as>
    </result>
    <result>
        <file>2.xml</file>
        <same-as/>
    </result>
    <result>
        <file>3.xml</file>
        <same-as/>
    </result>
    <result>
        <file>4.xml</file>
        <same-as>1.xml</same-as>
    </result>
</results>