Để tôi kể cho các bạn trường hợp cái app dưới sign tôi đang làm xem nó có cần học thuật toán hay không.
Nói đến cái webapp của tôi, thì nó là một cái công cụ dịch máy tiếng tàu. Nghe dịch máy thì rõ oai, nhưng về bản chất là thay thế 1:1 từ tiếng trung sang tiếng việt, ví dụ
程序员=>lập trình viên hay
码农=>code monkey... cho nên cái quan trọng nhất là dữ liệu từ điển đúng đắn đầy đủ, chứ không là thuật toán thông minh.
ví dụ kết quả cụ thể cho các bạn tham khảo:
https://chivi.xyz/~dai-phung-da-canh-nhan/chuong-162-lau-nam-ban-an-cu-xbiquge-36253791
chuyện nó chẳng có gì, nếu như không nói đến việc dữ liệu từ điển nó nằm tầm 500k tới 1 triệu entries, mỗi entries dài từ 1 tới hơn 10 ký tự, và độ dài của input tiếng chung thường từ một chương 4000 chữ tới cả bộ vài triệu chữ (bộ dài nhất tôi đọc có khoảng 18 triệu chữ)... nếu không dùng algo + data structure, thì đảm bảo kết quả sẽ vô cùng khó đỡ.
khi tôi làm cái chivi này, từng có một bạn liên hệ với tôi qua fb hỏi là mình cũng làm một cái tương tự cũng gần năm năm rồi, nhưng mà ra kết quả rất chậm dù rằng chỉ có 30k entries (bổ xung: riêng hán việt đã khoảng hơn 12k entries rồi, 30k entries hầu như chỉ chứa những từ phổ biến nhất, hoàn toàn không đủ).
hỏi ra mới biết là cách bạn ấy dịch rất trực quan: chạy một vòng lặp cho tất cả cặp từ trung/việt có sẵn trong từ điển, với mỗi cặp thì lại dùng hàm replace thay thế tất cả cụm
trung ở trên bằng cụm
việt... thực ra thì nếu chỉ có 30k từ, cho input dài 4k chữ thì nó cũng không nhiều, dù là cái server ghẻ lở thì cũng có khả năng ra kết quả sau một vài giây...
vấn đề ở đây là bạn này có dùng một cái khác gọi là "luật nhân", nói nôm na là một kiểu ngữ pháp tiếng trung, ghép lại vài cụm từ được đánh dấu danh động tĩnh các kiểu thành một cụm từ mới với cấu trúc thuần việt hơn... ờ giải thích hơi dài dòng, tóm lại thì các bạn hiểu đơn giản là phép "nhân" này biến 30k entries thành 300k thậm chí nhiều hơn, và kết quả là....
(p/s: ngoài mấy cái webapp thì trước đó có một cái desktop app gọi là QuickTranslator, và tôi cũng được nghe kể những trải nghiệm "rùng rợn" của một số bạn lạm dụng công cụ này, ví dụ 1 triệu entries từ điển x 100+ "luật nhân", nghe nói dịch một chương truyện 5k chữ thôi cũng có thể tính bằng tiếng, ăn hơn chục GB ram)
Tôi nghe loáng thoáng cũng có vài người có giải pháp tốt hơn tí, kiểu như chạy một vòng lặp duyệt cái dữ liệu input, rồi trích ra các substring (độ dài < 10 gì đấy), nếu tìm được cụm từ
việt phù hợp thì lưu kết quả vào, rồi nhảy qua độ dài cụm từ
trung vừa thấy... về cơ bản thì khá ổn, ngoại trừ hai chuyện là mỗi index của string đầu vào)đều phải trích ra khoảng 10 substring gì đấy rồi tìm nghĩa
việt, mà tìm nghĩa việt thì tuy dùng hash_map đúng là O(1) thật, nhưng thực tế cũng không đơn giản như vậy (hashing khá tốn kém). Vấn đề thứ hai là chạy từ trái sang phải như thế không hẳn là cách tốt nhất, vì có từ cần được ưu tiên hơn từ khác; ví dụ thành ngữ thường có 4 ký tự trở lên, hoặc tên người; chỉ dịch từ trái sang phải không ra được kết quả dịch tốt nhất có thể...
Các bạn có giải pháp gì tối ưu hơn có thể vào đây chém gió, cần thiết tôi có thể đưa thêm input (một file dữ liệu từ và một file text vài MB), tôi thấy đây là bài toán khá thú vị mặc dù cấu trúc dữ liệu tối ưu (mà tôi biết) thực ra cũng khá đơn giản :"> Lần cuối cùng tôi test thì thuật toán của tôi với dữ liệu là 200k từ + 10MB text file thì mất tầm 10s để dịch xong toàn bộ (bằng nodejs), kể ra cũng khá ổn, nhưng vẫn hóng xem có bạn nào nghĩ ra giải pháp hay hơn không :">
)
