thắc mắc [Học tập] Toán Rời Rạc trong cuộc đời lập trình viên

bribnt said:

Chỗ này không hiểu lắm, dùng hàm replace là theo đúng nghĩa đen luôn à? 30k từ là 30k lần replace, mỗi lần replace là phải tìm kiếm chuỗi rồi allocate với copy mem. Phải cỡ 30k * 4k = 120M thao tác là ít.

Click to expand...

terms = [...30k entries]
input = "...4k chars"

for (trung, viet in terms) input = input.replace(trung, viet)

cuuduongthancong.com said:

Tôi nhé
Ở đây còn nhiều hơn này, do tên môn học khác
https://cuuduongthancong.com/s/toan-roi-rac

Click to expand...

bribnt said:

Chỗ này không hiểu lắm, dùng hàm replace là theo đúng nghĩa đen luôn à? 30k từ là 30k lần replace, mỗi lần replace là phải tìm kiếm chuỗi rồi allocate với copy mem. Phải cỡ 30k * 4k = 120M thao tác là ít.

Click to expand...

Nipin said:

Để 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 :">

Click to expand...

Thích Màu Hường said:

Rồi ra đi làm bao nhiêu người ứng dụng vào làm rồi. Coder ở VN toàn code web, mobile ứng dụng thế nào vậy bạn? Viết ra để hù dọa người ta à?



Lý thuyết đồ thị ứng dụng vào xử lý ngôn ngữ, AI, ML thế nào vậy bạn? Nó có ứng dụng đó nhưng ra đời đi làm ko phải ai cũng đụng tới. Biết gì về xử lý ngôn ngữ, AI, ML ko mà chém.

Hỏi thật thím đi làm bao năm rồi và ứng dụng toán rời rạc đc nhiều thế nào mà nói là cực kỳ quan trọng.

Click to expand...

huyenoi said:

Ông đi làm bao nhiêu năm? Giờ vị trí của ông là gì? Team Lead? Manager? hay là dev quèn?
Tôi mới đi làm hơn năm mà thấy lý thuyết căn bản của toán rr giúp cho cv hơi bị nhiều đấy.
Tôi chỉ là dev quèn thôi nhé!

Click to expand...

Thích Màu Hường said:

Đọc lại hết 5 pages cho kỹ xem ý tôi muốn nói gì. 1 năm kinh nghiệm thì con non lắm. Định nói đôi lời mà thấy cái post này nên xin phép ignore vậy

View attachment 206404

Click to expand...

Nipin said:

Để 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 :">

Click to expand...

Usernem said:

Thế cái thuật toán nó ra sao anh

Click to expand...

{
  k: '',
  v: '',
  t: {
    a: {
      k: 'a',
      v: '1'
      t: {
        b: {
          k: 'ab',
          v: '21',
          t: {}
        }
      }
    },
    b: {
      k: 'b'
      v: '2',
      t: {}
    }
  }
}

Billr_rizer said:

Bài toán tokenize à thím? Quả này cũng loáng thoáng thấy các cụ trên cty dùng mấy cái word embedding kiểu word2vec, rồi thì cũng dùng mấy cái model RNN, nói chung là dân gà mờ như mình chỉ biết đến thế, không dám gõ phím to hơn.

Click to expand...

Nipin said:

có gì đặc biệt đâu, dùng trie như mấy bạn trên nói thôi.
ví dụ như lưu a=1;b=2;ab=21 thì sẽ thành cái cấu trúc dạng thế này:

Code:

{
  k: '',
  v: '',
  t: {
    a: {
      k: 'a',
      v: '1'
      t: {
        b: {
          k: 'ab',
          v: '21',
          t: {}
        }
      }
    },
    b: {
      k: 'b'
      v: '2',
      t: {}
    }
  }
}

cụ thể implement thế nào, dùng nó thế nào thì nó lại là chỗ khác, cơ mà về cơ bản thì thế.

Click to expand...

trungpham90 said:

Nếu cụm từ chỉ dừng ở 2-5 từ thì tôi nghĩ có thể dùng rolling hash (Rabin-Karp algorithm), khi duyệt thì chỉ lưu hash của 4 cụm từ gần nhất thôi. Ý tưởng thì thế nhưng ko biết có làm đc ko vì ko có kn xử lý tiếng Trung.

Click to expand...

Nipin said:

tôi nghĩ là không hợp.

tất cả các thuật toán tìm kiếm string đều là optimize cho việc tìm string này trong string kia, rồi early return nếu không match. ở đây là tìm tất cả các matches ở tất cả các vị trí cho vài trăm nghìn cái substrings.

với lạ độ dài của cụm từ thì không có giới hạn đâu, có lúc nó chỉ có 1 từ, có lúc nó là cả cụm thành ngữ thì có thể lên tới 8 ký tự thậm chí là hơn (vd 青出于蓝而胜于蓝 hay 苏维埃社会主义共和国联盟)

Click to expand...

Sniper_V2 said:

Nếu tiếng tàu như ông nipin kia nói, tức A đứng cạnh B sẽ cho ra từ C có nghĩa mới, ABC lại suy ra D, và có thể có đến ABCDEFGHIJKL đứng cạnh nhau tạo thành Z thì bài này không dễ xơi nếu dùng ML/DL đâu, tokenizer xịn nhất hiện nay cũng quỳ thôi. Kể cả có tokenizer hoàn hảo đi nữa thì vẫn vướng bài toán mapping từ từ vựng tiếng trung => tiếng việt nếu lượng từ trong từ điển quá lớn và số từ input vào cũng lớn (tuy là sau khi tách từ thì việc mapping đã trở thành dễ hơn rất nhiều) .
Nếu đổi lại đây là bài toán mapping Anh => Việt thì giải pháp tokenizer khả thi hơn nhiều, còn có nhanh hơn cái trie gì đó thì mình không rõ

Click to expand...

Billr_rizer said:

Vấn đề ABCDEF ra từ Z mình nghĩ dùng các mô hình NN tốt chứ nhỉ, trước kia truyền thống thì dùng HMM, MEMM, CRF,...đến thời gian gần đây thì bắt đầu chuyển dịch sang RNN. Có gì sai thím chỉ giáo.
Vấn đề về mapping từ vựng giữa 2 bộ từ điển thì mình k biết mấy, gốc mình không phải dân CNTT nên không dám bàn

Click to expand...

bribnt said:

Với prefix trie nếu đã build sẵn trie thì độ phức tạp của phép tìm kiếm từ tiếng Việt tương ứng là O(m), với m là số ký tự của chuỗi tiếngTrung. Mình không nghĩ là các mô hình ML có thể nhanh hơn được cỡ này.

Click to expand...

Thích Màu Hường said:

ML cụ thể trường hợp này là Deep Learning là làm việc với data dạng numeric. Cái input text sẽ được convert thành ma trận số, lúc dịch từ input -> output là các phép nhân ma trận với nhau nên nói về tốc độ thì chưa biết bên nào hơn bên nào. Một cái là tính toán số học, cái kia là search tree.

Nói về tính hiệu quả thì dùng Deep Learning hiệu quả hơn rất nhiều. Chấp hết các case khó như bên trên, chỉ cần có training set đủ lớn là được.

Click to expand...