一個在資料串流中統計次數的例子

在看 “Knowledge Discovery from Data Streams" 一書。第 13 頁看到這個例子,如下圖,一個題目,以及解題辦法。

15844327_1485392414807335_2258489309718129409_o.jpg

我想了四個小時,想不透那方法是怎麼回事。所處理的問題:要用二進位制數為基礎,用相對少的 log(M) 的空間,去統計 M 個數字裡頭存在多少個個別數,所用的方法就是概念上二元樹的結構。我卡著而想不透的是,為什麼最後用一個二進制數的表格登記法,就可以支援概括數字的推估。

後來想明白了:輸入的數字依照大小依序分為許多分區,每一個區段如果有數值存在,對空間的提取,直接提取該區段全部的空間。並且,依照二元樹的原則,後一個區段的空間數目,足以包含之前所有區段的空間。數學真是精煉,使我對數學學者產生敬意。

後記:而我覺得頁面最後一行 “the rightmost 1″ 應該是 “the rightmost zero" ,它寫錯了這個字,而使前後文字對不起來。

2017/1/7 後記:不過,我想不清楚的是,如果資料串流是 1, 2, 3, ... ,等資料一個一個出現時,當第二個數字出現之後, BITMAP 會填為 [0, 0, 0, 1, 1, 0] 而發現最右邊的 0 的 R=0 ,於是算出 d=2^0=1 。雖然明明有二個個別數,卻算出只有一個個別數,這使我無法理解何謂 approximate algorighm 。 資料串流的資料處理方案,是可以只算出近似的結果就好嗎?

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Uncategorized 並標籤為 , , , , 。將永久鏈結加入書籤。