1 chương trình tìm (các) từ được tạo ra từ 1 số lượng các chữ cái cho trước? [Archive]

View Full Version : 1 chương trình tìm (các) từ được tạo ra từ 1 số lượng các chữ cái cho trước?

11tn2

09-09-2011, 18:48

Chào mọi người. Xin được nói luôn là tôi là người ngoại đạo về lập trình nhưng đang có 1 vấn đề (mà theo tôi) khá là hấp dẫn nên mới lên đây post bài hi vọng nhờ được các bạn giúp. Nếu bài tôi post có bị sai chỗ thì mod chuyển hộ tôi nhé.
Vấn đề như sau: viết 1 phần mềm có thể truy cập vào 1 từ điển nào đó. Khi ta nhập 1 số lượng xác định các chữ cái vào thì chương trình sẽ cho ra kết quả là các tổ hợp từ thỏa mãn điều kiện:
1/ Tổng số chữ cái bằng với số chữ ta đã nhập
2/ Tất cả các từ đều có trong từ điển.
VD: ta nhập 3 chữ o, d, g thì phần mềm cho ra: 'dog' và 'god'
Đây là 1 số suy nghĩ của tôi:
1/ Chương trình cần có 1 tùy chọn giúp loại bỏ những từ chỉ có 1 chữ cái mà ta không thích có trong kết quả. Như trong VD trên, nếu không có tùy chọn này thì nó còn ra 1 đống 'o d g', 'o g d', 'd o g', 'd g o', 'g d o', 'g o d', 'do g', 'g do', 'go d', 'd go'; vì các từ có 1 chữ cái vẫn có ý nghĩa trong từ điển! Mặt khác có 1 số chữ có ý nghĩa mà trong 1 số trường hợp ta không muốn bỏ, như 'n' có nghĩa là 'và'. Thế nên tùy chọn này là cần thiết.
2/ Chương trình cũng cần có khả năng 'tra từ thông minh', đại loại như biết bỏ những kí hiệu như ' hay - trong từ điển đi, hay tự động tra cả chữ hoa chữ thường. VD nếu ta nhập 'a d y d' thì nó có thể cho ra 'D-day'.
3/ Có lẽ phần mềm chỉ nên giới hạn trong việc tìm từ tiếng Anh. Nếu tìm được tiếng Việt thì càng tốt, nhưng tôi đoán sẽ gặp vấn đề về dấu, mũ, chữ ă â ê v.v...
4/ Về từ điển để tra, nếu dùng từ điển online sẽ có lợi thế là kho từ khủng, nhưng bất cập lớn là phải có mạng mới dùng được, với lại có lẽ sẽ rất lâu và mất nhiều tiền mạng. Nếu truy cập vào từ điển trong máy thì lại có khó khăn là không phải máy nào cũng cài đúng loại từ điển mà chương trình áp dụng. Nếu tích hợp sẵn thì lại dính cái dung lượng hơi lớn quá, nhưng theo quan điểm của tôi thì có lẽ đây là cách khả thi nhất :(
Tóm lại, các bạn có thể cho biết là project này có khó không? Có mất nhiều thời gian không? Chương trình viết ra có ngốn quá nhiều tài nguyên máy không? Nếu nó không khó & mất không quá nhiều thời gian, có ai có thể viết nó không? Vì như tôi đã nói, 1 câu lệnh bẻ đôi tôi còn chẳng biết nữa là... Xin cám ơn trước.

hshason

10-09-2011, 01:07

11tn2 thân mến!
Những gì mà bạn nói đại loại như việc tra cứu từ điển. Nếu để tạo 1 project từ đầu thì time dành cho nó không phải tính từng ngày mà thậm trí đến hàng tháng, từ bước tạo lập cơ sở dữ liệu, tạo mối quan hệ, phân tích chức năng công việc cần xử lý khi tạo ra một từ điển mới (thế thì mới có để mà tra).
Vấn đề bạn đặt ra chỉ là xử lý chuỗi ký tự và tìm kiếm so sánh thì sẽ nhẹ nhàng hơn.
Để có thể tra từ thông minh như bạn mong muốn thì thời gian không thể xác định trước nó là bao lâu. Bạn có thể thấy 1 ví dụ là từ điển Lạc Việt đó, cả 1 quá trình phát triển tính đến hàng năm mà cũng không thể đáp ứng được hoàn toàn các mong muốn của người sử dụng.
Và tất nhiên nếu nói có khó hay không thì tùy thuộc vào khả năng coding của bạn thôi. Với mình nó không phải là quá khó nhưng rất phức tạp

Thân mến!

11tn2

10-09-2011, 15:36

Cám ơn bạn hshason. Có 1 điểm có lẽ tôi chưa nói rõ ở phần trước (mà tôi cũng không nghĩ đến) là chương trình không cần phải hiển thị nghĩa của các từ, tức là giảm được rất nhiều dung lượng. Điều đó cũng có nghĩa là trong cơ sở dữ liệu chỉ cần chứa list các từ thôi, có lẽ điều này khá đơn giản và dễ thực hiện? Do đó, vấn đề này đúng như bạn nói, chỉ là xử lí kí tự và tìm kiếm so sánh mà thôi.
Do tôi mù tịt về lập trình nên không biết là 'tra từ thông minh' lại khó code đến vậy :) Nhưng liệu chúng ta có thể xử lí nó ngay từ khâu cơ sở dữ liệu? Tức là loại bỏ chữ hoa & các kí tự vớ vẩn ở ngay list từ - điều này có lẽ sẽ đơn giản hóa vấn đề đi nhiều, phải không?
Với những chỉnh sửa như vậy, các bạn có thể cho tôi biết qua về độ phức tạp và thời gian để làm nếu chỉ có 1 người được không?

everest465

12-09-2011, 10:12

Ý tưởng của bạn rất hay, mình nghỉ là rất phức tạp. Nếu một người làm sẽ không quá 20 ngày

scooby

12-09-2011, 11:02

vấn đề bạn nêu ra không có gì mới cả về ý tưởng lẫn kỹ thuật.

Về mặt ý tưởng, vấn đề này đã được thực hiện trong một số phần mềm giải ô chữ. Ở nước ngoài người ta rất mê giải ô chữ nên có khá nhiều phần mềm phục vụ việc này.

Về mặt kỹ thuật việc này cũng khá đơn giản, code viết không khó và chương trình cũng chạy rất nhanh. (Cách đơn giản nhất là dùng thuật toán vét cạn - có vài chục hoặc tối đa vài nghìn trường hợp không là gì với máy tính ngày nay).

Với người mới tất nhiên là rất khó vì riêng việc hiểu là viết được chương trình từ điển đã là thách thức rất lớn (cứ nhìn mấy cái post xin giải thích hoặc xin hướng dẫn trong diễn đàn này là biết). Viết được chương trình tử điển chạy tốt (chạy đủ nhanh, chiếm bộ nhớ hợp lý) có thể ngang một luận án đại học cho sv ngành CNTT.

Sau nữa, thuật toán để viết theo yêu cầu trên như tôi nói là không khó nhưng nếu người viết không có căn bản tốt thì cũng rất chật vật.

11tn2

12-09-2011, 17:47

Cám ơn everest465 đã đóng góp. Bạn scooby có thể chỉ ra cho tôi 1 phần mềm nước ngoài giải quyết được vấn đề không? Thú thật là ngoài ddth ra tôi cũng không ghé thăm nhiều các trang IT VN, nói gì đến nước ngoài :"> nên không biết tìm ở chỗ nào.

vietboom

13-09-2011, 10:42

chỉ là so sánh và sắp xếp thôi mà .
nản nhất phần làm list word thôi X_X

11tn2

14-09-2011, 17:47

Phần list word tôi nghĩ có thể dùng thuật toán gì đấy để extract ra từ 1 từ điển nào đó, Lạc Việt chẳng hạn? Hoặc giả không làm được như vậy thì ngồi gõ khoảng 50k từ, mất khoảng 10 ngày chứ mấy :P.
Scooby? Bạn đã tìm hộ tôi chưa bạn ơi?

scooby

15-09-2011, 14:14

Không ngờ thế giới này còn có người lười hơn tôi!!!

Tôi đã gợi ý đến thế rồi, bạn phải tự mình GG nốt thôi. Lao động là vinh quang ;)

Một gợi ý tiếp là có nhiều từ điển Anh-Việt đã trở thành nguồn mở, tức là dữ liệu ở dạng "xơi" ngon rồi. Bạn hãy tìm hiểu từ điển StarDic.

11tn2

16-09-2011, 18:04

Nói lười thì cũng không sai, nhưng trường hợp này tôi có chăm chỉ cũng chẳng làm được bạn scooby à :) Bởi vì bạn lười quá không chịu đọc kĩ bài của tôi đấy thôi, tôi đã nói rõ là tôi không biết lập trình rồi mà =P Vì thế tôi mới post bài và chờ mong có ai đó sẽ ra tay làm giúp. Nếu bạn làm code cho tôi (và muốn tôi làm database), tôi xin sẵn sàng ngồi gõ 50k list từ tiếng Anh cho bạn, từ 10 - 30 ngày sẽ xong. Còn bảo tôi viết lệnh thì chịu rồi.
(Hoặc tốt hơn cả cho cả 2 người lười như tôi với bạn là bạn chịu khó tìm cho tôi cái phần mềm ô chữ mà bạn nói :) )

scooby

17-09-2011, 09:45

Tìm kiếm trên mạng không cần kỹ năng lập trình - bạn có thể tự mình tìm được mà.

11tn2

20-09-2011, 16:09

Bạn có thể nói rõ 1 chút về từ khóa tìm kiếm không? Theo những gì bạn viết thì tôi chỉ đoán được phần mềm ô chữ là crossword software, tìm trên google thì nhiều đấy, nhưng các phần mềm đều có chức năng là sắp xếp các TỪ cho trước theo hàng dọc hàng ngang, chứ không phải là sắp xếp các CHỮ cho trước và so sánh với từ điển.
Tôi nghĩ bạn đã từng đọc qua, xem qua về cái chương trình này rồi thì nhớ mang máng rồi tìm sẽ dễ hơn người chưa từng biết?

Lagi2

20-09-2011, 22:08

phần mềm có thể truy cập vào 1 từ điển nào đó. Khi ta nhập 1 số lượng xác định các chữ cái vào thì chương trình sẽ cho ra kết quả là các tổ hợp từ thỏa mãn điều kiện:
1/ Tổng số chữ cái bằng với số chữ ta đã nhập
2/ Tất cả các từ đều có trong từ điển.
VD: ta nhập 3 chữ o, d, g thì phần mềm cho ra: 'dog' và 'god'

Bạn nói rõ hơn về vấn đề cần giải quyết, bạn đặt ra ( các yêu cầu ) :
- phần mềm có thể truy cập vào 1 từ điển nào đó. 1 từ điển nào đó ở trên máy bạn ( trong CSDL ), hay trên webSite ( như search Google, Yahoo ) ?

- nhập 1 số lượng xác định các chữ cái có trùng nhau ( bài toán chỉnh hợp ) hay khác nhau ( bài toán tổ hợp ) ?

- có cần lọc bỏ ( so với bộ từ điển kiểm duyệt các chỉnh-tổ-hợp tạo được từ các chữ cái nhập vào không cần đến ) trước khi tìm, truy cập vào 1 từ điển ?

h2tforum

20-09-2011, 22:28

Ý tưởng của bạn rất hay ^^

11tn2

21-09-2011, 10:26

Bạn nói rõ hơn về vấn đề cần giải quyết, bạn đặt ra ( các yêu cầu ) :
- phần mềm có thể truy cập vào 1 từ điển nào đó. 1 từ điển nào đó ở trên máy bạn ( trong CSDL ), hay trên webSite ( như search Google, Yahoo ) ?

- nhập 1 số lượng xác định các chữ cái có trùng nhau ( bài toán chỉnh hợp ) hay khác nhau ( bài toán tổ hợp ) ?

- có cần lọc bỏ ( so với bộ từ điển kiểm duyệt các chỉnh-tổ-hợp tạo được từ các chữ cái nhập vào không cần đến ) trước khi tìm, truy cập vào 1 từ điển ?
- Về từ điển, như đã có thảo luận ở trên thì chỉ là list các từ thôi (chứ không cần nghĩa), do đó có thể là CSDL của chính chương trình (cách hay nhất), hoặc CSDL của 1 từ điển có sẵn trên máy.
- Các chữ cái hoàn toàn có thể trùng nhau. VD nhập 'd d a' có thể ra 'add' hoặc 'dad'.
- Câu hỏi thứ 3 của bạn tôi không hiểu rõ lắm. Theo tôi thì sau khi tra trong list từ & ra kết quả sơ bộ rồi thì mới áp dụng bộ lọc những chỉnh (tổ) hợp không cần thiết ra.
Bạn Lagi2 xem liệu có thể viết giúp tôi phần mềm này không? Nếu cần tôi ngồi gõ list từ cho ^^

Lagi2

21-09-2011, 14:15

Câu hỏi thứ 3 :
- Do bài toán chỉnh hợp có số chỉnh hợp rất lớn ( toán học : n => n! đọc là n giai thừa ), ví dụ n = 10, số chỉnh hợp là 10! = 3628800 ( = 1 * 2 * 3 *4 * 5 * 6 * 7 * 8 * 9 * 10 ). Trong đó có rất nhiều tổ hợp word - từ không cần đến, cần loại bỏ ( : một từ không có nguyên âm , một từ không có trong từ điển kiểm duyệt ). Từ viết tắt - không có nguyên âm - phải viết HOA ( TV, FTP, ... ).

Tôi nghĩ chương trình bạn yêu cầu, không phải là CT tạo từ ( có nghĩa ) mà lấy kết quả trả về từ việc tìm kiếm ( như Google, Yahoo, ... ), nên câu hỏi trên bạn cần trả lời chi tiết.

Bạn nghĩ được, tôi viết được. Lập trình viên đơn giản là người dịch, tôi dịch cho PC hiểu cái mà bạn muốn PC làm.

Thân.

11tn2

21-09-2011, 14:42

Trong đó có rất nhiều tổ hợp word - từ không cần đến, cần loại bỏ ( : một từ không có nguyên âm , một từ không có trong từ điển kiểm duyệt ). Từ viết tắt - không có nguyên âm - phải viết HOA ( TV, FTP, ... ).
Tôi nghĩ là những từ viết tắt vẫn nên có mặt, tức là không lọc. Từ bị kiểm duyệt thì đương nhiên là bị lọc rồi :) Từ không nguyên âm rõ ràng là nên lọc, nhưng xem ra sẽ bị xung đột với từ viết tắt :( Còn về từ viết hoa thì tôi không rõ ý bạn lắm, nhưng có lẽ để đơn giản ta cứ chuyển hết cả input lẫn output về chữ thường.
Nếu bạn nhận lời viết thì hay quá. Bạn cứ thoải mái, lúc nào rỗi rãi thì đem ra mà làm, coi như không có deadline :D (à nhưng cũng đừng quá 1 năm nhé ^^)

Lagi2

21-09-2011, 15:08

về từ viết hoa theo quy định của từ điển ( Việt Nam, English, ... ) : các ký tự - chữ cái, character - trong từ ( word ) đều viết hoa - UPPER.

chuyển về chữ thường - lower - hết là quá tốt cho LTV, không có lợi cho người dùng.

viết một CT đương nhiên cần bổ xung, hiệu chỉnh nhiều. Khách hàng mua một phần mềm, CT chạy đúng; KH ra lệnh tìm rồi ngồi đợi kết quả trả về là họ la lối um lên mà ( bạn sẽ yêu cầu về tốc độ, về tối ưu ngay thôi ). Không đáp ứng được => CT đó bị xóa bỏ.

Yêu cầu rõ ràng, thuận lợi cho đôi bên. Phát sinh nhiều => không đủ kinh phí, thời gian; kết cục bỏ của chạy lấy người mất.

Thân

11tn2

22-09-2011, 17:50

Tôi cũng không nắm rõ về chuyện UPPER hay lower sẽ ảnh hưởng thế nào đến lập trình, nhưng bạn cứ tùy ý mà làm, sao cho có dễ dàng cho bạn nhất là được. Về phần tôi thì dùng đồ free chưa phải cảm ơn là may rồi sao dám kêu ca (à mà tôi đã nói rõ là tôi nhờ các bạn viết hộ chương trình này free chưa nhỉ? Nghĩa là ai rỗi rãi và thấy cái này thú vị thì giúp ấy mà. Sợ bạn Lagi2 hiểu lầm :) ) Về chuyện đợi phần mềm chạy thì tôi có thể đợi được, miễn là đừng chiếm hết cả tài nguyên máy sao cho chạy mấy tác vụ bình thường khác như nghe nhạc, duyệt web vẫn ngon là được.

Van8Hien62

22-09-2011, 18:08

11tn2

23-09-2011, 10:02

Viết không ai viết hộ - viết free theo đơn đặt hàng cả, tôi có thể ăn cắp ý tưởng của bạn. Bạn chưa đăng ký bản quyền mà. Thương hiệu Caffee Buôn Ma Thuộc, Nước mắm Phú Quốc được tàu lạ đăng ký bên Trung Quốc rồi. Nó hợp lệ theo luật thương mại Quốc tế.

Tôi thường xuyên dùng Linux, copyLeft. Tôi dùng free, open source, những sản phẩm mà tác giả viết tự nguyện - họ không viết theo đơn đặt hàng của tôi, của bạn. Có những Cty - như IBM, Sun - mướn kỹ sư viết open source cho mục đích của họ ( suy diễn thôi : giành khách hàng của Cty khác, như thương gia Trung Quốc mua móng trâu bò ( đem về vứt đi ) để phá hoại nền kinh tế Việt Nam ).
Vậy ý bạn là muốn viết thì phải trả tiền chứ gì :D Cái chương trình này tôi nghĩ cũng không có giá trị kinh tế gì lớn lắm đâu, nên chắc cũng chẳng mấy ai muốn ăn cắp cái ý tưởng này làm gì? Cái mà tôi muốn thì không giống như đơn đặt hàng, nó chỉ giống như 1 cái chalenge thôi, ai muốn thử sức thì thử - tự nguyện là hàng đầu, nhân tiện là giúp tôi luôn ;p
P/S: Mà muốn đăng kí bản quyền thì đăng kí như thế nào nhỉ :) Cái của tôi mới dừng ở mức ý tưởng, chưa thành sản phẩm hình như không được làm bản quyền??

ebookfinder

23-09-2011, 23:07

@11tn2,
bạn ko trong ngành nên cũng ko thấy hết giá trị ý tưởng. lấy ví dụ bài toán bạn nhé; mọi người ngay lập tức đưa ra giải pháp là: làm 1 list các từ, tạo chỉnh/tồ hợp ký tự như từ, so trùng từ tạo tự động với list từ để trả lời. Đó là 1 ý tưởng rất chung và tầm thường. Trong khi đọc kỹ, sẽ thấy rằng cái list từ mới là quyết định chứ ko phải chỉnh/tổ hợp. Để ý rằng tiếng Anh từ dài nhất là 34 ký tự (http://en.wikipedia.org/wiki/Longest_word_in_English) nhưng 34! sản xuất ra số lượng thừa khủng khiếp hơn nhiều con số vài trăm ngàn từ tiếng anh có thực. Điều đó chứng tỏ thêm ý tưởng trên rất kém hiệu quả.
Khi nói vậy tất nhiên tôi có nhiều ý tưởng khác tốt hơn nhiều. Lấy 1 ví dụ, tôi làm ngược cái ý tưởng trên:
1) coding cái list từ có sẵn sử dụng cấu trúc cây với segment index, lấy ví dụ 1 phần của cây:

b
|
o - y
|
o - o - y
|
klà tôi đã coding 4 từ: by, boo, boy và book.
2) Duyệt cây sử dụng list ký tự (~24), như vậy ko gian search nhỏ hơn nhiều duyệt chỉnh/tổ hợp trên list từ (~165000).
3) Cây này bổ sung thêm bất cứ lúc nào, hôm nay có 4 từ nhưng ngày mai có thể có 100 từ.

Như vậy bạn đã thấy sự khác nhau và giá trị của ý tưởng trong lĩnh vực khoa học máy tính.
Bạn nói bài toán này tầm thường, đó cũng vì bạn chưa có nghề,
1) Bài toán này giúp giải tự động ô chữ, đó là 1 ví dụ đơn
2) Trong text mining thì bài toán cực kỳ quan trọng trong bộ N
3) Thêm chút về biological sequence analysis (http://en.wikipedia.org/wiki/Sequence_analysis) thì bạn sẽ té ngữa ra vì bài toán này còn giúp kiểm tra, dự báo hàng loạt thứ liên quan đến chức năng của genes, proteins.
Nói túm lại nó có giá của nó. rất đắt.

11tn2

24-09-2011, 23:31

ÀÀÀ... tôi hiểu rồi. Có phải bạn vanhien & ebookfinder muốn nói đến giá trị ý tưởng của những người lập trình sẽ bị đánh cắp nếu họ viết free cho người khác không? Hóa ra lúc trước tôi hiểu nhầm :">
Tôi thấy bạn ebookfinder là người có hiểu biết rộng về nhiều lĩnh vực, rất cám ơn bạn đã đóng góp 1 ý tưởng. Dù không biết lập trình nhưng tôi có thể thấy là nó rất hay, làm chương trình chạy nhanh hơn nhiều (tuy nhiên công sức ban đầu để tạo 26 cái cây thì lớn hơn là làm list từ).
Còn về giá của nó, tôi nghĩ là không đến mức 'rất đắt' như bạn nói đâu. Bạn thử xét lại xem: những lĩnh vực mà bạn kể đến đều cần 1 thuật toán khổng lồ với chương trình này (giả sử là cần đến nó) chỉ là 1 bộ phận rất rất nhỏ. Hình như đã có ai đó nói ở trang trước là viết phần mềm xử lí được yêu cầu của tôi chỉ mất khoảng 1 tuần. Ngay như tôi đây sau khi đọc ý tưởng của bạn cũng biết là nút thắt của bài toán đã được tháo gỡ, hơn 90% là ok rồi. Nếu như tôi biết lập trình thì đến giờ tôi cũng đã nhìn ra tất cả những gì mình phải làm.
Như vậy có ai muốn đứng ra viết hộ tôi không? Các bạn có thể đăng kí bản quyền phần mềm mình làm ra thoải mái, chỉ cần cho tôi 1 bản là được ^^

Van8Hien62

26-09-2011, 15:39

11tn2

27-09-2011, 16:43

Đăng kí bản quyền thì đăng kí như thế nào nhỉ Cái của tôi mới dừng ở mức ý tưởng.

Bạn có thể tham khảo bài viết bên cạnh, Phần mềm nhận dạng ký tự(OCR) : Đừng quên bản quyền thuộc về Freewarez@ddth.com nhé!!

Ở VN thường có nhiều cuộc thi, có giải thưởng cho ý tưởng .

Như các bài phân tích trên, độ phức tạp của vấn đề khá lớn, thời gian không thể ngắn, và như bạn nói chương trình này tôi nghĩ cũng không có giá trị kinh tế gì lớn lắm đâu nên .. muốn đứng ra viết hộ - theo tôi là rất hiếm ( lim(f) = 0 ).
Ý của bạn về vấn đề 'ý tưởng' là gì thế? Tôi nên đi thi??? :D Hay bạn muốn nói là ý của tôi cũ rồi không có gì mới mẻ, giống y như freewarez? :)
Tôi nghĩ vấn đề chính của chương trình này là database khá lớn & rắc rối thôi. Còn phần code chắc cũng không khó nhằn lắm. Nếu việc làm CSDL chỉ cần 1 ít kiến thức kết hợp với cần cù là chính thì ai dạy qua cho tôi cách, tôi ngồi làm CSDL cho?

emdichuahuong

07-10-2011, 16:29