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

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

Алгоритм Хаффмана для текста решение
Я
   JuixyJes
 
30.06.19 - 22:36
СЗ = Новый СписокЗначений;
    Для сч= 1 по (СтрДлина(ИсходныйТекст)) Цикл
        СЗ.Добавить(Сред(ИсходныйТекст,сч,1));    
    КонецЦикла;
    Для каждого Стр из СЗ Цикл
        
    КонецЦикла;
 
 
   JuixyJes
 
1 - 30.06.19 - 22:37
Возможно я что то не так поняла, но все же. Я создала СЗ в котором будет каждый символ как строчка. Но как мне найти количество одинаковых вхождений для каждого символа?
   H A D G E H O G s
 
2 - 30.06.19 - 23:09
Жесть.
Так ты Хаффмана не построишь
   JuixyJes
 
3 - 30.06.19 - 23:17
(2) А каким образом мне его построить?
   Garykom
 
4 - 30.06.19 - 23:22
Нахрена тебе это?

Возьми архиватор и не парь мозги или может с кодами Рида-Соломона путаешь?
   H A D G E H O G s
 
5 - 30.06.19 - 23:22
(3) Вам не надо его строить.
Вам надо сменить специальность в ВУЗе
   JuixyJes
 
6 - 30.06.19 - 23:23
(4) Нет, мне для общего развития требуется именно Хаффман. Ибо не хотят меня допускать до нормальной работы пока я не сделаю хаффмана. Я прекрасно понимаю как он работает.
   Garykom
 
7 - 30.06.19 - 23:23
(5) Это скорее какой то сайт где курсовые и контрольные заказывают, по сути фриланс биржа.
Слишком большой разброс заданий.
   Garykom
 
8 - 30.06.19 - 23:24
(6) Если понимаешь как он работает то я не понимаю проблем написать кодом.

Сколько символов для начала у тебя в алфавите/кодировке?
   Garykom
 
9 - 30.06.19 - 23:25
Короче похрен, все символы имеют коды, эти коды что?
И можно завести линейный массив нужной длины куда писать количество для каждого символа в кодировке.
   JuixyJes
 
10 - 30.06.19 - 23:26
(5) Вы не в праве решать что мне надо, а что мне не надо. Если я решила, что мне нужно реализовать алгоритм Хаффмана, значит мне нужно его реализовать, а свое мнение придержите при себе. Если вы не собираетесь помогать а будете только умничать, для этого есть другие темы. Не все вы сюда пришли такими умными и распрекрасными программистами.
 
 Рекламное место пустует
   Garykom
 
11 - 30.06.19 - 23:26
А делать через СЗ это только 1Сник со стажем, который алгоритмику не то что забыл, а никогда не знал ))
   JuixyJes
 
12 - 30.06.19 - 23:27
(9) Я полагала что при отработке алгоритма он сам должен составить для себя какой то алфавит условный.
   palsergeich
 
13 - 30.06.19 - 23:30
(10) Дерзко, но не к месту.
(12) Алгоритм сам по себе ничего не умеет, он делает ровно то что заложено.
(10) И да что бы чего то добиться - выезжать на хамстве не очень то верно. Вы с одной стороны вроде и говорите верные вещи, но реализация на 2-, 2 в 10 СС это показало.
   palsergeich
 
14 - 30.06.19 - 23:31
Если Вы понимаете как это работает, переложить в код - нет ничего проще. Все проблемы, когда понятия нет
   Garykom
 
15 - 30.06.19 - 23:31
(12) Для опытных специалистов немного дико выглядит, когда некто берется за задачу не своего уровня.
Даже если сможет сделать то результат будет говно.

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

Тогда и тупых вопросов не будет, вызывающих подобную (5) реакцию.
   H A D G E H O G s
 
16 - 30.06.19 - 23:33
(10)

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

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


Ты хотел быть поэтом?
   JuixyJes
 
17 - 30.06.19 - 23:34
(13) Ну уж извините, хамство не хамство, но для меня это оскорбление. Поэтому такая реакция. Я принимаю критику, но извините, не такое.
   JuixyJes
 
18 - 30.06.19 - 23:36
(13) а насчет реализации на 2- я могу сказать честно, я не понимаю как его реализовать, могу на бумаге его спокойно расписать, а вот алгоритм в программе....
   palsergeich
 
19 - 30.06.19 - 23:38
(18) Точно так же
   palsergeich
 
20 - 30.06.19 - 23:39
(19) в первой итерации делаешь ровно то что написано на бумаге, потом доводишь до ума.
Я именно так и пишу, сначала схемка, потом набросок 1ой итерациии, потом полировка
   JuixyJes
 
21 - 30.06.19 - 23:41
(20) Хорошо, постараюсь так и сделать.
   H A D G E H O G s
 
22 - 30.06.19 - 23:42
ТаблицаЧастот= Новый ТаблицаЗначений;
ТаблицаЧастот.Колонки.Добавить("Символ");
ТаблицаЧастот.Колонки.Добавить("КоличествоСимволов",Новый ОписаниеТипов("Число"));
ТаблицаЧастот.Индексы.Добавить("Символ"); 
    Для сч= 1 по (СтрДлина(ИсходныйТекст)) Цикл 
        ТекущийСимвол=Сред(ИсходныйТекст,сч,1);
СтрокаТаблицыЧастот=ТаблицаЧастот.Найти(ТекущийСимвол,"Символ");
Если СтрокаТаблицыЧастот=Неопределено Тогда
СтрокаТаблицыЧастот=ТаблицаЧастот.Добавить();
СтрокаТаблицыЧастот.Символ=ТекущийСимвол;
КонецЕсли;
СтрокаТаблицыЧастот.КоличествоСимволов=СтрокаТаблицыЧастот.КоличествоСимволов+1;
    КонецЦикла;
ТаблицаЧастот.Сортировать("КоличествоСимволов Убыв");
   palsergeich
 
23 - 30.06.19 - 23:44
(22) И зачем?
Если дать человеку рыбу он будет сыт один день.
Если дать сеть - то будет сыт всегда...
   Garykom
 
24 - 30.06.19 - 23:46
(23) Человеку не нужна сеть, ему нужно нечто за проданную рыбу.
А сеть хрен продаш...
   H A D G E H O G s
 
25 - 30.06.19 - 23:47
(23) Ну он хоть посмотрит, запустит отладчик, разбереться.
Это все же лучше, чем он будет смотреть в список как на новые ворота
   Garykom
 
26 - 30.06.19 - 23:57
Не проще?
МассивЧастот = Новый Массив(65536);
Для сч= 1 по (СтрДлина(ИсходныйТекст)) Цикл 
   ТекущийСимвол=Сред(ИсходныйТекст,сч,1);
   МассивЧастот[КодСимвола(ТекущийСимвол)] = МассивЧастот[КодСимвола(ТекущийСимвол)] + 1;
КонецЦикла;

   H A D G E H O G s
 
27 - 01.07.19 - 00:00
(26) Проще, но не правильно.
   Garykom
 
28 - 01.07.19 - 00:07
(27) Если текст очень большой и символов разных в нем дофига то решение на ТЗ помрет.
   H A D G E H O G s
 
29 - 01.07.19 - 00:12
(28) Твое - помрет, мое - нет.
   rphosts
 
30 - 01.07.19 - 02:38
(29) хм... да хз, скорее у тебя умрёт... поиск на всей таблице для каждого символа - не торт... от себя предложу 3 вариант: писать всё в таблицу а потом свернуть. если сподоблюсь - проверю все 3 варианта.
   NorthWind
 
31 - 01.07.19 - 07:45
(8) ну, положим что проблем там достаточно. И подсчитать частоты встречаемости символов - это, пожалуй, пятидесятая часть от того что там надо будет сделать.
   Сияющий в темноте
 
32 - 01.07.19 - 08:49
Ну,потом по частотам строить дерево.
просто,со массивом потом дерево строить,как со списком символы считать.
   Сияющий в темноте
 
33 - 01.07.19 - 08:50
хотя,если в списке хранить число,а представление как символ,то вполне взлетит,до сворачивания.
просто,массив потом надо от нулей вычищать.
 
 
   Garykom
 
34 - 01.07.19 - 09:28
(33) Не вычищать а всего один линейный проход выбрать не нулевые и одновременно сортировка.
   DmitriyDI
 
35 - 01.07.19 - 09:34
(30) символов вроде не так много, так что должно работать быстро
   FIXXXL
 
36 - 01.07.19 - 09:57
(30) и сколько строк для русского, к примеру, текста? :)
   Garykom
 
37 - 01.07.19 - 10:00
(36) В какой кодировке то текст?
   FIXXXL
 
38 - 01.07.19 - 10:01
(37) я не в курсе, ТС не рассказывает
   Garykom
 
39 - 01.07.19 - 10:02
(38) Так это первый самый вопрос и не понимая что такое кодировки и чем они отличаются (есть подозрение что ТС не в курсе этого) какой к черту Хаффман.
   Garykom
 
40 - 01.07.19 - 10:05
(39)+ Точнее можно написать и универсальные решения под любую практически кодировку.
Но это будут монстры на нечто вроде ТЗ, которые помрут на реальных текстах в больших кодировках.
   H A D G E H O G s
 
41 - 01.07.19 - 10:09
Мое решение будет быстро на любом тексте, а решение Гарри помрет на от 20 Мб текста.
Быстрее моего решения - только разбить на потоки и писать в несколько тз, а потом слить результат в 1 тз.
   АгентБезопаснойНацио
 
42 - 01.07.19 - 10:25
(41) в его решении от объема текста  (и распределения) зависит только число (счетчик встречаемости) в элементе массива. у тебя то же самое, только у тебя значительно меньше элементов, но больше затраты на индекс и поиск по индексу.
Почему у него умрет?
   H A D G E H O G s
 
43 - 01.07.19 - 10:55
(42) Потому что Массив в 1С - это СвязныйСписок, а не кусок памяти.
   Garykom
 
44 - 01.07.19 - 11:21
(41) ВК один фиг будет быстрее.
   Garykom
 
45 - 01.07.19 - 11:22
(43) Угу сейчас вспомнил про это, такую фигню я обычно в памяти не держу, что 1С тут слегка того ибо типизации то нет, хз сколько памяти надо под элементы, хотя размер массива задан.
   Garykom
 
46 - 01.07.19 - 11:23
Точно ТЗ с индексом будет быстрее Соответствия?
   МихаилМ
 
47 - 01.07.19 - 11:26
отсортировать + СтрЧислоВхождений
   МихаилМ
 
48 - 01.07.19 - 11:29
+(47) отсортировать  читать упорядочить
   Garykom
 
49 - 01.07.19 - 11:37
(47) СтрЧислоВхождений слишком просто, проверяющие зарубят - "использование готовых библиотек"
 
 Рекламное место пустует
   МихаилМ
 
50 - 01.07.19 - 11:42
(49)
быстро отсортировать - не просто.
   Garykom
 
51 - 01.07.19 - 11:54
(50) Ты фишки наверно не понял?

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

   Garykom
 
52 - 01.07.19 - 11:55
(51)+ Условие Частота>0 сами надеюсь сами легко добавить?
   H A D G E H O G s
 
53 - 01.07.19 - 12:12
(51) Он вообще с трудом догоняет.
Но и (51) - кусок шлака.
   H A D G E H O G s
 
54 - 01.07.19 - 12:13
(46) Также. Но что ты потом с Соответствием делать будешь?
   Вафель
 
55 - 01.07.19 - 12:39
(22) а чем таблица лучше соответствия?
Соотвествие - это всетаки хэшмэп. поинтереснее чем индекс для поиска
   Garykom
 
56 - 01.07.19 - 12:39
(54) Пофиг что, главное что быстрее для задачи.
   Garykom
 
57 - 01.07.19 - 12:41
(53) Для малых текстов с огромным количеством разных символов (не только латиница/кириллица но все что угодно из юникода) чье быстрее?
   Вафель
 
58 - 01.07.19 - 12:42
(57)а где тесты? докузывающее что твое решение быстрее?
кстати СтрЧислоВхождений ккакой сложности операция?
   H A D G E H O G s
 
59 - 01.07.19 - 12:43
(57) Как тебя вообще до программирования допускают?
У тебя 65535 раз полностью перебор текста будет
   Garykom
 
60 - 01.07.19 - 12:43
(58) Можешь заняться тестами если хочешь.

И я согласен что у меня хрень зато короткая по коду и работающая и даже очень неплохо при некоторых узких входных данных/условиях.
   Garykom
 
61 - 01.07.19 - 12:43
(59) Я в курсе.
   H A D G E H O G s
 
62 - 01.07.19 - 12:44
(55) О каком хэшмапе идет речь, если ключ поиска состоит из 1 символа?
   H A D G E H O G s
 
63 - 01.07.19 - 12:45
Я херею
   Вафель
 
64 - 01.07.19 - 12:45
(60) В гугл тебя не возьмут
   Garykom
 
65 - 01.07.19 - 12:46
(63) Если частота символов не более 65536 в тексте то строка наверно самое быстрое.
   Вафель
 
66 - 01.07.19 - 12:46
(62) а что хэш от 1 символа нельзя посчитать?
   H A D G E H O G s
 
67 - 01.07.19 - 12:46
(66) Но зачем?
   H A D G E H O G s
 
68 - 01.07.19 - 12:47
Хэшмап хорош для длинных ключей
   Garykom
 
69 - 01.07.19 - 12:47
(64) И не стремлюсь туда особо, у меня решение для параконкурса но для ТС пойдет.
   Вафель
 
70 - 01.07.19 - 12:47
(67) ну так хэш мэп - это константное время поиска, а интекс - логарифмическое
   Вафель
 
71 - 01.07.19 - 12:48
для коротких вообще можно свой хэш мэп организаовать
   Garykom
 
72 - 01.07.19 - 12:48
(65)+ Хотя кто мешает завести еще одну строку, когда переполнена предыдущая по символу
   Cyberhawk
 
73 - 01.07.19 - 12:48
(71) "свой хэш мэп организаовать" // Ну так соответствие же вроде это оно и есть?
   Вафель
 
74 - 01.07.19 - 12:48
Хэш[КодСимвола(Символа)]++
   H A D G E H O G s
 
75 - 01.07.19 - 12:49
(70) У тебя таблица будет максимум из 65535 строк . Тут и логарифм нормален. А для хэшмапа еще и хэш строить.
   Вафель
 
76 - 01.07.19 - 12:49
(73) чтобы исключить операцию вычисления хэша
   H A D G E H O G s
 
77 - 01.07.19 - 12:50
(76) ты хотел сказать - "переложить ее на платформу"
   H A D G E H O G s
 
78 - 01.07.19 - 12:51
Алгоритмы Хаффмана они собрались строить, ага
   Вафель
 
79 - 01.07.19 - 12:51
(74) Хэш - это массив
   Garykom
 
80 - 01.07.19 - 12:51
(75) +1. Символ(0) не забыл?
   Garykom
 
81 - 01.07.19 - 12:52
(77) (78) Обрати внимание что у тебя начинается "старческое брюзжание" ))
   H A D G E H O G s
 
82 - 01.07.19 - 12:53
(81) Давно пора
   Cyberhawk
 
83 - 01.07.19 - 12:55
(76) А получение элемента массива по индексу разве не тот же хэш?
   H A D G E H O G s
 
84 - 01.07.19 - 13:12
(79) в 1С 8 нет классических массивов как в 7.7 и обычных яп
   Garykom
 
85 - 01.07.19 - 13:16
(84) Эээ я думал там массив указателей по сути.
   АгентБезопаснойНацио
 
86 - 01.07.19 - 13:34
(43) именно связный, не массив указателей?
   H A D G E H O G s
 
87 - 01.07.19 - 13:36
(86) Судя по тому, что Удалить() в любом месте 1 млн массива массива отрабатывается с одинаковой скоростью - то - связный
   Garykom
 
88 - 01.07.19 - 13:47
(87) Уверено что удаляет а не помечает элемент как удаленный?
Или что при каждом удаление не происходит копирование массива в новый со всеми ссылками?
   АгентБезопаснойНацио
 
89 - 01.07.19 - 13:52
(87) в клюшках вроде был массив указателей. Или массив Char23...
   H A D G E H O G s
 
90 - 01.07.19 - 13:52
(88) Слово предоставляется молчаливому бобу.
   АгентБезопаснойНацио
 
91 - 01.07.19 - 13:53
(88) ну уж до додуматься такого, как "копирование  в новый" - это надо под грибами думать...
   H A D G E H O G s
 
92 - 01.07.19 - 13:55
Гарри, а ты представляешь, как работает классический массив, как он лежит в памяти, как к нему прикрутить пометку на удаление и, самое главное, как потом сделать обращение по индексу?
   H A D G E H O G s
 
93 - 01.07.19 - 13:56
Есть же понимание, что для удаление через копирование понадобиться 2x памяти в короткий момент?
   Garykom
 
94 - 01.07.19 - 14:03
(92) А я что написал в (88) ?
Представляю и причем кучей разных способов с разными плюсами и минусами их.
   Garykom
 
95 - 01.07.19 - 14:04
(93) А думаем почему 1С память жрет как не в себя?
   H A D G E H O G s
 
96 - 01.07.19 - 14:09
(94) Массив в классическом ЯП - это кусок памяти с ячейками одинакового размера. Зная размер и номер ячейки - можно максимально быстро обратится к элементу массива. Вводя пометку на удаление, мы уже лишаемся этого.
   Garykom
 
97 - 01.07.19 - 14:10
(96) Кто мешает скопировать часть массива (кусок памяти) до удаляемого и часть после удаляемого элемента в новый кусок памяти - массив
   Garykom
 
98 - 01.07.19 - 14:11
(97)+ В Golang это слайсы по сути
   АгентБезопаснойНацио
 
99 - 01.07.19 - 14:12
(97)  с помощью двух спиц и катушек из под ниток из булки хлеба...©
   Garykom
 
100 - 01.07.19 - 14:13
(99) Получается язык Go за программинг на котором платят уже хорошие деньги
  1  2   

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