[發明專利]一種錯誤親緣關系環深度優先檢測方法和裝置

無效

• 申請號: 201310582087.3
• 申請日: 2013-11-20
• 公開（公告）號: CN103632042A
• 公開（公告）日: 2014-03-12
• 發明（設計）人: 倪龍
• 申請（專利權）人: 寧波保稅區攀峒信息科技有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于計算機信息處理領域，尤其涉及一種錯誤親緣關系環深度優先檢測方法和裝置。

背景技術

數據質量問題是影響數據可用性的一個重要因素，在數據質量問題當中，主要有兩類問題，一是數據沖突，二是數據錯誤。數據沖突和數據錯誤在很多時候存在交叉，一般來說有很多數據沖突是由于錯誤的數據引起的，比如兩個數據分別表示某人有兩個不同親生父親，顯然其中有一個是錯誤的，但也不全部如此，有些數據沖突是親緣關系表示的原因造成的，比如說同類的親緣關系數據只能選其中一個（一般選最優的），比如一個人有兩個妻子，但其中必然有一個是不合法的或者是過去式的（前妻），但兩個數據本身并沒有錯。數據沖突只有在有兩個親緣關系數據進行比較時才有，而數據錯誤可以在兩個數據比較時發現錯誤，也可以在不進行比較時發現錯誤，還可以通過對多個數據進行綜合判斷而得出。這里的數據錯誤就是指形成一個關系環的數據錯誤，一般要通過對兩個以上的多個數據進行綜合判斷（但在極端情況下也可通過對一個或者兩個數據親緣關系數據進行判斷而得出）才能發現的錯誤，以和數據沖突時很多情形的數據錯誤及單個數據可以判斷等情況相區別。

并不是所有的關系環都是錯誤親緣關系環，一個親生父母子女關系在非通用的表示中，親生父母的親緣關系數據通過其親生子女屬性指向親生子女，而親生子女的親緣關系數據通過其親生父親或母親屬性指向親生父親或母親，就形成了一個關系環，這是由于親緣關系的相互性形成的最小的關系環，是正常的。錯誤親緣關系環的錯誤種類與親緣關系種類（包含多種親緣關系類別）有關，以血親關系為例，甲的父親為乙，乙的父親為丙，丙的父親為甲，這就形成了一個錯誤的親緣關系環，跨親緣關系種類的錯誤親緣關系環肯定也會存在，但比較復雜這里不考慮，這里只考慮一種親緣關系種類中的錯誤親緣關系環，也可以更短如甲的父親為甲或甲的父親為乙及乙的父親為甲，但這兩種情況可以通過其它的錯誤檢測方法檢測出來，這里作為兩種特例，即關系人自身之間的關系和兩個互為自反的關系的特例情況。一個有的親緣關系類別的親緣關系數據有可以判斷的數據錯誤，而有的則沒有。收養關系中也存在相同的情況，因此要檢測錯誤親緣關系環，必須根據不同親緣關系種類分別進行考慮，而目前還沒有相關的研究及檢測方法和裝置。

發明內容

本發明要解決錯誤親緣關系環檢測的問題，為解決上述問題，本發明的目的在于提供一種錯誤親緣關系環檢測方法和裝置，采用深度優先的算法，使錯誤親緣關系環能通過一個及以上（一般是三個及以上的多個）的親緣關系數據進行綜合判斷而檢測出錯誤。上述錯誤親緣關系環相比正確的關系環有一個最大的特點，就是親緣關系單向關聯，上述幾個例子就都是以親生父親關系人作為單向關聯的條件，所以導致錯誤的親緣關系環，而正常的則是雙向的關聯。其實在單向關聯的同時引入平行關系的關聯也是能夠判斷錯誤親緣關系環的，甲的父親為乙，乙的同父兄弟姐妹為丙，丙的父親為甲，也構成一個錯誤的關系環。單向關聯不限于同樣的關系人進行關聯，比如前面例子中的父親關系人，用母親關系人也可以，如甲的父親為乙，乙的同父兄弟姐妹為丙，丙的母親為甲，也構成一個錯誤的關系環。因此錯誤親緣關系環檢測的關鍵在于進行單向關聯，單向往上（上一輩的關系人）或者單向往下（下一輩的關系人），平行方向關系人（平輩關系人）均可包含在內不影響整個檢測的單向性，以上所有親緣關系均限于同一親緣關系種類之中。

為解決上述技術問題，本發明提出的錯誤親緣關系環深度優先檢測方法，主要包括以下步驟：

第一步，進行初始化，創建一個檢測分支棧并將第一個分支入棧成為棧頂分支，設置一個關系長度最高允許值，為棧頂第一個分支創建相應的關系長度計數器并置為零及創建一個為空的關系人集合、一個空的親緣關系數據集合及一個該親緣關系數據數據集合當前關聯數據是否已處理的狀態標記；

第二步，將開始檢測的第一個親緣關系數據放入棧頂第一個分支相應的親緣關系數據集合，并標記為該集合當前關聯數據，然后提取數據中參與親緣關系的兩個關系人，如果不相同則均放入棧頂第一個分支相應的關系人集合并將第一個分支相應的關系長度計數器加1，然后將相應的親緣關系數據集合當前關聯數據是否已處理的狀態標記設置為已處理；如果相同則得出檢測結果是檢測出錯誤親緣關系環且出錯的數據集合在上述親緣關系數據集合中，檢測過程結束；

第三步，如果棧為空則檢測過程結束；如果不為空對于且棧頂分支相應的親緣關系數據集合當前關聯數據是否已處理的狀態標記設置為已處理，則按照確定的親緣關系方向往上或往下（均可包括平行方向）取棧頂分支下一個關聯的同種類親緣關系數據，否則直接執行第五步；