Вход | Регистрация
    1  2
1С:Предприятие :: 1С:Предприятие 8 общая

Алгоритм Хаффмана для текста решение

Алгоритм Хаффмана для текста решение
Я
   JuixyJes
 
30.06.19 - 22:36
СЗ = Новый СписокЗначений;
    Для сч= 1 по (СтрДлина(ИсходныйТекст)) Цикл
        СЗ.Добавить(Сред(ИсходныйТекст,сч,1));    
    КонецЦикла;
    Для каждого Стр из СЗ Цикл
        
    КонецЦикла;
 
 
   H A D G E H O G s
 
101 - 01.07.19 - 14:15
(97) 2-х кратный рост потребления памяти массивом.
   МихаилМ
 
102 - 01.07.19 - 14:18
такой алгоритм работает в 20 раз быстрее 
чем (22)

на анализе текста первого тома "война и мир"


ТекДлинаФайла = СтрДлина(ТекстСтрока);
Пока ТекДлинаФайла > 10 Цикл
    ТекСимвол = Лев(ТекстСтрока,1); 
    
    ТекстСтрока = СтрЗаменить(ТекстСтрока,ТекСимвол,"");
    КонДлинаФайла = СтрДлина(ТекстСтрока);
    КолвоСимволов =  КонДлинаФайла-ТекДлинаФайла;
    //Сообщить("/"+ТекСимвол+"/   "+КолвоСимволов);

    ТекДлинаФайла = КонДлинаФайла;
    
КонецЦикла;
   АгентБезопаснойНацио
 
103 - 01.07.19 - 14:20
(101) ну в общем, битва "массив супротив ИТЗ" есть битва неиндексированного  массива против индексированного.
но причин "сдохнуть" варианту с массивом я не вижу. тормоза вижу, а вот смерти нет... в неиндексированном врем линейное, в индексированном  логарифмическоен
   АгентБезопаснойНацио
 
104 - 01.07.19 - 14:22
(102) кстати. время сильно будет зависеть от расположения символов в файле.
   Garykom
 
105 - 01.07.19 - 14:24
(102) Извращенец не хуже чем у меня в (51) с СтрЧислоВхождений
   Garykom
 
106 - 01.07.19 - 14:25
Так кому не влом, может соберем перечисленные извраты и проверим кто тормознее? Кому медаль самого паралгоритма?
   Garykom
 
107 - 01.07.19 - 14:33
(102) Интересно можно как то еще сортировку засунуть результата?
В смысле сразу сортировка вставками.
   Garykom
 
108 - 01.07.19 - 14:36
Но да понимать что можно один раз пройтись большой текст и получая очередной символ куда то его складывать суммируя.

А можно перебирать символы или из всего алфавита и считать сколько конкретного символа в тексте.

А можно соединить как (102) и перебирать символы из большого текста и сразу считать с удалением этого символа из него, автоматом большой текст для перебора сокращается.

Итого три сильно разные варианта алгоритма.
   Garykom
 
109 - 01.07.19 - 14:39
Написать что ли ТС, интересно как отреагирует на (102), мозги свернутся в трубочку или нет.
   H A D G E H O G s
 
110 - 01.07.19 - 14:53
(106) Метод Михаила дает раз в 20 быстрее моего, признаю. За счет быстрой свертки исходного текста.
   Garykom
 
111 - 01.07.19 - 14:55
(110) И он работает по сути на копировании кусков памяти.
Как иначе можно быстро заменять в строках символы?
   Garykom
 
112 - 01.07.19 - 14:57
(111)+ Это я к чему, он работает в 20 быстрее а жрет двойной объем памяти на "Войну и Мир" в начале, затем требуемый объем падает по мере обработки.
   H A D G E H O G s
 
113 - 01.07.19 - 14:58
(111) Да, скорее всего так. Там около 1 мб данных.
   Arbuz
 
114 - 01.07.19 - 15:15
а если ещё использовать для ТекСимвол не исходную строку а заранее заданную строку частотности букв русского языка, то будет ещё быстрее, для "Война и Мiр" конечно ;)
   Garykom
 
115 - 01.07.19 - 15:17
(114) Думаю новые архиваторы так примерно и устроены, жрут кучу памяти для ускорения старых алгоритмов сжатия данных.
   Garykom
 
116 - 01.07.19 - 15:18
(115)+ И места в самом архиваторе.
Т.е. частоты заранее предпрошиты, только по началу текста понять что перед нами, какой язык русский или нет и на основе этого брать заранее заданную последовальность символов.
   Arbuz
 
117 - 01.07.19 - 15:28
(116) даже не столько какой язык, а какой тип данных - текст ascii, юникод, графика, звук, и т.д. на основании этого выбирается цепочка алгоритмов. это если упрощённо. потому как на основании частотности даже не символов, а последовательностей этих символов и их распределения по исходным данным (блокам) - нужно выбирать разные алгоритмы для каждого блока.
   Arbuz
 
118 - 01.07.19 - 15:30
*последовательностей -> частотности последовательностей*
   АгентБезопаснойНацио
 
119 - 01.07.19 - 15:55
(117) ну я то же хотел сказать.но потом посмотрел на тему, и увидел, что только тексь
   Вафель
 
120 - 01.07.19 - 16:02
получается что основная броблема в том что нельзя побыстрому получить символ по индексу
   Arbuz
 
121 - 01.07.19 - 16:14
основная проблема в том, что рисовать Хаффмана на 1С - это редкостный идиотизм. Дальше только 3д графику обсчитывать на ТЗ и регистрах.
   АгентБезопаснойНацио
 
122 - 01.07.19 - 16:22
(121) кстати, прикольная идея - трассировку на регистрах
   Arbuz
 
123 - 01.07.19 - 16:31
(122) да, да и тема на мисте "алгоритм масштабирования сплайна кубических безье на регистре сведений, помогите новичку"
   Garykom
 
124 - 01.07.19 - 16:50
(123) Сколько новичок платит?
   Arbuz
 
125 - 01.07.19 - 16:53
а за сколько готов взяться? :D
   МихаилМ
 
126 - 01.07.19 - 17:51
(121)  (123) в 8.14  добавили решение СЛАУ . обе задачи можно свести к ним.
   Garykom
 
127 - 01.07.19 - 17:55
(126) OpenCL поддержку хочу в 1С.
   МихаилМ
 
128 - 01.07.19 - 18:03
   Garykom
 
129 - 01.07.19 - 18:09
(128) Так не OpenGL а OpenCL это слегка иное.
   NorthWind
 
130 - 01.07.19 - 20:00
(121) ну это же лаба, скорее всего, или курсовик. Я думаю, там даже не стоит задача реально сообщение в битах в файл записывать! Достаточно будет вывести на экран исходное сообщение и закодированное в виде строки из нулей и единиц.
 
 
   NorthWind
 
131 - 01.07.19 - 20:02
так что вся эта мастурбация, которую тут устроили с производительностью, никакого сакрального смысла не имеет. Тем более что построение дерева и его обход с целью получения кодов реально более муторная штука.
   rphosts
 
132 - 02.07.19 - 01:41
(35) (36) символов не много, но что-бы транслировать в более компактную запись (заархивировать) - требуется находить комбинации из нескольких символов и их частоту. В (26) кмк ищется частота вхождения фрагментов из 2 символов.
   rphosts
 
133 - 02.07.19 - 01:41
*из 2 символов длиной
   АгентБезопаснойНацио
 
134 - 02.07.19 - 08:15
(123) лучше классическая задача распознавания автомобильных номеров...
   Провинциальный 1сник
 
135 - 02.07.19 - 08:57
(126) Ждем когда решение системы дифур методом Рунге-Кутта в платформу внедрят) А то мало ли. Выйдет "1С:Управление ядерным реактором", а быстродействия не хватит.
   Garykom
 
136 - 02.07.19 - 15:00
(132) Комбинации из нескольких символов это сжатие по словарю, Хафман же вероятностное сжатие.

Более часто встречающиеся одиночные символы кодируются меньшим числом бит, чем реже встречающиеся.
Т.е. частые символы <8 (или 16) бит на символ, а редко >8 (или 16) бит на символ.
В результате сжатие.
   JuixyJes
 
137 - 03.07.19 - 00:44
Ох етижкин пасатижкин
   JuixyJes
 
138 - 03.07.19 - 00:44
Сколько вы тут понаписали, глазки расплываются..
   palsergeich
 
139 - 03.07.19 - 00:45
(135) Ты зря сммешься, тут на форуме есть госпожа, у которой префиксы объектов начинаются с аэс
   JuixyJes
 
140 - 03.07.19 - 00:48
Допустим, количество вхождений в текст каждого символа найдено, далее их же нужно кодом одарить для каждого, а это, как я понимаю должно быть что-то типа матрицы, не затолкаю же я в 1с дерево:D
   JuixyJes
 
141 - 03.07.19 - 00:51
Чем чаще символ - тем меньше тот самый пресловутый код, это я тоже поняла, на хабре статеек начиталась. Но в плане реализации... Кашица, нужно поспать пойти, но завтра требуют от меня хоть какого то результата, потому сидим-с, думаем-с
   JuixyJes
 
142 - 03.07.19 - 00:56
Понимаю, уже всем надоела. Да и по хорошему даже за такую задачку нужно платить
Но все же надеюсь на вашу помощь. В чужом коде разбираюсь хорошо, ведь за 11 лет в школе и 3 курса института научилась "списывать так чтоб не похоже было".
   palsergeich
 
143 - 03.07.19 - 00:56
(141) Это где такие требования?
   JuixyJes
 
144 - 03.07.19 - 00:57
(143) На обучении) Секретики - секретики.
   palsergeich
 
145 - 03.07.19 - 00:58
(144) Пф. У меня своих секретиков достаточно, что бы в чужие лезть)
   JuixyJes
 
146 - 03.07.19 - 00:58
(143) На работе работаю, вот, позвали работать с обучением бесплатным, а обучением оказалось самостоятельное решение задачек, просто задачки дают, а там как хочешь так и делай)
   palsergeich
 
147 - 03.07.19 - 00:59
(146) ИМХО, послушай старого дядьку - не те задачи ты решаешь. В ближайшие 3 года тебе эта чистая алгоритмика понадобится может раза 2.
   palsergeich
 
148 - 03.07.19 - 01:00
Нужно в проводочки и формочки - это среднесрочный фронт работ
   JuixyJes
 
149 - 03.07.19 - 01:02
(145) Верю) Не подскажите? Как эту чучелу мяучелу научить мяукать? Как я понимаю мне нужно на основании вот этих символов и их частот  создать таблицу Хаффмана? На том же самом хабре написано что кодировать лучше через табличку, которая будет либо связным список либо массивом
   JuixyJes
 
151 - 03.07.19 - 01:17
(148) Этим и так занимаюсь изо дня в день)
   JuixyJes
 
152 - 03.07.19 - 01:18
(148) Что-то с форумом было? А то страница не грузилась
   palsergeich
 
153 - 03.07.19 - 01:18
(149) Я если честно перевтыкал ERP за вечер и немного не в кондиции уже(
В час бекап снимается, около 20 минут оффлайна
   JuixyJes
 
154 - 03.07.19 - 01:22
(153) Понятно) А вообще, задачка вроде бы не очень сложная, насколько я понимаю, так? Ведь осталось присвоить каждому символу свой код, а потом составить из этих кодов исходный текст в виде 0 и 1.
   palsergeich
 
155 - 03.07.19 - 01:29
https://www.youtube.com/watch?v=9b2mCgSCjhw
Вот такую шню надо сделать)
   craxx
 
156 - 03.07.19 - 04:51
(147) Норм задачки она решает. Мозги должны работать и искать пути решения. А не шпарить по шаблону
   Провинциальный 1сник
 
157 - 03.07.19 - 08:04
(141) Задачка интересная и не так чтобы особо сложная. Уровень курсовика 2 курса программистской направленности. Но явно не уровня лабораторной работы, соответственно за пару вечеров это не сделать. И более помочь, чем гугл, форум вряд ли сумеет вам.
   АгентБезопаснойНацио
 
158 - 03.07.19 - 08:14
+(156)  И чем больше путей решения будет рассмотрено, тем легче будет решать будущие нешаблонные проблемки.
(157) так а что там выше трех лаботаторок? тем более, первый этап - построение частотности - уже фактически дали. вторая лаба - сопоставить символ/частоту/код. ну и третья лаба - читать поток, перекодировать, писать в другой... Из стандартного студенчского тайминга: "лаба за вечер, курсовик за ночь". и с учетом  известной первой части - осталось работы на два вечера.
   Провинциальный 1сник
 
159 - 03.07.19 - 08:20
(158) Ну я имею в виду не демонстрацию алгоритма, а более-менее отлаженный продукт, пусть и не оптимизированный. А если в оптимизацию влезть, то там можно вообще бесконечно дорабатывать.
   АгентБезопаснойНацио
 
160 - 03.07.19 - 09:06
(159) ну так "хаффман на 1с" - не для продакшена пишется.
   JuixyJes
 
161 - 05.07.19 - 23:16
Вечер добрый, форумчане! Допенькала я как мне приблизиться к решению задачки, и кодируется пусть не оптимально, но кодируется, пока что собственноручно вбивается код. Не подскажите, как в обратную сторону строку с тем же алфавитом раскодировать?
   JuixyJes
 
162 - 05.07.19 - 23:17
Могу обработку скинуть, она на обычных формах сделана
   АгентБезопаснойНацио
 
163 - 06.07.19 - 07:18
(162) декодеру код (а не алфавит) должен быть известен перед раскодированием.
К там уже просто - побитно читаешь вход и спускаешься по дереву до листа.
  1  2

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.