- Vào thập niên 1970,
spell của Unix tại AT&T phải tra cứu nhanh một từ điển 250KB trong chỉ 64KB RAM của PDP-11, và Douglas McIlroy đã giải quyết bằng cách tận dụng đặc tính dữ liệu thay vì nén đa dụng
- Nguyên mẫu ban đầu của Steve Johnson dựa trên đĩa nên chậm và độ chính xác thấp, nhưng McIlroy đã cải thiện hiệu năng và độ chính xác bằng stemming để rút từ điển xuống còn khoảng 25.000 từ
- Cấu trúc in-memory đầu tiên là Bloom filter do Dennis Ritchie triển khai, với bảng 400.000 bit và 11 hàm băm để đạt tỷ lệ dương tính giả khoảng 1/2000, nhờ đó bỏ qua việc tra cứu từ điển riêng
- Khi từ điển tăng lên 30.000 từ, chỉ dùng Bloom filter không còn đáp ứng được giới hạn bộ nhớ, nên ông đã sắp xếp các giá trị băm 27 bit rồi nén hiệu số giữa các giá trị băm bằng Golomb code
- Bản triển khai cuối cùng chia bảng hiệu số đã nén thành nhiều bin để tăng tốc độ tra cứu, đạt mức lưu trữ khoảng 14 bit mỗi từ và cho phép kiểm tra chính tả nhanh trong 64KB
Giới hạn bộ nhớ mà Unix spell phải đối mặt
- Bài toán cốt lõi là tra cứu nhanh một từ điển 250KB trong môi trường chỉ có 64KB RAM
- Ngay cả khi áp dụng nén hiện đại như
gzip -9, tệp này cũng không thể giảm xuống dưới 85KB
- Trên PDP-11 của thập niên 1970, không thể đưa toàn bộ từ điển vào bộ nhớ, còn tra cứu dựa trên đĩa thì chậm
- Thay vì nén đa dụng, McIlroy đã thiết kế một cấu trúc dữ liệu chuyên dụng khai thác cấu trúc và phân bố xác suất của dữ liệu từ điển
Unix spell ban đầu và việc thu nhỏ từ điển dựa trên stem
- Khi AT&T đề xuất Unix như một hệ thống xử lý văn bản cho bộ phận bằng sáng chế, nhu cầu về trình kiểm tra chính tả xuất hiện
- Steve Johnson đã viết nguyên mẫu Unix
spell đầu tiên vào năm 1975, và Jon Bentley kể rằng công việc này được hoàn thành chỉ trong một buổi chiều
- Phiên bản đầu tiên tách tệp đầu vào thành luồng từ, rồi loại bỏ số và ký tự đặc biệt, chuyển về chữ thường, sắp xếp, loại trùng, sau đó kiểm tra sự tồn tại của từng từ trong từ điển trên đĩa
- Cách tra cứu đĩa đơn giản này vừa chậm vừa kém chính xác
- Để tăng hiệu năng và độ chính xác, McIlroy đã thiết kế lại hai phần
- Thuật toán loại bỏ tiền tố và hậu tố để rút từ về stem
- Cấu trúc dữ liệu nén để đưa từ điển vào bộ nhớ và tra cứu nhanh
Thuật toán loại bỏ tiền tố và hậu tố
- Cách stemming của McIlroy lặp lại việc loại bỏ các tiền tố và hậu tố phổ biến khỏi một từ, rồi kiểm tra xem từ đã rút gọn có trong từ điển hay không
- Ví dụ,
misrepresented được rút thành present bằng cách loại bỏ các tiền tố mis, re và hậu tố ed
- Nếu
present có trong từ điển, từ gốc sẽ không bị đánh dấu là lỗi chính tả
- Cách này không chính xác 100%, nên có thể để lọt một số lỗi, nhưng khi đó được xem là chấp nhận được
- Các quy tắc ngoại lệ để tránh lỗi phổ biến cũng được triển khai cùng lúc
- Từ điển cuối cùng được rút xuống còn 25.000 từ, đủ nhỏ để có thể đưa vào bộ nhớ nếu dùng cấu trúc dữ liệu phù hợp
Tra cứu dựa trên Bloom filter
- Cấu trúc in-memory đầu tiên mà McIlroy dùng là Bloom filter, khi đó trong bài báo được gọi là “superimposed code scheme”
- Bài báo về Bloom filter được công bố năm 1970, còn Unix
spell được phát triển vào giữa thập niên 1970
- Phần triển khai này do Dennis Ritchie cung cấp
- Bloom filter khởi tạo một bảng bit toàn số 0, rồi với mỗi phần tử sẽ áp dụng nhiều hàm băm để đặt các bit tương ứng thành 1
- Khi tra cứu cũng áp dụng các hàm băm tương tự
- Nếu có dù chỉ một bit bằng 0 thì phần tử đó không tồn tại
- Nếu tất cả bit đều là 1 thì có thể tồn tại, nhưng vẫn còn khả năng dương tính giả (false positive)
- Bloom filter thông thường cần tra cứu thêm từ điển thật để xử lý dương tính giả, nhưng trong trình kiểm tra chính tả thì phần lớn từ đều tồn tại trong từ điển, nên việc tra cứu đầy đủ có thể xảy ra thường xuyên
- McIlroy hạ tỷ lệ dương tính giả xuống đủ thấp để bỏ hẳn bước tra cứu từ điển thật
- Tỷ lệ dương tính giả cho phép là 1/2000
- Số từ trong từ điển là 25.000
- Kích thước bảng bit là 400.000 bit
- Số hàm băm là 11
- Với tổ hợp này, tỷ lệ dương tính giả được đưa về khoảng 1/2000
Giới hạn của Bloom filter và cách băm nén
- Bloom filter được dùng trong một thời gian, nhưng khi từ mới tiếp tục được thêm vào, từ điển tăng từ 25.000 lên 30.000 từ
- Để giữ nguyên tỷ lệ dương tính giả cần một bảng bit lớn hơn, nhưng điều đó khó thực hiện vì giới hạn bộ nhớ
- McIlroy chuyển sang cách chỉ lưu các giá trị băm của từ thay vì cả bảng băm đầy đủ
- Việc tra cứu hoạt động bằng cách tính giá trị băm của từ đầu vào rồi kiểm tra xem nó có nằm trong danh sách giá trị băm đã lưu hay không
- Để giảm xác suất va chạm băm, cần mã băm đủ lớn
- Kích thước từ điển
v vào khoảng 30.000, tức gần 2^15
- Xác suất va chạm cho phép là
1 / 2^12
- Kích thước băm cần thiết là 27 bit
- Lưu 30.000 giá trị băm 27 bit sẽ không vừa trong 64KB RAM của PDP-11, nên nén là bắt buộc
Giới hạn nén theo lý thuyết
- Trước tiên, McIlroy tính số bit tối thiểu theo lý thuyết cần để lưu tập hợp các mã băm
- Nếu kích thước mã băm là
b bit thì sẽ có 2^b mã băm khả dĩ; việc chọn v mã băm duy nhất trong số đó được quy đổi thành lượng thông tin cần lưu
- Phép tính dùng xấp xỉ Stirling và giả định đơn giản hóa
v « 2^b
- Thay
v=30.000, b=27, giá trị tối thiểu cần cho mỗi mã băm là 13,57 bit
- Con số này ngắn hơn khoảng 50% so với băm 27 bit ban đầu và đủ để nằm trong giới hạn bộ nhớ của PDP-11
Lưu hiệu số băm và cách tra cứu
- McIlroy không nén trực tiếp các mã băm gốc mà lưu hiệu số giữa các mã băm đã sắp xếp
- Ví dụ như sau
sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12
- Việc lưu hiệu số có hai lợi thế
- Giá trị hiệu số nhỏ hơn mã băm gốc
- Cùng một giá trị hiệu số có thể lặp lại ở nhiều cặp mã băm
- Khi tra cứu, hệ thống tính giá trị băm của từ đầu vào rồi cộng dồn các hiệu số từ đầu danh sách
- Nếu tổng tích lũy bằng giá trị băm đầu vào thì từ đó tồn tại
- Nếu tổng tích lũy vượt quá giá trị băm đầu vào thì từ đó không tồn tại
- Dù giảm được dung lượng lưu trữ, cách này có thể làm tra cứu chậm đi vì phải giải mã và cộng dồn từ đầu
Mô hình hóa hiệu số băm bằng phân bố hình học
- Nén không mất dữ liệu hiệu quả nhất khi gán mã ngắn cho giá trị xuất hiện thường xuyên và mã dài cho giá trị hiếm
- Các cách nén thông thường dựa trên bảng phân bố xác suất không phù hợp với ràng buộc của McIlroy
- Nếu lưu bảng phân bố xác suất của khoảng 30.000 ký hiệu trong bộ nhớ thì lợi ích nén sẽ biến mất
- Việc tính tần suất và xác suất của các giá trị hiệu số sẽ cần cấu trúc dựa trên đĩa có chi phí lớn
- McIlroy tận dụng việc các hiệu số băm tuân theo phân bố hình học
- Không gian băm có
2^b vị trí và trong đó phân bố v mã băm
- Xác suất có một giá trị băm tại một vị trí là
q = v / 2^b
- Xác suất trống là
p = 1 - v / 2^b
- Hiệu số
k xuất hiện khi k-1 vị trí sau một giá trị băm là trống và vị trí thứ k chứa giá trị băm tiếp theo
- Vì vậy, xác suất của hiệu số
k là p^(k-1)q, tức đúng dạng phân bố hình học
Nén hiệu số bằng Golomb code
- McIlroy nén các hiệu số băm bằng Golomb code, vốn phù hợp với số nguyên có phân bố hình học
- Bài báo năm 1965 của Golomb đưa ra một phương pháp mã hóa độ dài chạy đơn giản cho các giá trị có phân bố hình học
- Với phân bố hình học, xác suất giảm theo hàm mũ, nên có thể nhóm các giá trị thành các khối kích thước
m và tăng độ dài mã thêm 1 bit mỗi khi sang khối tiếp theo
- Bản triển khai của Unix
spell dùng một thuật toán mã hóa và giải mã khác với cách trong bài báo Golomb, phức tạp hơn một chút nhưng hiệu quả hơn
- Có thể xem bản triển khai SVR4 gốc tại các vị trí sau
- Golomb code nén các hiệu số băm với độ dài mã kỳ vọng 13,60 bit cho mỗi từ
- Kết quả này rất gần với mức tối thiểu lý thuyết là 13,57 bit
Chia bin để tăng tốc độ tra cứu
- Nếu chỉ dùng bảng hiệu số đã nén, mỗi lần tra cứu sẽ phải giải mã và cộng dồn từ đầu nên chậm
- Bản triển khai cuối cùng của Unix
spell chia bảng hiệu số thành M bin
- Khi tra cứu, hệ thống tìm đúng bin trước rồi chỉ quét trong bin đó
- Cách này giúp tăng tốc độ tìm kiếm lên
M lần
- Đổi lại, cần lưu thêm con trỏ tới các bin nên phát sinh chi phí lưu trữ
log₂M bit cho mỗi từ
- Tổng dung lượng tăng lên khoảng 14 bit mỗi từ, nhưng đây là sự đánh đổi mang lại tra cứu nhanh hơn nhiều mà vẫn nằm trong ngân sách bộ nhớ
Thiết kế theo ràng buộc mà Unix spell thể hiện
- Unix
spell là một ví dụ thiết kế kết hợp Bloom filter, lý thuyết thông tin, lý thuyết xác suất và nén Golomb
- Quá trình phát triển diễn ra theo luồng sau
- Đạt tỷ lệ dương tính giả thấp bằng Bloom filter
- Khi từ điển lớn lên thì chuyển sang cách băm nén
- Tính mức bit tối thiểu theo lý thuyết cho việc lưu giá trị băm
- Nhận ra phân bố của các hiệu số băm
- Đạt mức nén gần tối ưu bằng Golomb code
- Thêm chia bin với chi phí dung lượng nhỏ để tăng tốc tra cứu
- Các trình kiểm tra chính tả hiện đại dùng những kỹ thuật khác như edit distance hay language model, nhưng Unix
spell vẫn là một ví dụ tiêu biểu về việc kết hợp hiểu biết lý thuyết với ràng buộc thực tế để tạo ra một hệ thống hiệu quả
1 bình luận
Ý kiến trên Hacker News
Ngay cả với rất ít RAM, vẫn có thể tạo một trình kiểm tra chính tả dùng bộ nhớ ngoài: sắp xếp các từ trong tài liệu, loại bỏ các từ trùng lặp, rồi hợp nhất với từ điển đã được sắp xếp để chỉ còn lại những từ không tồn tại
Tôi từng thấy cách này trong một ví dụ BASIC của Creative Computing, và vì tôi đã làm cho nó chạy được trên TRS-80 Color Computer với lượng RAM khả dụng còn ít hơn nhiều so với 32KB, nên vừa nhìn tiêu đề là tôi nghĩ ngay đến nó trước tiên
Hồi đó Turbo Lightning từng khiến mọi người kinh ngạc, vì từ điển nén của nó có thể nằm cùng với các chương trình khác đang chạy trên PC và kiểm tra chính tả ngay khi gõ
PC có giới hạn 640KB, nhưng nếu không muốn ảnh hưởng tới các chương trình khác thì chỉ nên dùng một phần trong số đó, và vào thời kỳ đầu của PC thì ngay cả việc lấp đầy ngần ấy bộ nhớ cũng không hề dễ về mặt chi phí
Có lẽ cũng có thể làm theo cách lưu bản sao làm việc xuống đĩa trước, sắp xếp, so sánh rồi nạp lại, nhưng tôi nghĩ các nhà phát triển C=64 hẳn đã tránh chiến lược đó vì giao diện đĩa quá chậm
Có đoạn nói rằng thời đó Bloom filter vẫn chưa được gọi là Bloom filter, và Douglas gọi nó là “superimposed code scheme” trong bài báo; thực ra Bloom filter là một loại cụ thể của superimposed code
Calvin Mooers đã phát triển random superimposed coding trong luận văn thạc sĩ ở MIT vào thập niên 1940, chịu ảnh hưởng trực tiếp từ Shannon
Cuốn sách rất hay năm 1963 của Bourne, “Methods of Information Handling”, có trình bày các chi tiết toán học
Tôi tin chắc Douglas hẳn đã biết kỹ thuật rộng hơn này. Chẳng hạn tác giả của “The Large Data Base File Structure Dilemma” (1975) cũng mô tả nó trong http://dx.doi.org/10.1021/ci60001a005 là “một kỹ thuật cũ gọi là super-imposed coding”
Ở đây từ hạn định “ngẫu nhiên” là quan trọng, vì trước Mooers cũng đã có superimposed code, nhưng chúng không thú vị về mặt toán học hay quan trọng về mặt thực tiễn
So với “worse is better” thì cái này thông minh quá mức. Phải nghĩ theo hướng tệ hơn nữa
Băng thông bộ nhớ chính và băng thông đĩa gần như tương đương nhau, cả hai đều chỉ hơn 1MB/s một chút
Nếu là tôi thì có lẽ tôi sẽ làm theo kiểu nhiều lượt quét, nhưng dù vậy tôi vẫn sẽ dùng Bloom filter vì nó quá hay
https://github.com/arnoldrobbins/v10spell
https://code.google.com/archive/p/unix-spell/
Bài báo gốc cũng rất tuyệt: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
Nó cũng được đăng trên trang web của ông ấy: https://www.cs.dartmouth.edu/~doug/
https://en.wikipedia.org/wiki/Douglas_McIlroy
Nếu bạn là người mê từ ngữ, khi tra “obovate” bạn cũng sẽ bắt gặp biểu đồ hình dạng lá này
https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg
Tôi không nhớ tên sản phẩm, nhưng vào thập niên 80 từng có một trình kiểm tra chính tả bằng phần cứng cho IBM PC. Đó là một hộp cắm giữa bàn phím và PC, và nếu bạn nhập một chuỗi mà nó không nhận ra là từ trong từ điển thì nó sẽ phát tiếng bíp để báo
Có bài đánh giá ở trang 237 của https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf. Lưu ý PDF rất lớn
Một trong những điều khiến tôi hứng thú với Unix là một bài trên Byte vào khoảng đầu thập niên 1980. Nó cho thấy cách tạo trình kiểm tra chính tả bằng pipeline split/sort/comm, tổng cộng khoảng 7 lệnh
Trên PC 8-bit thì hoàn toàn không có những thứ như vậy, nhưng nhìn kỹ thì nó cũng không có vẻ cần độ phức tạp gì quá ghê gớm
https://youtu.be/tc4ROCJYbm0?t=4m56s
Giờ mới đọc xong bài, và theo tôi thì ý chính là thế này: có một “từ điển” gồm 30.000 từ, và nếu chấp nhận tỷ lệ dương tính giả khoảng 1/4000 thì có thể băm mỗi từ thành một chuỗi 27 bit, tức một số nguyên, rồi bỏ từ điển đi và chuyển bài toán thành lưu một tập gồm 30.000 chuỗi 27 bit
Hơi bất ngờ là theo lý thuyết thông tin, 30.000 chuỗi 27 bit này không cần 27 bit cho mỗi từ mà chỉ cần khoảng 13,57 bit. Tôi hiểu toán học đằng sau (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), nhưng vì 30.000 quá nhỏ so với 2^27, tức khoảng 134 triệu, nên để trực giác chấp nhận được chỗ lợi này chắc tôi còn phải ngẫm thêm
Để mã hóa tập con 30.000 giá trị băm 27 bit này, họ dùng sai khác giữa các giá trị băm, và vì các sai khác này tuân theo phân phối hình học nên dùng mã hóa Golomb vốn phù hợp với đầu vào có phân phối hình học, từ đó đạt khoảng 13,6 bit trên mỗi từ trong thực tế
Tôi đã nghĩ liệu về nguyên lý có thể làm tốt hơn theo hướng kiểu “băm hoàn hảo” hay không. Có lẽ sẽ tồn tại một hàm nhận vào từ chữ cái, thực hiện một số phép biến đổi, rồi dễ dàng kiểm tra xem kết quả băm có thuộc một tập tốt nào đó hay không
Nhưng nghĩ lại thì vì cần có tỷ lệ dương tính giả, nên để đảm bảo các từ không có trong từ điển không bị ánh xạ vào tập “tốt” đó, giá trị băm phải có ít nhất 27 bit. Cách này về cơ bản có vẻ đã tối ưu theo lý thuyết. Trừ phi tồn tại cách ánh xạ mỗi từ thành một số nguyên 27 bit nhưng lại khiến các chuỗi “tốt” chẳng hạn đều là các giá trị nhỏ hơn 30000?
Nhân tiện, khoảng năm 1983, Grammatik trên CP/M chạy trong chưa đầy 64KB và thực hiện “kiểm tra ngữ pháp” trên hệ 8 bit. Thực ra nó giống kiểm tra chính tả cộng thêm các quy tắc hệ chuyên gia
Điều khiến tôi nhớ mãi là vì nó đào rất sâu vào phần thú vị, và lý do nó có thể nhỏ đến vậy là vì được viết bằng Forth; bên trong sản phẩm có đủ phần của một trình thông dịch ngoài, đến mức chỉ cần chỉnh hex một chút là có thể dùng nó như một trình thông dịch Forth với các hàm chuyên biệt được nạp sẵn
Tôi chưa từng dịch ngược để xem nó hoạt động ra sao, nhưng nó nhỏ, nhanh và chạy rất tốt
Tôi tò mò không biết việc băm khiến nó bỏ sót những lỗi gõ thường gặp nào
Liên quan thì còn có cả cuộc thi nén từ điển Wordle: http://golf.horse/wordle/
Tôi từng làm một việc tương tự vào giữa những năm 80. Nói là nhanh thì còn tùy tương đối
Dữ liệu rất nhiều, RAM là 640KB, heap là 64KB, stack là 64KB. Chúng tôi phải tìm kiếm và trích xuất dữ liệu từ vài trăm MB rồi ghép một phần của chúng lại với nhau
Tôi đã thử biến dữ liệu thành một cấu trúc chỉ mục kiểu cây tam phân. Xét về ý tưởng thì hợp lý, nhưng khi triển khai thì chỉ riêng thông tin quan hệ và đường đi cũng đã quá lớn để nhét vào 64KB
Thay vì nén, tôi chọn hoán đổi. Tôi viết mã TSR, kiểu như dịch vụ ngày nay, để xử lý một khối dữ liệu, trích kết quả rồi lưu lên stack, sau đó bỏ dữ liệu gốc đi và gọi ngắt tới TSR. TSR sẽ xóa heap, đọc khối tiếp theo từ thiết bị lưu trữ rồi trả quyền điều khiển lại cho chương trình; chương trình lại xử lý, kết hợp với dữ liệu trên stack, và lặp như vậy cho tới khi xong toàn bộ
Ban đầu công việc này cần 3 nhân viên nhập liệu làm khoảng một tuần, rồi thêm một chuyên gia để ghép thông tin lại. Cứ hình dung khoảng mười hai cuốn bìa còng 3 inch đầy bảng biểu. Chương trình hoàn thành trong vài giờ và “nhanh” một cách đáng kinh ngạc
Tất cả diễn ra trên một hệ thống đơn luồng
https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program
Tôi nhớ đã dùng tùy chọn
-btrong UNIX spell để dùng cách viết chính tả Anh-Anh. Chỉ có hai tùy chọn ngôn ngữ, nên tôi tự hỏi vì sao họ lại quyết định như vậy, mã nguồn xử lý điều đó thế nào, và từng từ điển đến từ đâuNgười Úc và New Zealand khi đó dùng chính tả Anh-Anh hay Anh-Mỹ?
UNIX spell giống như ZX81 1K chess của lĩnh vực kiểm tra chính tả, và trên máy tính gia đình thì kiểm tra chính tả không phổ biến lắm cho đến khi MS Word cho Windows 3.1 xuất hiện. Trước đó ở văn phòng, các thư ký gõ bằng WordPerfect và đóng vai trò như những bộ kiểm tra chính tả bằng người cho từng quản lý và từng nhóm
Còn ở nhà, với máy in kim và màn hình nhấp nháy, tôi đã sống sót qua cả giai đoạn đầu của máy tính bằng cách dựa vào từ điển giấy. Hồi đó ai cũng biết đánh vần, nên tôi không nhớ kiểm tra chính tả lại quan trọng đến thế. Trong một trường có cả nghìn học sinh, chỉ có đúng một đứa tự nhận là bị chứng khó đọc, và đó là một cái cớ nghe cũng hợp lý cho việc không đánh vần được
Có khi thập niên 1980 là thời hoàng kim của năng lực đọc viết, và ngày UNIX spell được viết ra chính là ngày bắt đầu rõ rệt của sự suy giảm khả năng đánh vần
Tôi thích Scrabble. Đây là một bài toán rất khác với kiểm tra chính tả, nhưng quy trình xử lý có chung vài bước với UNIX spell. Bạn tìm các tiền tố và hậu tố từ phổ biến rồi gắn chúng với các thành phần khác trên giá chữ hoặc trên bàn cờ
Từ điển Scrabble cũng hơi giống UNIX spell ở chỗ nó chỉ là một danh sách từ lớn không kèm nghĩa. Điều quan trọng chỉ là từ đó có xuất hiện trong sách hay không. Ngoài ra còn có vài bảng tra cứu đặc biệt như danh sách 102 từ gồm hai chữ cái
Nó kiểm tra bằng cách đọc từ điển từ đĩa, nên mất vài phút, rồi sau đó có thể rà qua các từ không khớp