✖

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 คำนวณได้จาก:

v=12d⋅N

โดยที่ N คือจำนวนเวกเตอร์ทั้งหมดในชุด ส่วนท้ายความยาว 3 (เช่น …010) ควรปรากฏใน 1/2^3 N = 1/8 N เวกเตอร์ คือ 12.5% ของเวกเตอร์ทั้งหมด

ต่อไปเป็นเรื่องชวนทึ่งเล็กน้อย ให้มัลติเซตของเวกเตอร์ที่ไม่ซ้ำกัน 1,024 เวกเตอร์ ควรมีกี่เวกเตอร์ที่ลงท้ายด้วยส่วนท้าย 0000000000 (ศูนย์สิบตัว) แทนค่าในสูตรจะได้

v=1210⋅1024=11024⋅1024=1

หนึ่งเวกเตอร์ ในเวกเตอร์ฐานสองที่สร้างแบบสุ่มราวหนึ่งพันเวกเตอร์ ควรมีเพียงเวกเตอร์เดียวที่ลงท้ายด้วยศูนย์สิบตัว แล้วจะใช้ข้อมูลนี้ประมาณจำนวนสมาชิกที่ไม่ซ้ำกันได้อย่างไร ทำย้อนกลับได้ ถ้าไล่ดูเวกเตอร์ฐานสองทั้งหมดที่ป้อนเข้า แล้วพบว่าในชุดมีเวกเตอร์เดียวที่ลงท้ายด้วยศูนย์สิบตัว ก็ประมาณได้ว่าชุดนั้นมี 1,024 เวกเตอร์

การวางนัยทั่วไปและการสร้างขั้นตอนวิธี

เป้าหมายคือหาส่วนท้ายที่มีอยู่ในเวกเตอร์เพียงเวกเตอร์เดียว และเป็นส่วนท้ายที่สั้นที่สุดเท่าที่เป็นไปได้ แต่ทำได้ยากมาก เพราะการจะหาเวกเตอร์เช่นนั้นได้จริงต้องเก็บส่วนท้ายทั้งหมดไว้ ซึ่งไม่ต้องการเพราะใช้หน่วยความจำมากเกินไป แทนที่จะทำเช่นนั้น จะหาลำดับของเลขศูนย์ที่ยาวที่สุดที่ท้ายเวกเตอร์ก็พอ

ดังนั้นไล่ดูเวกเตอร์ทั้งหมด นับว่าแต่ละเวกเตอร์มีเลขศูนย์ต่อท้ายกี่ตัว และเก็บค่าสูงสุดของค่าเหล่านี้ไว้ในตัวแปรตัวเดียว เมื่อไล่ดูเวกเตอร์ครบแล้ว จะรู้ความยาวของส่วนท้ายที่ยาวที่สุดซึ่งประกอบด้วยเลขศูนย์เท่านั้น ให้ความยาวนี้แทนด้วยตัวอักษร d ต่อไปจัดรูปสูตรก่อนหน้าให้ตัวแปร N อยู่ข้างเดียว เพื่อให้เป็นผลลัพธ์ของขั้นตอนวิธี ไม่ใช่สิ่งที่ป้อนเข้า และแทน v ด้วยหนึ่งได้ เพราะคาดว่าจะพบเวกเตอร์เช่นนี้เพียงเวกเตอร์เดียว นั่นคือคาดว่า v=1

v=N2dv⋅2d=N2d=N

ดังนั้นเมื่อหาความยาว 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 แทนค่าในสูตรจะได้

22.75≈6.727

นี่คือจำนวนสมาชิกที่ไม่ซ้ำกันโดยเฉลี่ยในแต่ละกลุ่ม ซึ่งแน่นอนว่าไม่ตรงเลย แต่ไม่ต้องกังวล สำหรับเซตขนาดเล็ก ขั้นตอนวิธี 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 ที่อธิบายไว้แล้ว เรื่องนี้จะกล่าวถึงคราวหน้าเช่นกัน

แหล่งอ้างอิง:

สารบัญ: Linear counting: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, Min Value: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, LogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, HyperLogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกันอย่างแม่นยำ