Kompresja kodu HTML

0

Problem jest następujący: uporządkować kod HTML, a konkretniej różnokolorowy tekst, tak aby objętość kodu była jak najmniejsza.

Czyli problem polega na tym, że zmiany koloru tekstu wymagają użycia znaczników <FONT color="...">tekst</FONT>
Jeżeli mamy n fragmentów różnego koloru (mam na myśli zmiany między sąsiadującymi fragmentami) to możemy zapisać to w postaci prostej sekwencji:
<FONT color="...">A</FONT><FONT color="...">B</FONT><FONT color="...">C</FONT>...<FONT color="...">Z</FONT>

Jednak kod taki możnaby skompresować, gdyby zamykać znaczniki </FONT> tylko w odpowiednich miejscach. Czyli gdyby pierwszy kolor i ostatni byłyby takie same, to mielibyśmy kod mniej więcej taki:
<FONT color="kolor1">A<FONT color="...">B</FONT><FONT color="...">C</FONT>...<FONT color="...">Y</FONT>Z</FONT>

Możnaby zastosować ten trik również wewnątrz, ale nie wiem jak wygenerować najbardziej optymalną kombinację.
Do tego dochodzi też problem, gdy kolory (oznaczone tu literkami) ukłądają się mniej więcej tak:
A B C... A B
można zrobić <FONT COLOR="A"><FONT COLOR="B">tekst</FONT><FONT COLOR="...">...</FONT></FONT><FONT COLOR="B">tekst</FONT>
lub <FONT COLOR="A">tekst</FONT><FONT COLOR="B">tekst<FONT COLOR="...">...</FONT>tekst</FONT>

Mam nadzieję, że rozumiecie mniej więcej, co mam na myśli.
Za wszystkie pomysły i sugestie będę bardzo wdzięczny. :)

0

nie rozumiem o co chodzi - ale wydaje mi się że wystarczy żeby kod php czy coś policzyło który kolor się najczęściej powtarza i wszystko nim objął i ignorował po prostu zmianę na ten kolor - ale można jeszcze bardziej to uprościć

0

no to oczywiste, ale to jest tylko jeden kolor
a mi chodzi o optymalny rozkład zmiany kolorów w sekwencji ;P

aha, i tu nie chodzi o PHP, bo kod HTML jest generowany przez program, tylko chodzi o to, zeby zajmowal jak najmniej

0

Użyć css ;)

0
Dryobates napisał(a)

Użyć css ;)
To zamiast <FONT COLOR="A"> będzie lub - na to samo wychodzi.

0

o wykorzystaniu css-a, żeby stworzyć krótsze znaczniki o określonym kolorze już myślałem, ale tu chodzi o algorytm, który by dał optymalne ułożenie znaczników otwierających i zamykających.

Enybady?

0
Marooned napisał(a)
Dryobates napisał(a)

Użyć css ;)
To zamiast <FONT COLOR="A"> będzie lub - na to samo wychodzi.

Koloru jako jeden znak nie zapiszesz ;)

Ale rozumiem, że tutaj i tak nie o to chodzi. Niestety jakoś nie mam ochoty myśleć nad algorytmem.
Pewnie zaczałbym od małego parsowania i stworzenia drzewka, a później w sąsiadujących gałęziach zamieniałbym wspólne elementy na 1 font.
To załatwiałoby realizację pierwszego pomysłu. Jeśli zaś chodzi o umieszczanie font w font, to zapewne należałoby sprawdzać gałęzie od zewnątrz idąc od prawej i lewej i jeżeli znalazłyby się 2 takie same to pogrupować. Nie bardzo wiem jak to przekazać słowami. Spróbuję symbolicznie zapisać:

Mamy drzewko tylko z liśćmi:

<ka>A</ka> <kb>B</kb> <kc>C</kc> <ka>A</ka> <kb>B</kb> Najpierw wszystko "otaczamy" przez A <ka>A <kb>B</kb> <kc>C</kc> <ka>A</ka> <kb>B</kb></ka>. Co oczywiście nic nam nie zmienia. Następnie wewnątrz tego znacznika odrzucamy kolejne, nie pasujące nam znaczniki (wyciągamy "przed nawias") i redukujemy otoczkę przy drugim A: <ka>A <kb>B</kb> <kc>C</kc> A</ka><kb>B</kb>. Należałoby postępować tak dalej w głąb "nawiasów". Oczywiście taki sam rezultat (w tym przypadku) dałoby sprawdzanie od prawej. W innych mogłoby być lepiej z prawej innych z lewej. Należałoby zrobić jakieś zliczanie i dopasować.
0

faktycznie, to jest jakies rozwiazanie :)

ja myślałem, że możnaby jakąś funkcję wywołać dla całej sekwencji, następnie rekurencyjnie dla każdego zawartego w sekwencji przedziału wyznaczonego przez dwa wystąpienia tego samego koloru i tak dalej wgłąb :)

Dla ciągu kolorów:
ABCDADCBA
możemy utworzyć kod najdłuższy:
<A><B><C><D><A><D><C><B><A> - 18 znaczników
"<" - otwarcie znacznika
">" - zamknięcie znacznika
lub najkrótszy:
<A<B<C<D<A>D>C>B>A> - 10 znaczników
gdyby po pierwszym "D" zejść na spód "kopca":
<A<B<C<D>>>A<D><C><B>A>
równoważne temu:
<A<B><C><D>A<D><C><B>A> - 14 znaczników
krótsze od pierwszej wersji, ale nie najlepsze

teraz rozważając przykład z "C" w środku:
ABCDCDCBA
mamy: najdłuższy 18 znaczników
najkrótszy:
<A<B<C<D<C>D>C>B>A> - 10 znaczników
który nie jest gorszy wcale od sposobu z zejściem po "D" do poziomu "C":
<A<B<C<D>C<D>C>B>A> - 10 znaczników

czyli jesli tworze przedział np. dla "A", to "A" w środku mnie nie interesują
czy to dobre rozumowanie?
pomóżcie, bo coś zaczyna mi świtać :)

algorytm powinien zwrócić tablicę n-elementową, gdzie:
n - liczba pól tablicy kolorów
możliwe wartości:
0 - nie stawiaj znacznika
1 - znacznik otwierający
2 - znacznik zamykający
3 - znacznik zamykający i otwierający

wtedy dla ciągu kolorów:
AABCA
mielibyśmy tablicę wynikową:
10132
ostatnie n+1 pole byłoby równe 2, bo znacznik na końcu trzebaby zamknąć

0

Po wszelkich próbach doszedłem do wniosku, że algorytm Dryo jest najbardziej optymalny (czy tak? :> )
pozostaje teraz tylko zaimplementować, ale może sobie poradzę :)
dzięki wielkie!

0

Dzięki za pomoc, po długiej walce napisałem rekurencyjną funkcję porządkującą kod optymalnie :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0