СЗ = Новый СписокЗначений;
    Для сч= 1 по (СтрДлина(ИсходныйТекст)) Цикл
        СЗ.Добавить(Сред(ИсходныйТекст,сч,1));    
    КонецЦикла;
    Для каждого Стр из СЗ Цикл
        
    КонецЦикла;

Возможно я что то не так поняла, но все же. Я создала СЗ в котором будет каждый символ как строчка. Но как мне найти количество одинаковых вхождений для каждого символа?

Жесть.
Так ты Хаффмана не построишь

(2) А каким образом мне его построить?

Нахрена тебе это?

Возьми архиватор и не парь мозги или может с кодами Рида-Соломона путаешь?

(3) Вам не надо его строить.
Вам надо сменить специальность в ВУЗе

(4) Нет, мне для общего развития требуется именно Хаффман. Ибо не хотят меня допускать до нормальной работы пока я не сделаю хаффмана. Я прекрасно понимаю как он работает.

(5) Это скорее какой то сайт где курсовые и контрольные заказывают, по сути фриланс биржа.
Слишком большой разброс заданий.

(6) Если понимаешь как он работает то я не понимаю проблем написать кодом.

Сколько символов для начала у тебя в алфавите/кодировке?

Короче похрен, все символы имеют коды, эти коды что?
И можно завести линейный массив нужной длины куда писать количество для каждого символа в кодировке.

(5) Вы не в праве решать что мне надо, а что мне не надо. Если я решила, что мне нужно реализовать алгоритм Хаффмана, значит мне нужно его реализовать, а свое мнение придержите при себе. Если вы не собираетесь помогать а будете только умничать, для этого есть другие темы. Не все вы сюда пришли такими умными и распрекрасными программистами.

А делать через СЗ это только 1Сник со стажем, который алгоритмику не то что забыл, а никогда не знал ))

(9) Я полагала что при отработке алгоритма он сам должен составить для себя какой то алфавит условный.

(10) Дерзко, но не к месту.
(12) Алгоритм сам по себе ничего не умеет, он делает ровно то что заложено.
(10) И да что бы чего то добиться - выезжать на хамстве не очень то верно. Вы с одной стороны вроде и говорите верные вещи, но реализация на 2-, 2 в 10 СС это показало.

Если Вы понимаете как это работает, переложить в код - нет ничего проще. Все проблемы, когда понятия нет

(12) Для опытных специалистов немного дико выглядит, когда некто берется за задачу не своего уровня.
Даже если сможет сделать то результат будет говно.

Для самообучения же лучше заниматься последовательно, начиная с более простых задач, чтобы когда подойти к подобной уже обладать неким опытом и объемом знаний.

Тогда и тупых вопросов не будет, вызывающих подобную (5) реакцию.

(10)

Я знаю, скоро утро взорвется рассветом.
И это будет последний мирный рассвет.
Здравствуй дружок, ты хотел быть поэтом?
Что же, прошу к амбразуре – теперь ты поэт.

Были артерии трасс и оазисы станций,
Все что увидеть успел, запиши, и пора,
Мирно живут только те, кому не за что драться,
Ты стал слишком взрослым, ты понял что это война.


Ты хотел быть поэтом?

(13) Ну уж извините, хамство не хамство, но для меня это оскорбление. Поэтому такая реакция. Я принимаю критику, но извините, не такое.

(13) а насчет реализации на 2- я могу сказать честно, я не понимаю как его реализовать, могу на бумаге его спокойно расписать, а вот алгоритм в программе....

(18) Точно так же

(19) в первой итерации делаешь ровно то что написано на бумаге, потом доводишь до ума.
Я именно так и пишу, сначала схемка, потом набросок 1ой итерациии, потом полировка

(20) Хорошо, постараюсь так и сделать.

ТаблицаЧастот= Новый ТаблицаЗначений;
ТаблицаЧастот.Колонки.Добавить("Символ");
ТаблицаЧастот.Колонки.Добавить("КоличествоСимволов",Новый ОписаниеТипов("Число"));
ТаблицаЧастот.Индексы.Добавить("Символ");
    Для сч= 1 по (СтрДлина(ИсходныйТекст)) Цикл
        ТекущийСимвол=Сред(ИсходныйТекст,сч,1);
СтрокаТаблицыЧастот=ТаблицаЧастот.Найти(ТекущийСимвол,"Символ");
Если СтрокаТаблицыЧастот=Неопределено Тогда
СтрокаТаблицыЧастот=ТаблицаЧастот.Добавить();
СтрокаТаблицыЧастот.Символ=ТекущийСимвол;
КонецЕсли;
СтрокаТаблицыЧастот.КоличествоСимволов=СтрокаТаблицыЧастот.КоличествоСимволов+1;
    КонецЦикла;
ТаблицаЧастот.Сортировать("КоличествоСимволов Убыв");

(22) И зачем?
Если дать человеку рыбу он будет сыт один день.
Если дать сеть - то будет сыт всегда...

(23) Человеку не нужна сеть, ему нужно нечто за проданную рыбу.
А сеть хрен продаш...

(23) Ну он хоть посмотрит, запустит отладчик, разбереться.
Это все же лучше, чем он будет смотреть в список как на новые ворота

Не проще?

МассивЧастот = Новый Массив(65536);
Для сч= 1 по (СтрДлина(ИсходныйТекст)) Цикл
   ТекущийСимвол=Сред(ИсходныйТекст,сч,1);
   МассивЧастот[КодСимвола(ТекущийСимвол)] = МассивЧастот[КодСимвола(ТекущийСимвол)] + 1;
КонецЦикла;


(26) Проще, но не правильно.

(27) Если текст очень большой и символов разных в нем дофига то решение на ТЗ помрет.

(28) Твое - помрет, мое - нет.

(29) хм... да хз, скорее у тебя умрёт... поиск на всей таблице для каждого символа - не торт... от себя предложу 3 вариант: писать всё в таблицу а потом свернуть. если сподоблюсь - проверю все 3 варианта.

(8) ну, положим что проблем там достаточно. И подсчитать частоты встречаемости символов - это, пожалуй, пятидесятая часть от того что там надо будет сделать.

Ну,потом по частотам строить дерево.
просто,со массивом потом дерево строить,как со списком символы считать.

хотя,если в списке хранить число,а представление как символ,то вполне взлетит,до сворачивания.
просто,массив потом надо от нулей вычищать.

(33) Не вычищать а всего один линейный проход выбрать не нулевые и одновременно сортировка.

(30) символов вроде не так много, так что должно работать быстро

(30) и сколько строк для русского, к примеру, текста? :)

(36) В какой кодировке то текст?

(37) я не в курсе, ТС не рассказывает

(38) Так это первый самый вопрос и не понимая что такое кодировки и чем они отличаются (есть подозрение что ТС не в курсе этого) какой к черту Хаффман.

(39)+ Точнее можно написать и универсальные решения под любую практически кодировку.
Но это будут монстры на нечто вроде ТЗ, которые помрут на реальных текстах в больших кодировках.

Мое решение будет быстро на любом тексте, а решение Гарри помрет на от 20 Мб текста.
Быстрее моего решения - только разбить на потоки и писать в несколько тз, а потом слить результат в 1 тз.

(41) в его решении от объема текста  (и распределения) зависит только число (счетчик встречаемости) в элементе массива. у тебя то же самое, только у тебя значительно меньше элементов, но больше затраты на индекс и поиск по индексу.
Почему у него умрет?

(42) Потому что Массив в 1С - это СвязныйСписок, а не кусок памяти.

(41) ВК один фиг будет быстрее.

(43) Угу сейчас вспомнил про это, такую фигню я обычно в памяти не держу, что 1С тут слегка того ибо типизации то нет, хз сколько памяти надо под элементы, хотя размер массива задан.

Точно ТЗ с индексом будет быстрее Соответствия?

отсортировать + СтрЧислоВхождений

+(47) отсортировать  читать упорядочить

(47) СтрЧислоВхождений слишком просто, проверяющие зарубят - "использование готовых библиотек"

(49)
быстро отсортировать - не просто.

(50) Ты фишки наверно не понял?


СЗ = Новый СписокЗначений;
Для ТекКодСимвола = 65536 По 1 Цикл
  ТекСимвол = Символ(ТекКодСимвола);
  Частота = СтрЧислоВхождений(ИсходныйТекст, ТекСимвол);
  СЗ.Добавить(ТекСимвол, Частота);
КонецЦикла


(51)+ Условие Частота>0 сами надеюсь сами легко добавить?

(51) Он вообще с трудом догоняет.
Но и (51) - кусок шлака.

(46) Также. Но что ты потом с Соответствием делать будешь?

(22) а чем таблица лучше соответствия?
Соотвествие - это всетаки хэшмэп. поинтереснее чем индекс для поиска

(54) Пофиг что, главное что быстрее для задачи.

(53) Для малых текстов с огромным количеством разных символов (не только латиница/кириллица но все что угодно из юникода) чье быстрее?

(57)а где тесты? докузывающее что твое решение быстрее?
кстати СтрЧислоВхождений ккакой сложности операция?

(57) Как тебя вообще до программирования допускают?
У тебя 65535 раз полностью перебор текста будет

(58) Можешь заняться тестами если хочешь.

И я согласен что у меня хрень зато короткая по коду и работающая и даже очень неплохо при некоторых узких входных данных/условиях.

(59) Я в курсе.

(55) О каком хэшмапе идет речь, если ключ поиска состоит из 1 символа?

Я херею

(60) В гугл тебя не возьмут

(63) Если частота символов не более 65536 в тексте то строка наверно самое быстрое.

(62) а что хэш от 1 символа нельзя посчитать?

(66) Но зачем?

Хэшмап хорош для длинных ключей

(64) И не стремлюсь туда особо, у меня решение для параконкурса но для ТС пойдет.

(67) ну так хэш мэп - это константное время поиска, а интекс - логарифмическое

для коротких вообще можно свой хэш мэп организаовать

(65)+ Хотя кто мешает завести еще одну строку, когда переполнена предыдущая по символу

(71) "свой хэш мэп организаовать" // Ну так соответствие же вроде это оно и есть?

Хэш[КодСимвола(Символа)]++

(70) У тебя таблица будет максимум из 65535 строк . Тут и логарифм нормален. А для хэшмапа еще и хэш строить.

(73) чтобы исключить операцию вычисления хэша

(76) ты хотел сказать - "переложить ее на платформу"

Алгоритмы Хаффмана они собрались строить, ага

(74) Хэш - это массив

(75) +1. Символ(0) не забыл?

(77) (78) Обрати внимание что у тебя начинается "старческое брюзжание" ))

(81) Давно пора

(76) А получение элемента массива по индексу разве не тот же хэш?

(79) в 1С 8 нет классических массивов как в 7.7 и обычных яп

(84) Эээ я думал там массив указателей по сути.

(43) именно связный, не массив указателей?

(86) Судя по тому, что Удалить() в любом месте 1 млн массива массива отрабатывается с одинаковой скоростью - то - связный

(87) Уверено что удаляет а не помечает элемент как удаленный?
Или что при каждом удаление не происходит копирование массива в новый со всеми ссылками?

(87) в клюшках вроде был массив указателей. Или массив Char23...

(88) Слово предоставляется молчаливому бобу.

(88) ну уж до додуматься такого, как "копирование  в новый" - это надо под грибами думать...

Гарри, а ты представляешь, как работает классический массив, как он лежит в памяти, как к нему прикрутить пометку на удаление и, самое главное, как потом сделать обращение по индексу?

Есть же понимание, что для удаление через копирование понадобиться 2x памяти в короткий момент?

(92) А я что написал в (88) ?
Представляю и причем кучей разных способов с разными плюсами и минусами их.

(93) А думаем почему 1С память жрет как не в себя?

(94) Массив в классическом ЯП - это кусок памяти с ячейками одинакового размера. Зная размер и номер ячейки - можно максимально быстро обратится к элементу массива. Вводя пометку на удаление, мы уже лишаемся этого.

(96) Кто мешает скопировать часть массива (кусок памяти) до удаляемого и часть после удаляемого элемента в новый кусок памяти - массив

(97)+ В Golang это слайсы по сути

(97)  с помощью двух спиц и катушек из под ниток из булки хлеба...©

(99) Получается язык Go за программинг на котором платят уже хорошие деньги

(97) 2-х кратный рост потребления памяти массивом.

такой алгоритм работает в 20 раз быстрее
чем (22)

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


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

(101) ну в общем, битва "массив супротив ИТЗ" есть битва неиндексированного  массива против индексированного.
но причин "сдохнуть" варианту с массивом я не вижу. тормоза вижу, а вот смерти нет... в неиндексированном врем линейное, в индексированном  логарифмическоен

(102) кстати. время сильно будет зависеть от расположения символов в файле.

(102) Извращенец не хуже чем у меня в (51) с СтрЧислоВхождений

Так кому не влом, может соберем перечисленные извраты и проверим кто тормознее? Кому медаль самого паралгоритма?

(102) Интересно можно как то еще сортировку засунуть результата?
В смысле сразу сортировка вставками.

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

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

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

Итого три сильно разные варианта алгоритма.

Написать что ли ТС, интересно как отреагирует на (102), мозги свернутся в трубочку или нет.

(106) Метод Михаила дает раз в 20 быстрее моего, признаю. За счет быстрой свертки исходного текста.

(110) И он работает по сути на копировании кусков памяти.
Как иначе можно быстро заменять в строках символы?

(111)+ Это я к чему, он работает в 20 быстрее а жрет двойной объем памяти на "Войну и Мир" в начале, затем требуемый объем падает по мере обработки.

(111) Да, скорее всего так. Там около 1 мб данных.

а если ещё использовать для ТекСимвол не исходную строку а заранее заданную строку частотности букв русского языка, то будет ещё быстрее, для "Война и Мiр" конечно ;)

(114) Думаю новые архиваторы так примерно и устроены, жрут кучу памяти для ускорения старых алгоритмов сжатия данных.

(115)+ И места в самом архиваторе.
Т.е. частоты заранее предпрошиты, только по началу текста понять что перед нами, какой язык русский или нет и на основе этого брать заранее заданную последовальность символов.

(116) даже не столько какой язык, а какой тип данных - текст ascii, юникод, графика, звук, и т.д. на основании этого выбирается цепочка алгоритмов. это если упрощённо. потому как на основании частотности даже не символов, а последовательностей этих символов и их распределения по исходным данным (блокам) - нужно выбирать разные алгоритмы для каждого блока.

*последовательностей -> частотности последовательностей*

(117) ну я то же хотел сказать.но потом посмотрел на тему, и увидел, что только тексь

получается что основная броблема в том что нельзя побыстрому получить символ по индексу

основная проблема в том, что рисовать Хаффмана на 1С - это редкостный идиотизм. Дальше только 3д графику обсчитывать на ТЗ и регистрах.

(121) кстати, прикольная идея - трассировку на регистрах

(122) да, да и тема на мисте "алгоритм масштабирования сплайна кубических безье на регистре сведений, помогите новичку"

(123) Сколько новичок платит?

а за сколько готов взяться? :D

(121)  (123) в 8.14  добавили решение СЛАУ . обе задачи можно свести к ним.

(126) OpenCL поддержку хочу в 1С.

(127) ждать не долго https://www.google.com/search?ei=iyAaXenRKp3ImwWeo5TYAw&q=webkit+render+to+opengl&oq=webkit+OpenCL+&gs_l=psy-ab.1.4.0i13i30l3j0i13i5i30j0i8i13i30.5639.12151..21478...0.0..0.80.134.2......0....1j2..gws-wiz.......0i71j0i67j0.Y8K6lGzJeEU

(128) Так не OpenGL а OpenCL это слегка иное.

(121) ну это же лаба, скорее всего, или курсовик. Я думаю, там даже не стоит задача реально сообщение в битах в файл записывать! Достаточно будет вывести на экран исходное сообщение и закодированное в виде строки из нулей и единиц.

так что вся эта мастурбация, которую тут устроили с производительностью, никакого сакрального смысла не имеет. Тем более что построение дерева и его обход с целью получения кодов реально более муторная штука.

(35) (36) символов не много, но что-бы транслировать в более компактную запись (заархивировать) - требуется находить комбинации из нескольких символов и их частоту. В (26) кмк ищется частота вхождения фрагментов из 2 символов.

*из 2 символов длиной

(123) лучше классическая задача распознавания автомобильных номеров...

(126) Ждем когда решение системы дифур методом Рунге-Кутта в платформу внедрят) А то мало ли. Выйдет "1С:Управление ядерным реактором", а быстродействия не хватит.

(132) Комбинации из нескольких символов это сжатие по словарю, Хафман же вероятностное сжатие.

Более часто встречающиеся одиночные символы кодируются меньшим числом бит, чем реже встречающиеся.
Т.е. частые символы <8 (или 16) бит на символ, а редко >8 (или 16) бит на символ.
В результате сжатие.

Ох етижкин пасатижкин

Сколько вы тут понаписали, глазки расплываются..

(135) Ты зря сммешься, тут на форуме есть госпожа, у которой префиксы объектов начинаются с аэс

Допустим, количество вхождений в текст каждого символа найдено, далее их же нужно кодом одарить для каждого, а это, как я понимаю должно быть что-то типа матрицы, не затолкаю же я в 1с дерево:D

Чем чаще символ - тем меньше тот самый пресловутый код, это я тоже поняла, на хабре статеек начиталась. Но в плане реализации... Кашица, нужно поспать пойти, но завтра требуют от меня хоть какого то результата, потому сидим-с, думаем-с

Понимаю, уже всем надоела. Да и по хорошему даже за такую задачку нужно платить
Но все же надеюсь на вашу помощь. В чужом коде разбираюсь хорошо, ведь за 11 лет в школе и 3 курса института научилась "списывать так чтоб не похоже было".

(141) Это где такие требования?

(143) На обучении) Секретики - секретики.

(144) Пф. У меня своих секретиков достаточно, что бы в чужие лезть)

(143) На работе работаю, вот, позвали работать с обучением бесплатным, а обучением оказалось самостоятельное решение задачек, просто задачки дают, а там как хочешь так и делай)

(146) ИМХО, послушай старого дядьку - не те задачи ты решаешь. В ближайшие 3 года тебе эта чистая алгоритмика понадобится может раза 2.

Нужно в проводочки и формочки - это среднесрочный фронт работ

(145) Верю) Не подскажите? Как эту чучелу мяучелу научить мяукать? Как я понимаю мне нужно на основании вот этих символов и их частот  создать таблицу Хаффмана? На том же самом хабре написано что кодировать лучше через табличку, которая будет либо связным список либо массивом

(148) Этим и так занимаюсь изо дня в день)

(148) Что-то с форумом было? А то страница не грузилась

(149) Я если честно перевтыкал ERP за вечер и немного не в кондиции уже(
В час бекап снимается, около 20 минут оффлайна

(153) Понятно) А вообще, задачка вроде бы не очень сложная, насколько я понимаю, так? Ведь осталось присвоить каждому символу свой код, а потом составить из этих кодов исходный текст в виде 0 и 1.

https://www.youtube.com/watch?v=9b2mCgSCjhw
Вот такую шню надо сделать)

(147) Норм задачки она решает. Мозги должны работать и искать пути решения. А не шпарить по шаблону

(141) Задачка интересная и не так чтобы особо сложная. Уровень курсовика 2 курса программистской направленности. Но явно не уровня лабораторной работы, соответственно за пару вечеров это не сделать. И более помочь, чем гугл, форум вряд ли сумеет вам.

+(156)  И чем больше путей решения будет рассмотрено, тем легче будет решать будущие нешаблонные проблемки.
(157) так а что там выше трех лаботаторок? тем более, первый этап - построение частотности - уже фактически дали. вторая лаба - сопоставить символ/частоту/код. ну и третья лаба - читать поток, перекодировать, писать в другой... Из стандартного студенчского тайминга: "лаба за вечер, курсовик за ночь". и с учетом  известной первой части - осталось работы на два вечера.

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

(159) ну так "хаффман на 1с" - не для продакшена пишется.

Вечер добрый, форумчане! Допенькала я как мне приблизиться к решению задачки, и кодируется пусть не оптимально, но кодируется, пока что собственноручно вбивается код. Не подскажите, как в обратную сторону строку с тем же алфавитом раскодировать?

Могу обработку скинуть, она на обычных формах сделана

(162) декодеру код (а не алфавит) должен быть известен перед раскодированием.
К там уже просто - побитно читаешь вход и спускаешься по дереву до листа.