BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
W  X NGUYỄN THỊ THANH HUYỀN
ĐỐI SÁNH MẪU THEO TIẾP CẬN
OTOMAT MỜ VÀ ỨNG DỤNG

Chuyên ngành: Đảm bảo toán học cho máy tính và hệ thống tính toán
Mã số : 62.46.35.01
TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC

"
Hà Nội – 2007
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI
DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ
1. Nguyễn Thị Thanh Huyền, Phan Trung Huy (2002), “Tiếp cận mờ
trong một số thuật toán so mẫu”, Tạp chí Tin học và điều khiển học
18(3), tr. 201–210.
2. Nguyễn Thị Thanh Huyền, Bùi Kiên Cường, Phan Trung Huy
(2003), “Các thuật toán tìm kiếm xâu con và tìm kiếm tựa ngữ nghĩa
dựa trên otomat mờ”, Kỷ yếu Hội thảo Quốc gia lần thứ VI “ Một số
vấn đề chọn l
ọc của công nghệ thông tin”, Thái Nguyên – 8/2003, tr.
152–163.
3. Nguyễn Thị Thanh Huyền, Phan Trung Huy, Hồ Thuần (2004),
“Thuật toán so mẫu nhanh theo tiếp cận mờ trên dữ liệu text nén và
không nén”, Kỷ yếu Hội thảo quốc gia lần thứ VII “Một số vấn đề
chọn lọc của công nghệ thông tin”, Đà Nẵng – 8/2004, tr. 198–209.
4. Phan Trung Huy, Nguyễn Thị Thanh Huyền (2005), “Nửa nhóm tác
dụng mờ và ứng dụng”, Kỷ yếu hội th
ảo quốc gia lần thứ 8 về “Một
số vấn đề chọn lọc của Công nghệ Thông tin”, 25–27/8 /2005, Hải
Phòng , tr. 371–384.
5. Nguyễn Thị Thanh Huyền, Nguyễn Đắc Tuấn, Phan Trung Huy
(2006), “Xác định một số độ đo sự tương tự giữa hai xâu theo mô
hình otomat mờ”, Tạp chí Bưu chính Viễn thông và Công nghệ
thông tin, Chuyên san “Các công trình nghiên cứu – triển khai viễn
thông và công nghệ thông tin” (16), tr. 86–94.
6. Vũ Thành Nam, Nguyễn Thị Thanh Huyền, Phan Trung Huy (2006),
“Mã tích đ
àn hồi và tìm kiếm trên văn bản mã hoá sử dụng thuật toán
so mẫu theo tiếp cận mờ”, Tuyển tập các bài báo khoa học, Hội nghị

chưa có giải pháp nào được biết.
Đối với nước ta, việc nghiên cứu các thuật toán so mẫu là cần
thiết vì trong nhiều tr
ường hợp, các máy tìm kiếm có tính toàn cầu 2
không được phép truy nhập sâu vào các hệ thống mạng nội bộ, hơn
nữa thuật toán của những tổ chức này không phải lúc nào cũng được
công bố.
II. Nội dung nghiên cứu của luận án
Với mục đích đi sâu nghiên cứu và đóng góp một phần trong lĩnh
vực phát triển các công cụ tìm kiếm văn bản. Đối tượng nghiên cứu
của luận án là bài toán so xâu mẫu theo tiếp c
ận otomat mờ. Phạm vi
nghiên cứu của luận án bao gồm:
1. Xây dựng các giải thuật hiệu quả cho bài toán so đơn mẫu chính
xác, với mẫu là một xâu kí tự.
2. Nghiên cứu và đề xuất một số phương pháp xác định độ tương tự
giữa hai xâu để giải quyết bài toán so mẫu xấp xỉ.
3. Giải quyết bài toán so đơn mẫu để tìm kiếm trên môi trường văn
b
ản nén và mã hoá.
III. Những điểm mới của luận án
1. Tận dụng những ưu điểm của tiếp cận otomat, đồng thời kết hợp
với ý tưởng của lý thuyết tập mờ, luận án đề xuất một số hệ hình
thức otomat mờ để giải quyết các dạng bài toán so xâu mẫu.
2. Luận án đưa ra hai độ đo xác định sự t
ương tự giữa hai xâu, làm cơ
sở giải quyết bài toán so mẫu xấp xỉ.

ấy rằng, khi số lượng trạng thái của otomat càng
tăng thì đáp ứng được các yêu cầu tính toán càng phức tạp. Việc tăng
này theo quan điểm của tập rõ chỉ đơn thuần là về số lượng. Khi đưa
vào quan điểm của tập mờ, sự tăng được nhìn nhận một cách tinh tế
hơn, đó là tăng về cấu trúc của tập trạng thái.
Xuất phát t
ừ những ý tưởng về tập mờ, khi giải bài toán so xâu
mẫu, luận án đưa ra khái niệm độ mờ xuất hiện mẫu để mô tả “mức
độ xuất hiện” hay “mức độ khớp” của mẫu trong văn bản. Tuỳ thuộc
vào nhu cầu hay quan niệm về mức độ khớp trong từng hệ thống tìm 4
kiếm, định nghĩa về độ mờ xuất hiện mẫu cho từng trường hợp cụ thể
sẽ được phát biểu chính xác. Khi đó, một yêu cầu đặt ra là cần tính
được ngay độ mờ xuất hiện mẫu mỗi khi duyệt đến một kí tự trên xâu
đích. Các mô hình otomat mờ được đề xuất trong luận án là một tiếp
cận hợp lý để đáp ứng được yêu cầ
u này, thể hiện rõ qua các bước
tính toán tinh tế của hàm chuyển trạng thái mờ.
IV. Ý nghĩa khoa học của luận án
Tiếp cận otomat mờ do luận án đề xuất đem lại một cách nhìn
nhất quán về một lớp mô hình otomat mờ cho bài toán so đơn mẫu,
với mức độ từ đơn giản đến phức tạp. Từ đó, ta có thể phát triển mô
hình này để giải quyết những yêu cầu
đa dạng khác của bài toán so
mẫu.
Đặc biệt, từ các nghiên cứu về hệ hình thức otomat mờ giải bài
toán so mẫu đã nảy sinh khả năng mở rộng về mặt lý thuyết của mô
hình otomat mờ trong mối liên hệ với đại số, đó là các hệ hình thức

bổ trợ cho Mục 3.3.
Phụ lục B – Giới thiệ
u một số phần mềm trong đó có cài đặt thử
nghiệm các thuật toán so xâu mẫu được đề xuất trong luận án.
Chương 1. TỔNG QUAN VỀ BÀI TOÁN SO MẪU
1.1 Bài toán so mẫu và tình hình nghiên cứu hiện nay
1.1.1 Giới thiệu chung
So mẫu, hay đối sánh mẫu (pattern matching) là bài toán tìm sự
xuất hiện của một mẫu (pattern) với một số đặc tính nào đó trong
chuỗi các ký hiệu cho trước (gọi là xâu đích). Mục này tậ
p trung
trình bày về bài toán so xâu mẫu, tổng quan tình hình nghiên cứu và
ứng dụng. 6
1.1.2 Các dạng của bài toán so mẫu và các kết quả nghiên cứu
Các dạng của bài toán so mẫu bao gồm: so đơn mẫu, so đa mẫu
(mẫu là một tập các xâu), so mẫu mở rộng, so biểu thức chính qui,
theo hai hướng chính xác và xấp xỉ. Nội dung của luận án tập trung
giải quyết bài toán so đơn mẫu, chính xác và xấp xỉ. Vì thế, trong
luận án, mỗi khi nhắc đến so mẫu sẽ ngầm hiểu mẫ
u là một xâu kí tự.
1.1.3 So mẫu xấp xỉ
Các thuật toán so mẫu xấp xỉ hiện nay được chia ra thành bốn loại:
– Các thuật toán dựa trên quy hoạch động.
– Các thuật toán sử dụng otomat tìm kiếm.
– Các thuật toán sử dụng cơ chế song song bit (bit–parallelism).
– Các thuật toán sử dụng cơ chế lọc.
Để so mẫu xấp xỉ, ta cần đo độ tương tự gi

1.3 Hướng tiếp cận otomat mờ cho bài toán so mẫu
1.3.1 Ý tưởng chung của tiếp cận otomat mờ
Các thuật toán so mẫu theo tiếp cận otomat mờ bao gồm hai giai
đoạn: Giai đoạn tiền xử lý mẫu xây dựng otomat mờ dựa vào thông
tin trên mẫu; Giai đoạn sánh mẫu duyệt xâu đích từ trái sang phải và
dựa vào otomat mờ so mẫu để tính ngay được độ mờ xuất hiện mẫu
tại mỗi vị trí được duyệt. Ưu điểm quan trọng nhất của các thuật toán
so mẫu theo tiếp cận otomat mờ là:
− Chi tiết hoá cấu trúc thông tin trong từng tr
ạng thái mờ cho phép
thiết lập những phép chuyển trạng thái tinh tế, nhờ đó mà có thể
giải quyết được những yêu cầu phức tạp của bài toán so mẫu.
− Không đòi hỏi lưu trữ toàn bộ S rồi mới so mẫu, nên có thể áp
dụng trong các thuật toán hướng online.
− Thông tin về mẫu bao hàm trong cấu trúc của otomat mờ nên luôn 8
phản ánh được thông tin về sự xuất hiện mẫu mỗi khi duyệt đến một
vị trí bất kỳ trên xâu đích S và khi cần tìm kiếm mẫu P trong nhiều
xâu S, chỉ cần dùng chung một otomat mờ so mẫu được xây dựng từ
mẫu P (Điều này đặc biệt hữu ích khi tìm kiếm trong cơ sở dữ liệu).
1.3.2 Khái niệm otomat mờ so mẫu
Mục này trình bày mô hình tổng quát của các otomat mờ so mẫu
được sử dụng trong luận án. Khác với các hình thức otomat mờ đã giới
thiệu ở Mục 1.2.3, otomat mờ do luận án đề xuất có trạng thái là một tập
mờ với hàm chuyển trạng thái rõ (có thể được biểu diễn dưới dạng một
quan hệ rõ truyền thống, là một dạng đặc biệt của quan hệ mờ).
Định nghĩa 1.7. Một otomat mờ là bộ năm
A

: Q
×
A
→
Q. Hàm chuyển có thể được mở rộng
trong đó tín hiệu tác động là một xâu thuộc A*:
δ
(q, wa) =
δ
(
δ
(q,w),a), w
∈
A*, a
∈
A.
Số chiều của trạng thái mờ phụ thuộc vào quan điểm về “độ mờ
xuất hiện mẫu” và nhu cầu tìm kiếm trong từng bài toán cụ thể.
1.3.3 Các ký hiệu
Mục này giới thiệu các ký hiệu được sử dụng trong luận án. 9
1.4 Một số thuật toán về so mẫu
Mục này trình bày nội dung hai thuật toán so mẫu kinh điển là
Knuth–Morris–Pratt (KMP) và Boyer–Moore (BM), mà những ý
tưởng cơ bản của chúng được sử dụng để phát triển hai thuật toán so
mẫu chính xác theo tiếp cận otomat mờ của luận án (Chương 2).
Chương 2. BÀI TOÁN SO MẪU CHÍNH XÁC THEO
TIẾP CẬN OTOMAT MỜ

λ
+ 1
S
j –
λ
+ 2
S
j
.
Gọi A
P
là tập các kí tự có trong mẫu P, # là một kí tự đại diện cho
các kí tự thuộc A nhưng không xuất hiện trong P (thuộc A \ A
P
). Độ
mờ xuất hiện mẫu P được xác định thông qua hàm TFuzz như sau:
TFuzz: {0,1, , m} × (A
P
∪ #) → {0,1, , m}
Bổ đề 2.1 đưa ra một phương pháp tính hàm TFuzz.
2.3 Thuật toán KMP mờ
2.3.1 Otomat mờ so mẫu
Định nghĩa 2.2. Otomat mờ so mẫu là bộ
A
(P) = (A, Q, q
0
,
δ
, F),
trong đó:

,w), w
∈
A*. Nếu q = F thì
P là khúc cuối của w.
2.3.3 Thuật toán
Mục này trình bày chi tiết thuật toán tính bảng TFuzz dựa trên
mẫu P cho trước, thuật toán tìm sự xuất hiện mẫu P trong xâu đích S
và một ví dụ về so mẫu theo thuật toán KMP mờ.
2.3.4 So sánh thuật toán KMP và thuật toán KMP mờ
Trong thuật toán KMP, có lúc con trỏ j trên S giữ nguyên, còn
con trỏ trên mẫu dịch chuyển nhiều lần nên làm chậm đáng kể so với
thuật toán KMP mờ: mỗi lần nhậ
n một kí tự S
j
là một lần điều chỉnh
giá trị mờ theo otomat: λ
j
= TFuzz(λ
j – 1
,S
j
).
2.4 Thuật toán KMP–BM mờ
2.4.1 Ý tưởng của thuật toán
Thuật toán KMP–BM mờ là một cải tiến của thuật toán KMP mờ,
kết hợp với ý tưởng về bước dịch chuyển xa trên xâu đích trong pha
tìm kiếm như thuật toán BM. Thuật toán sử dụng mô hình otomat mờ
với trạng thái mờ hai chiều, cho phép tận dụng thông tin của mẫu
nhiều hơn, đem lại tốc độ thực tế
cao hơn so với thuật toán KMP mờ.

m, 1
≤
n2
≤
k}
− n1 gọi là độ mờ tại vị trí đang xét,
− n2 gọi là bước nhảy tiếp theo vị trí đang xét.
+ q
0
là trạng thái khởi đầu, q
0
= (0, 1),
+ F là trạng thái kết thúc, F = (m, 1),
+ Hàm chuyển
δ
: Q
×
A
k

→
Q,
(q, w)
↦
q’=
δ
(q, w).
Với q = (n1, n2) thì q’ = (n1’, n2’) được xác định như sau:
Nếu n2 > 1 thì đặt n1 = 0,
− Tính n1’ = TFuzz(n1, w

hai xâu theo một mô hình lỗi nào đó. Các mô hình lỗi kinh điển chỉ
hiệu quả khi có những sai khác về mặt chính tả, nhưng trong nhiều
tình huống, những k
ĩ thuật này chưa đáp ứng đầy đủ yêu cầu thực tế.
Với mẫu P và xâu đích S, độ gần tựa ngữ nghĩa do luận án đề xuất
được tổng hợp từ tần suất xuất hiện các khúc con của P trong S, còn
độ bảo toàn thứ tự xuất hiện các kí tự được tính toán dựa trên sự bảo
toàn thứ tự của từng bộ phận của P trong S. Do độ t
ương tự xác định
theo hai cách này phản ánh được độ gần gũi ngữ nghĩa giữa hai xâu,
xét về mặt thống kê, nên được gọi là độ tương tự tựa ngữ nghĩa.
Một mô hình lỗi kinh điển là dựa vào độ dài khúc con chung dài
nhất, song với tiếp cận otomat mờ của luận án sẽ đem lại một thuật
toán nhanh, đặc biệt hiệu quả khi cần so mẫu P với nhiều xâu S.
3.2 Bài toán đo độ tương tự giữa hai xâu
Bài toán: Cho xâu mẫu P độ dài m và xâu đích S độ dài n. Xác định
độ tương tự giữa hai xâu P và S.
3.3 Độ tương tự dựa trên độ dài khúc con chung của hai xâu
3.3.1 Phát biểu bài toán
Bài toán: Cho xâu mẫu P = P
1
P
2
P
m
và xâu đích S = S
1
S
2
S

u
k
.
Quy ước pref
0
(u) = suf
0
(u) = ε (từ rỗng).
− Với hai số tự nhiên f, d, |u| ≥ d ≥ f ≥ 0, đặt u(f, d) = suf
f
(pref
d
(u)).
Quy ước u(0,d) = ε.
− Với mỗi xâu y là khúc con của u,
đặt lid(y,u) = (|y|, Min {d∈N| ∃f ≥ 0: u(f,d) = y}).
− Cho hai xâu u, v, ký hiệu lfact(v, u) là khúc cuối y dài nhất của v
mà y là khúc con nào đó của u, độ dài của xâu y như vậy được ký
hiệu là lfuz(v, u).
Với xâu P độ dài m, trên các cặp số (f,d), với m ≥ d ≥ f ≥ 0, xác
định một quan hệ tương đương: (f,d) tương đương với (f’,d’) nếu
P(f,d) = P(f’,d’). Cặp (f,d) được gọi là có nghĩa (với P) nế
u (f,d) là
cặp có d nhỏ nhất trong lớp, nghĩa là có khúc con y của P sao cho
lid(y, P) = (f,d).
3.3.2 Otomat so mẫu: mô hình và cơ sở toán học
Định nghĩa 3.1 trình bày về khái niệm otomat trạng thái các khúc
con của P, có vai trò bổ trợ làm rõ bản chất của otomat mờ cơ sở của
thuật toán. Với mỗi chữ a, mỗi khúc con u của P, hàm chuyển T cho
bởi: T(u,a) := lfact(ua, P).

một cách truyền thống theo đệ quy:
TFuzz((f,d),
ε
) = (f,d), (n = 0)
TFuzz((f,d), w) = TFuzz(TFuzz((f,d),w(n–1)),w
n
), (n > 0).
+ Do bản chất thuật toán, otomat này không xét đến tập kết thúc.
Định lý 3.2. Cho v là xâu tuỳ ý, TFuzz((0,0),v) = lid(lfact(v,P),P).
3.3.3 Thuật toán
Mục này trình bày thuật toán tìm khúc con chung dài nhất của
mẫu P và xâu đích S dựa trên otomat mờ được xây dựng từ trước.
3.3.4 Một phương pháp tính hàm chuyển trạng thái TFuzz
Mục này trình bày một phương pháp quy nạp để tính hàm chuyển
trạng thái TFuzz của otomat mờ trong Định nghĩa 3.2 và cấu trúc dữ
liệu phù hợp cho TFuzz. Tính đúng đắ
n của phương pháp được đảm
bảo bởi các định nghĩa và tính chất sẽ giới thiệu ở Phụ lục A.
3.3.5 Đánh giá thuật toán
Tổng thời gian tìm kiếm là n + T
pr
, trong đó n là thời gian sánh
mẫu P với xâu đích S; T
pr
là thời gian tiền xử lí mẫu P cỡ O(|A
P
| m
3
).
Thuật toán này đặc biệt hiệu quả khi cần so sánh một mẫu P với

t
tkPSH
1
*),(
, với k là số khối độ dài t của
mẫu P mà xuất hiện trong xâu đích S.
+ Gọi M là giá trị cực đại của hàm giá ( khi S = P),
M =
∑
=
+−=
m
t
ttmPPH
1
*)1(),(
(3.1)
+ Độ gần của S so với P là tỷ số H/M.
Thuật toán 3.2. Tính độ gần tựa ngữ nghĩa của xâu S so với mẫu P.
M =
∑
=
+−=
m
t
ttmPPH
1
*)1(),(
;
H := 0;

3.4.5 Otomat mờ và thuật toán tính độ gần mờ
Gọi otomat cải tiến là A
1
(P), trạng thái là bộ ba (f,d,k), với f, d
được xác định như trong otomat ở Mục 3.3, k là tần suất xuất hiện
trong mẫu P của khúc con đặc trưng bởi P(f,d). Trạng thái khởi đầu
q
0
= (0,0,0), không có trạng thái kết thúc, hàm chuyển TF xác định
bởi TF((f,d,k), a) = (f’,d’,k’), với f’,d’ được tính theo hàm TFuzz:
(f’,d’) = TFuzz((f,d),a). Tại mỗi vị trí j khi duyệt trên S từ trái sang
phải, giả sử trạng thái mờ tính được là (f,d,k). Điều này có nghĩa trên 17
S đã xuất hiện k khối độ dài f của P có nội dung giống nhau và giống
với khối (f,d – f +1). Nếu dùng thuật toán sơ bộ, mỗi khi xét một trong
k khối giống nhau đó, hàm giá được tăng bởi công thức H := H + f,
với thuật toán sử dụng otomat mờ, khi xét đến kí tự S
j
, thay cho k lần
tăng, hàm giá chỉ tăng một lần bởi công thức: H := H + k * f (3.3)
Hiệu quả của thuật toán này còn cao hơn nữa do: khi trạng thái
mờ tại vị trí S
j
là (f,d,k), không chỉ báo hiệu đã xuất hiện k khối độ
dài f của P thuộc lớp tương đương [f,d – f + 1] mà còn báo hiệu các
khối (f – 1, d – f + 2), (f – 2, d – f + 3), ,(1, d) cũng có mặt trong S.
Vì trong thuật toán tính độ gần giữa hai xâu P và S, ta chỉ xét xem
khối (t,i) của P có xuất hiện trong S hay không nên để đảm bảo công

Ta đưa ra khái niệm thuận thế và độ bảo toàn thứ tự bằng chính số 18
thuận thế của S so với mẫu P.
3.5.2 Khái niệm thuận thế
Định nghĩa 3.5.
Phép nhúng bảo toàn thứ tự từ một khúc con S
j
S
j +1
S
j + k

của S vào khúc con P
i
P
i + 1
P
i + t
của P là một ánh xạ
ϕ
tăng sao cho:
+
ϕ
(j) = i <
ϕ
(j + 1) < <
ϕ
(j + k)

S
j + k
của S vào khúc
con P
i
P
i + 1
P
m
của P. Khi đó ta nói độ dài của khúc được xét
này là k.
+ Khúc con bỏ qua cấp i kể từ vị trí j là khúc con S
j
S
j + 1
S
j + k
,
trong đó k là số nguyên lớn nhất sao cho S
q

≠
P
i
,
∀
q = j, j + 1, ,
j + k và bằng
ε
nếu S

(A
i
,Q
i
,q
i0
, q
if
,
δ
i
), trong đó: 19
+ A
i
là bảng chữ, A
i
= A
P

∪
{#}, A
P
là

tập các chữ cái thuộc P
ref(i – 1)



hoặc q = m ta có:
–
δ
i
(q, P
i
) = i
–
δ
i
(q,a) = i – 1, với
∀
a
∈
P
ref(i – 1)
và a
≠
P
i
Với i – 1 < q < m, ta có:
q, nếu a = #
δ
i
(q,a) =
j,
nếu tồn tại j nhỏ nhất, m
≥
j > q sao

,s
2
, s
m – 1
),a) = (δ
1
(s
1
,a), δ
2
(s
2
,a), ,δ
m – 1
(s
m – 1
,a))
Trạng thái khởi đầu là (q
10
, q
20
, ,q
m – 1,0
) = (0, 1, , m – 1). Duyệt
trên xâu đích S từ trái sang phải, mỗi lần một kí tự. Hàm ra T
i
(j), i =
1, 2, , m – 1, cho biết số thuận thế cấp i, tính đến vị trí thứ j trên xâu
S và như vậy tổng số thuận thế các cấp là Σ
i
Hình 4.1. Hình 4.2.
Phương pháp so mẫu không giải mã được đưa ra nhằm đảm bảo
an toàn thông tin khi tìm kiếm trên văn bản mã hoá. Ý tưởng chung
của các phương pháp so mẫu không giải mã là sử dụng kết hợp
otomat đoán nhận từ mã và otomat mờ so mẫu.
4.2 So mẫu trên văn bản nén
Ý tưởng cơ bản để so mẫu trên văn bản nén là đọc tuần tự trên tệp 21
nén và mở nén một số mã nén, lưu kết quả giải nén cục bộ vào một
vùng đệm và áp dụng thuật toán so mẫu theo tiếp cận mờ trên vùng
đệm này. Cấu trúc dữ liệu được lựa chọn cho vùng đệm là một hàng
đợi vòng tròn (circular queue) dựa trên một mảng kí tự có độ dài
buf_len. Hàng đợi vòng tròn được xác định bởi hai con trỏ: F trỏ vào
đầu lấy ra một phần tử trong queue, B trỏ vào đầu đưa một phần tử

vào hàng đợi. Phép định vị con trỏ T trên hàng đợi sau bước nhảy
qua k phần tử được xác định theo chiều kim đồng hồ bởi công thức:
⎩
⎨
⎧
>+−+
≤++
=⊕
lenbufkTlenbufkT
lenbufkTkT
kT

y, được xác định bởi một đường đi p có nhãn w từ x
B

đến y
B
không

qua các đỉnh trung gian thuộc X, p:x
B
y
B
như
sau: x.
p
y = xw.
Ví dụ 4.2. Cho B
3
, ngôn ngữ X = {000, 010, 101, 111}. Giả sử có
ánh xạ mã: a → 000, b → 010, c → 111, d →101 (Hình 4.6). 22
Tích abd được mã hóa bởi đường đi từ đỉnh 000 qua 001, 010 đến
101 là: abd → 000101. Việc giải mã được tiến hành bằng việc duyệt
theo một con đường xác định bởi các nhãn.

Hình 4.6. Đồ thị xác định mã đàn hồi
4.3.3 So mẫu trên văn bản mã hóa bởi mã đàn hồi
Nhờ tiếp cận otomat mờ, thuật toán so mẫu trên văn bản mã hóa
bởi mã đàn hồi không cần giải mã mà vẫn thống kê được tần suất