✖

Linear counting: การประมาณจำนวนค่าที่ไม่ซ้ำกัน

ถ้ามีข้อมูลจำนวนมหาศาล จะนับจำนวนค่าที่ไม่ซ้ำกันในชุดข้อมูลนั้นได้อย่างไร เช่น อาจมีบริการที่วัดจำนวนผู้ใช้ที่ไม่ซ้ำกันของเว็บไซต์ขนาดใหญ่ หรือแม้แต่ของทั้งโดเมน .th/.com/.อะไรก็ได้

วิธีพื้นฐาน

ดูเหมือนไม่มีอะไรยาก แค่ไล่ดูข้อมูลทีละตัวแล้วเก็บแต่ละค่าไว้เพียงครั้งเดียวในโครงสร้างข้อมูลที่เหมาะสม ในภาษา Python อาจเขียนได้ประมาณนี้ (โค้ดยาวเกินจำเป็นโดยตั้งใจ):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

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

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

ไม่มีใครอยากได้แบบนี้ แล้วจะแก้อย่างไร

อาจลองเก็บตัวระบุให้มีประสิทธิภาพมากขึ้น หรือใช้ภาษา C แทน Python ซึ่งลดหน่วยความจำที่ใช้ได้มาก แต่ก็ยังไม่ดีพอ และโปรแกรมก็ยังใช้พื้นที่มหาศาลอยู่ดี จึงต้องถามตัวเองว่า จำเป็นต้องรู้อย่างแม่นยำจริง ๆ ว่าค่าที่ไม่ซ้ำกันมี 9,563,618 ค่าไม่ขาดไม่เกิน ถ้าใช้จำนวน 9,547,666 แทนจะเสียหายอะไรหรือไม่ ถ้าคำตอบคือเสียหายและต้องการค่าที่แม่นยำ ก็ทำแบบนั้นไป แต่ถ้าไม่ใช่ ลองมาดูวิธีประมาณจำนวนค่าที่ไม่ซ้ำกันในชุดข้อมูลให้แม่นยำที่สุด เร็วที่สุด และใช้หน่วยความจำน้อยที่สุด

ฟังก์ชันแฮช ตัวช่วยของเรา

พิจารณาฟังก์ชันแฮช (hash function) ที่รับสตริงเข้าไปและคืนค่าเป็นจำนวน n บิต ถ้าคุ้นเคยกับฟังก์ชันแฮชที่ “คืนค่าเป็นสตริง” มากกว่า ก็ให้นึกว่าฟังก์ชันนำสตริงนั้นไปแปลงเป็นจำนวนต่ออีกทอดหนึ่ง ไม่มีอะไรซับซ้อน จำนวนบิตบอกว่าจำนวนนั้นใหญ่เพียงใด ฟังก์ชัน 8 บิตคืนค่าเป็นจำนวนที่ใช้แปดบิต และแปดบิตเก็บค่าที่ต่างกันได้ 28 ค่า ซึ่งโดยทั่วไปคือจำนวนเต็มตั้งแต่ 0 ถึง 255 ต่อไปจะใช้ฟังก์ชันแฮช 24 บิต ฟังก์ชันเช่นนี้คืนค่าที่ต่างกันได้ 224 ค่า ซึ่งเท่ากับ 16,777,216

แทนที่จะเก็บค่าเอง จะเก็บค่าแฮช 24 บิตของค่าเหล่านั้น การเก็บค่าแฮช 24 บิตสิบล้านค่าต้องใช้ 30 MB ซึ่งดีกว่า 360 MB เดิมถึงสิบเท่า โค้ดอาจเป็นดังนี้:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

ฟังก์ชัน hash เป็นฟังก์ชันในตัวของ Python ซึ่งคืนค่าเป็นจำนวนเต็ม ฟังก์ชัน nhash แสดงการเขียนฟังก์ชันแฮช n บิตแบบง่าย ๆ ไม่จำเป็นต้องเข้าใจว่าทำงานอย่างไร เพราะที่จริงก็ทำงานไม่ถูกต้อง ผลลัพธ์ของฟังก์ชันนี้ไม่ได้ใช้ 24 บิต แต่ตอนนี้ไม่สำคัญ สิ่งที่ต้องการแสดงคือหลักการ

ต่อมาคือฟังก์ชัน count_unique_using_nhash ซึ่งนับค่าที่ไม่ซ้ำกัน ฟังก์ชันนี้ไล่ดูทุกค่า คำนวณค่าแฮชของแต่ละค่า แล้วเก็บไว้ในตัวแปร found ถ้ายังไม่มีค่านั้นอยู่

ปัญหาของวิธีนี้คือ ฟังก์ชันแฮชอาจคืนผลรวมตรวจสอบ (checksum) เดียวกันสำหรับสตริงที่ต่างกัน นั่นคืออาจเกิดการชน (collision) ยิ่งเกิดการชนมาก ผลลัพธ์ก็ยิ่งคลาดเคลื่อน ฟังก์ชัน count_unique_using_nhash เกือบทุกครั้งจะคืนจำนวนค่าที่ไม่ซ้ำกันน้อยกว่าที่มีอยู่จริง

แล้วควรเลือกฟังก์ชันแฮชใด เรื่องนี้ไม่สำคัญนัก แต่โดยทั่วไปแนะนำให้ใช้ MurmurHash รุ่นใดรุ่นหนึ่ง

บิตแมป

ถ้าเคยเรียนพื้นฐานการเขียนโปรแกรมภาษา C มาอย่างตั้งใจ ก็คงรู้จักบิตแมป (bitmap) แล้วจะใช้บิตแมปได้อย่างไร

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

def count_unique_using_array(values):
    # ลิสต์ยาว 2^24 ที่ทุกตัวเริ่มต้นเป็นศูนย์
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

อย่างไรก็ตาม การใช้อาร์เรย์ในกรณีนี้สิ้นเปลืองหน่วยความจำมาก เพราะแต่ละช่องต้องเก็บเพียงเลข 1 หรือ 0 เท่านั้น จึงใช้อาร์เรย์บิต (bit array) แทนได้ เพื่อให้เข้าใจ จำนวนเต็ม (integer) เก็บได้ เช่น ใน 32 บิต ถ้าแปลงจำนวน 354 เป็นเลขฐานสอง จะได้ 101100010 ดังนั้นในคอมพิวเตอร์ จำนวน 354 ในรูปจำนวนเต็ม 32 บิตจะเก็บไว้ดังนี้ (ไม่สนใจรายละเอียดปลีกย่อย):

00000000 00000000 00000001 01100010

รูปแบบนี้น่าใช้ทีเดียว เพราะในฟังก์ชันของเราต้องการเก็บเพียงเลข 1 และ 0 และเพิ่งเห็นว่าจำนวนธรรมดาก็เป็นเพียงกองของเลข 0 และ 1 นั่นเอง (เหมือนทุกอย่างในคอมพิวเตอร์) กล่าวโดยสรุปคือ ด้วยการดำเนินการระดับบิต (bitwise operation) จะเก็บเลข 1 ให้ใช้พื้นที่เพียงหนึ่งบิตจริง ๆ ได้

กลับไปที่ฟังก์ชันที่ใช้อาร์เรย์ ถ้าเขียนใหม่ด้วยอาร์เรย์บิต สำหรับฟังก์ชันแฮช 24 บิตจะใช้อาร์เรย์บิตขนาด 224 บิตก็พอ ซึ่งเท่ากับ 2 MiB เป็นการปรับปรุงที่ดีมาก

ถ้าใช้ฟังก์ชันแฮช 32 บิต ซึ่งมีค่าผลลัพธ์ที่ต่างกันได้ 232 ค่า หรือ 4,294,967,296 ค่า จะต้องใช้อาร์เรย์บิตขนาดครึ่งกิกะไบต์ ซึ่งถือว่าไม่เลว เพราะนับค่าที่ไม่ซ้ำกันได้ถึงระดับพันล้าน

Linear Counting

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

อย่างไรก็ตาม ค่าประมาณที่คำนวณด้วยฟังก์ชันแฮชทำให้แม่นยำขึ้นได้อีก โดยใช้แนวคิดง่าย ๆ ว่า ยิ่งชุดข้อมูลมีค่าที่ไม่ซ้ำกันมาก ก็ยิ่งมีโอกาสเกิดการชนมากขึ้นเรื่อย ๆ (การชน คือข้อมูลขาเข้าสองค่าที่ต่างกันให้ผลลัพธ์จากฟังก์ชันแฮชเดียวกัน คือผลรวมตรวจสอบเดียวกัน) ต่อไปจะคำนวณกันเล็กน้อย จึงกำหนดตัวแปรบางตัวไว้ก่อน:

  • จะใช้ฟังก์ชันแฮช h ขนาด n บิต
  • จำนวนผลลัพธ์ที่เป็นไปได้ทั้งหมดของฟังก์ชัน h จึงเท่ากับ 2n ให้จำนวนนี้แทนด้วยตัวอักษร m นั่นคือ m=2n
  • อาร์เรย์บิตที่ใช้บันทึกว่าพบผลรวมตรวจสอบใดแล้ว แทนด้วยอักษรตัวใหญ่ A อาร์เรย์ A มีความยาว m
  • เมื่อขั้นตอนวิธีไล่ดูชุดข้อมูลครบแล้ว บางค่าในอาร์เรย์บิตจะเป็นศูนย์และบางค่าจะเป็นหนึ่ง สิ่งที่สนใจเป็นหลักคืออัตราส่วน “จำนวนศูนย์หารด้วยความยาวของอาร์เรย์” ซึ่งบอกสัดส่วนของศูนย์ในอาร์เรย์บิต ตอนเริ่มต้นอัตราส่วนนี้เท่ากับ 1 เพราะอาร์เรย์เริ่มต้นเป็นศูนย์ทั้งหมด ถ้าเป็นครึ่งต่อครึ่ง อัตราส่วนจะเท่ากับหนึ่งส่วนสอง เป็นต้น ให้ค่านี้แทนด้วย Z และคำนวณจาก Z = จำนวนศูนย์ / m

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

ถ้าค่า Z เท่ากับ 0.99 หมายความว่าอาร์เรย์บิตมีเลข 1 อยู่หนึ่งส่วนร้อย และ 99% ของอาร์เรย์เป็นศูนย์ ซึ่งยังดีอยู่ มีแนวโน้มว่าระหว่างการคำนวณไม่ได้เกิดการชนมากนัก และอาจไม่ต้องแก้ไขเลยหรือแก้ไขเพียงเล็กน้อย แต่ถ้าค่า Z เท่ากับ 0.05 แสดงว่าอาร์เรย์เหลือศูนย์อยู่เพียง 5% และระหว่างการคำนวณน่าจะเกิดการชนมากมาย จึงต้องแก้ไขมาก

แล้วจะคำนวณการแก้ไขนี้อย่างไร จะใช้ลอการิทึมช่วย ซึ่งเป็นฟังก์ชันที่มีลักษณะดังนี้:

สิ่งที่สนใจคือส่วนสีแดงบนช่วง (0, 1] ถ้าให้ค่า Z อยู่บนแกน x จะได้ว่า ยิ่ง Z มีค่ามาก ค่า y ก็ยิ่งเข้าใกล้ศูนย์ ในทางกลับกัน ยิ่ง Z มีค่าน้อย ค่า y ก็ยิ่งน้อย ค่าประมาณสุดท้ายคำนวณได้โดยนำจำนวนนี้คูณด้วย -m สังเกตว่าถ้า Z มีค่าน้อยพอ จะได้จำนวนที่น้อยกว่า -1 ด้วยซ้ำ และเมื่อคูณค่านี้ด้วย -m จะได้ค่าประมาณที่มากกว่า m นั่นคือประมาณว่าจำนวนค่าที่ไม่ซ้ำกันมากกว่าจำนวนผลรวมตรวจสอบทั้งหมดที่ฟังก์ชันแฮช h ให้ได้

สูตรทั้งหมดสำหรับคำนวณจำนวน p ของค่าที่ไม่ซ้ำกันเป็นดังนี้:

p=−m⋅ln⁡Z

การเขียนโปรแกรม (ไม่ใช้อาร์เรย์บิต ใช้เพียงอาร์เรย์ธรรมดา) อาจเป็นดังนี้:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log ในที่นี้คือลอการิทึมธรรมชาติฐาน e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

ในฟังก์ชัน linear_counting ขั้นแรกคำนวณค่าประมาณแรกด้วยขั้นตอนวิธีก่อนหน้าซึ่งใช้ฟังก์ชันแฮช n บิต จากนั้นคำนวณสัดส่วนของศูนย์ในอาร์เรย์และแก้ไขตามสูตร ลอการิทึมในโค้ดคือลอการิทึมธรรมชาติ ตัวแปร nonunique_values มีสตริงที่ไม่ซ้ำกัน number_of_unique_values สตริง ในตัวอย่างนี้ลิสต์ nonunique_values จึงมีค่าที่ไม่ซ้ำกันหนึ่งหมื่นค่า โค้ดแปลก ๆ ในบรรทัดที่หกทำให้ลิสต์มีค่าที่ซ้ำกันหลายค่า คือนำลิสต์ของค่าชุดเดิมไปต่อท้ายลิสต์ ทำให้แต่ละค่าอยู่ในลิสต์สองครั้ง แล้วจึงเริ่มนับ ในอุดมคติฟังก์ชันควรตอบว่าลิสต์มีค่าที่ไม่ซ้ำกันหนึ่งหมื่นค่า ผลลัพธ์:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

เนื่องจากโปรแกรมสร้างลิสต์ nonunique_values ใหม่ทุกครั้ง ผลลัพธ์จึงต่างกันในแต่ละครั้งที่เรียกใช้ ในที่นี้ใช้ฟังก์ชันแฮช 16 บิต จะเห็นว่าค่าประมาณแรกจากฟังก์ชัน count_unique_using_array คือลิสต์มีค่าที่ไม่ซ้ำกัน 9,289 ค่า การแก้ไขทำให้ค่าประมาณแม่นยำขึ้นเป็น 10,017 ซึ่งถือว่าดีพอสมควร ค่าประมาณมากกว่าค่าจริงเพียง 0.17% ขณะที่ก่อนแก้ไขน้อยกว่าค่าจริงถึง 7.11% ซึ่งค่อนข้างมาก

ถ้าใช้ฟังก์ชันแฮชที่ “ใหญ่กว่า” เช่น 24 บิต จะได้ผลลัพธ์ที่แม่นยำกว่า:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

แค่ค่าประมาณแรกก็ใช้ได้แล้ว และหลังแก้ไขได้หนึ่งหมื่นตรงตามจริง ลองดูตัวอย่างที่มีตัวระบุที่ไม่ซ้ำกันหนึ่งล้านตัว นั่นคือ number_of_unique_values = 1000000 เมื่อใช้ฟังก์ชันแฮช 24 บิตจะได้ผลลัพธ์ดังนี้:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

ใช้ได้ทีเดียว และถ้าเขียนโปรแกรมด้วยอาร์เรย์บิต อาร์เรย์จะใช้หน่วยความจำเพียงสองเมกะไบต์ตามที่กล่าวไว้ (บวกกับที่ภาษาโปรแกรมใช้เอง) ถือว่าดีทีเดียว But we can do better! ทำได้ดีกว่านี้มาก แต่ไว้คราวหน้า

ระหว่างนี้อ่านบทความ A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] ได้ หรือจะอ่านตอนถัดไปของชุดบทความนี้ต่อก็ได้: ขั้นตอนวิธี min-value

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