อัลกอริทึมการนับโดยประมาณช่วยให้สามารถนับเหตุการณ์จำนวนมากโดยใช้หน่วยความจำเพียงเล็กน้อย คิดค้นขึ้นในปี 1977 โดยRobert MorrisจากBell Labsโดยใช้เทคนิคความน่าจะเป็นในการเพิ่มค่าตัวนับได้รับการวิเคราะห์อย่างละเอียดในช่วงต้นทศวรรษ 1980 โดยPhilippe FlajoletจากINRIA Rocquencourt ซึ่งเป็นผู้ตั้งชื่อว่าการนับโดยประมาณและมีส่วนสำคัญอย่างยิ่งต่อการยอมรับในหมู่นักวิจัย เมื่อมุ่งเน้นไปที่คุณภาพของการประมาณค่าที่สูงและความน่าจะเป็นของความล้มเหลวที่ต่ำNelsonและ Yu แสดงให้เห็นว่าการปรับเปลี่ยนเพียงเล็กน้อยกับตัวนับของ Morris นั้นเหมาะสมที่สุดในเชิงอะซิมโทติกเมื่อเทียบกับอัลกอริทึมอื่นๆ สำหรับปัญหานี้^{[ 1 ]}อัลกอริทึมนี้ถือเป็นหนึ่งในต้นแบบของอัลกอริทึมการสตรีมและปัญหาทั่วไปของการกำหนดช่วงเวลาความถี่ของสตรีมข้อมูลเป็นหัวใจสำคัญของสาขานี้

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

ในการเพิ่มค่าตัวนับ จะใช้เหตุการณ์ สุ่มเทียมทำให้การเพิ่มค่าเป็นเหตุการณ์เชิงความน่าจะเป็น เพื่อประหยัดพื้นที่ จึงเก็บเฉพาะเลขชี้กำลังเท่านั้น ตัวอย่างเช่น ในระบบเลขฐาน 2 ตัวนับสามารถประมาณค่าได้เป็น 1, 2, 4, 8, 16, 32 และกำลังทั้งหมดของเลขสองความต้องการหน่วยความจำจึงมีเพียงเพื่อเก็บเลขชี้กำลังเท่านั้น

ตัวอย่างเช่น หากต้องการเพิ่มค่าจาก 4 เป็น 8 จะสร้างเลขสุ่มเทียมขึ้นมาโดยให้ความน่าจะเป็นที่ค่าตัวนับจะเพิ่มขึ้นคือ 0.25 มิฉะนั้น ค่าตัวนับจะคงอยู่ที่ 4

ตารางด้านล่างแสดงค่าที่เป็นไปได้บางส่วนของตัวนับ:

ถ้าตัวนับมีค่าเท่ากับ 101 ซึ่งเทียบเท่ากับเลขชี้กำลัง 5 (ค่าทศนิยมเทียบเท่าของ 101) แล้วจำนวนนับโดยประมาณคือหรือ 32 โอกาสที่จำนวนเหตุการณ์เพิ่มขึ้นจริงจะเป็น 5 นั้นค่อนข้างต่ำ ( ) จำนวนเหตุการณ์เพิ่มขึ้นจริงน่าจะอยู่ที่ "ประมาณ 32" แต่ก็อาจสูงกว่านั้นได้ (โดยมีโอกาสลดลงสำหรับจำนวนจริงที่มากกว่า 39) ${\displaystyle 2^{5}}$${\displaystyle {\frac {1}{1024}}=1\times {\frac {1}{2}}\times {\frac {1}{4}}\times {\frac {1}{8}}\times {\frac {1}{16}}}$

แม้ว่าการใช้กำลังของ 2 เป็นค่าตัวนับจะมีประสิทธิภาพด้านหน่วยความจำ แต่ค่าที่กำหนดโดยพลการมักจะสร้างช่วงข้อผิดพลาดแบบไดนามิก และค่าที่เล็กกว่าจะมีอัตราส่วนข้อผิดพลาดมากกว่าค่าที่ใหญ่กว่า วิธีการอื่นในการเลือกค่าตัวนับจะพิจารณาพารามิเตอร์ต่างๆ เช่น ความพร้อมใช้งานของหน่วยความจำ อัตราส่วนข้อผิดพลาดที่ต้องการ หรือช่วงการนับ เพื่อให้ได้ชุดค่าที่เหมาะสมที่สุด^{[ 2 ]}

อย่างไรก็ตาม เมื่อตัวนับหลายตัวมีค่าเดียวกัน ค่าจะถูกปรับให้เหมาะสมตามตัวนับที่มีช่วงการนับที่ใหญ่ที่สุด และให้ความแม่นยำที่ไม่เหมาะสมสำหรับตัวนับที่มีช่วงการนับน้อยกว่า การแก้ไขทำได้โดยการรักษากลุ่มการประมาณค่าตัวนับอิสระ^{[ 3 ]}ซึ่งจำกัดผลกระทบของตัวนับขนาดใหญ่ต่อตัวนับอื่นๆ ในกลุ่ม

สามารถนำอัลกอริทึมนี้ไปใช้ด้วยมือได้ เมื่อเพิ่มค่าตัวนับ ให้โยนเหรียญจำนวนครั้งที่สอดคล้องกับค่าตัวนับปัจจุบัน ถ้าออกหัวทุกครั้ง ให้เพิ่มค่าตัวนับ มิฉะนั้น อย่าเพิ่มค่าตัวนับ

วิธีการนี้สามารถทำได้ง่ายๆ บนคอมพิวเตอร์ สมมติให้เป็นค่าปัจจุบันของตัวนับ สร้างบิตสุ่มเทียม แล้วใช้การดำเนินการทางตรรกะ ANDกับบิตเหล่านั้นทั้งหมด จากนั้นบวกผลลัพธ์เข้ากับตัวนับ เนื่องจากผลลัพธ์จะเป็นศูนย์หากบิตสุ่มเทียมใดๆ เป็นศูนย์ จึงทำให้มีโอกาสเพิ่มขึ้นเท่ากับกระบวนการนี้จะถูกดำเนินการทุกครั้งที่มีการร้องขอให้เพิ่มค่าตัวนับ ${\displaystyle c}$${\displaystyle c}$${\displaystyle 2^{-c}}$

อัลกอริทึมนี้มีประโยชน์ในการตรวจสอบกระแสข้อมูลขนาดใหญ่เพื่อค้นหารูปแบบ ซึ่งมีประโยชน์อย่างยิ่งในแอปพลิเคชันด้านการบีบอัดข้อมูลการจดจำภาพและเสียง และแอปพลิ เคชัน ปัญญาประดิษฐ์ อื่นๆ

• ไฮเปอร์ล็อกล็อก

• มอร์ริส, อาร์. การนับเหตุการณ์จำนวนมากในรีจิสเตอร์ขนาดเล็กการสื่อสารของ ACM 21, 10 (1978), 840–842
• Flajolet, P. การนับโดยประมาณ: การวิเคราะห์โดยละเอียด BIT 25, (1985), 113–134 [1]
• Fouchs, M., Lee, CK., Prodinger, H., การนับโดยประมาณผ่านวิธี Poisson-Laplace-Mellin [2]