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>