Кодирование фразы Методом Шеннона-фано и Хаффмена

@Yakov112 · Регистрация: 08.12.2011

Author24 — интернет-сервис помощи студентам

Привет всем))))
помогите мне написать программу,пожалуйста))))
мне необходимо написать программу на языке Visual Basic for Applications лучше в Excel про "кодирование фразы Методом Шеннона-фано и Хаффмена" например фразы

_ПАРК_БРОМ_БОРЩ_ЛУПА_ТРУД_

@gaw · 08.12.2011, 19:49

в каком объеме помощь то нужна

@Yakov112 · 08.12.2011, 20:34 **[ТС]**

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

@gaw · 08.12.2011, 20:40

если в

Сообщение от Yakov112

в программировании я ничего не смыслю

то и

Сообщение от Yakov112

то любой помощи

как таковой зачем
просто

Сообщение от Yakov112

буду рад готовой программе

кстати, кажется это два в одном надо

@Yakov112 · 08.12.2011, 20:48 **[ТС]**

ну немного я понимаю,но это очень-очень мало((((

да в чем заключается

два в одном

?

@gaw · 08.12.2011, 21:20

Сообщение от Yakov112

Методом Шеннона-фано и Хаффмена

вот буковка "И" тут скорей всегл указывает, что это 2 метода, хотя и очень похожи

@Yakov112 · 08.12.2011, 21:48 **[ТС]**

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

gaw, так ты мне можешь помочь с ее написанием???ПОЖАЛУЙСТА,ПОМОГИ

@Казанский · 08.12.2011, 22:14

Сообщение от Yakov112

лучше в Excel

Кодирование текста!

@YuraAAA · 08.12.2011, 22:15

ну раз

Сообщение от Yakov112

любой помощи

тогда
Допустим, у нас есть следующая таблица частот:
15 7 6 6 5
А Б В Г Д

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

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

Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.
А Б В Г Д
0 100 101 110 111

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д — наибольшим.

ну естественно, что таблица частот - скоолько раз встречается буква

@Yakov112 · 08.12.2011, 22:38 **[ТС]**

Казанский, а можно комментарии попросить? в программе что каждый процесс объясняет?

@gaw · 08.12.2011, 22:51

Казанский
а вот в коде по ссылке, там двоичные коды по какому приципу набраны

я знаком с методом, о котором говорил Юра, а тут что то не вруб

@Казанский · 08.12.2011, 22:52

Программа, как видите, не моя. В функции code каждая буква заменяется на соответствующую строку нулей и единиц. То есть считается, что дерево уже выращено

и закодировано.

@Yakov112 · 08.12.2011, 23:09 **[ТС]**

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

@gaw · 08.12.2011, 23:21

Сообщение от Казанский

дерево уже выращено

@Yakov112 · 08.12.2011, 23:49 **[ТС]**

gaw, не у оно то предполагаемо выращено,разве не так? а по методу то для каждого примера свое дерево,как я помню с пар,а тут не так вроде или я чего то не так понимаю

@gaw · 09.12.2011, 00:26

Сообщение от YuraAAA

Допустим, у нас есть следующая таблица частот:
15 7 6 6 5
А Б В Г Д

т.е. исходную фразу надо просчитать -- сколько раз в ней чего встречается
и получится вот такая таблица, понятно что для "коловорот" --- к-1 л-1 в-1 р-1 т-1 о-4
дальше надо считать вероятности к,л,в,р,т-1/9 о-4/9
в то же время для "колобок" это будет уже др таблица

@Yakov112 · 09.12.2011, 00:43 **[ТС]**

это я понимаю,но вот в программе куда этот поиск делся? там не ищется вероятность встречи букв, там сразу функцию запускают, хотя я еще не до конца разобрался и пока не понял все что там делается

@R Dmitry · 09.12.2011, 11:20

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

может кому и сгодиться

Visual Basic

Public Function codepass(st As String)
Dim i&
For i = 1 To Len(st)
codepass = codepass & Format((Asc(Mid(st, i, 1)) + 2) * 2 + i + Len(st), "00000")
Next
codepass = StrReverse(codepass)
End Function

Visual Basic

Public Function decodePass(st As String)
Dim i&, x&
st = StrReverse(st)
For i = 1 To Len(st) Step 5
x = x + 1
decodePass = decodePass & Chr((CLng(Mid(st, i, 5)) - x - (Len(st) / 5)) / 2 - 2)
Next
End Function

@Yakov112 0 / 0 / 1 Регистрация: 08.12.2011 Сообщений: 69
	08.12.2011, 23:09 [ТС]	13
	теперь стало понятнее что к чему, а как тогда составить код дерева кодирования,причем для каждой фразы свое? 0

@gaw 6644 / 1511 / 169 Регистрация: 09.01.2010 Сообщений: 4,298
	09.12.2011, 00:26	16
	Сообщение от YuraAAA Допустим, у нас есть следующая таблица частот: 15 7 6 6 5 А Б В Г Д т.е. исходную фразу надо просчитать -- сколько раз в ней чего встречается и получится вот такая таблица, понятно что для "коловорот" --- к-1 л-1 в-1 р-1 т-1 о-4 дальше надо считать вероятности к,л,в,р,т-1/9 о-4/9 в то же время для "колобок" это будет уже др таблица 0

@Yakov112 0 / 0 / 1 Регистрация: 08.12.2011 Сообщений: 69
	09.12.2011, 00:43 [ТС]	17
	это я понимаю,но вот в программе куда этот поиск делся? там не ищется вероятность встречи букв, там сразу функцию запускают, хотя я еще не до конца разобрался и пока не понял все что там делается 0

@gaw 6644 / 1511 / 169 Регистрация: 09.01.2010 Сообщений: 4,298
	08.12.2011, 19:49	2
	в каком объеме помощь то нужна 0

@Yakov112 0 / 0 / 1 Регистрация: 08.12.2011 Сообщений: 69
	08.12.2011, 20:34 [ТС]	3
	ну если возможно то буду рад готовой программе,а если нет,то любой помощи если честно то в программировании я ничего не смыслю а прогу нужно сдавать 0

@gaw 6644 / 1511 / 169 Регистрация: 09.01.2010 Сообщений: 4,298
	08.12.2011, 20:40	4
	если в Сообщение от Yakov112 в программировании я ничего не смыслю то и Сообщение от Yakov112 то любой помощи как таковой зачем просто Сообщение от Yakov112 буду рад готовой программе кстати, кажется это два в одном надо 0

@Yakov112 0 / 0 / 1 Регистрация: 08.12.2011 Сообщений: 69
	08.12.2011, 20:48 [ТС]	5
	ну немного я понимаю,но это очень-очень мало(((( да в чем заключается два в одном ? 0

@gaw 6644 / 1511 / 169 Регистрация: 09.01.2010 Сообщений: 4,298
	08.12.2011, 21:20	6
	Сообщение от Yakov112 Методом Шеннона-фано и Хаффмена вот буковка "И" тут скорей всегл указывает, что это 2 метода, хотя и очень похожи 0

@Yakov112 0 / 0 / 1 Регистрация: 08.12.2011 Сообщений: 69
	08.12.2011, 21:48 [ТС]	7
	возможно и разные но сходятся к одному конечно, а вот что касается разности кодов в программе это я уже не представляю gaw, так ты мне можешь помочь с ее написанием???ПОЖАЛУЙСТА,ПОМОГИ 0

@Казанский 15145 / 6418 / 1731 Регистрация: 24.09.2011 Сообщений: 9,999
	08.12.2011, 22:14	8
	Сообщение от Yakov112 лучше в Excel Кодирование текста! 1

@YuraAAA 1605 / 1337 / 291 Регистрация: 25.10.2009 Сообщений: 3,487 Записей в блоге: 2
	08.12.2011, 22:15	9
	ну раз Сообщение от Yakov112 любой помощи тогда Допустим, у нас есть следующая таблица частот: 15 7 6 6 5 А Б В Г Д Этот процесс можно представить как построение дерева, корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n0 потомков — символы из предыдущего шага и т. д. Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке. Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом. А Б В Г Д 0 100 101 110 111 Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством бит, а наиболее редкий символ Д — наибольшим. ну естественно, что таблица частот - скоолько раз встречается буква 1

@Yakov112 0 / 0 / 1 Регистрация: 08.12.2011 Сообщений: 69
	08.12.2011, 22:38 [ТС]	10
	Казанский, а можно комментарии попросить? в программе что каждый процесс объясняет? 0

@gaw 6644 / 1511 / 169 Регистрация: 09.01.2010 Сообщений: 4,298
	08.12.2011, 22:51	11
	Казанский а вот в коде по ссылке, там двоичные коды по какому приципу набраны я знаком с методом, о котором говорил Юра, а тут что то не вруб 0

	09.12.2011, 11:20

Опции темы

@Казанский 15145 / 6418 / 1731 Регистрация: 24.09.2011 Сообщений: 9,999
	08.12.2011, 22:52	12
	Программа, как видите, не моя. В функции code каждая буква заменяется на соответствующую строку нулей и единиц. То есть считается, что дерево уже выращено и закодировано. 1

@gaw 6644 / 1511 / 169 Регистрация: 09.01.2010 Сообщений: 4,298
	08.12.2011, 23:21	14
	Сообщение от Казанский дерево уже выращено 0

@Yakov112 0 / 0 / 1 Регистрация: 08.12.2011 Сообщений: 69
	08.12.2011, 23:49 [ТС]	15
	gaw, не у оно то предполагаемо выращено,разве не так? а по методу то для каждого примера свое дерево,как я помню с пар,а тут не так вроде или я чего то не так понимаю 0