Нетривиальная задача

Boyov · Nov 6, 2003, 18:16

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

AAAAAAAAAABABABCCD

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

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

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

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

Что скажете

?
Boyov.

W_z_rd · Nov 6, 2003, 18:51

A zazipovat` slabo ?

LZW compressiey

Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii.

DaNYer · Nov 6, 2003, 19:42

u vas kursovaya da?

p.s. Vas ne Armen sluchaino zvat'?

[ Xelgen ] · Nov 6, 2003, 20:01

Quote:

Originally posted by DaNYer
u vas kursovaya da?

p.s. Vas ne Armen sluchaino zvat'?

Не, Карен, у нас олимпиада

И зовут его Артемом

nm · Nov 6, 2003, 23:01

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'

Boyov · Nov 6, 2003, 23:16

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.

W_z_rd · Nov 7, 2003, 02:13

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.

greka · Nov 7, 2003, 08:07

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 ?

greka · Nov 7, 2003, 08:19

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

a smysl topika ya ne ponyal - algoritm napisat'?

[ Xelgen ] · Nov 7, 2003, 12:32

Quote:

Originally posted by Greco El
a smysl topika ya ne ponyal - algoritm napisat'?

если не написать, то хотя бы описать

Boyov · Nov 7, 2003, 13:21

Quote:

Originally posted by Greco El
s kakix por MD5 stal "compression" -om ?

Народ ,пардон, но вы меня не так поняли

. It was a Joke

. Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.

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

Boyov

W_z_rd · Nov 7, 2003, 13:51

Quote:

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

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

Boyov

Shyutnik !

Udachi !

Tumanyan · Nov 7, 2003, 15:18

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.

nm · Nov 8, 2003, 18:02

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 ?

Boyov · Nov 8, 2003, 19:00

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

.

Nov 6, 2003, 18:16	#1
Boyov 4294967296 Join Date: Mar 2002 Location: /proc/1 Posts: 378 Rep Power: 7 Reputation: 10	Нетривиальная задача Дана строка типа: AAAAAAAAAABABABCCD Нужно упаковать повторяющиеся подстроки так чтобы кол-во символов в результирующей строке было минимальным. Т.е. если на входе : AAAAAAAAAABABABCCD то на выходе должно быть : 9(A)3(AB)CCD Обратите внимание на то, что если бы CCD превратилось в 2(C)D то результирующая строка стала бы длинее ( т.е. скобки и числа в результирующей строке тоже считаются символами ). Вот ещё один пример: Вход: NEERCYESYESYESNEERCYESYESYES Выход: 2(NEERC3(YES)) Что скажете ? Boyov. __________________ Free your mind and your OS will follow

Nov 6, 2003, 18:51	#2
W_z_rd Академик Join Date: Aug 2002 Location: Yerevan, Armenia Posts: 4,781 Rep Power: 7 Reputation: 191	A zazipovat` slabo ? LZW compressiey Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii. __________________ Женщин не надо понимать, их надо любить!

Nov 7, 2003, 08:19	#9
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	eta zadacha - PCX-compression. t.e. graficheskij format PCX. a smysl topika ya ne ponyal - algoritm napisat'? __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Nov 6, 2003, 19:42	#3
DaNYer Banned Join Date: Oct 2002 Location: Brooklyn, New York Posts: 3,760 Rep Power: 0 Reputation: 10	u vas kursovaya da? p.s. Vas ne Armen sluchaino zvat'?