Spell checker C program

Nguyen_Long5 · May 27, 2020, 6:41pm

có chuyên gia nào cho em hỏi là làm cách nào để nạp 1 file text cỡ lớn vào bộ đệm được không?
Em đang có 1 vấn đề đó là:
Thiết kế 1 chương trình C mang tên “Spell checker”
Yêu cầu là :

Cho một file từ điển có sẵn (file text gồm khoảng 30000 từ(dòng) )

Người dùng sẽ nhập từ bán phím những từ mà họ muốn kiểm tra

Sau đó Spellchecker.c sẽ kiểm tra trong thư viện có từ đó hay không

Nếu không có thì nó sẽ gợi ý cho mình .

(Quả thực mà để đọc tất cả file mà dùng đọc file thông thường rất là tốn thời gian)

dưới đây là interface và sample test

library · May 28, 2020, 2:16am

Hi @Nguyen_Long5,

Tớ có 1 vài thắc mắc mong cậu giải đáp trước. Tớ nghĩ mọi người ở đây cũng sẽ có cùng thắc mắc.

Liên quan tới câu này:

“Nạp 1 file text cỡ lớn vào bộ đệm được” là sao à cậu? Ý cậu là bộ nhớ đệm nào vậy?

Liên quan tới câu này của cậu:

Cậu có thể cho bọn tớ biết tốn bao nhiêu thời gian để đọc tất cả file mà dùng đọc file thông thường được không?

Mong nhận được câu trả lời của cậu.

nitro2 · May 28, 2020, 4:59am

Theo mình thì bạn ấy sợ file có 30000 từ có kích thước lớn, nếu load hết vào buffer thì chương trình tốn nhiều RAM, thậm chí không cấp phát được vùng nhớ.
Cũng theo mình thấy thì từ điển của bạn đã sắp xếp theo alphabet. Bạn có thể tra từ trong từ điển theo binary search.

library · May 28, 2020, 5:45am

Hì, tớ hiểu.
Thực ra là tớ muốn chỉ cho cậu ấy 1 điều thôi: Don’t assume it. Prove it!. Cậu ấy mới đưa ra assumption, nhưng chưa thử verify điều đó đúng hay không.

Tuy nhiên, cá nhân tớ đồng ý với cậu, binary search trên file là 1 solution tốt.

rogp10 · May 28, 2020, 5:54am

Không tới 1MB nếu load nguyên con còn biến thành cái tree thì 5-7MB RAM.

Nguyen_Long5 · May 28, 2020, 6:29am

Thực sự là cái này mình vẫn chưa hiểu cốt lõi của vấn đề cho lắm
Mình tham khảo một số nguồn thì có nhiều gợi ý là sử dụng cài đặt từ điển qua

HashTable

Nhưng mà mình đang không biết làm thế nào để giải quyết được vấn đề này,thực sự là bây giờ bế tắc quá

Nguyen_Long5 · May 28, 2020, 6:32am

Mình cũng mới tập toẹ học data structure nên mấy cái này vẫn còn mù tịt

Nguyen_Long5 · May 28, 2020, 6:40am

binary search thì phân chia middle theo tổng mã ascii hay là chỉ index[0] của mỗi word trong file ạ
Mong được anh(chị) chỉ bảo thêm

library · May 28, 2020, 6:56am

Cậu đang đi nhanh quá đó Long
Để giải quyết vấn đề, cậu cần biết vấn đề là gì đã.
Từ 1 vấn đề to, cậu nên break nó ra các vấn đề nhỏ, và giải quyết từng cái một. Cậu biết divide and conquer rồi phải không?
Giờ cậu có thể liệt kê vấn đề của cậu cho bọn tớ được không? Trước khi cậu xác định (nhầm) việc implement hash table bằng C là vấn đề của cậu

Ngoài ra, câu dưới đây cậu đề cập có vẻ không đúng, khi cậu từ chối chứng minh nó:

Như @rogp10 có nói, tớ nghĩ 300.000 dòng, mỗi dòng có 1 từ, gần như không có ý nghĩa gì khi cậu load toàn bộ cả file vào RAM.
Còn vấn đề buffer, cậu có thể đọc từng dòng một. Mỗi dòng của cậu có 1 từ, nên sẽ không có vấn đề gì với buffer cả.

Liên quan tới câu hỏi dưới đây của cậu:

Làm sao cậu search được bằng tổng mã ascii/index[0] của mỗi word trong file vậy?
Cậu có chắc là không ngồi nhầm lớp đấy chứ?
“Middle” nên là dòng chính giữa của file/của đoạn từ dòng x tới dòng y nào đó. Middle cuối cùng của cậu sẽ là dòng, hoặc là chính xác từ mà người dùng nhập vào, hoặc là một trong những từ gần nhất với từ nhập vào.

Stanley00 · May 28, 2020, 3:36pm

Spell checker là một bài toán cực kỳ phổ biến, tại sao bạn không tìm hiểu thử xem người ta đang làm như thế nào rồi? Cứ thích tự tin invent the wheel chi cho cực khổ vậy bạn. Hay là lại chê wiki viết bài chung chung nữa

Link tham khảo: https://en.wikipedia.org/wiki/Spell_checker
Mình check thì ít nhất có khoảng 5 cái link reference trong bài đó có thể sử dụng được.

Còn cùng lắm ấy, cách ngu ngốc nhất là đọc hết từ điển rồi so sánh. Bạn cứ mãi mê lo tối ưu, trong khi cái cách nhìn “ngu ngốc” kia vậy mà lại chạy được trong khi cách “thông minh” của bạn lại chẳng tồn tại nổi nữa cơ.

Nguyen_Long5 · May 28, 2020, 7:04am

Hiện tại thì em chưa ngồi nhầm lớp nhưng mà em sẽ cố gắng để tương lai nó sẽ không bị như thế ,Thiếu hiểu biết thế này tạo topic ăn gạch đá mới nhận thức được là mình cần phải học hỏi thêm nhiều
Cảm ơn mọi người đã góp ý
Chắc em tự nghiên cứu cái này thêm một thời gian nữa để thu nhận thêm đủ thông tin rồi quay lại hỏi mọi người sau

nitro2 · May 28, 2020, 7:52am

Thấy câu hỏi đầu tiên cũng không có vấn đề gì. Đừng nản lòng

library · May 28, 2020, 11:00am

Ừ cậu, tớ nghĩ đó là điều tốt đó. Cậu nên dành thêm chút thời gian tìm hiểu trước khi đưa ra câu hỏi. Nó sẽ giúp cậu rèn luyện cách tiếp cận 1 vấn đề.
Bọn tớ luôn welcome với các câu hỏi của cậu. Hi vọng cậu sẽ sớm giải quyết được bài tập đó.