- Unix spell ของ AT&T ในยุค 1970 ต้องค้นหา พจนานุกรมขนาด 250KB อย่างรวดเร็วภายใน RAM 64KB ของ PDP-11 และ Douglas McIlroy แก้ปัญหาด้วยการใช้คุณลักษณะของข้อมูล แทนการบีบอัดแบบทั่วไป
- โปรโตไทป์แรกของ Steve Johnson ใช้ดิสก์จึงช้าและมีความแม่นยำต่ำ แต่ McIlroy ลดขนาดพจนานุกรมลงเหลือระดับ 25,000 คำด้วย การสกัดรากศัพท์ ทำให้ประสิทธิภาพและความแม่นยำดีขึ้น
- โครงสร้างแบบ in-memory แรกคือ Bloom filter ที่ Dennis Ritchie นำไปใช้ โดยใช้ตาราง 400,000 บิตและฟังก์ชันแฮช 11 ตัว เพื่อให้อัตรา false positive อยู่ราว 1/2000 และตัดการค้นพจนานุกรมแยกต่างหากออกไป
- เมื่อพจนานุกรมขยายเป็น 30,000 คำ การใช้เพียง Bloom filter ไม่พอสำหรับข้อจำกัดด้านหน่วยความจำ จึงเรียงแฮช 27 บิตแล้วบีบอัด ผลต่างของแฮช ด้วย Golomb code
- การใช้งานสุดท้ายแบ่งตารางผลต่างที่บีบอัดแล้วออกเป็นหลาย bin เพื่อเพิ่มความเร็วในการค้นหา และทำให้ตรวจสะกดได้อย่างรวดเร็วภายใน 64KB ด้วยพื้นที่จัดเก็บประมาณ 14 บิตต่อคำ
ข้อจำกัดด้านหน่วยความจำที่ Unix spell เผชิญ
- ปัญหาหลักคือการค้นหา พจนานุกรมขนาด 250KB อย่างรวดเร็วในสภาพแวดล้อม RAM 64KB
- แม้ใช้การบีบอัดสมัยใหม่อย่าง
gzip -9 ไฟล์นี้ก็ยังลดลงต่ำกว่า 85KB ไม่ได้
- บน PDP-11 ในยุค 1970 ไม่สามารถโหลดพจนานุกรมทั้งหมดขึ้นหน่วยความจำได้ และการค้นหาจากดิสก์ก็ช้า
- McIlroy ออกแบบ โครงสร้างข้อมูลเฉพาะทาง ที่ใช้โครงสร้างและการแจกแจงความน่าจะเป็นของข้อมูลพจนานุกรม แทนการบีบอัดแบบทั่วไป
Unix spell รุ่นแรกและการลดขนาดพจนานุกรมด้วยรากศัพท์
- เมื่อ AT&T เสนอ Unix เป็น ระบบประมวลผลข้อความ สำหรับฝ่ายสิทธิบัตร จึงต้องมีตัวตรวจสะกด
- Steve Johnson เขียนโปรโตไทป์ Unix spell ตัวแรกในปี 1975 และ Jon Bentley เล่าว่างานนี้ทำขึ้นในช่วงบ่ายเดียว
- เวอร์ชันแรกแบ่งไฟล์อินพุตเป็นสตรีมของคำ จากนั้นลบตัวเลขและอักขระพิเศษ แปลงเป็นตัวพิมพ์เล็ก เรียงลำดับ ลบคำซ้ำ แล้วตรวจว่าคำนั้นมีอยู่ในพจนานุกรมบนดิสก์หรือไม่
- วิธีค้นจากดิสก์แบบตรงไปตรงมานั้นช้าและความแม่นยำต่ำ
- McIlroy ออกแบบใหม่สองส่วนเพื่อเพิ่มประสิทธิภาพและความแม่นยำ
- อัลกอริทึมที่ลบคำนำหน้าและคำต่อท้าย เพื่อลดคำให้เหลือ รากศัพท์
- โครงสร้างข้อมูลแบบบีบอัด ที่โหลดพจนานุกรมขึ้นหน่วยความจำเพื่อค้นหาได้รวดเร็ว
อัลกอริทึมลบคำนำหน้าและคำต่อท้าย
- วิธีสกัดรากศัพท์ของ McIlroy จะลบคำนำหน้าและคำต่อท้ายที่พบบ่อยออกจากคำซ้ำ ๆ แล้วตรวจว่าคำที่ถูกลดรูปแล้วมีอยู่ในพจนานุกรมหรือไม่
- ตัวอย่างเช่น
misrepresented ถูกลดเป็น present โดยลบคำนำหน้า mis, re และคำต่อท้าย ed
- หาก
present อยู่ในพจนานุกรม ก็จะไม่ทำเครื่องหมายคำเดิมว่าเป็นคำสะกดผิด
- วิธีนี้ไม่ได้แม่นยำ 100% และอาจปล่อยให้คำผิดบางคำผ่านไปได้ แต่ในเวลานั้นถือว่าอยู่ในระดับที่ยอมรับได้
- ยังมีการใช้กฎยกเว้นเพื่อหลีกเลี่ยงข้อผิดพลาดที่พบบ่อยด้วย
- พจนานุกรมสุดท้ายลดลงเหลือ 25,000 คำ ซึ่งเป็นขนาดที่สามารถโหลดขึ้นหน่วยความจำได้หากใช้โครงสร้างข้อมูลที่ออกแบบมาดี
การค้นหาด้วย Bloom filter
- โครงสร้าง in-memory ตัวแรกที่ McIlroy ใช้คือ Bloom filter ซึ่งในบทความวิชาการยุคนั้นเรียกว่า “superimposed code scheme”
- บทความ Bloom filter เผยแพร่ในปี 1970 และ Unix spell ถูกพัฒนาในช่วงกลางทศวรรษ 1970
- การใช้งานนี้จัดทำโดย Dennis Ritchie
- Bloom filter เริ่มจากตั้งค่าตารางบิตเป็น 0 จากนั้นใช้ฟังก์ชันแฮชหลายตัวกับแต่ละรายการ แล้วตั้งบิตที่สอดคล้องกันเป็น 1
- ตอนค้นหาก็ใช้ฟังก์ชันแฮชชุดเดียวกัน
- ถ้ามีบิตใดเป็น 0 รายการนั้นจะไม่มีอยู่แน่นอน
- ถ้าบิตทั้งหมดเป็น 1 รายการนั้นอาจมีอยู่ แต่ยังมีความเป็นไปได้ของ false positive
- Bloom filter ทั่วไปต้องค้นพจนานุกรมจริงเพื่อจัดการ false positive แต่ในตัวตรวจสะกด คำส่วนใหญ่มักมีอยู่ในพจนานุกรม จึงอาจทำให้ต้องค้นพจนานุกรมเต็มบ่อยครั้ง
- McIlroy ลดอัตรา false positive ให้ต่ำพอจนละการค้นพจนานุกรมจริงได้
- อัตรา false positive ที่ยอมรับได้คือ 1/2000
- จำนวนคำในพจนานุกรมคือ 25,000 คำ
- ขนาดตารางบิตคือ 400,000 บิต
- ฟังก์ชันแฮชมี 11 ตัว
- ชุดค่านี้ทำให้อัตรา false positive อยู่ราว 1/2000
ข้อจำกัดของ Bloom filter และวิธีแฮชแบบบีบอัด
- วิธี Bloom filter ถูกใช้อยู่ช่วงหนึ่ง แต่เมื่อมีการเพิ่มคำใหม่อย่างต่อเนื่อง พจนานุกรมก็ขยายจาก 25,000 คำเป็น 30,000 คำ
- หากต้องรักษาอัตรา false positive เดิมไว้ จำเป็นต้องใช้ตารางบิตที่ใหญ่ขึ้น แต่ทำได้ยากเพราะข้อจำกัดด้านหน่วยความจำ
- McIlroy เปลี่ยนไปใช้วิธีเก็บเฉพาะ ค่าแฮช ของคำ แทนตารางแฮชทั้งหมด
- การค้นหาทำงานโดยคำนวณแฮชของคำอินพุต แล้วตรวจว่ามีอยู่ในรายการแฮชที่จัดเก็บไว้หรือไม่
- เพื่อลดโอกาสชนกันของแฮช ต้องใช้โค้ดแฮชที่ใหญ่พอ
- ขนาดพจนานุกรม
v อยู่ราว 30,000 หรือประมาณ 2^15
- ความน่าจะเป็นของการชนกันที่ยอมรับได้คือ
1 / 2^12
- ขนาดแฮชที่ต้องใช้คือ 27 บิต
- หากเก็บแฮช 27 บิตจำนวน 30,000 ค่า จะไม่พอดีกับ RAM 64KB ของ PDP-11 จึงจำเป็นต้องบีบอัด
ขีดจำกัดทางทฤษฎีของการบีบอัด
- McIlroy คำนวณ จำนวนบิตขั้นต่ำทางทฤษฎี ที่จำเป็นสำหรับการเก็บชุดโค้ดแฮชก่อน
- หากขนาดโค้ดแฮชคือ
b บิต จะมีโค้ดแฮชที่เป็นไปได้ 2^b ค่า และเมื่อนำจำนวนวิธีเลือกโค้ดแฮชไม่ซ้ำ v ค่าจากทั้งหมดนั้นมาแปลงเป็นปริมาณข้อมูล
- การคำนวณใช้การประมาณของ Stirling และสมมติฐานแบบทำให้ง่ายว่า
v « 2^b
- เมื่อแทนค่า
v=30,000, b=27 ค่าขั้นต่ำที่ต้องใช้ต่อการเก็บโค้ดแฮชหนึ่งค่าคือ 13.57 บิต
- ค่านี้สั้นกว่าแฮช 27 บิตเดิมราว 50% และอยู่ในระดับที่ใส่ในความจุหน่วยความจำของ PDP-11 ได้
การเก็บผลต่างของแฮชและการค้นหา
- McIlroy ไม่ได้บีบอัดโค้ดแฮชต้นฉบับโดยตรง แต่เก็บ ผลต่าง ระหว่างโค้ดแฮชที่เรียงลำดับแล้ว
- ตัวอย่างมีดังนี้
sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12
- การเก็บผลต่างมีข้อดีสองอย่าง
- ค่าผลต่างเล็กกว่าโค้ดแฮชเดิม
- ค่าผลต่างเดียวกันอาจเกิดซ้ำในคู่โค้ดแฮชหลายคู่
- การค้นหาจะคำนวณแฮชของคำอินพุต แล้วสะสมผลต่างจากต้นรายการ
- หากผลรวมสะสมเท่ากับแฮชอินพุต แปลว่ามีอยู่
- หากผลรวมสะสมเกินแฮชอินพุต แปลว่าไม่มีอยู่
- แม้ลดพื้นที่จัดเก็บได้ แต่การค้นหาอาจช้าลง เพราะต้องถอดรหัสค่าที่บีบอัดและสะสมจากต้นรายการ
การจำลองผลต่างของแฮชด้วยการแจกแจงเรขาคณิต
- การบีบอัดแบบไม่สูญเสียข้อมูลจะมีประสิทธิภาพเมื่อกำหนดโค้ดสั้นให้ค่าที่พบบ่อย และโค้ดยาวให้ค่าที่พบได้น้อย
- การบีบอัดทั่วไปที่อิงตารางการแจกแจงความน่าจะเป็นไม่เหมาะกับข้อจำกัดของ McIlroy
- หากเก็บตารางการแจกแจงความน่าจะเป็นของสัญลักษณ์ราว 30,000 ตัวในหน่วยความจำ ประโยชน์จากการบีบอัดจะหายไป
- การคำนวณความถี่และความน่าจะเป็นของค่าผลต่างต้องใช้โครงสร้างบนดิสก์ที่มีต้นทุนสูง
- McIlroy ใช้ข้อเท็จจริงที่ว่าผลต่างของแฮชเป็นไปตาม การแจกแจงเรขาคณิต
- พื้นที่แฮชมีจุดทั้งหมด
2^b จุด และมีโค้ดแฮช v ค่ากระจายอยู่ภายใน
- ความน่าจะเป็นที่จุดหนึ่งมีแฮชคือ
q = v / 2^b
- ความน่าจะเป็นที่ว่างคือ
p = 1 - v / 2^b
- ผลต่าง
k เกิดเมื่อมีตำแหน่งว่าง k-1 ตำแหน่งหลังแฮชหนึ่งค่า และแฮชถัดไปอยู่ที่ตำแหน่งที่ k
- ดังนั้นความน่าจะเป็นของผลต่าง
k คือ p^(k-1)q ซึ่งตรงกับรูปแบบการแจกแจงเรขาคณิต
บีบอัดผลต่างด้วย Golomb code
- McIlroy บีบอัดผลต่างของแฮชด้วย Golomb code ซึ่งเหมาะกับจำนวนเต็มที่มีการแจกแจงเรขาคณิต
- บทความปี 1965 ของ Golomb เสนอวิธีเข้ารหัสความยาวรันแบบง่ายสำหรับค่าที่มีการแจกแจงเรขาคณิต
- ในการแจกแจงเรขาคณิต ความน่าจะเป็นลดลงแบบเอ็กซ์โปเนนเชียล จึงสามารถจัดกลุ่มค่าเป็นบล็อกขนาด
m และสร้างโครงสร้างที่เพิ่มความยาวโค้ดทีละ 1 บิตเมื่อขยับไปยังบล็อกถัดไป
- การใช้งานใน Unix spell ใช้อัลกอริทึมเข้ารหัสและถอดรหัสที่ซับซ้อนกว่าเล็กน้อย แต่มีประสิทธิภาพกว่า เมื่อเทียบกับวิธีในบทความของ Golomb
- การใช้งาน SVR4 ต้นฉบับดูได้ที่ตำแหน่งต่อไปนี้
- Golomb code บีบอัดผลต่างของแฮชได้ด้วยความยาวโค้ดคาดหมาย 13.60 บิต ต่อคำ
- นี่เป็นผลลัพธ์ที่ใกล้เคียงมากกับค่าขั้นต่ำทางทฤษฎี 13.57 บิต
การแบ่ง bin เพื่อความเร็วในการค้นหา
- หากใช้เพียงตารางผลต่างที่บีบอัดแล้ว ตอนค้นหาจะต้องถอดรหัสและสะสมตั้งแต่ต้น จึงช้า
- การใช้งาน Unix spell ขั้นสุดท้ายแบ่งตารางผลต่างออกเป็น bin จำนวน
M bin
- เมื่อต้องค้นหา จะหา bin ที่เกี่ยวข้องก่อน แล้วสแกนเฉพาะภายใน bin นั้น
- วิธีนี้เพิ่มความเร็วในการค้นหาได้
M เท่า
- แต่ต้องเก็บพอยน์เตอร์ของ bin จึงต้องใช้พื้นที่จัดเก็บเพิ่มเติม
log₂M บิตต่อคำ
- พื้นที่จัดเก็บรวมเพิ่มเป็นประมาณ 14 บิต ต่อคำ แต่เป็นการประนีประนอมที่ให้การค้นหาเร็วขึ้นมากภายในงบหน่วยความจำ
การออกแบบตามข้อจำกัดที่ Unix spell แสดงให้เห็น
- Unix spell เป็นกรณีศึกษาการออกแบบที่ผสาน Bloom filter, ทฤษฎีสารสนเทศ, ทฤษฎีความน่าจะเป็น และการบีบอัดแบบ Golomb
- กระบวนการพัฒนาดำเนินไปตามลำดับดังนี้
- บรรลุอัตรา false positive ต่ำด้วย Bloom filter
- เมื่อพจนานุกรมใหญ่ขึ้น จึงเปลี่ยนไปใช้วิธีแฮชแบบบีบอัด
- คำนวณจำนวนบิตขั้นต่ำทางทฤษฎีสำหรับการเก็บแฮช
- มองเห็นการแจกแจงของผลต่างแฮช
- ใช้ Golomb code เพื่อให้ได้การบีบอัดที่เกือบเหมาะสมที่สุด
- แบ่ง bin เพื่อเพิ่มความเร็วในการค้นหาด้วย overhead ด้านพื้นที่เพียงเล็กน้อย
- ตัวตรวจสะกดสมัยใหม่ใช้เทคนิคอื่น เช่น edit distance หรือโมเดลภาษา แต่ Unix spell ยังคงเป็นตัวอย่างของระบบที่มีประสิทธิภาพซึ่งผสานความเข้าใจเชิงทฤษฎีกับข้อจำกัดในการใช้งานจริง
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
แม้มี RAM น้อยมากก็ยังสร้าง ตัวตรวจสะกดแบบใช้หน่วยความจำภายนอก ได้: จัดเรียงคำในเอกสาร ลบคำที่ซ้ำให้เหลือคำไม่ซ้ำ จากนั้น merge กับพจนานุกรมที่จัดเรียงไว้ แล้วเหลือไว้เฉพาะคำที่ไม่มีในพจนานุกรม
ผมเคยเห็นวิธีนี้ในตัวอย่าง BASIC ของ Creative Computing และทำให้มันทำงานบน TRS-80 Color Computer ได้ ทั้งที่มี RAM ใช้งานได้น้อยกว่า 32KB มาก พอเห็นชื่อเรื่องก็เลยนึกถึงเรื่องนั้นขึ้นมาก่อน
ตอนนั้น Turbo Lightning ทำให้คนประหลาดใจ เพราะพจนานุกรมแบบบีบอัดสามารถอยู่ร่วมกับโปรแกรมอื่นที่กำลังรันบน PC และตรวจสะกดขณะพิมพ์ได้
PC มีข้อจำกัด 640KB แต่ถ้าไม่อยากรบกวนโปรแกรมอื่นก็ต้องใช้ได้แค่บางส่วนเท่านั้น และในยุคต้น ๆ ของ PC การใส่หน่วยความจำให้เต็มขนาดนั้นก็ไม่ใช่เรื่องง่ายในแง่ค่าใช้จ่าย
อาจทำได้โดยบันทึกสำเนาสำหรับทำงานลงดิสก์ก่อน จากนั้นจัดเรียง เปรียบเทียบ แล้วค่อยโหลดกลับมา แต่ผมคิดว่านักพัฒนา C=64 คงหลีกเลี่ยงกลยุทธ์แบบนั้น เพราะอินเทอร์เฟซดิสก์ช้าเกินไป
มีตอนหนึ่งบอกว่าในยุคนั้น Bloom filter ยังไม่ถูกเรียกว่า Bloom filter และ Douglas เรียกมันในบทความว่า “superimposed code scheme” ซึ่ง Bloom filter เป็น superimposed code ประเภทหนึ่ง
Calvin Mooers พัฒนา random superimposed coding ในวิทยานิพนธ์ปริญญาโทที่ MIT ช่วงทศวรรษ 1940 โดยได้รับอิทธิพลโดยตรงจาก Shannon
หนังสือยอดเยี่ยมของ Bourne ปี 1963 ชื่อ “Methods of Information Handling” มีรายละเอียดทางคณิตศาสตร์อยู่
ผมมั่นใจว่า Douglas น่าจะรู้จักเทคนิคที่กว้างกว่านั้น เช่น ผู้เขียน “The Large Data Base File Structure Dilemma”(1975) ก็เรียกสิ่งนี้ใน http://dx.doi.org/10.1021/ci60001a005 ว่า “เทคนิคเก่าแก่ที่เรียกว่า super-imposed coding”
ตรงนี้คำขยายว่า “random” สำคัญ เพราะก่อน Mooers ก็มี superimposed code อยู่แล้ว แต่ยังไม่ได้มีความน่าสนใจทางคณิตศาสตร์หรือมีความสำคัญในทางปฏิบัติ
ถ้าจะเรียกว่า “worse is better” ก็ฉลาดเกินไป ต้องคิดให้แย่กว่านี้
แบนด์วิดท์หน่วยความจำหลักกับแบนด์วิดท์ดิสก์แทบเท่ากัน ทั้งคู่มากกว่า 1MB/s นิดหน่อย
ถ้าเป็นผมน่าจะทำแบบผ่านข้อมูลหลายรอบ แต่ถึงอย่างนั้น Bloom filter ก็เจ๋งดี คงใช้เหมือนกัน
https://github.com/arnoldrobbins/v10spell
https://code.google.com/archive/p/unix-spell/
บทความต้นฉบับก็ดีมาก: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
บนเว็บเพจของเขาก็มีด้วย: https://www.cs.dartmouth.edu/~doug/
https://en.wikipedia.org/wiki/Douglas_McIlroy
ถ้าคุณเป็นพวกคลั่งคำศัพท์ พอไปค้นคำว่า “obovate” ก็น่าจะได้เห็นแผนภูมิรูปทรงใบไม้นี้ด้วย
https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg
จำชื่อผลิตภัณฑ์ไม่ได้ แต่ในยุค 80 มี ตัวตรวจสะกดแบบฮาร์ดแวร์ สำหรับ IBM PC อยู่ เป็นกล่องที่ต่อระหว่างคีย์บอร์ดกับ PC และถ้าพิมพ์สตริงที่มันไม่รู้จักว่าเป็นคำในพจนานุกรม ก็จะส่งเสียงบี๊บเตือน
มีรีวิวอยู่หน้า 237 ใน https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf ระวัง PDF ไฟล์ใหญ่
หนึ่งในสิ่งที่ทำให้ผมสนใจ Unix คือบทความใน Byte ราวต้นทศวรรษ 1980 ที่แสดงวิธีสร้างตัวตรวจสะกดด้วย pipeline ของ split/sort/comm ใช้คำสั่งประมาณ 7 คำสั่ง
PC 8 บิตไม่มีอะไรแบบนั้นเลย แต่พอเห็นแล้วก็ไม่ได้รู้สึกว่าต้องใช้ความซับซ้อนมากมายขนาดนั้น
https://youtu.be/tc4ROCJYbm0?t=4m56s
เพิ่งอ่านบทความจบตอนนี้ และมองว่าแก่นสำคัญคือแบบนี้: มี “พจนานุกรม” 30,000 คำ และถ้ายอมรับ อัตรา false positive ประมาณ 1/4000 ได้ ก็สามารถแฮชแต่ละคำให้เป็นสตริง 27 บิต หรือก็คือจำนวนเต็ม แล้วทิ้งพจนานุกรมไป เปลี่ยนเป็นปัญหาการเก็บเซตของสตริง 27 บิตจำนวน 30,000 ตัวแทนได้
ที่ค่อนข้างน่าทึ่งคือ ตามทฤษฎีสารสนเทศแล้ว สตริง 27 บิตจำนวน 30,000 ตัวสามารถเก็บได้ด้วยประมาณ 13.57 บิตต่อคำเท่านั้น ไม่ใช่ 27 บิตต่อคำ ผมเข้าใจคณิตศาสตร์นะ (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000) แต่ 30,000 นั้นเล็กมากเมื่อเทียบกับ 2^27 หรือราว 134 ล้าน เลยคงต้องใช้เวลาสักหน่อยกว่าจะรับรู้โดยสัญชาตญาณได้ว่ากำไรมาจากตรงไหน
เพื่อเข้ารหัสซับเซตของแฮช 27 บิตจำนวน 30,000 ตัวนี้ มีการใช้ผลต่างของแฮช และเพราะผลต่างนี้เป็นไปตามการแจกแจงเรขาคณิต จึงใช้ Golomb coding ที่ปรับให้เหมาะกับอินพุตแบบการแจกแจงเรขาคณิต จนทำได้จริงที่ประมาณ 13.6 บิตต่อคำ
ผมลองคิดดูว่าจะทำให้ดีกว่านี้ในเชิงหลักการได้ไหม ในแนวทางอย่าง “perfect hashing” อาจมีฟังก์ชันที่รับคำตัวอักษรเข้ามา ผ่านการแปลงบางอย่าง แล้วตรวจสอบได้ง่ายว่าแฮชผลลัพธ์อยู่ในเซตที่ดีหรือไม่
แต่พอคิดอีกที เนื่องจากต้องมี false positive ดังนั้นเพื่อไม่ให้คำที่ไม่มีในพจนานุกรมถูกแมปไปยังเซต “ดี” แฮชก็ต้องมีอย่างน้อย 27 บิต วิธีนี้โดยพื้นฐานแล้วดูเหมือนจะเหมาะที่สุดตามทฤษฎีแล้ว หรือไม่ก็อาจมีวิธีที่แมปแต่ละคำเป็นจำนวนเต็ม 27 บิต แต่ทำให้สตริงที่ดีเป็นอย่างเช่นค่าที่ต่ำกว่า 30000 ได้ไหม?
อ้างอิงเพิ่มเติม ราวปี 1983 Grammatik บน CP/M ทำงานได้ในหน่วยความจำน้อยกว่า 64KB และทำ “ตัวตรวจไวยากรณ์” บนระบบ 8 บิตได้ ในทางปฏิบัติมันคือการตรวจสะกดคำที่เพิ่มกฎแบบ expert system เข้าไป
ที่จำได้ก็เพราะผมไปขุดดูส่วนที่น่าสนใจ เหตุผลที่มันเล็กได้ขนาดนั้นคือเขียนด้วย Forth และในผลิตภัณฑ์มีตัว interpreter ภายนอกใส่มาเพียงพอ จนถ้าแก้ hex นิดหน่อย ก็ใช้มันได้เหมือน Forth interpreter ที่โหลดฟังก์ชันเฉพาะทางไว้ล่วงหน้า
ผมไม่ได้ decompile เพื่อดูว่ามันทำงานอย่างไร แต่มันเล็ก เร็ว และใช้งานได้ดี
สงสัยเหมือนกันว่าเพราะการแฮช มันพลาดคำสะกดผิดที่พบบ่อยแบบไหนไปบ้าง
เกี่ยวข้องกันคือมีการแข่งขันบีบอัดพจนานุกรม Wordle ด้วย: http://golf.horse/wordle/
ผมเคยเจออะไรคล้าย ๆ กันช่วงกลางยุค 80 คำว่าเร็วเป็นเรื่องสัมพัทธ์
ข้อมูลมีเยอะมาก, RAM 640KB, heap 64KB, stack 64KB ต้องค้นหาและดึงข้อมูลจากหลายร้อย MB แล้วนำบางส่วนมารวมกัน
เคยทดลองทำข้อมูลเป็นโครงสร้างดัชนีแบบ ternary tree ในเชิงแนวคิดมันสมเหตุสมผล แต่พอลงมือทำจริง แค่ข้อมูลความสัมพันธ์และเส้นทางก็ใหญ่เกินกว่าจะยัดลงใน 64KB ได้แล้ว
แทนที่จะบีบอัด ผมเลือกการสลับเข้าออกแทน เขียนโค้ดแบบ TSR หรือถ้าเทียบปัจจุบันก็คล้าย service ให้ประมวลผลก้อนข้อมูล ดึงผลลัพธ์ไปเก็บไว้ใน stack แล้วทิ้งข้อมูลต้นฉบับ จากนั้นส่ง interrupt call ไปหา TSR แล้ว TSR ก็ล้าง heap อ่านก้อนถัดไปจากอุปกรณ์เก็บข้อมูล แล้วคืนการควบคุมให้โปรแกรม โปรแกรมก็ประมวลผลและรวมกับข้อมูลใน stack ทำซ้ำจนเสร็จทั้งหมด
เดิมทีงานนี้ต้องใช้เจ้าหน้าที่ป้อนข้อมูล 3 คนราวหนึ่งสัปดาห์ และต้องมีผู้เชี่ยวชาญคอยรวมข้อมูล ลองนึกถึงตารางประมาณแฟ้ม ring binder 3 นิ้วสักสิบสองเล่ม โปรแกรมทำเสร็จในไม่กี่ชั่วโมง และ “เร็ว” อย่างน่าทึ่ง
ทั้งหมดทำบนระบบแบบเธรดเดียว
https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program
จำได้ว่าเคยใช้ตัวเลือก
-bเพื่อใช้การสะกดแบบอังกฤษใน UNIX spell ตอนนั้นมีตัวเลือกภาษาแค่สองแบบ เลยสงสัยว่าทำไมจึงตัดสินใจแบบนั้น โค้ดจัดการอย่างไร และพจนานุกรมแต่ละชุดมาจากไหนคนออสเตรเลียกับนิวซีแลนด์ใช้การสะกดแบบอังกฤษ หรือแบบอเมริกันกันนะ?
UNIX spell เป็นเหมือน ZX81 1K Chess ของวงการตรวจสะกดคำ และบนคอมพิวเตอร์ที่บ้าน แทบไม่มีระบบตรวจสะกดคำมากนักจนกระทั่ง MS Word สำหรับ Windows 3.1 ออกมา ก่อนหน้านั้นในสำนักงาน เลขานุการพิมพ์ด้วย WordPerfect และทำหน้าที่เป็นตัวตรวจสะกดคำที่เป็นมนุษย์ให้ผู้จัดการและทีมแต่ละคน
ส่วนที่บ้าน ผมใช้เครื่องพิมพ์ dot matrix กับหน้าจอกะพริบ ๆ และตลอดยุคคอมพิวเตอร์แรกเริ่มก็อาศัยพจนานุกรมกระดาษเอาตัวรอดไปได้ ตอนนั้นทุกคนสะกดคำเป็นกัน เลยจำไม่ได้ว่าตัวตรวจสะกดคำสำคัญขนาดนั้น ในโรงเรียนที่มีนักเรียนพันคน มีเด็กแค่คนเดียวที่อ้างว่าเป็น dyslexia และมันก็กลายเป็นข้อแก้ตัวที่ฟังขึ้นสำหรับการสะกดคำไม่ได้
บางทีทศวรรษ 1980 อาจเป็นยุคทองของการรู้หนังสือ และวันที่ชัดเจนซึ่งความสามารถในการสะกดคำเริ่มเสื่อมถอย ก็คือวันที่ UNIX spell ถูกเขียนขึ้นมาก็ได้
ผมชอบ Scrabble มันเป็นปัญหาที่ต่างจากการตรวจสะกดคำมาก แต่กระบวนการก็มีบางขั้นตอนร่วมกับ UNIX spell คือหาคำนำหน้าและคำต่อท้ายที่พบบ่อย แล้วนำไปประกอบกับองค์ประกอบอื่น ๆ บน rack หรือบนกระดาน
พจนานุกรม Scrabble ก็คล้าย UNIX spell อยู่บ้างตรงที่เป็นเพียงรายการคำขนาดใหญ่ที่ไม่ได้ให้ความหมาย สิ่งสำคัญมีแค่ว่าคำที่ให้มามีอยู่ในหนังสือหรือไม่ นอกจากนี้ยังมีตารางค้นหาเฉพาะทางไม่กี่ชุด เช่น คำสองตัวอักษร 102 คำ
มันตรวจโดยอ่านพจนานุกรมจากดิสก์ไปด้วย จึงใช้เวลาหลายนาที หลังจากนั้นจึงค่อยไล่ดูคำที่ไม่ตรงกันได้