✖

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

ในบทความก่อนเรื่อง Linear Counting ได้กล่าวถึงขั้นตอนวิธีพื้นฐานสำหรับคำนวณและประมาณจำนวนค่าที่ไม่ซ้ำกันในชุดข้อมูล คราวนี้จะพิจารณาอัลกอริทึมเชิงความน่าจะเป็น (probabilistic algorithm) อีกแบบหนึ่ง ซึ่งประมาณจำนวนค่าที่ไม่ซ้ำกันได้ค่อนข้างแม่นยำและใช้หน่วยความจำน้อย

Min Value

ในบทความนี้จะใช้เฉพาะจำนวนจริงจากช่วงหนึ่งหน่วย (unit interval) (0, 1) เท่านั้น ลองนึกถึงเซตของจำนวนจากช่วงนี้ที่กระจายอย่างสม่ำเสมอ เช่น เซตของจำนวน {0.25, 0.5, 0.75} จำนวนที่อยู่ติดกันห่างกัน (และห่างจากศูนย์และหนึ่ง) 0.25 เสมอ สิ่งนี้ช่วยนับจำนวนสมาชิกที่ไม่ซ้ำกันได้อย่างไร

ถ้าบอกว่ามีเซตของจำนวนจากช่วงหนึ่งหน่วยที่กระจายอย่างสม่ำเสมอ และจำนวนเหล่านี้ห่างกัน 0.2 จะคำนวณได้หรือไม่ว่าเซตนี้มีสมาชิกกี่ตัว ได้แน่นอน เซตนี้คือ {0.2, 0.4, 0.6, 0.8} ซึ่งมีคาร์ดินัลลิตีเท่ากับสี่ ถ้าข้อมูลขาเข้าเป็นจำนวนจากช่วงหนึ่งหน่วยที่กระจายอย่างสม่ำเสมอ และรู้ระยะห่างระหว่างจำนวนที่อยู่ติดกัน ก็คำนวณจำนวนสมาชิกได้ง่าย

ระยะห่างระหว่างจำนวนที่อยู่ติดกันเท่ากับสมาชิกที่น้อยที่สุดของเซต เช่น ระยะห่างระหว่างสมาชิกที่อยู่ติดกันของเซต {0.25, 0.5, 0.75} คือ 0.25 ดังนั้นเมื่อคำนวณจำนวนสมาชิกของจำนวนที่กระจายอย่างสม่ำเสมอ เพียงหาสมาชิกที่น้อยที่สุดให้ได้ ก็คำนวณจำนวนสมาชิก p ได้ด้วยสูตรง่าย ๆ:

p=1m−1

โดยที่ m คือสมาชิกที่น้อยที่สุดนั้น

กลับมาใช้แฮชอีกครั้ง…

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

วิธีนี้ทำให้ได้จำนวนตรรกยะจากข้อมูล แต่จะทำให้จำนวนเหล่านี้กระจายอย่างสม่ำเสมอได้อย่างไร ข้อนี้ทำไม่ได้ แต่มีทางอื่นช่วยได้ จากมุมมองของเรา ฟังก์ชันแฮชทำงานค่อนข้าง “สุ่ม” สำหรับคำที่คล้ายกันมากอย่าง “ahoj” “ahok” และ “ahol” ฟังก์ชันแฮชน่าจะคืนผลรวมตรวจสอบที่ต่างกันมาก กล่าวอีกอย่างคือ ถ้าแฮชค่าที่ต่างกันหนึ่งพันค่าลงในช่วงหนึ่งหน่วย มีโอกาสน้อยมากที่จำนวนส่วนใหญ่จะน้อยกว่าครึ่งหนึ่ง ในทางกลับกัน มีโอกาสสูงมากที่จำนวนเหล่านี้จะกระจายค่อนข้างสม่ำเสมอ ยิ่งแฮชข้อมูลมาก การกระจายก็ยิ่งสม่ำเสมอ

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

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

ฟังก์ชัน unit_interval_hash คืนทศนิยมจากช่วง (0, 1] ฟังก์ชัน count_unique_using_minimum แปลงค่าขาเข้าทุกค่าเป็นจำนวนดังกล่าวก่อน แล้วหาค่าต่ำสุดและคืนค่า 1 / minimum - 1 สังเกตว่าไม่สำคัญเลยว่าชุดข้อมูลมีค่าที่ซ้ำกันกี่ค่า สำหรับค่าที่เหมือนกันสองค่า ฟังก์ชันแฮชจะคืนจำนวนตรรกยะเดียวกัน ซึ่งไม่มีผลต่อค่าต่ำสุดที่ได้ ขั้นตอนวิธีนี้จึงนับจำนวนสมาชิกที่ไม่ซ้ำกัน

ผลลัพธ์เป็นอย่างไร (แต่ละบรรทัดคือคาร์ดินัลลิตีที่ประมาณได้ โดยคาร์ดินัลลิตีที่ถูกต้องคือ 10,000)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

ไม่ค่อยดีนัก ขั้นตอนวิธีไล่ดูชุดของตัวระบุสิบชุดที่ต่างกัน ซึ่งแต่ละชุดมีค่าที่ไม่ซ้ำกันหนึ่งหมื่นค่า ค่าประมาณที่คำนวณได้ส่วนใหญ่คลาดเคลื่อนมาก ถ้าหาค่าเฉลี่ยจะได้ค่า 18,352 ซึ่งก็ยังคลาดเคลื่อนมาก แต่ในอีกด้านหนึ่ง ลองดูหน่วยความจำที่ใช้ ซึ่งคงตัว การหาค่าต่ำสุดต้องเก็บตัวแปรเพียงตัวเดียวในหน่วยความจำ เพื่อเก็บค่าต่ำสุดปัจจุบัน แค่นั้นเอง ดังนั้นค่าประมาณไม่ดีก็จริง แต่แทบไม่ต้องลงทุนอะไรเลย

การปรับปรุง

จะเห็นว่าปัญหาหลักของขั้นตอนวิธีคือไม่เสถียร บางครั้งให้ค่าประมาณที่ค่อนข้างดี (9,362) บางครั้งให้ค่าประมาณที่ผิดไปมาก (65,536) จะแก้อย่างไร อาจแบ่งข้อมูลขาเข้าออกเป็นหลายส่วน นับจำนวนสมาชิกที่ไม่ซ้ำกันของแต่ละส่วน แล้วหาค่าเฉลี่ยรวมกันในตอนท้าย อาจแบ่งตามอักขระตัวแรกของตัวระบุ คือนับจำนวนค่าที่ไม่ซ้ำกันแยกกันสำหรับตัวระบุที่ขึ้นต้นด้วยตัวอักษร “a” แล้วสำหรับตัวระบุที่ขึ้นต้นด้วยตัวอักษร “b” และต่อไปเรื่อย ๆ โค้ด:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

ส่วนที่เปลี่ยนอยู่ในฟังก์ชัน count_unique_using_minimum ตัวแปร min_values เก็บค่าต่ำสุดของแต่ละกลุ่ม ในตอนท้ายนำค่าต่ำสุดทั้งหมดมาบวกกันแล้วหารด้วยจำนวนค่าที่เก็บไว้ทั้งหมด จะได้ค่าต่ำสุดเฉลี่ย นิพจน์ 1/average_minimum บอกจำนวนค่าที่ไม่ซ้ำกันโดยเฉลี่ยในแต่ละกลุ่ม แล้วนำค่านี้คูณด้วยจำนวนกลุ่ม จะได้ค่าประมาณจำนวนค่าที่ไม่ซ้ำกันในชุดข้อมูลที่ป้อนเข้า ขั้นตอนที่ปรับแล้วนี้ทำงานได้ดีเพียงใด

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

ยังไม่ดีนัก แต่ดีขึ้นแน่นอน ขั้นตอนวิธีเสถียรขึ้น อาจลองปรับฟังก์ชันให้แบ่งกลุ่มไม่ใช่ตามอักขระตัวแรก แต่ตามอักขระสองตัวแรกของตัวระบุ ดังนี้:

first_char = str(item)[0:2] # ToDo: choose better name for variable

ผลลัพธ์จะเป็นดังนี้:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

แบบนี้ก็ไม่เลวแล้วใช่ไหม ถ้าลองใช้ค่าที่ไม่ซ้ำกันหนึ่งแสนค่า อักขระสองตัวแรก และ n = 24 จะได้ผลลัพธ์ดังนี้:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

ถือว่าใช้ได้ แต่ไม่ต้องห่วง ยังมีขั้นตอนวิธีที่ดีกว่านี้อีก

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

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

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