powered by simpleCommunicator - 2.0.18     © 2024 Programmizd 02
Map
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задание по информатике 10 класс
49 сообщений из 49, показаны все 2 страниц
Задание по информатике 10 класс
    #40116799
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дочке задали по информатике такое задание (на некоем сайте)...
Нужно сжать текст
Код: javascript
1.
A_tutor_who_tooted_the_flute_Tried_to_tutor_two_tooters_to_toot_Said_the_two_to_their_tutor,_"Is_it_harder_to_toot_Or_to_tutor_two_tooters_to_toot?"


С максимальным процентом сжатия (это оценивает сайт), заменой подстроки на символ (выделяет сайт).

Никогда с архивацией дело не имел
Как вообще такое делается?
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116802
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот как там это все выглядит...
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116819
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как-то странно выглядит Dictionary. Я-бы лупил просто отдельные слова или слоги.
- tutor
- toot
- to
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116820
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton , это только
Код: javascript
1.
Compression: 17.57%
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116823
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот так
Код: javascript
1.
2.
3.
4.
_tutor
_toot
_to
Compression: 26.35%


У нас получилось только 29%...
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116824
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А можно эти странные символы подчёркиваний просто заменить на пробелы?
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116827
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот так пока максимально получается
Код: plaintext
1.
2.
3.
4.
5.
6.
_toot
d_the_
_to
_tutor
two
ers
Compression: 29.73%
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116830
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
А можно эти странные символы подчёркиваний просто заменить на пробелы?

На пробелы не получится...
Там текст менять самому нельзя.
Можно его копировать и вставлять в правую часть. После этого он заменяется на тот символ, что программка подставляет для этой строки
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116834
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тому, выше, добавили еще
Код: plaintext
1.
2.
3.
4.
5.
6.
_toot
d_the_
_to
_tutor
two
ers
★☀☆☃☀
Получили
Код: plaintext
Compression: 31.08%
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116835
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У gzip получается 12% по этой формуле. Вроде я не ошибся.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
String s = "A_tutor_who_tooted_the_flute_Tried_to_tutor_two_tooters_to_toot_Said_the_two_to_their_tutor";
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        GZIPOutputStream gzip = new GZIPOutputStream(out);
        gzip.write(s.getBytes());
        gzip.close();
        byte[] outArray = out.toByteArray();
        assertEquals(80, outArray.length);
        assertEquals(0.12, 1.0 - (double) outArray.length / s.length(), 0.01);
        assertEquals("1f8b0800000000000000738c2f292dc9" +
                     "2f8a2fcfc88f2fc9cf2f494d892fc948" +
                     "8d4fcb292d498d0f29ca04f1f3a16a4a" +
                     "caa16a8a8ac18240667c706226440744" +
                     "12c4cc2c82a80700053c9a765b000000",
                Hex.encodeHexString(outArray));



Но по бинарю видно что на малых размерах Gzip пишет слишком много служебной инфы с головы. И в хвосте
какой-то padding забитый нулями.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116839
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
krvsa

★☀☆☃☀

Этот набор символов - из расширенных диапазонов Unicode. Там каждый символ - точно не 1 байт.
Вобщем сама идея реплейсмента одних лексем на другие - не работает на обобщённом текстовом
файле. Что делать если сам файл состоит из таких служебных. Эскейпить? Знаит еще +1 служебный
символ к каждому.

Хотя может для учебной задачи по информатике оно и катит.

Как мо мне если играть со строками то лучше уж не архивация а криптография. Шифр Виженнера...
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116841
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Хотя может для учебной задачи по информатике оно и катит.

Конечно.
Это ведь условная "замена".
mayton
Как мо мне если играть со строками то лучше уж не архивация а криптография. Шифр Виженнера...

Ты не выделывайся... Ты пальцем покажи. (с)
Т.е. как и что делать конкретно на этом примере.
Именно его и нужно сжать.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116842
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
У gzip получается 12% по этой формуле. Вроде я не ошибся.

Ты бы написал последовательность подстрок для "замены"...
А так, в программке нет никакого смысла. Дочка ведь такое не покажет училке...

Училке нужна последовательность строк и максимальный процент сжатия...
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116862
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не надо ничего училке показывать. Мне просто было интересно сравнить. И понять что gzip для коротких
строчек типа url - не годится.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116865
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А вот попробуй сжать вот такой текст этой заменой.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
     Так говорила в июле 1805 года известная Анна Павловна Шерер, фрейлина и
  приближенная  императрицы  Марии  Феодоровны,  встречая важного и  чиновного
  князя  Василия,  первого  приехавшего  на  ее вечер. Анна  Павловна  кашляла
  несколько  дней, у  нее был грипп, как она говорила (грипп  был тогда  новое
  слово, употреблявшееся только  редкими).  В записочках, разосланных  утром с
  красным лакеем, было написано без различия во всех:
       "Si vous n'avez rien de mieux à faire, M. le comte (или mon prince), et
  si la perspective de passer la soirée chez une pauvre malade ne vous effraye
  pas  trop,  je serai charmée de vous  voir chez moi  entre 7 et  10  heures.
  Annette Scherer".
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116866
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
А вот попробуй сжать вот такой текст этой заменой.

Зачем мне сжимать этот текст?
В задании текст тот, что я уже процитировал выше. Другие тексты не нужны, они никому не интересны.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116874
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
krvsa,

классический lzw должен удовлетворить
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116876
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если не менять принципиально алгоритм но дать больше контекста - то можно наверное получить выгоду.

К примеру русский текст выделяется и обрабатывается LZW с одним справочником
а французский - с другим.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
     Так говорила в июле 1805 года известная Анна Павловна Шерер, фрейлина и
  приближенная  императрицы  Марии  Феодоровны,  встречая важного и  чиновного
  князя  Василия,  первого  приехавшего  на  ее вечер. Анна  Павловна  кашляла
  несколько  дней, у  нее был грипп, как она говорила (грипп  был тогда  новое
  слово, употреблявшееся только  редкими).  В записочках, разосланных  утром с
  красным лакеем, было написано без различия во всех:
       "Si vous n'avez rien de mieux à faire, M. le comte (или mon prince), et
  si la perspective de passer la soirée chez une pauvre malade ne vous effraye
  pas  trop,  je serai charmée de vous  voir chez moi  entre 7 et  10  heures.
  Annette Scherer".
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116886
SpringMan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Чекни эти два варианта (без добавления отсебятины - она может что-то испортить)
_to_tutor_two_tooters_to_toot
_t
oo
utor
dhe
te_

и
_to_tutor_two_tooters_to_toot
_t
oo
utor
dhe
te_
t_
wh
ie
rd
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116907
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
krvsa
mayton
А вот попробуй сжать вот такой текст этой заменой.

Зачем мне сжимать этот текст?
В задании текст тот, что я уже процитировал выше. Другие тексты не нужны, они никому не интересны.

Тогда меняй весь текст на один символ.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116911
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SpringMan
Чекни эти два варианта (без добавления отсебятины - она может что-то испортить)

Отправил дочке - напишет как сжалось.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116912
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargl
классический lzw должен удовлетворить

Вот смотри... Я неумеха в этом деле... Ты видать спец.
Просто примени тот метод сам на моем примере. А результат (подстроки) покажи тут.

Так можешь?
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116923
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
krvsa
Отправил дочке - напишет как сжалось.

Ушла в школу... Будет только вечером.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116934
Фотография П.С.М.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Тогда меняй весь текст на один символ.

Самый лучший ответ )))
(если, конечно, словарь не участвует в расчете процента сжатия)
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116963
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
krvsa,

lzw дает сжатие до 99 байт (из 148), т.е 33.1%

Но там на выходе битовая строка
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116970
Фотография П.С.М.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargllzwдает сжатие до 99 байт (из 148), т.е 33.1%

А у krvsa получиось 31.08%. Думаю, на пятерку этого достаточно)))
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40116985
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargl
Но там на выходе битовая строка

Тогда зачем она мне в этом задании?
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117020
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если кодер или декодер слегка изменить - то можно получить Нормальный Алгоритм маркова.

Еще интересно из декодера получить генератор слов.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117039
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Burrows-Wheeler Transform (5 chars)

Код: sql
1.
(tAu_t,0)(rwho_,2)(ooot_,1)(dett_,3)(eh_lf,3)(_etuT,4)(deir_,4)(otu_t,2)(rtot_,3)(owt_o,4)(tsero,1)(ott__,1)(_tSoo,2)(dtia_,1)(ehw_t,2)(oot__,3)(hteir,4)(otu_t,0)
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117040
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
6 chars

Код: sql
1.
(oAtu_t,0)(orwh__,4)(ettood,5)(efh_t_,1)(_etTul,3)(deirt_,4)(ootu_t,1)(orw__t,3)(ttoeor,5)(sott__,3)(_tSaoo,3)(dihte_,4)(otw__t,1)(ohtei_,4)(rtou_t,2)



7 chars

Код: sql
1.
(rAtou_t,0)(oowht__,1)(dettho_,4)(eet_ful,1)(__deirT,1)(ottou_t,3)(orwt__t,3)(st_oero,2)(ottot_o,4)(_tdSia_,1)(oeh_w_t,3)(ohtet_i,6)
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117057
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
А вот попробуй сжать вот такой текст этой заменой.
Код: plaintext
1.
   ... у  нее был  грипп , как она говорила ( грипп   был тогда  новое
  слово...
грипп --> Cov

Надо с самого начала выяснить, какими методами, инструментами и какими "словарями" можно пользоваться, как учитывается словарь в % сжатия. Без этого гадать можно много и не достичь рез-та.
А так хафман, м.б. "_" сама по себе вкупе с уже названными и даст рекорд,
или частотность 1 2 3 4... вхождений.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117059
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хаффман - это самый начальниый уровень. И то он не действует самостоятельно а обычно добавляется
как фильтр к какому-то уже обработанному потоку. Кроме того его легко сломать. Может быть файл
с достаточно линейной гистограммой частот символов. И тут хаффмен безсилен. Хотя LZW может
сработать.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117063
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Для BWT еще padding нужен. И какой-то условный символ-филлер. Я не реализовал поэтому длина строки - меньше вышла.
А вообще это не сжатие а просто какая-то предварительная фаза подготовки символов.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117065
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здесь очевидна заведомая повторяемость. В принципе задача, уловить это, если преп сам не сказал.
Вот как словарь понимается, как цельный символ или можно 1 бит? и как он в подсчёте участвует. Вопрос,да.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117068
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
В принципе задача, уловить это, если преп сам не сказал

Училка сказала:
- Вот так выделяете часть строки и копируете в правую часть... Видите как она (часть) заменилась вот на тот символ? Вот так и меняйте. Задача - получить максимальное сжатие, оно показывается в самом низу.

Вот и все.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117077
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
Здесь очевидна заведомая повторяемость. В принципе задача, уловить это, если преп сам не сказал.
Вот как словарь понимается, как цельный символ или можно 1 бит? и как он в подсчёте участвует. Вопрос,да.

Игры со словарём можно рассматривать как забавный хак системы.
Что будет если словарь удалённый и лежит где-то в гугле?
Мы получаем такой себе Бабушкин-лайк-архиватор с супер-пупер
характеристиками.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117080
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SpringMan
Чекни эти два варианта (без добавления отсебятины - она может что-то испортить)

Дочка написала авторполучилось 17 и 12
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117081
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
П.С.М.
А у krvsa получиось 31.08%. Думаю, на пятерку этого достаточно)))

Так и вышло - дочка довольна.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117090
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А как компрессия считалась, относительная убыль длины нового текста? или доля длины нового текста?
потому что с ходу по 2-му подсчёту сразу 50% получается. Следовательно 1-й вариант тоже 50%.

Ну да и училка не сказала, в каком порядке закрашивать если хочешь _to и _too в словаре. Ну да, это для ручной раскраски. Кто-то может и не просечь. Оплошала училка.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117104
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
А как компрессия считалась, относительная убыль длины нового текста? или доля длины нового текста?

Я особо не вдавался в алгоритм расчета этого процента... Там на картинке несколько цифр - возможно на них тот расчет и опирается.

exp98
Оплошала училка.

Старшая дочь несколько лет байты в килобайты переводила (у другой училки)... А тут такой "старт"!
Х.з. чего дальше ждать на том сайте.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117106
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Когда я учился - мы на уроке информатики сразу вряли калькулятор МК-60 и погнали кодить.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117594
DanilaSP
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Попробуйте
1 _tutor
2 _to
3 ot
4 _the
5 21_two23ers223

Должно быть 34.46%
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117697
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
DanilaSP , задание уже не активно, проверить не смогу. Извини...
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117719
DanilaSP
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
krvsa, ничего страшного
Я просто написал программку, которая строит словарь рандомизированным алгоритмом)
На официальном форуме пишут, что можно дойти до 35.9%.
Может и моя программа такое найдёт, если подольше подождать.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117873
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
DanilaSP
Попробуйте
1 2 3 4..... 5 21_two23ers223
А это как понимать, словарь в словаре?
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40117989
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98 , задание допускало любые замены.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40118184
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На официальном форуме пишут, что можно дойти до 35.9%. Это сколько процентов 68 из 148 ?
Length= 148, new length= 68
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
			new 
vocab	cnt	length	length	src text
_to_tutor_two_tooters
	2	21	2	42
_toot	4	5	4	20
_to	4	3	4	12
_tutor	2	6	2	12
_the	2	4	2	8
_two	1	4	4	4
_flute	1	6	6	6
_harder	1	7	7	7
_Is	1	3	3	3
_it	1	3	3	3
_Or	1	3	3	3
_Said	1	5	5	5
_their	1	6	6	6
_Tried	1	6	6	6
_who	1	4	4	4
A	1	1	1	1
"	2	1	2	2
,	1	1	1	1
?	1	1	1	1
ed	1	2	2	2
_	0	1	0	0
ers	0	3	0	0
(пусто)				

Сводная таблица в эксе + немножечко подумать.
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40118194
Фотография krvsa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98 , в той программке не все замены увеличивают процент сжатия...
Некоторые его уменьшают.

Т.ч. если это твой конечный результат - не факт что ты получил бы там хорошие показатели по сжатию.
Проверить конечно уже не смогу...
...
Рейтинг: 0 / 0
Задание по информатике 10 класс
    #40118343
DanilaSP
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
exp98
А как компрессия считалась, относительная убыль длины нового текста? или доля длины нового текста?

Для вычисления компрессии нужно посчитать total = итоговая длина текста + размер словаря (одна строка словаря занимает число символов в слове + 1).
Далее вычислить компрессию как (148 - total) / 148, где 148 - длина исходного текста.
...
Рейтинг: 0 / 0
49 сообщений из 49, показаны все 2 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задание по информатике 10 класс
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (1): Анонимы (1)
Читали форум (1): Анонимы (1)
Пользователи онлайн (7): Анонимы (4), Bing Bot, Yandex Bot 2 мин., Google Bot 5 мин.
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]