LogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกัน
หลังจากตอนก่อน ๆ เรื่อง Linear Counting และ Min Value ในที่สุดก็มาถึง LogLog ซึ่งเป็นอัลกอริทึมเชิงความน่าจะเป็นสำหรับประมาณจำนวนค่าที่ไม่ซ้ำกันในชุดข้อมูลที่เกือบจะดีที่สุด ที่ดีกว่านี้มีเพียงน้องชายคือ HyperLogLog ซึ่งพัฒนามาจาก LogLog แต่ไว้กล่าวถึงคราวหน้า
ทบทวนโจทย์อีกครั้ง ข้อมูลขาเข้าคือชุดข้อมูลหรือมัลติเซต (multiset) เช่น อาร์เรย์หรือตัวสร้าง (generator) ของตัวระบุ ในอาร์เรย์นี้มีบางค่าซ้ำกันหลายครั้ง และต้องการนับจำนวนค่าที่ไม่ซ้ำกันในอาร์เรย์นี้ จำนวนนี้เรียกว่าคาร์ดินัลลิตี (จำนวนค่าที่ไม่ซ้ำกัน) คาดว่าคาร์ดินัลลิตีนี้จะมีค่ามากจริง ๆ มิฉะนั้นก็ใช้ขั้นตอนวิธีแบบดั้งเดิมได้
แนวคิดของขั้นตอนวิธี LogLog
สมมติว่ามีชุดของเวกเตอร์ฐานสอง ไม่ต้องตกใจ เช่น 0001011001001100 เป็นเวกเตอร์ฐานสองที่มีความยาว 16 สมมติว่ามีเวกเตอร์ฐานสองความยาว 32 ทั้งหมดหนึ่งล้านเวกเตอร์ ซึ่งทุกเวกเตอร์สร้างขึ้นแบบสุ่มโดยสมบูรณ์ จะมีเวกเตอร์กี่เวกเตอร์ที่ลงท้ายด้วยเลขศูนย์
แน่นอนว่ารู้แน่ชัดไม่ได้ แต่ถ้าสร้างเวกเตอร์แบบสุ่มจริง ประมาณครึ่งหนึ่งควรลงท้ายด้วยศูนย์ คือ 500,000 เวกเตอร์ แล้วจะมีกี่เวกเตอร์ที่ลงท้ายด้วย 00 หนึ่งส่วนสี่ ลงท้ายด้วย 000 หนึ่งส่วนแปด และต่อไปเรื่อย ๆ แสดงคร่าว ๆ ได้ดังนี้:
รูปแบบของเวกเตอร์ สัดส่วนจากเวกเตอร์ทั้งหมด
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12.5%
...xxx0000 6.25%
... ...
ถ้าถามหาส่วนท้าย (suffix ซึ่งคือสตริงที่อยู่ท้ายสตริงอื่น ตรงข้ามกับส่วนหน้า หรือ prefix) ที่มีความยาว d คาดว่าจะพบเวกเตอร์ v เวกเตอร์ที่ลงท้ายด้วยส่วนท้ายนี้ ค่า v คำนวณได้จาก:
โดยที่ N คือจำนวนเวกเตอร์ทั้งหมดในชุด ส่วนท้ายความยาว 3 (เช่น …010) ควรปรากฏใน 1/2^3 N = 1/8 N เวกเตอร์ คือ 12.5% ของเวกเตอร์ทั้งหมด
ต่อไปเป็นเรื่องชวนทึ่งเล็กน้อย ให้มัลติเซตของเวกเตอร์ที่ไม่ซ้ำกัน 1,024 เวกเตอร์ ควรมีกี่เวกเตอร์ที่ลงท้ายด้วยส่วนท้าย 0000000000 (ศูนย์สิบตัว) แทนค่าในสูตรจะได้
หนึ่งเวกเตอร์ ในเวกเตอร์ฐานสองที่สร้างแบบสุ่มราวหนึ่งพันเวกเตอร์ ควรมีเพียงเวกเตอร์เดียวที่ลงท้ายด้วยศูนย์สิบตัว แล้วจะใช้ข้อมูลนี้ประมาณจำนวนสมาชิกที่ไม่ซ้ำกันได้อย่างไร ทำย้อนกลับได้ ถ้าไล่ดูเวกเตอร์ฐานสองทั้งหมดที่ป้อนเข้า แล้วพบว่าในชุดมีเวกเตอร์เดียวที่ลงท้ายด้วยศูนย์สิบตัว ก็ประมาณได้ว่าชุดนั้นมี 1,024 เวกเตอร์
การวางนัยทั่วไปและการสร้างขั้นตอนวิธี
เป้าหมายคือหาส่วนท้ายที่มีอยู่ในเวกเตอร์เพียงเวกเตอร์เดียว และเป็นส่วนท้ายที่สั้นที่สุดเท่าที่เป็นไปได้ แต่ทำได้ยากมาก เพราะการจะหาเวกเตอร์เช่นนั้นได้จริงต้องเก็บส่วนท้ายทั้งหมดไว้ ซึ่งไม่ต้องการเพราะใช้หน่วยความจำมากเกินไป แทนที่จะทำเช่นนั้น จะหาลำดับของเลขศูนย์ที่ยาวที่สุดที่ท้ายเวกเตอร์ก็พอ
ดังนั้นไล่ดูเวกเตอร์ทั้งหมด นับว่าแต่ละเวกเตอร์มีเลขศูนย์ต่อท้ายกี่ตัว และเก็บค่าสูงสุดของค่าเหล่านี้ไว้ในตัวแปรตัวเดียว เมื่อไล่ดูเวกเตอร์ครบแล้ว จะรู้ความยาวของส่วนท้ายที่ยาวที่สุดซึ่งประกอบด้วยเลขศูนย์เท่านั้น ให้ความยาวนี้แทนด้วยตัวอักษร d ต่อไปจัดรูปสูตรก่อนหน้าให้ตัวแปร N อยู่ข้างเดียว เพื่อให้เป็นผลลัพธ์ของขั้นตอนวิธี ไม่ใช่สิ่งที่ป้อนเข้า และแทน v ด้วยหนึ่งได้ เพราะคาดว่าจะพบเวกเตอร์เช่นนี้เพียงเวกเตอร์เดียว นั่นคือคาดว่า v=1
ดังนั้นเมื่อหาความยาว d ของส่วนท้ายที่เป็นศูนย์ที่ยาวที่สุดได้ ก็ประมาณคาร์ดินัลลิตีด้วยสูตร N=2d
จะได้เวกเตอร์ฐานสองแบบสุ่มมาอย่างไร
สำหรับเวกเตอร์ฐานสองแบบสุ่ม ขั้นตอนวิธีใช้ได้แล้ว แต่จะใช้วิธีนี้กับข้อมูลจริงได้อย่างไร ตามปกติจะใช้ฟังก์ชันแฮชที่เหมาะสม ถ้าข้อมูลขาเข้าเป็นชุดข้อมูล เช่น ตัวระบุ (สตริง) ก็แฮชข้อมูลเหล่านั้นก่อน ผลลัพธ์ของฟังก์ชันแฮช n บิตคือ n บิต ซึ่งในทางปฏิบัติดูเหมือนเวกเตอร์ฐานสองที่สร้างแบบสุ่ม
ถึงตอนนี้เขียนขั้นตอนวิธีได้แล้ว:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
ฟังก์ชัน trailing_zeroes คืนจำนวนเลขศูนย์ที่ท้ายจำนวน ทำได้อย่างไร ถ้าดูจากโค้ดแล้วไม่เข้าใจ ก็อย่าถามเลยดีกว่า แล้วฟังก์ชันนี้แม่นยำเพียงใด สำหรับเซตที่มีสมาชิกไม่ซ้ำกันหนึ่งแสนตัว ฟังก์ชันคืนค่าประมาณ 524,288
อืม…
ไม่ค่อยดีนักใช่ไหม แต่ไม่เป็นไร จะลองปรับปรุงขั้นตอนวิธีแบบเดียวกับ Min Value ก่อนหน้าทุกประการ คือแบ่งข้อมูลขาเข้าเป็นกลุ่มที่ไม่มีสมาชิกร่วมกันหลายกลุ่ม หาส่วนท้ายที่เป็นศูนย์ที่ยาวที่สุดของแต่ละกลุ่ม แล้วหาความยาวเฉลี่ยของส่วนท้ายที่เป็นศูนย์ และใช้ค่านี้ประมาณจำนวนค่าที่ไม่ซ้ำกัน
เช่น อาจกำหนดว่าบิตสองบิตสุดท้ายของแต่ละเวกเตอร์บอกหมายเลขกลุ่ม (bucket) ที่เวกเตอร์นั้นอยู่ เวกเตอร์หกเวกเตอร์นี้
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
แบ่งเป็นสี่กลุ่มได้ตามส่วนท้าย:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
ต่อไปหาความยาวของส่วนท้ายที่เป็นศูนย์ที่ยาวที่สุดในแต่ละเวกเตอร์ โดยข้ามบิตที่ใช้เป็นหมายเลขกลุ่ม “ส่วนท้าย” ที่เป็นศูนย์แสดงด้วยสีเขียว:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
ท้ายสุดคือความยาวของส่วนท้ายที่เป็นศูนย์ที่ยาวที่สุดของแต่ละกลุ่ม จากส่วนท้ายเหล่านี้คำนวณค่าเฉลี่ยเลขคณิตได้ 2.75 แทนค่าในสูตรจะได้
นี่คือจำนวนสมาชิกที่ไม่ซ้ำกันโดยเฉลี่ยในแต่ละกลุ่ม ซึ่งแน่นอนว่าไม่ตรงเลย แต่ไม่ต้องกังวล สำหรับเซตขนาดเล็ก ขั้นตอนวิธี LogLog ให้ผลลัพธ์ที่แย่มาก
เพื่อประมาณคาร์ดินัลลิตีของทั้งเซต ต้องนำค่านี้คูณด้วยจำนวนกลุ่มอีก: 6.727 × 4 = 26.908 ขั้นตอนวิธีคำนวณได้ว่าในชุดมีค่าที่ไม่ซ้ำกันประมาณ 27 ค่า แต่ที่จริงมีหกค่า จึงผิดไปมาก แต่ตอนนี้ไม่เป็นไรจริง ๆ
การเขียนโปรแกรม
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
พารามิเตอร์ k กำหนดว่าจะใช้กี่บิตเป็นดัชนีของกลุ่ม พารามิเตอร์นี้กำหนดความแม่นยำของขั้นตอนวิธี ยิ่ง k มาก ก็ยิ่งแม่นยำ ตัวแปร bucket_index เก็บหมายเลขกลุ่ม แล้วเวทมนตร์ทางขวาของเครื่องหมายเท่ากับทำงานอย่างไร
ตัวแปร num_buckets เก็บจำนวนกลุ่ม ซึ่งเป็นกำลังของสองเสมอ เช่น ถ้า k = 3 แล้ว num_buckets=8 จำนวน 8 ในระบบเลขฐานสองคือ 1000 ลบหนึ่งออกจะได้ 7 ซึ่งคือ 0111 เมื่อลบหนึ่งออกจาก num_buckets จะได้จำนวนที่มีเลข 1 จำนวน k ตัวที่ท้ายและมีแต่ศูนย์ข้างหน้าเสมอ ต่อไปใช้การดำเนินการ AND ระดับบิต (ตัวดำเนินการ &) สำหรับเวกเตอร์ 1110110010100101 การดำเนินการนี้จะเป็นดังนี้:
1110110010100101
& 0000000000000111
------------------
0000000000000101
จุดประสงค์ของเวทมนตร์ทั้งหมดนี้คือ ให้ได้จำนวนที่ข้างหน้ามีแต่ศูนย์ และ k บิตสุดท้ายเหมือนกับค่าแฮช h ที่กำหนด
ต่อไปคำนวณ bucket_hash ซึ่งคือค่าแฮชเดิมที่ตัด k บิตสุดท้ายออก โดยเลื่อนค่าแฮชทั้งหมดไปทางขวา k บิต การเลื่อนบิต (bit shift) คือการเลื่อนทุกบิตในจำนวนไปทางขวา k บิต แล้วเติมศูนย์ทางซ้าย (การเลื่อนบิตไปทางขวาหนึ่งบิตให้ผลเหมือนการหารจำนวนด้วยสองแล้วทิ้งเศษ) จากเวกเตอร์ 1110110010100101 เมื่อเลื่อนสามบิตจะได้ 0001110110010100 เวกเตอร์นี้จะเก็บไว้ในตัวแปร bucket_hash
ต่อไปนับจำนวนศูนย์ที่ท้ายเวกเตอร์นี้ ถ้าค่านี้มากกว่าค่าสูงสุดปัจจุบันที่เก็บไว้ในอาร์เรย์ max_zeroes ที่ดัชนี bucket_index ก็เขียนทับค่านั้น
ท้ายสุดคำนวณจำนวนศูนย์เฉลี่ยของทุกกลุ่ม แล้วคำนวณจำนวนสมาชิกที่ไม่ซ้ำกันโดยเฉลี่ยในแต่ละกลุ่ม (2 ** average_max_zeros) เนื่องจากมีกลุ่มทั้งหมด num_buckets กลุ่ม จึงนำค่านี้คูณด้วยจำนวนกลุ่ม จะได้ค่าประมาณสุดท้ายของจำนวนสมาชิกที่ไม่ซ้ำกัน เฮ้อ ไม่เจ็บตัวเลย ผลลัพธ์สำหรับชุดข้อมูลหลายชุดที่มีค่าที่ไม่ซ้ำกัน 250,000 ค่า และ k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
ไม่นะ ยังผิดอยู่ :-( แต่ไม่ต้องห่วง ใกล้แล้ว สังเกตว่าผลลัพธ์ทุกค่ามากกว่าผลลัพธ์ที่ถูกต้อง ระหว่างการทำงานของขั้นตอนวิธีจะมีความคลาดเคลื่อนต่าง ๆ สะสมขึ้น ค่าประมาณจึงมากกว่าค่าที่ถูกต้องอย่างเห็นได้ชัด อย่างไรก็ตาม ความคลาดเคลื่อนเหล่านี้ค่อนข้างคงที่ และประมาณได้ว่าคลาดเคลื่อนไปเท่าใด เมื่อนำค่าประมาณคูณด้วยค่าคงตัวสำหรับปรับแก้ (correction constant) 0.79402 จะได้ผลลัพธ์ที่ดีขึ้นมาก:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
ได้ลองกับมัลติเซตที่มีคาร์ดินัลลิตีหนึ่งล้านด้วย ผลลัพธ์คือ:
ผลลัพธ์ อัตราส่วนต่อค่าจริง
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
ดีมาก ความคลาดเคลื่อนต่ำกว่า 2.5% ซึ่งถือว่าทำได้ดี และนี่แหละคือขั้นตอนวิธี LogLog โปรแกรมฉบับสุดท้ายที่มีค่าคงตัวสำหรับปรับแก้เป็นดังนี้:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
คราวหน้าจะกล่าวถึงวิธีปรับขั้นตอนวิธีนี้ให้เป็น HyperLogLog ที่เลื่องชื่อและดีที่สุด ตอนนี้จะดูว่าขั้นตอนวิธีนี้ใช้หน่วยความจำเท่าใด
หน่วยความจำที่ใช้
ขั้นตอนวิธีนี้ใช้หน่วยความจำอย่างมีประสิทธิภาพมาก สิ่งเดียวที่ต้องจำคืออาร์เรย์ที่เก็บค่าสูงสุด ความยาวของอาร์เรย์นี้ขึ้นกับค่า k คือจำนวนบิตจากเวกเตอร์ที่ใช้เป็นดัชนีของกลุ่ม สำหรับ k ที่กำหนด จะมีกลุ่มที่ต่างกันทั้งหมด 2k กลุ่ม อาร์เรย์ของค่าสูงสุดจึงมีความยาว 2k ในโปรแกรมเรียกค่านี้ว่า num_buckets
ช่องหนึ่งของอาร์เรย์ต้องใหญ่เพียงใด ช่องนี้เก็บความยาวของส่วนท้ายที่เป็นศูนย์ บอกไว้ก่อนได้เลยว่าค่าแฮช 64 บิตน่าจะเพียงพอสำหรับมัลติเซตทุกเซตที่นึกออกในโลก ดังนั้นอาร์เรย์นี้ต้องเก็บจำนวนตั้งแต่ 0 (เวกเตอร์ที่เป็นเลข 1 ทั้งหมด) ถึง 64 (เวกเตอร์ที่เป็นเลข 0 ทั้งหมด) ได้ นอกจากนี้ ถ้าสมมติว่า k มากกว่าศูนย์เสมอ ก็เก็บเพียงจำนวนตั้งแต่ 0 ถึง 63 ก็พอ ซึ่งใช้เพียง 6 บิต เพราะ 26 = 64
ใช่แล้ว ใช้ “อาร์เรย์” ที่แต่ละช่องมีขนาด 6 บิตก็พอ นอกจากนี้บอกได้ว่าค่า k=10 เพียงพอสำหรับประมาณคาร์ดินัลลิตีได้ค่อนข้างดีจนถึงระดับหลายร้อยล้าน ขั้นตอนวิธีที่ตั้งค่าเช่นนี้จะสร้างอาร์เรย์ขนาด 210 = 1024 ซึ่งแต่ละช่องใช้ 6 บิต รวมแล้วอาร์เรย์นี้ใช้ 6,144 บิต หรือ 768 ไบต์ ไม่ถึงหนึ่งกิโลไบต์ด้วยซ้ำ
แค่นั้นเอง
ไม่ต้องเก็บอะไรอื่นอีก ค่าแฮชที่คำนวณได้ทิ้งไปได้ทันที เพียงรู้จำนวนศูนย์ที่ท้ายเวกเตอร์ก็พอ
สังเกตว่าถ้าใช้ฟังก์ชันแฮชที่ใหญ่กว่า เช่น คืนค่า 128 บิต หน่วยความจำที่ใช้จะเปลี่ยนไม่มากนัก เพราะต้องเก็บจำนวนตั้งแต่ 0 ถึง 127 ซึ่งใช้ 7 บิตก็พอ หน่วยความจำที่ใช้จึงขึ้นกับพารามิเตอร์ k เป็นหลัก นั่นคือจำนวนกลุ่ม
LogLog เหมาะเป็นพิเศษเมื่อต้องนับมัลติเซตที่มีคาร์ดินัลลิตีสูงมากจริง ๆ ดังที่เห็นจากตัวอย่างง่าย ๆ ข้างต้น LogLog จัดการกับมัลติเซตที่มีคาร์ดินัลลิตีต่ำได้ไม่ดีนัก แต่แก้ได้เช่นกัน เช่น ถ้าพบว่ามัลติเซตมีคาร์ดินัลลิตีต่ำ ก็ใช้ขั้นตอนวิธีอื่นในการประมาณแทน เช่น Linear Counting ที่อธิบายไว้แล้ว เรื่องนี้จะกล่าวถึงคราวหน้าเช่นกัน
แหล่งอ้างอิง:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (โค้ดของ LogLog ส่วนใหญ่นำมาจากที่นี่)
สารบัญ: Linear counting: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, Min Value: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, LogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, HyperLogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกันอย่างแม่นยำ