Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới

 
Giỏ hàng

Xem giỏ hàng


Giỏ hàng chưa có sản phẩm

 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (701 bài viết)
  • Sản phẩm mới (217 bài viết)
  • Dành cho Giáo viên (552 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (155 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (126 bài viết)
  • Hỗ trợ khách hàng (482 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (182 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (71 bài viết)
  • Cùng Học (98 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (74 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • School@net 15 năm (153 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (123 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (360 bài viết)
  • Các vấn đề giáo dục (1209 bài viết)
  • Bài học trực tuyến (1033 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (276 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (181 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 4
    Thành viên: 0
    Tổng cộng: 4
     
    Số người truy cập
    Hiện đã có 54824742 lượt người đến thăm trang Web của chúng tôi.

    Trie và một vài ứng dụng

    Ngày gửi bài: 15/02/2010
    Số lượt đọc: 1876

    Trong rất nhiều bài toán, một thao tác cơ bản cần phải thực hiện là tìm kiếm một dữ liệu (Chẳng hạn khi thực hiện loang trên một tập trạng thái, bạn cần tìm kiếm xem một trạng thái đã được thăm trước đó hay chưa, (mà không thể dùng mảng đánh dấu vì mỗi trạng thái lại là một dãy số, một ma trận hay một xâu ký tự...), bằng cách tìm kiếm trạng thái hiện tại trong danh sách tập trạng thái đã thăm; hay trong quá trình quy hoạch động, bạn cần kiểm tra xem một dãy số hay một chuỗi kí tự có nằm trong một tập cho trước không...). Để tìm kiếm một cách có hiệu quả là một việc không hề đơn giản. Có rất nhiều cấu trúc dữ liệu giúp bạn thực hiện thao tác tìm kiếm: binary search tree, hash table, ... Trong bài viết này, tôi xin đề cập đến cấu trúc dữ liệu Trie.

    Thông thường, người ta thường sử dụng trie khi cần lưu trữ một tập dữ liệu gồm các xâu (tổng quát hơn, có thể là các số lớn vài chục chữ số...)

    Cấu trúc:

    Trie gồm một gốc không chứa thông tin, trên mỗi cạnh lưu một ký tự, mỗi nút và đường đi từ gốc đến nút đó thể hiện 1 xâu, gồm các ký tự là các ký tự thuộc cạnh trên đường đi đó.

    Ví dụ:

    Trong hình vẽ trên, nút 1 là nút gốc, nút 7 thể hiện có 1 xâu là ‘bg’, nút 8 thể hiện có 1 xâu là ‘db’, nút 9 thể hiện có 1 xâu là ‘dc’, nút 10 thể hiện có 1 xâu là ‘acd’, nút 5 thể hiện là có 1 xâu là ‘ab’.

    Tuy nhiên, như các bạn có thể thấy, đối với một số nút, chẳng hạn nút 4, ta không biết nó là thể hiện kết thúc 1 xâu hay chỉ là 1 phần của đường đi từ nút 1 đến nút 9. Vì vậy, khi cài đặt, thông thường, tại nút U ta cần lưu thêm thông tin nút U có là kết thúc của 1 xâu hay không, hoặc nút U là kết thúc của bao nhiêu xâu (tuỳ bài toán).

    Một số ưu điểm của trie:

    1/ Cài đặt đơn giản, dễ nhớ

    2/ Tiết kiệm bộ nhớ: Khi số lượng khóa lớn và các khóa có độ dài nhỏ, thông thường trie tiết kiệm bộ nhớ hơn do các phần đầu giống nhau của các khoá chỉ được lưu 1 lần. Ưu điểm này có ứng dụng rất lớn, chẳng hạn trong từ điển điện thoại

    3/ Thao tác tìm kiếm: O(m) với m là độ dài khóa. Với binary search tree (cân bằng): là O(logN). Khi số lượng khóa cần tìm lớn, logN xấp xỉ m, và như các bạn đã biết, để cài được binary search tree cân bằng không phải là một việc đơn giản. Hơn nữa, trên thực tế, trie chỉ đòi hỏi các phép đi đến 1 phần tử có chỉ số cho trước của mảng, và thông thường thao tác này nhanh hơn trên thực tế.

    4/ Dựa vào tính chất của cây trie, có thể thực hiện một số liên quan đến thứ tự từ điển như sắp xếp, tìm một khóa có thứ tự từ điển nhỏ nhất và lớn hơn một khóa cho trước...; và một số thao tác liên quan đến tiền tố, hậu tố.

    Cài đặt cụ thể:

    //Định nghĩa kiểu trie

    type

    trie=^node;

    node=record

    count:longint; //Số lượng xâu kết thúc tại một nút

    c:array[‘a’..’z’] of trie; //Link đến các nút con của một nút

    end;

    var

    root:trie; //Gốc trie

    //Thêm một nút rỗng vào trie

    procedure add(var a:trie);

    var

    c:char;

    begin

    new(a);

    a^.count:=0;

    for c:=’a’ to ‘z’ do

    a^.c[c]:=nil;

    end;

    //Thêm xâu s vào trie

    procedure insert(s:string);

    var

    i:longint;

    begin

    for i:=1 to length(s) do

    begin

    //Duyệt mỗi kí tự i của s. Với mỗi kí tự, ta đi theo nhánh tương ứng với ký tự i, nếu nhánh này chưa có, ta thêm vào cây

    if p^.c[s[i]]=nil then add(p^.c[s[i]]);

    p:=p^.c[s[i]];

    end;

    inc(p^.count);

    end;

    //Tìmxem xâu s có trong trie không

    function find(s:string):boolean;

    var

    i:longint;

    p:trie;

    begin

    p:=root;

    for i:=1 to length(s) do

    begin

    if p^.c[s[i]]=nil then exit(false);

    p:=p^.c[s[i]];

    end;

    exit(true);

    end;

    (Có thể cài đặt thêm thao tác xóa một từ khỏi trie, nhưng đối với các bài toán thường gặp đối với học sinh cấp 3 thì thông thường thao tác này không cần thiết. Việc cài đặt cụ thể xin nhường lại cho bạn đọc)

    Một vài ứng dụng trong các bài toán

    Sau đây là một vài ví dụ cơ bản thể hiện tác dụng của trie

    1/ Chuỗi từ:

    (Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2007-2008)

    Chuỗi từ có độ dài n là một dãy các từ w1, w2, ..., wn sao cho với mọi 1 ≤ i < n, từ wilà tiền tố của từ wi+1.Từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu tiên của v trùng với từ u. Cho tập hợp các từ S={s1, s2, ..., sm}. Tìm chuỗi từ dài nhất có thể xây dựng được bằng cách dùng các từ trong tập hợp S (có thể không sử dụng hết các từ).

    Thuật toán:

    Một trong những cách giải khá đơn giản đối với bài này là sử dụng trie:

    Lưu tất cả các từ lại vào trie. Đối với mỗi nút trên cây, ta tính f là độ dài chuỗi từ dài nhất bắt đầu ở nút đó.

    Cài đặt một số phần quan trọng:

    type

    trie=^node;

    node=record

    f,u:longint; //Số lượng xâu kết thúc tại một nút

    c:array[‘a’..’z’] of trie; //Link đến các nút con của một nút

    end;

    ...

    procedure dfs(a:trie);

    var

    c:char;

    begin

    a^.f:=0

    for c:=’a’ to ‘z’ do

    begin

    dfs(a^.c[c]);

    a^.f:=max(a^.f,a^.c[c].f);

    end;;

    inc(a^.f,a^.u);

    end;

    function solve:longint;

    begin

    add(root);

    for i:=1 to m do insert(s[i]);

    dfs(root);

    exit(root^.f);

    end;

    2/ Tách từ:

    (Nguồn: Croatian OI 2006)

    Một xâu S độ dài ≤ 300 000 cần được tách thành các đoạn con sao cho mỗi đoạn con thuộc một tập gồm ≤ 400 từ cho trước, mỗi từ có độ dài ≤ 100, không có 2 từ nào giống nhau.

    Viết chương trình xác định số cách tách một từ cho trước.

    Thuật toán:

    Quy hoạch động.

    Đặt f[i] = số cách tách đoạn từ 1..i của S.

    Như vậy, f[i] = tổng f[j] với mỗi j thoả mãn đoạn từ j+1..i là một từ thuộc tập từ đã cho. Ta lần lượt tính f[i] với i chạy từ 1 đến n. Với mỗi i, để kiểm tra mọi đoạn j..i có là một từ cho trước không, chú ý là khi giảm j, các từ này có độ dài tăng lên, và từ trước là hậu tố của từ sau, các từ có độ dài hơn kém nhau một đơn vị. Do đó, trên cây trie, ta có thể đi từ gốc xuống các nút thể hiện các xâu này, nếu không đi được nữa, tức là không có từ nào thoả mãn. Chú ý là khi thêm các xâu của tập đã cho, ta cần thêm các xâu này theo chiều ngược (hoặc một cách xử lý khác là ta tính hàm f từ n đến 1).

    Cài đặt một số phần quan trọng:

    f[0]=1;

    for i:=1 to n do

    begin

    j:=i; p:=root;

    while (j>0) and (p^.c[s[j]]<>nil) do

    begin

    p:=p^.c[s[j]];

    dec(j);

    if (x^.c=1) then inc(f[i],f[j]);

    end;

    end;

    School@net



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (024) 62511017 - Fax: (024) 62511081
    Email: school.net@hn.vnn.vn / thukhachhang@yahoo.com


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.