Флажолет - Мартин алгоритмі - Flajolet–Martin algorithm

The Флажолет - Мартин алгоритмі болып табылады алгоритм ағындағы ерекше элементтердің санын бір реттік өтуімен және ағынның мүмкін болатын элементтерінің максималды санында кеңістікті тұтыну логарифмімен жуықтау үшін ( нақты мәселе ). Алгоритм енгізілді Филипп Флажолет және Г.Найджел Мартин олардың 1984 жылғы «Деректер базасына қосымшалар үшін ықтимал санау алгоритмдері» мақаласында.^[1] Кейінірек ол «үлкен логиналдарды LogLog санауында» нақтыланған Марианна Дюранд және Филипп Флажолет,^[2] және »HyperLogLog: Кардиналды бағалаудың оңтайлы алгоритмін талдау »бойынша Филипп Флажолет т.б.^[3]

2010 жылғы «Айқын элементтердің оңтайлы алгоритмі» мақаласында,^[4] Дэниэл М. Кейн, Джелани Нельсон және Дэвид П. Вудрафф оңтайлы кеңістікті қолданатын және оңтайлы кеңейтілген алгоритм береді. O(1) жаңарту және есеп беру уақыты.

Алгоритм

Бізге a берілген деп есептейік хэш функциясы ${ displaystyle mathrm {hash} (x)}$ бұл кірісті бейнелейді ${ displaystyle x}$ диапазондағы бүтін сандарға дейін ${ displaystyle [0; 2 ^ {L} -1]}$ және нәтижелер жеткілікті болатын жерде біркелкі бөлінген. 0-ден бастап бүтін сандар жиынтығына назар аударыңыз ${ displaystyle 2 ^ {L} -1}$ ұзындықтың екілік жолдарының жиынтығына сәйкес келеді ${ displaystyle L}$ . Кез-келген теріс емес бүтін сан үшін ${ displaystyle y}$ , анықтаңыз ${ displaystyle mathrm {bit} (y, k)}$ болу ${ displaystyle k}$ екілік көрінісіндегі -ші бит ${ displaystyle y}$ , мысалы:

{ displaystyle y = sum _ {k geq 0} mathrm {bit} (y, k) 2 ^ {k}.}

Содан кейін біз функцияны анықтаймыз ${ displaystyle rho (y)}$ екілік ұсынуда ең аз мәнді жиынтықтың орнын шығаратын ${ displaystyle y}$ :

{ displaystyle rho (y) = min {k geq 0 mid mathrm {bit} (y, k) neq 0 }}

қайда ${ displaystyle rho (0) = L}$ . Жоғарыда көрсетілген анықтамамен біз позициялар үшін 0 индекстеуін қолданатындығымызды ескеріңіз. Мысалға, ${ displaystyle rho (13) = rho (1101_ {2}) = 0}$ , өйткені ең аз бит 1 (0 позиция), және ${ displaystyle rho (8) = rho (1000_ {2}) = 3}$ , өйткені ең аз бит 3-ші орында. Осы сәтте біздің хэш-функциямыздың шығысы біркелкі бөлінеді деген болжам бойынша хэш шығуын бақылау ықтималдылығымен аяқталатынын ескеріңіз. ${ displaystyle 2 ^ {k}}$ (біреуі, содан кейін ${ displaystyle k}$ нөлдер) болып табылады ${ displaystyle 2 ^ {- (k + 1)}}$ , өйткені бұл аударуға сәйкес келеді ${ displaystyle k}$ бастары, содан кейін әділ монетасы бар құйрық.

Енді а-ның маңыздылығын бағалаудың Флажолет-Мартин алгоритмі мультисет ${ displaystyle M}$ келесідей:

Ұзындығы бойынша бит-векторлы BITMAP инициализациясы ${ displaystyle L}$ және барлық 0-ді қамтуы керек.
Әрбір элемент үшін ${ displaystyle x}$ $х$ жылы ${ displaystyle M}$ $М$ :
1. Индексті есептеңіз ${ displaystyle i = rho ( mathrm {hash} (x))}$ .
2. Орнатыңыз ${ displaystyle mathrm {BITMAP} [i] = 1}$ .
Келіңіздер ${ displaystyle R}$ ең кіші индексті белгілеңіз ${ displaystyle i}$ осындай ${ displaystyle mathrm {BITMAP} [i] = 0}$ .
-Ның маңыздылығын бағалаңыз ${ displaystyle M}$ сияқты ${ displaystyle 2 ^ {R} / phi}$ , қайда ${ displaystyle phi шамамен 0.77351}$ .

Идеясы егер ${ displaystyle n}$ - бұл мультисистемадағы белгілі элементтер саны ${ displaystyle M}$ , содан кейін ${ displaystyle mathrm {BITMAP} [0]}$ шамамен қол жетімді ${ displaystyle n / 2}$ рет, ${ displaystyle mathrm {BITMAP} [1]}$ шамамен қол жетімді ${ displaystyle n / 4}$ рет және т.б. Демек, егер ${ displaystyle i gg log _ {2} n}$ , содан кейін ${ displaystyle mathrm {BITMAP} [i]}$ 0-ге тең, әрине ${ displaystyle i ll log _ {2} n}$ , содан кейін ${ displaystyle mathrm {BITMAP} [i]}$ сөзсіз дерлік 1. Егер ${ displaystyle i approx log _ {2} n}$ , содан кейін ${ displaystyle mathrm {BITMAP} [i]}$ 1 немесе 0 деп күтуге болады.

Түзету коэффициенті ${ displaystyle phi шамамен 0.77351}$ есептеулер арқылы табылған, оны түпнұсқа мақалада табуға болады.

Дәлдікті арттыру

Жоғарыдағы формадағы Flajolet-Martin алгоритмінің проблемасы - нәтижелер айтарлықтай өзгереді. Жалпы шешім алгоритмді бірнеше рет іске қосу болды ${ displaystyle k}$ әр түрлі хэш функциялары және әр түрлі жүгіру нәтижелерін біріктіру. Бір идея - мағынасын қабылдау ${ displaystyle k}$ әрбір хэш-функцияның нәтижелері бойынша, түпнұсқалықтың бір бағасын алады. Мәселе мынада, орта есеппен есептелінгендерге өте сезімтал (бұл жерде болуы мүмкін). Басқа идея - пайдалану медиана, бұл аусылшылардың ықпалына аз ұшырайды. Мәселе мынада, нәтиже тек формада болуы мүмкін ${ displaystyle 2 ^ {R} / phi}$ , қайда ${ displaystyle R}$ бүтін сан. Жалпы шешім - орташа мен медиананы біріктіру: Жасау ${ displaystyle k cdot l}$ хэш функциялары және оларды бөлу ${ displaystyle k}$ әр түрлі топтар (әрқайсысының мөлшері) ${ displaystyle l}$ ). Әр топ ішінде медиананы біріктіру үшін пайдаланады ${ displaystyle l}$ нәтижелері, және ақыр соңында ${ displaystyle k}$ соңғы бағалау ретінде топтық бағалау.

2007 жыл HyperLogLog алгоритм мультисетені ішкі жиындарға бөліп, олардың маңыздылығын бағалайды, содан кейін гармоникалық орта оларды түпнұсқа түпнұсқалық үшін бағалауға біріктіру.^[3]

Сондай-ақ қараңыз

Әдебиеттер тізімі

^ Флажолет, Филипп; Мартин, Г.Найджел (1985). «Деректер базасы қосымшаларының ықтимал санау алгоритмдері» (PDF). Компьютерлік және жүйелік ғылымдар журналы. 31 (2): 182–209. дои:10.1016/0022-0000(85)90041-8. Алынған 2016-12-11.
^ Дюрен, Марианна; Флажолет, Филипп (2003). «Ірі кардиналдарды логологиялық санау» (PDF). Алгоритмдер - ESA 2003 ж. Информатика пәнінен дәрістер. 2832. б. 605. дои:10.1007/978-3-540-39658-1_55. ISBN 978-3-540-20064-2. Алынған 2016-12-11.
^ ^а ^б Флажолет, Филипп; Фьюзи, Эрик; Гандует, Оливье; Мюнье, Фредерик (2007). «Гиперлоглог: Кардиналды бағалаудың оңтайлы алгоритмін талдау» (PDF). Дискретті математика және теориялық информатика материалдары. Нанси, Франция. AH: 127–146. CiteSeerX 10.1.1.76.4286. Алынған 2016-12-11.
^ Кейн, Даниэль М .; Нельсон, Джелани; Woodruff, David P. (2010). «Айқын элементтердің оңтайлы алгоритмі» (PDF). Жиырма тоғызыншы ACM SIGMOD-SIGACT-SIGART мәліметтер базасы жүйелерінің принциптері симпозиумының материалдары - PODS '10. б. 41. дои:10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. Алынған 2016-12-11.

Қосымша ақпарат көздері

Раджараман, Ананд; Ульман, Джеффри Дэвид (2011-10-27). Массивті деректерді өндіру. Кембридж университетінің баспасы. б. 119. ISBN 9781139505345. Алынған 2014-11-09.

[1] Флажолет, Филипп; Мартин, Г.Найджел (1985). «Деректер базасы қосымшаларының ықтимал санау алгоритмдері» (PDF). Компьютерлік және жүйелік ғылымдар журналы. 31 (2): 182–209. дои:10.1016/0022-0000(85)90041-8. Алынған 2016-12-11.

[2] Дюрен, Марианна; Флажолет, Филипп (2003). «Ірі кардиналдарды логологиялық санау» (PDF). Алгоритмдер - ESA 2003 ж. Информатика пәнінен дәрістер. 2832. б. 605. дои:10.1007/978-3-540-39658-1_55. ISBN 978-3-540-20064-2. Алынған 2016-12-11.

[flajolet07-3] а ^б Флажолет, Филипп; Фьюзи, Эрик; Гандует, Оливье; Мюнье, Фредерик (2007). «Гиперлоглог: Кардиналды бағалаудың оңтайлы алгоритмін талдау» (PDF). Дискретті математика және теориялық информатика материалдары. Нанси, Франция. AH: 127–146. CiteSeerX 10.1.1.76.4286. Алынған 2016-12-11.

[4] Кейн, Даниэль М .; Нельсон, Джелани; Woodruff, David P. (2010). «Айқын элементтердің оңтайлы алгоритмі» (PDF). Жиырма тоғызыншы ACM SIGMOD-SIGACT-SIGART мәліметтер базасы жүйелерінің принциптері симпозиумының материалдары - PODS '10. б. 41. дои:10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. Алынған 2016-12-11.

[1]

[2]

[3]

[4]