如何查找層次結構中的數據項目位置？

我需要開發一個算法，可以找到某些層次結構中的數據項位置。我有層次結構來分類某些數據集的元素。層次結構是分類學的 - 頂級元素是最通用的類，它匹配數據集的任何元素，更深的元素包含更多與數據集的某個子集相匹配的特定類。如何查找層次結構中的數據項目位置？

例如，考慮遊艇的層次結構。我們有頂級遊艇。在下一級我們有帆船遊艇和機動遊艇。 帆船遊艇有兩個小孩 - 巡遊遊艇和競速遊艇。巡洋艦可以由製造商進一步劃分，例如巴伐利亞遊艇和Dufour Yachts。然後，每個類別可以進一步分爲船體類型，長度，帆面積等。

這是從數據集的例子：

Drive Class Manufacturer Hull type Len Sails Area ... Model 
Sailing Cruiser Bavaria Yachts Mono-hull 25ft 560sqft ... Bavaria 32 
Sailing Cruiser Dufour Yachts Mono-hull 27ft 580sqft ... Dufour 32 Classic

我可以很容易地通過在深度優先順序搜索它的每個樣品，以層次結構進行映射。

這是一個簡單的搜索問題乍一看，但有一些困難。

第一個難點：數據項不一定包含所有元素。數據項缺乏10％到50％的元素是很常見的。很多這樣的元素並不是很重要，例如遊艇變頻器只能是電機或航行所以它不會帶來很多信息（只有1位）。這些元素可以使用更重要的元素輕鬆推斷，例如，如果我們知道遊艇模型，我們可以推斷數據項的所有其他元素（或字段）。

第二個難點：即使它們對應於層次結構中相同的地方（相同的遊艇模型），某些元素可能在不同的數據項之間有所不同。例如帆船區域可能會有很大差異，因爲船主以不同的方式修改了遊艇的鑽井平臺，或者只是圍繞面積值進行修改。

正如我已經提到的，我需要從層次結構中的數據集中找到不同的數據項。每個數據項可以以不同的精度定位。精度是搜索過程停止的層級中的深度。換句話說，我需要在與每個數據項對應的層次結構中獲取路徑，並且此路徑可能不完整。例如，算法可以發現數據項對應於Juliet 23遊艇，但生產年份仍然未知。

這將是很酷，如果我可以得到多個路徑與概率測量每個。例如，對於不同的生產年份，算法可以返回4個路徑，每個路徑的概率爲25％。

在這一刻我用一些啓發式的深度優先搜索來解決這個問題。它給出了很好的結果，但我認爲有可能獲得更好的結果。也許你可以用更一般的方式來制定這個問題，這樣我可以搜索一些有關它的學術論文。

來源

2013-01-22 Lazin

我覺得SQL可以真正幫助您解決困難，

你的第一個困難：使用NVL（字段值是否爲空）

例如：打印類型&生產一年（如果存在）的賽艇

SELECT Y.TYPE, NVL(Y.PRDYEAR, 'UNKNOWN') 
FROM T_YACHT Y WHERE Y.CLASS = 'RACING'

例如：讓所有遊艇，其生產年份是在2000年

SELECT * FROM T_YACHT Y WHERE 
NVL(Y.PRDYEAR,TO_TIMESTAMP('01-01-0001','DD-MM-YYYY')) 
    > TO_TIMESTAMP('01-01-2000','DD-MM-YYYY')

你的第二個困難：使用GROUP BY \ CASCADING-SQL \ DISTINCT \ NVL

例如：看看有多少種賽車遊艇

SELECT Y.TYPE, COUNT(Y.ID) AS YACHT_TYPE 
FROM T_YACHT Y 
WHERE Y.CLASS = 'RACING' 
GROUP BY Y.TYPE

來源

2013-03-23 15:51:09

如何查找層次結構中的數據項目位置？

回答

相關問題