Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 06.11.2003, 18:16   #1
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default Нетривиальная задача

Дана строка типа:

AAAAAAAAAABABABCCD

Нужно упаковать повторяющиеся подстроки так чтобы кол-во символов в результирующей строке было минимальным.

Т.е. если на входе : AAAAAAAAAABABABCCD
то на выходе должно быть : 9(A)3(AB)CCD

Обратите внимание на то, что если бы CCD превратилось в
2(C)D то результирующая строка стала бы длинее ( т.е. скобки и числа в результирующей строке тоже считаются символами ).

Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))


Что скажете ?
Boyov.
Reply With Quote
Old 06.11.2003, 18:51   #2
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 4
Default

A zazipovat` slabo ? LZW compressiey
Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii.
Reply With Quote
Old 06.11.2003, 19:42   #3
Banned
 
DaNYer's Avatar
 
Join Date: 10 2002
Location: Brooklyn, New York
Age: 39
Posts: 3,760
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

u vas kursovaya da?

p.s. Vas ne Armen sluchaino zvat'?
Reply With Quote
Old 06.11.2003, 20:01   #4
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default

Quote:
Originally posted by DaNYer
u vas kursovaya da?

p.s. Vas ne Armen sluchaino zvat'?
Не, Карен, у нас олимпиада
И зовут его Артемом
Reply With Quote
Old 06.11.2003, 23:01   #5
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by W_z_rd
A zazipovat` slabo ? LZW compressiey
Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii.

lzw ne katit t.k. zdes' buffery mogut byt' wlozhennymi - wot eto primer .....
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))


nu wo wsjakom sluchae ne katit w original'nom wariante, a tak -mozhno peredelat'
Reply With Quote
Old 06.11.2003, 23:16   #6
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally posted by W_z_rd
A zazipovat` slabo ? LZW compressiey .
А смысл ???

LZW это конечно хорошо (http://dogma.net/markn/articles/lzw/lzw.htm), а ещё существует туева хуча всяких других способов "compression"-а (md5 например http://www.faqs.org/rfcs/rfc1321.html) ,но я не думаю что эта задача вот так просто решится с помощю какого-то конкретного (известого) алгоритма. Correct me in case I'm wrong. Буду very very happy если я неправ


All the best
Boyov.
Reply With Quote
Old 07.11.2003, 02:13   #7
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 4
Default

Quote:
Originally posted by nm
lzw ne katit t.k. zdes' buffery mogut byt' wlozhennymi - wot eto primer .....
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))


nu wo wsjakom sluchae ne katit w original'nom wariante, a tak -mozhno peredelat'
So vlozhennymi ciklami interesnee. Konechno, ya ne imel vvidu LZW v original`nom variante. Eto bila shutka s izryadnoy doley pravdi: mozhno ispolzovat` idei lezhashie v osnove LZW i podobnix kompressiy.



To Boyov:

MD5 eto hash-funkciya (message digest), a ne compressiya. No eto nevazhno. Ne, ti prav, gotovix sposobov netu, no sm. vishe.
__________________
Женщин не надо понимать, их надо любить!
Reply With Quote
Old 07.11.2003, 08:07   #8
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

Quote:
Originally posted by Boyov
А смысл ???

LZW это конечно хорошо (http://dogma.net/markn/articles/lzw/lzw.htm), а ещё существует туева хуча всяких других способов "compression"-а (md5 например http://www.faqs.org/rfcs/rfc1321.html)...
s kakix por MD5 stal "compression" -om ?
Reply With Quote
Old 07.11.2003, 08:19   #9
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

eta zadacha - PCX-compression.
t.e. graficheskij format PCX.

a smysl topika ya ne ponyal - algoritm napisat'?
Reply With Quote
Old 07.11.2003, 12:32   #10
инсценирующи
 
[ Xelgen ]'s Avatar
 
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 31
Posts: 4,327
Downloads: 22
Uploads: 0
Reputation: 193 | 4
Default

Quote:
Originally posted by Greco El
a smysl topika ya ne ponyal - algoritm napisat'?
если не написать, то хотя бы описать
Reply With Quote
Old 07.11.2003, 13:21   #11
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally posted by Greco El
s kakix por MD5 stal "compression" -om ?
Народ ,пардон, но вы меня не так поняли . It was a Joke . Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.

O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.


Boyov
Reply With Quote
Old 07.11.2003, 13:51   #12
Академик
 
W_z_rd's Avatar
 
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 45
Posts: 4,854
Downloads: 1
Uploads: 0
Reputation: 225 | 4
Default

Quote:
Originally posted by Boyov
Народ ,пардон, но вы меня не так поняли . It was a Joke . Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.

O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.


Boyov

Shyutnik !
Udachi !
Reply With Quote
Old 07.11.2003, 15:18   #13
Бакалавр
 
Join Date: 03 2002
Location: Detroit, MI, USA
Posts: 482
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Re: Нетривиальная задача

Quote:
Originally posted by Boyov
Дана строка типа:

AAAAAAAAAABABABCCD

Нужно упаковать повторяющиеся подстроки так чтобы кол-во символов в результирующей строке было минимальным.

Т.е. если на входе : AAAAAAAAAABABABCCD
то на выходе должно быть : 9(A)3(AB)CCD

Обратите внимание на то, что если бы CCD превратилось в
2(C)D то результирующая строка стала бы длинее ( т.е. скобки и числа в результирующей строке тоже считаются символами ).

Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))


Что скажете ?
Boyov.
A esli primenit' vesovuyu funkciyu? Tipa
F(X) = number of elements in compressed x. Sootvetstvenno, iskat' min x.

Naprimer F(CCD) = 4, sledovatel'no, CCD ne kompressiruem. F(AAAAAAAAAA) = 4 - kompressiruem.
Reply With Quote
Old 08.11.2003, 18:02   #14
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally posted by Boyov
Народ ,пардон, но вы меня не так поняли :). It was a Joke ;). Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.

O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.


Boyov
kstati naschet LZ - esli ja prawil'no ponimaju, tebe nuzhno na Ziv-e gonjat' LZ algoritm, rekursiwno ....
chtob i w Ziv-e najti powtorjajushiesja stroki ...
a washe eto wse ne effektiwno :)))

kstati kakie ogranichenija es't ? na ozu, wremja wypolnenija ?
Reply With Quote
Old 08.11.2003, 19:00   #15
4294967296
 
Boyov's Avatar
 
Join Date: 03 2002
Location: /proc/1
Age: 33
Posts: 379
Downloads: 4
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally posted by nm
a washe eto wse ne effektiwno ))
?
A chto sobstvenno effectivno ???

Quote:
Originally posted by nm
kstati kakie ogranichenija es't ? na ozu, wremja wypolnenija ? [/B]
Vot original'naya zadacha
http://neerc.ifmo.ru/past/2002/problems/folding.htm

Tam ob ogranicheniyax vaabshe ne skazano, (eto otnositsya i ko vsem ostal'nim zadacham 2002 goda) ,navernoe nado polagat' chto ix net .
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 19:55.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.