Trie
Tác giả: Nguyễn RR Thành Trung
Trie là một cấu trúc dữ liệu dùng để quản lý một tập hợp các xâu. Trie cho phép:
- Thêm một xâu vào tập hợp
- Xóa một xâu khỏi tập hợp
- Kiểm tra một xâu có tồn tại trong tập hợp hay không.
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 đó.
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ỳ theo yêu cầu bài toán.
Một số ưu điểm của trie
-
Cài đặt đơn giản, dễ nhớ
-
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.
-
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 và độ dài mỗi khóa tương đối nhỏ, $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, các thao tác trên trie rất đơn giản và thường chạy nhanh hơn trên thực tế.
-
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
//Đị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ìm xem 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(p^.count>0);
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 thì 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
Chuỗi từ
Nguồn: Цикл Интернет-олимпиад для школьников, сезон 2007-2008
Chuỗi từ có độ dài $n$ là một dãy các từ $w_1, w_2, …, w_n$ sao cho với mọi $1 \le i < n$, từ $w_i$ là tiền tố của từ $w_{i+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 = {s_1, s_2, …, s_m}$. 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;
Tách từ
Nguồn: Croatian OI 2006
Một xâu $S$ độ dài không quá $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 không quá 400 từ cho trước, mỗi từ có độ dài không quá 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]$ là số cách tách đoạn từ 1 đến $i$ của $S$.
Như vậy, $f[i] = \sum{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;