Lưu trữ từ điển sử dụng B-Tree

[08520549]

thầy cho em hỏi ở bài tập 5 dùng Btree???
vậy trong .Net có hổ trợ sẵn kiểu dữ liệu Btree ko thầy hay là phải tự cài đặt ah
mong thầy nó rõ hơn cách lưu trữ và tra cứu từ điên trong B-tree vì cấu trúc của từ điển gồm nhiều thành phần -HEAD-POS- BODY-TXT_V-EXAMPLE-TXT_V,TXT_E....

[toannv]

thầy cho em hỏi ở bài tập 5 dùng Btree???
vậy trong .Net có hổ trợ sẵn kiểu dữ liệu Btree ko thầy hay là phải tự cài đặt ah
mong thầy nó rõ hơn cách lưu trữ và tra cứu từ điên trong B-tree vì cấu trúc của từ điển gồm nhiều thành phần -HEAD-POS- BODY-TXT_V-EXAMPLE-TXT_V,TXT_E....

Cái này thì SV tự tìm hiểu à.
Trên YinYang hay codeproject đều có cái tương tự, nhiều. Ở http://msdn.microsoft.com/en-us/libr...(v=VS.80).aspx cũng có một số ý (Hình như các bài đồ án trước các bạn không xem ở đó ).

Về từ điển thì có thể lấy 3 ký tự đầu của HEAD làm khóa trong B-Tree hay làm như thế nào cũng được. Các bạn xem hình sau sẽ hiểu

[08520480]

Trên trang codeproject nó viết 1 cái namespace Sop, nhưng khi add vào sử dụng nó giống như Dictionary trong C# có sẵn vậy thầy.

[08520348]

Thưa thầy em xin có chút ý kiến về mô hình Btree trên của thầy:
1/ Mô hình này chỉ dùng để xử lý 1 ký tự bất kỳ thôi chứ không thể áp dụng cho 1 chuỗi (gồm nhiều ký tự liên tiếp nhau) như yêu cầu của bài từ điển được.
Ví dụ: Nếu muốn tra từ "met" thì theo cấu trúc trên sẽ phải đi xuống và đi ngược lại => không đúng với ý nghĩa của Btree.
2/ Nếu muốn tra được từ điển theo Btree thì em nghĩ phải thiết kế cái cây sao cho tầng đầu tiên bao gồm cả 27 chữ cái (hết bảng chữ cái tiếng anh) và trong mỗi chữ cái rẻ nhánh xuống phải có 27 chữ cái khác nữa (để có thể tra được bất kỳ từ nào) ...
Và theo cấu trúc này thì nếu cây có độ cao là 3 thì có thể chứa tối đa được : 27^1+27^2+27^3=20439 từ. Nhưng từ điển của ta lại có hơn 1 trăm ngàn từ nên ta phải dùng tới tầng thứ 4, lúc đó có thể chứa được 27^1+27^2+27^3+27^4=551880 từ (thỏa yêu cầu). Tuy nhiên nếu theo cách này thì cấu trúc Btree là vô nghĩa vì không cần xét duyệt xem từ này có ở trước từ kia hay không mà đơn giản chỉ là xét 4 ký tự đầu phân tầng xuống và cho ra kết quả thôi.
Mong thầy cho ý kiến về vấn đề này!

[09520668]

Anh hiểu sai ý thầy rồi, cái trên của thầy chỉ là ví dụ cho hiểu B-tree là thế nào thôi. Còn băm 3 kí tự đầu, bữa thứ 3 đi học thầy nói thế này nè:

Không nhất thiết là dùng Hashtable như hình

[08520348]

Thịnh: mình thấy mô hình của bạn y chang ý kiến của mình mà, tại mình không vẽ ra nên chắc là bạn hiểu sai. Theo mô hình bạn nêu trên thì kết quả tính ra sẽ là 27^1+27^2+27^3+27^4 như mình nêu trên nếu muốn lưu được hết tất cả các HEAD trong từ điển.

[09520668]

Em không biết phải nói sao cho ông anh hiểu rõ
Thứ 3 thầy cũng nói sơ qua, và vẽ hình. Đại khái là thế này: tại các node bậc 1 và 2 không dùng để lưu từ. Chỉ có node bậc 3 mới dùng để lưu tất cả từ có 3 kí tự đầu giống node(chỉ có 26^3 node dùng để lưu từ).
Ví dụ:
Node "ban" thì sẽ dùng 1 CTDL mình đề xuất để lưu lại tất cả từ và dữ liệu của từ band, bane, bank, ....
Node "thi" thì sẽ dùng 1 CTDL mình đề xuất để lưu lại tất cả từ và dữ liệu của từ think, thin, thing ....
Có thể tận dụng lại CTDL bài 1 để xài cho khỏe, bỏ ví dụ của từ ra là được
Thầy chỉ yêu cầu băm 3 kí tự đầu thôi, nhưng anh cũng có thể làm thêm, tại cái này thầy chỉ gợi ý cho những ai chưa nắm rõ làm theo thôi

[08520160]

Em không biết phải nói sao cho ông anh hiểu rõ
Thứ 3 thầy cũng nói sơ qua, và vẽ hình. Đại khái là thế này: tại các node bậc 1 và 2 không dùng để lưu từ. Chỉ có node bậc 3 mới dùng để lưu tất cả từ có 3 kí tự đầu giống node(chỉ có 26^3 node dùng để lưu từ).
Ví dụ:
Node "ban" thì sẽ dùng 1 CTDL mình đề xuất để lưu lại tất cả từ và dữ liệu của từ band, bane, bank, ....
Node "thi" thì sẽ dùng 1 CTDL mình đề xuất để lưu lại tất cả từ và dữ liệu của từ think, thin, thing ....
Có thể tận dụng lại CTDL bài 1 để xài cho khỏe, bỏ ví dụ của từ ra là được
Thầy chỉ yêu cầu băm 3 kí tự đầu thôi, nhưng anh cũng có thể làm thêm, tại cái này thầy chỉ gợi ý cho những ai chưa nắm rõ làm theo thôi

Hi! Thịnh!
cách của bạn và bạn Thành là giống nhau: chẳng qua chỉ khác nhau cách lưu thôi. Bạn có thể xem sét cách tìm đường đi của bạn Thành, và giá trị trên nút của bạn.

[08520348]

Em không biết phải nói sao cho ông anh hiểu rõ
Thứ 3 thầy cũng nói sơ qua, và vẽ hình. Đại khái là thế này: tại các node bậc 1 và 2 không dùng để lưu từ. Chỉ có node bậc 3 mới dùng để lưu tất cả từ có 3 kí tự đầu giống node(chỉ có 26^3 node dùng để lưu từ).
Ví dụ:
Node "ban" thì sẽ dùng 1 CTDL mình đề xuất để lưu lại tất cả từ và dữ liệu của từ band, bane, bank, ....
Node "thi" thì sẽ dùng 1 CTDL mình đề xuất để lưu lại tất cả từ và dữ liệu của từ think, thin, thing ....
Có thể tận dụng lại CTDL bài 1 để xài cho khỏe, bỏ ví dụ của từ ra là được
Thầy chỉ yêu cầu băm 3 kí tự đầu thôi, nhưng anh cũng có thể làm thêm, tại cái này thầy chỉ gợi ý cho những ai chưa nắm rõ làm theo thôi

Được rồi, anh hiểu ý của em. Cách của anh khác em ở 1 điểm thế này. Tất cả các bậc của anh đều xét 1 ký tự thôi, không xét phân cấp tăng dần như của em, nhưng số lượng ô nhớ được tạo ra là tương đương nhau như anh nói phía trên. Nếu như đây là cách thầy bảo làm thì anh theo cách này vậy vì trông có vẻ gọn gàng hơn cách của anh.

[08520480]

cái này cũng như dùng key là ký tự a,b,c.......... và value là ký tự a,b,c...... mình so từng ký tự của từ cần tìm.rồi load nó bằng file xml ra thôi. Htruoc thầy cũng nói rồi mà

[09520548]

Thưa thầy em vẫn chưa hiểu về vấn đề băm từ để đưa dữ liệu từ XML vào B-Tree. Nếu các node là các chữ cái sẽ có 26 chữ cái thôi chứ không thể đưa vào trùng được, và còn những kí tự đặc biệt nữa thì sao thầy? Nếu nói băm 3 kí tự đầu tiên thì có những từ chỉ có 1-2 chữ cái, làm sao để tìm nó được vì đến node lá mới lưu nội dung của từ? Còn nếu băm theo kiểu dùng hàm băm để có số thì như vậy thành hashtable rồi, sao không tìm kiếm trên hashtable luôn mà phải đưa vào B-Tree tìm kiếm vậy thầy? Trong các tài liệu chỉ nói đến dùng B-Tree để tìm khóa chứ còn phần tìm nội dung mà khóa đó chỉ đến thì không nói tới. Mong thầy giải đáp em những thắc mắc trên.
Em cám ơn thầy!

[09520533]

Thưa thầy em vẫn chưa hiểu về vấn đề băm từ để đưa dữ liệu từ XML vào B-Tree. Nếu các node là các chữ cái sẽ có 26 chữ cái thôi chứ không thể đưa vào trùng được, và còn những kí tự đặc biệt nữa thì sao thầy? Nếu nói băm 3 kí tự đầu tiên thì có những từ chỉ có 1-2 chữ cái, làm sao để tìm nó được vì đến node lá mới lưu nội dung của từ? Còn nếu băm theo kiểu dùng hàm băm để có số thì như vậy thành hashtable rồi, sao không tìm kiếm trên hashtable luôn mà phải đưa vào B-Tree tìm kiếm vậy thầy? Trong các tài liệu chỉ nói đến dùng B-Tree để tìm khóa chứ còn phần tìm nội dung mà khóa đó chỉ đến thì không nói tới. Mong thầy giải đáp em những thắc mắc trên.
Em cám ơn thầy!

các ký tự đặc biệt thì ta gom chung vào 1 nhóm, vì số từ có các ký tự mở đầu này không nhiều, băm 3 ký tự với những từ >= 3 ký tự , còn những từ < 3 ký tự thì băm theo số ký tự của nó , tức là phải đề xuất hàm băm sao cho không có khóa nào trùng nhau cả, với những từ > 3 ký tự có 3 ký tự đầu trùng nhau thì làm theo cách của bạn Thịnh ấy , về nội dung của khóa thì nếu bạn tìm được khóa thì sẽ tìm được nội dung của nó thôi, bài này dùng btree mới phải suy nghĩ chứ hashtable thì nói làm gì nữa nó tự làm hết cho mình rồi

[09520668]

- Cái hình của Thịnh chỉ mang tính chất minh họa cho các bạn hiểu thôi, chứ B-Tree không tổ chức ra được cái cây dạng cây như hình đâu trừ khi cố ép nó như thế nên các bạn đừng hiểu nhầm, tại vì cây như dạng đó thì khi tìm kiếm không đạt hiệu quả cao nhất. Tốt nhất nên lấy code C của thầy cho để chạy thử để hiểu rõ hơn cách thêm node vào cây(sẽ hiểu được tại sao không thể ra cây dạng như hình nếu không cố ép).
- Vấn đề cách lưu từ vào node thì tùy mình thiết kế, nên mỗi người 1 hướng, tùy vào cách giải quyết sẽ làm ra 1 hàm tìm kiếm (dựa vào cách băm và cách lưu từ) khác nhau (Không nhất thiết trong node aaa phải lưu từ bắt đầu = 3 kí tự aaa)

[09520339]

các ký tự đặc biệt thì ta gom chung vào 1 nhóm, vì số từ có các ký tự mở đầu này không nhiều, băm 3 ký tự với những từ >= 3 ký tự , còn những từ < 3 ký tự thì băm theo số ký tự của nó , tức là phải đề xuất hàm băm sao cho không có khóa nào trùng nhau cả, với những từ > 3 ký tự có 3 ký tự đầu trùng nhau thì làm theo cách của bạn Thịnh ấy , về nội dung của khóa thì nếu bạn tìm được khóa thì sẽ tìm được nội dung của nó thôi, bài này dùng btree mới phải suy nghĩ chứ hashtable thì nói làm gì nữa nó tự làm hết cho mình rồi

Nói như chú thì dùng Hashtable cho rồi chiện gì phải làm B-tree vào để mắc công suy nghĩ nhiều?)) theo a nghĩ nên tổ chức các Hashtable theo dạng giống B-tree =>Hạn chế được khóa/node(Hashtable) =>tìm khóa nhanh hơn@@

P/s ko biết đúng ko nữa?

[09520548]

Vậy còn phương pháp lưu trữ bằng cách băm các khóa ra bằng cách sử dụng 1 hàm băm, sau đó lưu trữ vào b-tree bằng cách lấy kết quả băm được làm khóa và nội dung dùng để băm làm giá trị cho khóa đó. Khi tìm kiếm thì sử dụng tìm kiếm trên b-tree tìm được khóa đó sẽ xuất luôn được nội dung của khóa đó luôn