Tài liệu bồi dưỡng Tin học cho giáo viên
Chia sẻ bởi Trương Nhân |
Ngày 10/05/2019 |
45
Chia sẻ tài liệu: Tài liệu bồi dưỡng Tin học cho giáo viên thuộc Tin học 12
Nội dung tài liệu:
CÂY HẬU TỐ VÀ ỨNG DỤNG
Cây hậu tố và các cấu trúc dữ liệu dẫn xuất
Những thuật toán xây dựng cấu trúc dữ liệu
Một số bài toán ứng dụng và mở rộng
Khái niệm cơ sở
Tiền tố, hậu tố, xâu con
3
O
U
T
S
T
A
N
D
I
N
G
(tiền tố)
(hậu tố)
(xâu con)
(tiền tố của hậu tố)
Quan hệ giữa các tiền tố và hậu tố
4
B
A
N
A
N
A
B
A
Xâu con chung dài nhất
5
6
O
U
T
S
T
A
N
D
I
N
G
U
N
D
E
R
S
T
A
N
D
A
B
L
E
7
O
U
T
S
T
A
N
D
I
N
G
U
N
D
E
R
S
T
A
N
D
A
B
L
E
Donald Ervin Knuth
Tóm tắt quá trình phát triển
8
Tóm tắt quá trình phát triển
[Kasai et al.]: Mảng tiền tố chung dài nhất và phép dựng cây hậu tố từ mảng hậu tố [2001]
[Abouelhoda et al.]: Mảng hậu tố tăng cường và cây lcp-interval [2004]
[Kärkkäinen et al.][Ko et al.]: Thuật toán tuyến tính xây dựng mảng hậu tố [2003]
[Puglisi]: Đánh giá ~20 thuật toán xây dựng mảng hậu tố [2007]
[Kim et al.]: Cài đặt lcp-interval trees trên bảng chữ cái lớn, thuật toán tính liên kết hậu tố không qua RMQ. [2008]
9
Trie
10
11
STOC
Trie hậu tố (suffix trie)
12
13
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
BANANA@
ANA
Ký tự cầm canh @
14
15
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
Xâu AN xuất hiện bao nhiêu lần?
BANANA@
16
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
Tìm xâu dài nhất xuất hiện 2 lần
BANANA@
17
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
Tìm xâu dài nhất xuất hiện 3 lần
BANANA@
Dựng trie hậu tố
Chèn lần lượt từng hậu tố vào Trie
Khi rẽ nhánh, bổ sung nút con nếu cần thiết
Số nút của trie và độ phức tạp?
18
19
BANANA@
20
ANANA@
21
NANA@
22
ANA@
23
NA@
24
A@
25
@
Cây hậu tố
26
27
Cây hậu tố
28
29
Thuật toán xây dựng cây hậu tố
30
Mảng hậu tố
31
32
Xây dựng mảng hậu tố từ cây hậu tố
Duyệt cây bằng DFS bắt đầu từ gốc
Thứ tự các nút con của cùng một nút: Nút con ứng với cạnh mang nhãn nhỏ hơn được xét trước nút con ứng với cạnh mang nhãn lớn hơn (theo thứ tự từ điển)
Thứ tự các nút lá được liệt kê chính là mảng hậu tố
33
34
@
Xây dựng mảng hậu tố
Thuật toán trực tiếp
Thuật toán nhân đôi tiền tố (doubling prefix)
Các thuật toán chia để trị (divide & conquer)
35
Thuật toán nhân đôi tiền tố (1)
36
B
A
N
A
N
A
@
Thuật toán nhân đôi tiền tố (2)
37
38
0
1
2
3
4
5
6
Gán khóa sơ cấp:
2
1
3
1
3
1
0
Thuật toán nhân đôi tiền tố (3)
39
3
2
4
2
4
1
0
40
0
1
2
3
4
5
6
Khóa sơ cấp:
2
1
3
1
3
1
0
Khóa thứ cấp:
1
3
1
3
1
0
2
Khóa sơ cấp mới:
4
3
6
2
5
1
0
41
0
1
2
3
4
5
6
Khóa sơ cấp:
3
2
4
2
4
1
0
Khóa thứ cấp:
4
2
4
1
0
3
2
Khóa sơ cấp mới:
B
A
N
A
N
A
@
42
Khóa sơ cấp:
Dãy hậu tố
Xâu:
Vị trí:
Thuật toán nhân đôi tiền tố (4)
43
Thuật toán chia để trị
44
Mảng tiền tố chung dài nhất
45
46
B
A
N
A
N
A
@
A
N
A
N
A
@
N
A
N
A
@
A
N
A
@
N
A
@
A
@
@
Tiền tố chung dài nhất giữa hai hậu tố
47
48
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
ANA@
ANANA@
ANA
49
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
A@
ANANA@
A
Thuật toán Kasai
50
51
rank: 0
rank: 1
rank: 2
rank: 3
rank: 4
rank: 5
rank: 6
52
Thứ tự từ điển
53
Thứ tự từ điển
…
…
…
…
54
Dựng cây hậu tố (1)
55
Dựng cây hậu tố (2)
56
57
lá cực phải
AB
CAB
EF@
EF@
58
lá cực phải
AB
CAB
CD@
C
AB
D@
Dựng cây hậu tố (3)
59
60
@
61
A@
62
ANA@
63
ANANA@
64
BANANA@
65
NA@
66
NANA@
67
Đếm số xâu con
68
Đếm số xâu con
69
70
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
71
72
73
74
75
76
77
Đếm số xâu con
78
79
80
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
81
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
82
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
83
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Phần tử nhỏ nhất trong đoạn
84
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Tìm đoạn độ dài 2 có giá lớn nhất
85
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
86
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Tìm đoạn độ dài 4 có giá lớn nhất
87
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Liên kết hậu tố
88
89
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
Xâu con chung dài nhất
90
Xâu con chung dài nhất
91
92
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
PANAMA và BANANA
Xâu con chung dài nhất (Cách 2)
93
Xâu con chung dài nhất (Cách 3)
94
95
P
A
N
A
M
A
@
B
A
N
A
N
A
$
0
0
0
1
1
1
3
3
0
0
0
2
2
0
$
@
B
A
N
A
N
A
$
A
$
A
@
B
A
N
A
N
A
$
A
M
A
@
B
A
N
A
N
A
$
A
N
A
$
A
N
A
M
A
@
B
A
N
A
N
A
$
A
N
A
N
A
$
B
A
N
A
N
A
$
M
A
@
B
A
N
A
N
A
$
N
A
$
N
A
M
A
@
B
A
N
A
N
A
$
N
A
N
A
$
P
A
N
A
M
A
@
B
A
N
A
N
A
$
Các bài toán khác và mở rộng
Mẫu ghép
Xâu con đối xứng dài nhất
Cài đặt trên bảng chữ cái lớn
Mảng hậu tố tăng cường
96
Cây hậu tố và các cấu trúc dữ liệu dẫn xuất
Những thuật toán xây dựng cấu trúc dữ liệu
Một số bài toán ứng dụng và mở rộng
Khái niệm cơ sở
Tiền tố, hậu tố, xâu con
3
O
U
T
S
T
A
N
D
I
N
G
(tiền tố)
(hậu tố)
(xâu con)
(tiền tố của hậu tố)
Quan hệ giữa các tiền tố và hậu tố
4
B
A
N
A
N
A
B
A
Xâu con chung dài nhất
5
6
O
U
T
S
T
A
N
D
I
N
G
U
N
D
E
R
S
T
A
N
D
A
B
L
E
7
O
U
T
S
T
A
N
D
I
N
G
U
N
D
E
R
S
T
A
N
D
A
B
L
E
Donald Ervin Knuth
Tóm tắt quá trình phát triển
8
Tóm tắt quá trình phát triển
[Kasai et al.]: Mảng tiền tố chung dài nhất và phép dựng cây hậu tố từ mảng hậu tố [2001]
[Abouelhoda et al.]: Mảng hậu tố tăng cường và cây lcp-interval [2004]
[Kärkkäinen et al.][Ko et al.]: Thuật toán tuyến tính xây dựng mảng hậu tố [2003]
[Puglisi]: Đánh giá ~20 thuật toán xây dựng mảng hậu tố [2007]
[Kim et al.]: Cài đặt lcp-interval trees trên bảng chữ cái lớn, thuật toán tính liên kết hậu tố không qua RMQ. [2008]
9
Trie
10
11
STOC
Trie hậu tố (suffix trie)
12
13
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
BANANA@
ANA
Ký tự cầm canh @
14
15
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
Xâu AN xuất hiện bao nhiêu lần?
BANANA@
16
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
Tìm xâu dài nhất xuất hiện 2 lần
BANANA@
17
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
Tìm xâu dài nhất xuất hiện 3 lần
BANANA@
Dựng trie hậu tố
Chèn lần lượt từng hậu tố vào Trie
Khi rẽ nhánh, bổ sung nút con nếu cần thiết
Số nút của trie và độ phức tạp?
18
19
BANANA@
20
ANANA@
21
NANA@
22
ANA@
23
NA@
24
A@
25
@
Cây hậu tố
26
27
Cây hậu tố
28
29
Thuật toán xây dựng cây hậu tố
30
Mảng hậu tố
31
32
Xây dựng mảng hậu tố từ cây hậu tố
Duyệt cây bằng DFS bắt đầu từ gốc
Thứ tự các nút con của cùng một nút: Nút con ứng với cạnh mang nhãn nhỏ hơn được xét trước nút con ứng với cạnh mang nhãn lớn hơn (theo thứ tự từ điển)
Thứ tự các nút lá được liệt kê chính là mảng hậu tố
33
34
@
Xây dựng mảng hậu tố
Thuật toán trực tiếp
Thuật toán nhân đôi tiền tố (doubling prefix)
Các thuật toán chia để trị (divide & conquer)
35
Thuật toán nhân đôi tiền tố (1)
36
B
A
N
A
N
A
@
Thuật toán nhân đôi tiền tố (2)
37
38
0
1
2
3
4
5
6
Gán khóa sơ cấp:
2
1
3
1
3
1
0
Thuật toán nhân đôi tiền tố (3)
39
3
2
4
2
4
1
0
40
0
1
2
3
4
5
6
Khóa sơ cấp:
2
1
3
1
3
1
0
Khóa thứ cấp:
1
3
1
3
1
0
2
Khóa sơ cấp mới:
4
3
6
2
5
1
0
41
0
1
2
3
4
5
6
Khóa sơ cấp:
3
2
4
2
4
1
0
Khóa thứ cấp:
4
2
4
1
0
3
2
Khóa sơ cấp mới:
B
A
N
A
N
A
@
42
Khóa sơ cấp:
Dãy hậu tố
Xâu:
Vị trí:
Thuật toán nhân đôi tiền tố (4)
43
Thuật toán chia để trị
44
Mảng tiền tố chung dài nhất
45
46
B
A
N
A
N
A
@
A
N
A
N
A
@
N
A
N
A
@
A
N
A
@
N
A
@
A
@
@
Tiền tố chung dài nhất giữa hai hậu tố
47
48
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
ANA@
ANANA@
ANA
49
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
A@
ANANA@
A
Thuật toán Kasai
50
51
rank: 0
rank: 1
rank: 2
rank: 3
rank: 4
rank: 5
rank: 6
52
Thứ tự từ điển
53
Thứ tự từ điển
…
…
…
…
54
Dựng cây hậu tố (1)
55
Dựng cây hậu tố (2)
56
57
lá cực phải
AB
CAB
EF@
EF@
58
lá cực phải
AB
CAB
CD@
C
AB
D@
Dựng cây hậu tố (3)
59
60
@
61
A@
62
ANA@
63
ANANA@
64
BANANA@
65
NA@
66
NANA@
67
Đếm số xâu con
68
Đếm số xâu con
69
70
B
A
N
A
N
A
@
N
@
A
@
N
A
@
N
A
@
A
N
A
@
@
71
72
73
74
75
76
77
Đếm số xâu con
78
79
80
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
81
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
82
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
83
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Phần tử nhỏ nhất trong đoạn
84
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Tìm đoạn độ dài 2 có giá lớn nhất
85
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
86
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Tìm đoạn độ dài 4 có giá lớn nhất
87
@
0
0
1
2
4
5
0
2
3
5
6
1
3
4
Liên kết hậu tố
88
89
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
Xâu con chung dài nhất
90
Xâu con chung dài nhất
91
92
@
A
BANANA@
NA
@
NA
@
NA@
@
NA@
PANAMA và BANANA
Xâu con chung dài nhất (Cách 2)
93
Xâu con chung dài nhất (Cách 3)
94
95
P
A
N
A
M
A
@
B
A
N
A
N
A
$
0
0
0
1
1
1
3
3
0
0
0
2
2
0
$
@
B
A
N
A
N
A
$
A
$
A
@
B
A
N
A
N
A
$
A
M
A
@
B
A
N
A
N
A
$
A
N
A
$
A
N
A
M
A
@
B
A
N
A
N
A
$
A
N
A
N
A
$
B
A
N
A
N
A
$
M
A
@
B
A
N
A
N
A
$
N
A
$
N
A
M
A
@
B
A
N
A
N
A
$
N
A
N
A
$
P
A
N
A
M
A
@
B
A
N
A
N
A
$
Các bài toán khác và mở rộng
Mẫu ghép
Xâu con đối xứng dài nhất
Cài đặt trên bảng chữ cái lớn
Mảng hậu tố tăng cường
96
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Trương Nhân
Dung lượng: |
Lượt tài: 1
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)