PDA

View Full Version : Thuat toan cho bai chuoi thuan nhat



songok
02-04-2005, 19:29
Cho mot chuoi thuan nhat la chuoi toan chu cai tieng Anh, vi du
XCAABAABAABDDA..
yeu cau : rut gon chuoi nay ve dang XC(AAB)3D2A..
Co bac nao co thuat toan cho bai nay hong ?

bete
02-04-2005, 22:52
Thân gửi songok: nếu có hơn 1 cách làm thì mình chọn cái nào !?
Ví dụ: aabcabc => a2bcabc hoặc a(abc)2

-thân

real_time
02-04-2005, 23:31
Các bạn thân mến đây chính là thuật toán nén runlength chịu khó search trên mạng từ khóa runlength là ra tất.

bete
02-04-2005, 23:39
Thân gửi real_time: tui nghĩ bài này không đơn giản như run_length "thông thường" đâu
Ví dụ nếu mình có aabcdeabcdeabcde thì

1) run_length "thông thường" sẽ cho ra a2bcdeabcdeabcde

2) còn bài của songok thì sẽ cho ra: a(abcde)3 => có thể coi như run_length "cao cấp" chứ không còn là run_length "thông thường"

Tui nghĩ run_length thông thường thì làm O(N) là được.
Còn bài này làm O(N^2) thì chắc cũng phải coi rất kỹ (không chừng lên tới O(N^3) hay O(N^4) luôn:))

(tui có 1 số ý, nhưng muốn chờ phe ta vô bàn bạc cho vui)

(không biết tìm trên mạng có ra cái run_length "cao cấp" này hay không; mà nếu có thì tui nghĩ cũng nên thử tự giải trước và nếu mình thì lục trên mạng :))

-thân

real_time
03-04-2005, 00:00
tôi cũng đã đọc kỹ hơn thấy nó đúng là phức tạp hơn nhưng dự đoán có thể là runlength+LZW? bởi trong này có thấy sự lập từ điển rồi sử dụng runlength để lưu? rất phức tạp đó chứ ko phải bình thường. bete có ý gì đưa ra anh em nghiên cứu thử xem sao? tôi có mỗi một tối kiến đó thôi anh em thử xem có được ko?

songok
03-04-2005, 19:24
theo toi thi chuoi : aabcabc nen chon a(abc)2 vi no duoc rut gon hon la chuoi kia
That tinh ma noi tui khong biet cac thuat toan ma cac ban da neu ra, tui chi suy nghi theo cach duyet chuoi, Quy hoach dong duoc khogn ?

bete
04-04-2005, 02:23
LZW cũng là 1 hướng.
Nếu qui hoạch động được thì tốt quá đi chứ (ráng kìm độ phức tạp chừng O(N^3) trở xuống)

Tui định chặt chuỗi đã cho thành 3 khúc: L, M & R thỏa M là 1 chuỗi con có thể phân tích thành 1 chuỗi lặp (M=T^k (k>=2)). Sau đó đệ qui cho L, T & R (đệ qui là ý tưởng; có hàm đệ qui tốt rồi thì có thể thử chuyển đổi sang QHD).

Một vài ví dụ về chặt chuỗi:

aabcabc = a|abcabc| (L=a; M=abcabc (T=abc); R='')

aababa = aa|baba| (L=aa; M=baba (T=ba); R='')

ababaa = |abab|aa (L=''; M=abab (T=ab); R=aa)

cdacdabcdabcda = cdacda|bcdabcda| (L=cdacda; M=bcdabcd (T=bcda); R='')
hoặc cdacd|abcdabcd|a (L=cdacd; M=abcdabc (T=abcd); R=a)

abcdabcdacdacd = |abcdabcd|acdacd (L=''; M=abcdabcd (T=abcd); R=acdacd)
hoặc a|bcdabcda|cdacd (L=a; M=bcdabcda (T=bcda); R=cdacd)

ababababab = |ababababab| (L=''; M=ababababa (T=ab); R='')

abcde = |abcde| (M=a hoặc b hoặc c hoặc d hoặc e)

caaaaaaaabab = c|aaaaaaaa|bab (L=c; M=aaaaaaaa; R=bab)
hoặc caaaaaaa|abab (L=c; M=aaaaaaa; R=abab)

-thân

StarGhost
19-04-2005, 13:18
Bạn songok có thể cho biết chi tiết hơn về đề bài được không: dấu ngoặc được dùng như thế nào, tại sao có lúc trước số 2 lại có ngoặc mà có lúc không? Theo bạn như thế nào được gọi là rút gọn hơn, có phải là dựa vào độ dài của string không, độ dài đó có kể cả số và ngoặc hay không?

Theo tôi, bài này đơn giản chỉ là qui hoạch động O(n^2) thôi

songok
19-04-2005, 19:19
De bai nay nhu sau : Cho mot chuoi ky tu thuan nhat, chi gom cac ky tu A..Z, Tu chuoi do ta rut gon chuoi do ( neu co 2 chuoi nay do giong nhau thi coi nhu la mot va de chuoi do trong ngoac roi cho biet so lan lap cua chuoi do.
Vi du nhu trong chuoi tren aabcabc neu ta rut gon la a2bcabc thi khong toi uu bang cach rut gon a(abc)2.

That ra bai nay la de thi olimpic 30/4 lop 10 cua truong Nguyen Thuong Hien

StarGhost
19-04-2005, 20:26
Vi du nhu trong chuoi tren aabcabc neu ta rut gon la a2bcabc thi khong toi uu bang cach rut gon a(abc)2.


Quan trọng là tại sao bạn lại cho rằng a(abc)2 thì tối ưu hơn a2bcabc vì tôi thấy độ dài của 2 cái như nhau đấy chứ, thậm chí bằng luôn chuỗi ban đầu, hay là ý bạn là cái nào rút gọn được nhiều hơn thì tối ưu hơn?

bete
20-04-2005, 04:39
Tui nghĩ như vầy

1) mình coi như là có 1 hàm ĐộDài: lấy vô 1 chuỗi và trả về độ dài.

Có nhiều cách lựa chọn cài đặt cho ĐộDài:

* trả về số ký tự trong chuỗi: a(abc)10=> 8
* hoặc trả về số ký tự trong chuỗi nhưng bỏ qua '(' và ')': a(abc)10 => 6
* hoặc trả về số ký tự trong chuỗi nhưng bỏ qua '(' và ')', hơn nữa số lần lặp tính là 1 kí tự: a(abc)10 => 5
......................

2) cài đặt hàm ĐôDài ra sao không quan trọng. Quan trọng là cho trước 1 hàm ĐộDài nào đó (tương đối "có lý" 1 chút): cách giải của mình sẽ trả về 1 cách biểu diễn "ngắn nhứt" (nếu có nhiều hơn 1 cách thì trả về cách nào cũng được, ngon lành hơn thì trả về hết tất cả các cách)

Bài này tui có nghĩ sơ qua rồi để đó, chờ phe ta có ai hứng thú thì bàn tiếp.
StarGhost thử cho biết cách của bạn ra sao để tui được học hỏi thêm. Tui nghĩ QHD mảng 2 chiều thì chưa chắc là O(n^2) đâu, phải không: nếu điền 1 ô cần O(1) thì thiệt sự là O(n^2), nhưng nếu điền 1 ô lại cần O(n) thì sẽ lên tới O(n^3) lận !?

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

-thân

tlb
21-04-2005, 08:56
bài này sử dụng kỹ thuật 2 pha, bài này là đề thi tỉnh năm tui 11, ko biết giải thế là ngủm năm ấy. huhuuhuh.