รหัสซ้อนทับเช่นZatocoding เป็น รหัสแฮชชนิดหนึ่งที่เคยได้รับความนิยมในระบบบัตรเจาะรูแบบดั้งเดิม

มีการใช้ชื่อเรียกมากมายสำหรับระบบบัตรเจาะรูแบบขอบ เช่น บัตรเจาะรูขอบ บัตรเสียบ EZ Sort Zatocards McBee McBee Keysort Flexisort Velom Rocket เป็นต้น ตรงกลางของบัตรแต่ละใบจะมีข้อมูลที่เกี่ยวข้อง โดยทั่วไปจะเป็นชื่อและผู้เขียนหนังสือ บทความวิจัย หรือบทความวารสารบนชั้นวางใกล้เคียง และรายการหัวข้อและคำสำคัญ บัตรบางชุดมีข้อมูลทั้งหมดที่ผู้ใช้ต้องการอยู่บนบัตรเอง ไม่ว่าจะเป็นลายมือ พิมพ์ หรืออยู่ในไมโครฟิล์ม ( บัตรเจาะรู ) บัตรทุกใบในกองจะมีรูเจาะชุดเดียวกัน ผู้ใช้จะค้นหาบัตรที่เกี่ยวข้องกับการค้นหาโดยการจัดเรียงรูในกองบัตร (โดยใช้ที่ใส่บัตรหรือถาดใส่บัตร) แล้วเสียบแท่งคล้ายเข็มถักหนึ่งแท่งหรือมากกว่านั้นลงไปในกองบัตรจนสุด เพื่อให้บัตรที่ต้องการ (ซึ่งถูกเจาะหรือตัดเปิดไว้แล้ว) หลุดออกมาจากบัตรที่ไม่เกี่ยวข้องในชุด (ที่ไม่ได้เจาะ) ซึ่งจะยังคงอยู่บนแท่งนั้น ผู้ใช้สามารถเลือกซ้ำได้หลายครั้งเพื่อสร้าง คำค้นหา แบบบูลีน ที่ซับซ้อน การ์ดที่เกี่ยวข้องกับ 2 หัวข้อขึ้นไปจะมีช่องสำหรับแต่ละหัวข้อที่ถูกตัดออก ดังนั้นการ์ดนั้นจะหายไปเมื่อเลือกหัวข้อใดหัวข้อหนึ่งหรือทั้งสองหัวข้อ ระบบการเข้ารหัสแบบ "รหัสซ้อนทับ" เช่น Zatocoding ช่วยประหยัดพื้นที่โดยการใส่หัวข้อหลายหัวข้อหรือทั้งหมดลงในช่องเดียวกัน รหัสซ้อนทับดังกล่าวสามารถจัดเก็บข้อมูลได้มากขึ้นในพื้นที่น้อยลง แต่ต้องแลกมาด้วยการเลือก "ผิดพลาด" เป็นครั้งคราว^{[ 1 ]}

เมื่อคุณมีชุดการ์ดดัชนีหนึ่งใบต่อหนังสือ งานวิจัย หรือบทความวารสารในห้องสมุด โดยมีรายการคำสำคัญ (หัวข้อ) ที่กล่าวถึงในหนังสือเล่มใดเล่มหนึ่งเขียนไว้บนการ์ดของหนังสือเล่มนั้น วิธีที่ "ชัดเจน" ในการเข้ารหัสหัวข้อเหล่านั้นคือการนับจำนวนหัวข้อทั้งหมดที่ใช้ในชุดสะสมทั้งหมด R เจาะรู R รูใกล้กับด้านบนของการ์ดทุกใบ และสำหรับแต่ละหัวข้อที่กล่าวถึงจริงในหนังสือเล่มใดเล่มหนึ่ง ให้ตัดช่องจากรูที่ตรงกับหัวข้อนั้นในการ์ดที่ตรงกับหนังสือเล่มนั้น ^{[ 2 ]} แน่นอนว่า วิธีนี้ยังต้องมีรายการแยกต่างหากของทุกหัวข้อที่ใช้ในชุดสะสม ซึ่งระบุว่าเจาะรูใดสำหรับแต่ละหัวข้อ น่าเสียดายที่อาจมีหัวข้อที่แตกต่างกันหลายพันหัวข้อในชุดสะสม และการเจาะรูหลายพันรูในการ์ดทุกใบนั้นเป็นไปไม่ได้ในทางปฏิบัติ แม้ว่าอาจดูเหมือนเป็นไปไม่ได้ที่จะใช้รูน้อยกว่า 1 รูต่อหัวข้อ แต่ระบบรหัสที่ซ้อนทับกันสามารถแก้ปัญหานี้ได้

ระบบ Zatocoding สำหรับการดึงข้อมูลได้รับการพัฒนาโดยCalvin Mooersในปี พ.ศ. 2490 ^{[ 3 ]}

Calvin Mooers คิดค้นZatocodingที่ MIT ซึ่งเป็นระบบการค้นหาข้อมูลเชิงกลที่ใช้รหัสซ้อนทับ และก่อตั้งบริษัท Zatorในปี 1947 เพื่อทำการค้าแอปพลิเคชัน^{[ 4 ]} รหัสซ้อนทับเฉพาะที่ใช้ในระบบนั้นเรียกว่าZatocodingในขณะที่ระบบการค้นหาข้อมูลด้วยบัตรเจาะรูแบบขอบโดยรวมเรียกว่า " Zator " ^{[ 5 ]}

การตั้งค่าโค้ดที่ซ้อนทับกันสำหรับไลบรารีเฉพาะนั้นมีขั้นตอนดังนี้:

• เมื่อตรวจสอบการ์ดทุกใบในดัชนีแล้ว จะได้รายการวิชาทั้งหมด R ที่ใช้ในห้องสมุดแห่งนี้ และจะบันทึกจำนวนวิชาสูงสุด r ที่เขียนลงบนการ์ดใบเดียว (ตัวอย่างเช่น สมมติว่าเรามี 8000 วิชา และบรรณารักษ์ตัดสินใจจัดทำดัชนีเฉพาะวิชา r สูงสุด 4 วิชาต่อหนังสือหนึ่งเล่ม)
• บรรณารักษ์ตรวจสอบบัตรที่มีรอยบากที่ขอบและจดบันทึกจำนวนรู N ​​ในแต่ละบัตร (ถ้า N >= R เราสามารถใช้ "วิธีที่ชัดเจน" ที่กล่าวไว้ข้างต้นได้—จุดประสงค์หลักของการเข้ารหัสแบบ Zatocoding คือมันใช้งานได้แม้ว่า N จะน้อยกว่า R มากก็ตาม)
• บรรณารักษ์จะเลือกช่องจำนวน n ช่องต่อวิชาโดยทั่วไป^{[ 2 ]}${\displaystyle n=N(1-2^{-{\frac {1}{r}}})}$
• ในรายการของวิชา R ทั้งหมด สำหรับแต่ละวิชา ให้เขียนลงไปว่าช่องว่างใดจะถูกเสียบสำหรับวิชานั้น แทนที่จะเสียบช่องว่างหนึ่งช่องต่อวิชาใน "วิธีที่เห็นได้ชัด" รหัสที่ซ้อนทับกันจะเสียบช่องว่าง n ช่องต่อวิชา (มีหลายวิธีในการเลือกรูปแบบเหล่านี้ ซึ่งเป็นสิ่งที่ทำให้รหัสที่ซ้อนทับกันแต่ละแบบแตกต่างกัน เราจะกล่าวถึงรายละเอียดเพิ่มเติมด้านล่าง)
• เมื่อมีหนังสือเล่มใหม่เข้ามา ให้ทำบัตรใหม่สำหรับหนังสือเล่มนั้น:
  • หาการ์ดเปล่าที่มีรูมาตรฐาน N รู แล้วเขียนชื่อหนังสือ ฯลฯ ลงตรงกลาง
  • เขียนหัวข้อต่างๆ ที่หนังสือเล่มนี้กล่าวถึงลงบนการ์ด
  • สำหรับวิชาที่มีผู้เรียนมากที่สุด r วิชา ให้ค้นหาวิชานั้นในรายการใหญ่ แล้วดูว่าต้องตัดช่องว่าง n ช่องใดบ้างสำหรับวิชานั้น จากนั้นจึงตัดช่องว่างเหล่านั้นออก
  • เมื่อการ์ดเสร็จสมบูรณ์ อาจมีช่องเจาะมากถึง r*n ช่อง แต่โดยส่วนใหญ่แล้ว รูปแบบของช่องเจาะบางส่วนอาจทับซ้อนกัน ทำให้มีช่องเจาะเพียง v < r*n ช่องเท่านั้น

ต่อมา เมื่อเราต้องการค้นหาหนังสือเกี่ยวกับหัวข้อใดหัวข้อหนึ่งโดยเฉพาะ เราจะค้นหาหัวข้อนั้นในรายการหัวข้อทั้งหมด R ของเรา ค้นหารูปแบบช่องที่สอดคล้องกันของช่อง n ช่อง และเจาะเข็ม n อันผ่านกองทั้งหมดตามรูปแบบนั้น การ์ดทั้งหมดที่ถูกตัดตามรูปแบบนั้นจะหลุดออกมา เป็นไปได้ว่าการ์ดอื่นๆ ที่ไม่ต้องการอาจหลุดออกมาด้วย การ์ดที่มีหัวข้อหลายหัวข้อซึ่งรูปแบบรูซ้อนทับกันในลักษณะที่เลียนแบบรูปแบบที่ต้องการ ความน่าจะเป็น F ของการ์ดที่ไม่ต้องการบางใบที่มีช่อง v ช่องที่ตัดไว้จะหลุดออกมาเมื่อเราเลือกรูปแบบของเข็ม n อันนั้นมีค่าประมาณระบบส่วนใหญ่มี N ที่ใหญ่พอและ r ที่เล็กพอที่ v < N/2 (เช่น การ์ดถูกเจาะน้อยกว่าครึ่ง) ดังนั้นความน่าจะเป็นของการ์ดที่ไม่ต้องการจะหลุดออกมาจึงน้อย กว่า^{[ 2 ]}${\displaystyle F=\left({\frac {v}{N}}\right)^{n}}$${\displaystyle F<\left({\frac {1}{2}}\right)^{n}}$

มีหลายวิธีในการเลือกตำแหน่งรูที่จะเจาะรูสำหรับแต่ละหัวข้อ

(มีการพัฒนา Zatocoding หลายรูปแบบ Bourne อธิบายรูปแบบหนึ่ง "สำหรับระบบการเรียกค้นข้อมูลใหม่ที่ต้องการประสิทธิภาพสูงของระบบการเข้ารหัสแบบซ้อนทับ" ^{[ 6 ]}โดยใช้วิธีการที่ Mooers เผยแพร่ในปี 1959 ^{[ 7 ]} )

การตั้งค่า Zatocode สำหรับรายการวิชา R เฉพาะเจาะจงมีลักษณะดังนี้: ^{[ 2 ]}

• สำหรับวิชาแรก ให้เลือกช่อง n จากช่องทั้งหมด N ช่องโดยสุ่ม
• สำหรับหัวข้อที่สอง ให้เลือกช่อง n ช่องจากทั้งหมด N ช่องแบบสุ่ม แต่ต้องแน่ใจว่ารูปแบบที่ได้ไม่เหมือนกับหัวข้อแรก
• ...
• สำหรับวิชาที่ R ให้เลือก n วิชาจากทั้งหมด N วิชาแบบสุ่ม แต่ต้องแน่ใจว่าไม่ซ้ำกับวิชาใดๆ ก่อนหน้า

Zatocode ต้องใช้สมุดรหัสที่แสดงรายการหัวข้อทั้งหมดและรหัสรอยบากที่สร้างขึ้นแบบสุ่มที่เกี่ยวข้องกับแต่ละหัวข้อ รหัสซ้อนทับ "โดยตรง" อื่นๆ มีฟังก์ชันแฮช คงที่ สำหรับการแปลงตัวอักษรใน (การสะกดคำหนึ่ง) ของหัวข้อให้เป็นรหัสรอยบาก รหัสดังกล่าวต้องใช้สมุดรหัสที่สั้นกว่ามากซึ่งอธิบายการแปลตัวอักษรในคำเป็นรหัสรอยบากที่สอดคล้องกัน และโดยหลักการแล้วสามารถเพิ่มหัวข้อใหม่ได้อย่างง่ายดายโดยไม่ต้องเปลี่ยนสมุดรหัส^{[ 5 ]}

ตัวกรอง Bloomสามารถถือได้ว่าเป็นรหัสซ้อนทับชนิดหนึ่ง^{[ 8 ]}

• เมทริกซ์แยกส่วน

• Calvin N. Mooers. "การประยุกต์ใช้รหัสสุ่มในการรวบรวมข้อมูลทางสถิติ"วิทยานิพนธ์ปริญญาโท (MS) สถาบันเทคโนโลยีแมสซาชูเซตส์ ภาควิชาคณิตศาสตร์ ปี 1948
• Calvin N. Mooers. "การประยุกต์ใช้ Zatocoding ในการจัดระเบียบความรู้เชิงกล"วารสารของสมาคมวิทยาศาสตร์และเทคโนโลยีสารสนเทศแห่งอเมริกา. 2007.