演算法要求:
給定錯誤率ε∈(0,φ),該演算法設定m個計數器,且m=1/ε,每個計數器的內容為(e, f, d),
其中e是資料項,f為e的近似頻率,d為近似頻率f與真實頻率F之間的最大差值,即誤差。
對于資料流S中出現的每個元素e按照如下程序記錄每個資料項的出現頻率。
如果當前計數器中存在e的計數器,將計數器的f值增1;
如果當前計數器中不存在e的計數器,但是當前的計數器個數小于m,則新增計數器,令其取值為(e,1,0);
如果當前計數器中不存在e的計數器,且當前的計數器個數等于m,則找到f值最小的計數器,設該計數器記錄的資訊為(em, fm, dm)將其改為記錄當前資料項e,令計數器其取值為(e, fm+1, fm),其中fm和dm是這個計數器原來記錄的資料項的相應的近似頻率和誤差。
當用戶發出查詢滿足φ的頻繁的資料項時,輸出計數器記錄的滿足f >φN的所有資料項。
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/39471.html
標籤:C++ 語言
