xin chỉ giáo về Boyer-Moore

[Xmen]

Chào các bác, tui đã nắm thuật toán, các nguyên tắc Bad char và Good Suffix nhưng vẫn còn vấn đề với thuật toán này tí xíu, mong các bác chỉ giáo
Vì cái tui hỏi nó hơi chi tiết, các bác vui lòng mở trang http://www-igm.univ-mlv.fr/~lecroq/string/node14.html , ở phần cuối , nó define hai cái:
Co(I,s) và Cs(I,s). Theo như định nghĩa của nó thì hai cái này không có trị trả về (chỉ là điều kiện).
Thế nhưng dòng dưới lại gán:
bmGs[i+1]=min{s>0 : Cs(i, s) and Co(i, s) hold} , nghĩa là gì, có phải tìm min của hai trị trả về s của hai hàm Cs, Co, rồi gán cho bmGs[i+1]? mà nếu làm như vậy thì kết quả trong cái The Example (cuối trang, sau C code) tại sao lại ra như vậy.
Mong các bác chỉ giáo, xin cảm ơn.

[bete]

Thân gửi Xmen:

1) Co(I,s) và Cs(I,s): 2 điều kiện => lượng giá thành true hoặc false

2) bmGs[i+1]=min{s>0 : Cs(i, s) and Co(i, s) hold}
=> bmGs[i+1]=min{ s: s>0 và cả Cs(i, s) lẫn Co(i, s) là true }
(trong các s thỏa (s>0 và cả Cs(i, s) lẫn Co(i, s) là true) => tìm s nhỏ nhứt (tìm min))

-thân

[Xmen]

Cám ơn bác nhiều , bete ! tui hiểu thêm được nhiều điều từ cái tip của bác.

[binary_c2]

Chà chà, chắc bác đang học lớp CTDL trường KHTN của thầy Tuấn phải không ? hehê, thứ sáu lên lớp nhận mặt cái coi.
Tui cũng đang đau đầu về 2 "ông nội" B và M này đây.
Boyer-Moore thì tui thấy OK rồi, nhưng phần Turbo Boyer-Moore thì tui không hiểu làm sao nó lại dịch được một khỏang Turboshift mà bảo đảm không bị bỏ sót ký tự ? Bác nào quan tâm thì giải thích giùm, cảm ơn.
http://www-igm.univ-mlv.fr/~lecroq/string/node15.html

[bete]

Thân gửi binary_c2: tui cũng thấy khó thiệt; thử coi nghen:

u: match của lần trước, u là 1 hậu tố (suffix) của pattern x
v: match của lần này, |v| < |u|, v cũng là 1 hậu tố của pattern x
uzv: là 1 hậu tố của pattern x (do vừa mới shift nên u nằm lọt trong x)
Mình vừa mới shift đi 1 khoảng là p=|zv|
Đang bị mismatch giữa b (trong text y) và a (trong pattern x), a là ký tự cuối của z
Trong text y cũng có a (đứng trước b 1 khoảng là p ký tự)

Xét các ký tự trong chuỗi uzv: nếu xét chỉ số (bắt đầu từ 0) trong pattern x thì:

x: các ký tự có chỉ số từ 0 -> (m-1)
v: (m-|v|) -> (m-1)
a: ở chỉ số (m-|v|-1): ngay trước x
z: (m-p) -> (m-|v|-1): a là ký tự cuối của z
u: (m-p-|u|) -> (m-p-1)

Vì u cũng là hậu tố của pattern x nên u cũng xuất hiện ở chỉ số (m-|u|) -> (m-1)
Gọi đây là u2 (v là hậu tố của u2)
u2 chính là bản sao của u (u: (m-p-|u|) -> (m-p-1)): bị shift đi 1 khoảng là p

Đang bị mismatch => phải shift pattern x về phía phải: ít nhất là phải match đuợc a và
b trong text y (a đứng trước b 1 khoảng là p ký tự)

Nếu mình chọn 1 ký tự nào đó trong u2 để match với b: gọi chỉ số (trong pattern x)
của ký tự này là k (k: (m-|u|-1) -> (m-1)). Khi đó a trong text y sẽ được match với
ký tự ở chỉ số (k-p) trong pattern x (vì a đứng trước b 1 khoảng là p ký tự).
Nhưng vì u2 chính là bản sao của u (u: (m-p-|u|) -> (m-p-1)) (bị shift đi 1 khoảng là p) cho nên x[k-p] chính là x[k] => x[k-p] là b (vì x[k] đang được match với b).
Như vậy không thể nào match x[k-p] với a => không thể chọn 1 ký tự nào đó trong
u2 để match với b được
=> muốn match b phải chọn 1 ký tự nằm trước u2: chỉ số lớn nhứt được phép là
(m-|u|-1).

Mình biết là đang bị mismatch giữa b trong text y với a trong pattern x; a ở chỉ số
(m-|v|-1) trong x. Bây giờ phải match b với 1 ký tự nằm trước u2: tệ lắm cũng phải là ký tự nằm ngay trươc u2: ở chỉ số (m-|u|-1) => phải dịch tiếp pattern x qua phải 1 khoảng ít nhứt là (m-|u|-1) - (m-|v|-1) = |u| - |v|: đây chính là turbo shift

Sau cùng, mình tính được 3 khoảng shift:
a) good suffix (từ Boyer-Moore thông thường)
b) bad character (từ Boyer-Moore thông thường)
c) và turbo shift
=> khoảng cần shift kế tiếp phải là MAX của 3 khoảng này

Tui thử vẽ cái hình:

text y:..........................d....a................ ...bvvvvv
pattern x (lần trước):......cuuuUuuuuu (mismatch giữa c và d)
pattern x (lần trước):......c.....avvvvv
pattern x (lần này):........cuuuUuuuuu...........avvvvv (mismatch giữa a và b)
pattern x (lần này):............(k-p)...............(k) <--- chỉ số
pattern x (lần này):........cuuuUuuuuu......uuuUuuuuu
pattern x (lần kế):................cuuuuuuuuu.....Xuuuauuuuu
(sẽ thử match X (ngay trước u2) với b nếu chọn turbo shift -- nếu turbo shift là MAX; để ý khoảng cách shift từ a đến X là (|u|-|v|))

(có gì sai sót xin các bạn chỉ giùm, cám ơn rất nhiều)

-thân

[binary_c2]

THANKS ALOT. BETE quả nhiên là quái thú. thanks bete. MIỄN BÌNH LUẬN