Unix spell ที่รันบน RAM 64kB

 (blog.codingconfessions.com)
3 คะแนน โดย GN⁺ 2025-01-20 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

วิธีที่ Unix Spell ทำงานบน RAM 64kB

จะยัดพจนานุกรมลงใน RAM 64kB ได้อย่างไร?
  • วิศวกร Unix แก้ปัญหาการยัดพจนานุกรมขนาด 250kB ลงใน RAM 64kB ด้วยการใช้โครงสร้างข้อมูลและเทคนิคการบีบอัด
  • ในช่วงทศวรรษ 1970 Douglas McIlroy ต้องเผชิญกับปัญหานี้ขณะพัฒนาตัวตรวจการสะกดคำของ Unix ที่ AT&T
  • เขาพัฒนาอัลกอริทึมการบีบอัดที่เข้าใกล้ขีดจำกัดเชิงทฤษฎี โดยอาศัยคุณลักษณะของข้อมูล

TL;DR

  • ตัวตรวจการสะกดคำของ Unix เริ่มต้นจากต้นแบบที่ Steve Johnson แห่ง AT&T สร้างขึ้นในช่วงทศวรรษ 1970
  • McIlroy พัฒนาอัลกอริทึม stemming ที่อิงภาษาศาสตร์เพื่อลดขนาดพจนานุกรมเหลือ 25,000 คำ
  • ใช้ Bloom filter เพื่อให้ค้นหาได้รวดเร็ว และ Dennis Ritchie เป็นผู้จัดทำ implementation
  • เมื่อพจนานุกรมเพิ่มเป็น 30,000 คำ แนวทางแบบ Bloom filter ก็เริ่มไม่มีประสิทธิภาพ จึงนำเทคนิค compressed hashing มาใช้
  • ใช้รหัสแฮช 27 บิตเพื่อลดความน่าจะเป็นของการชนกัน และใช้รหัสของ Golomb เพื่อบีบอัดได้ถึง 13.60 บิตต่อคำ

จุดกำเนิดของคำสั่งสะกดคำใน Unix

  • Unix ถูกเสนอให้กับแผนกสิทธิบัตรของ AT&T ในฐานะระบบประมวลผลข้อความ และจำเป็นต้องมีตัวตรวจการสะกดคำ
  • เวอร์ชันแรกเขียนโดย Steve Johnson ในปี 1975 แต่มีความแม่นยำต่ำ
  • Douglas McIlroy เขียนโครงการนี้ขึ้นใหม่เพื่อปรับปรุงทั้งความแม่นยำและประสิทธิภาพ

อัลกอริทึมการตัดคำนำหน้า

  • McIlroy พัฒนาอัลกอริทึมสำหรับตัดคำนำหน้าและคำต่อท้ายที่พบร่วมกันออกจากคำก่อนนำไปค้นในพจนานุกรม
  • วิธีนี้ไม่ได้แม่นยำ 100% แต่ถือว่ายอมรับได้ในเวลานั้น

การค้นหาโดยอาศัย Bloom filter

  • Bloom filter ช่วยประหยัดหน่วยความจำและทำให้ค้นหาได้รวดเร็ว
  • ถูกใช้เพื่อโหลดพจนานุกรม 25,000 คำลงใน RAM 64kB
  • Bloom filter ถูกปรับแต่งให้คงอัตรา false positive ไว้ในระดับต่ำ

เทคนิค compressed hashing สำหรับค้นหาพจนานุกรม

  • เมื่อขนาดพจนานุกรมเพิ่มเป็น 30,000 คำ ก็จำเป็นต้องใช้โครงสร้างข้อมูลที่ใช้หน่วยความจำได้มีประสิทธิภาพยิ่งขึ้น
  • McIlroy ใช้วิธีเก็บผลต่างของรหัสแฮชเพื่อประหยัดหน่วยความจำ
  • ใช้รหัสของ Golomb เพื่อบีบอัดผลต่างของแฮช

บทสรุป

  • คำสั่งสะกดคำของ Unix เป็นประวัติศาสตร์วิศวกรรมที่น่าสนใจซึ่งเกิดจากข้อจำกัดด้านหน่วยความจำของ PDP-11
  • มันมอบโซลูชันที่สง่างามด้วยการผสาน Bloom filter, ทฤษฎีสารสนเทศ, ทฤษฎีความน่าจะเป็น และอัลกอริทึมการบีบอัด
  • แสดงให้เห็นว่าเมื่อทรัพยากรมีจำกัด ก็ยังสามารถแก้ปัญหาอย่างลึกซึ้งได้

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-01-20
ความคิดเห็นบน Hacker News

  • เดิมที Bloom filter ถูกเรียกว่า "superimposed code scheme" ซึ่งเป็น superimposed code ประเภทหนึ่ง

    • Calvin Mooers ได้พัฒนา random superimposed coding ที่ MIT ในช่วงทศวรรษ 1940 โดยได้รับอิทธิพลจากงานของ Shannon
    • หนังสือปี 1963 ของ Bourne ชื่อ "Methods of Information Handling" ให้รายละเอียดทางคณิตศาสตร์ไว้
    • มีความเป็นไปได้สูงว่า Douglas จะรู้จักเทคนิคนี้

  • สามารถทำตัวตรวจการสะกดคำแบบ external-memory ได้ด้วย RAM เพียงเล็กน้อย

    • วิธีการคือเรียงลำดับคำในเอกสาร ลบคำที่ซ้ำกัน แล้วรวมเข้ากับพจนานุกรมเพื่อคงไว้เฉพาะคำที่ขาดหายไป
    • เคยทำให้ทำงานได้บน TRS-80 Color Computer ด้วย RAM น้อยกว่า 32k
    • Turbo Lightning ใช้พจนานุกรมแบบบีบอัดเพื่อตรวจการสะกดขณะพิมพ์บน PC

  • แบนด์วิดท์หน่วยความจำและแบนด์วิดท์ดิสก์ใกล้เคียงกัน และสามารถทำงานให้เสร็จได้ด้วยการทำหลาย pass

    • การใช้ Bloom filter ทำงานนี้เป็นแนวทางที่ดี

  • ในยุค 1980 มีฮาร์ดแวร์ตรวจการสะกดสำหรับ IBM PC

    • มันเชื่อมอยู่ระหว่างคีย์บอร์ดกับ PC และจะส่งเสียงเตือนเมื่อพิมพ์คำที่ไม่รู้จัก

  • Unix ถูกนำเสนอให้ AT&T ในฐานะระบบประมวลผลข้อความ และจำเป็นต้องมีตัวตรวจการสะกด

    • UNIX ถูกใช้งานหลักเพื่อการประมวลผลข้อความ

  • บทความใน Byte ช่วงต้นทศวรรษ 1980 อธิบายวิธีสร้างตัวตรวจการสะกดของ Unix

    • บน PC แบบ 8 บิตยังไม่มีความสามารถแบบนี้

  • อาจมีคำสะกดผิดที่พลาดไปได้ซึ่งเป็นผลจากการแฮช

    • มีการแข่งขันเกี่ยวกับการบีบอัดพจนานุกรม Wordle

  • ช่วงกลางทศวรรษ 1980 มีการประมวลผลข้อมูลโดยใช้ RAM 640KB และ heap กับ stack 64KB

    • การดึงและรวมข้อมูลใช้เวลาหลายชั่วโมง และทำบนระบบ single-thread

  • ราวปี 1983 บน CP/M, Grammatik ทำงานได้ด้วยหน่วยความจำน้อยกว่า 64k และมีทั้งการตรวจไวยากรณ์กับกฎของ expert system

    • เขียนด้วย Forth จึงมีขนาดกะทัดรัดมาก

  • UNIX รุ่นแรกต้องการ 24kB โดยครึ่งหนึ่งเป็นของเคอร์เนล