Java алгоритм шеннона фано

Алгоритм Шеннона-Фано

Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
3. Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
4. Шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень».

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева
3. Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок

Таким образом, видно, что алгоритм Хаффмана как бы движется от листьев к корню, а алгоритм Шеннона-Фано, используя деление, движется от корня к листям.

Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.

program ShennonFano; uses crt; const a :array[1..6] of char = ('a','b','c','d','e','f'); < символы >af:array[1..6] of integer = (10, 8, 6, 5, 4, 3); < частота символов > < Процедура для поиска кода каждой буквы >procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer); var dS:real; < Среднее значение массива >i, m, S:integer; < m - номер средней буквы в последовательности, S - сумма чисел, левой ветки >c_branch:string; < текущая история поворотов по веткам >begin < проверка если это вход нулевой то очистить историю >if (a<>' ') then c_branch := full_branch + branch else c_branch := ''; < Критерий выхода: если позиции символов совпали, то это конец >if (start_pos = end_pos) then begin WriteLn(a[start_pos], ' = ', c_branch); exit; end; < Подсчет среднего значения частоты в последовательности >dS := 0; for i:=start_pos to end_pos do dS:= dS + af[i]; dS := dS/2; < Тут какой угодно можно цикл for, while, repeat поиск середины >S := 0; i := start_pos; m := i; while ((S+af[i] SearchTree('1', c_branch, start_pos, m); < Правая ветка дерева >SearchTree('0', c_branch, m+1, end_pos); end; begin WriteLn('Press to show'); ReadLn; ClrScr; < Поиск кода Фано, входные параметры начало и конец последовательности >SearchTree(' ',' ', 1, 6); ReadLn; end; 

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

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Implementation of Shannon-Fano Coding (also Decoding) Algorithm.

License

recep-yildirim/Shannon-Fano-Algorithm

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

In this project, there are four files to do coding.

One of these files are Node.java file. This file contain the node properties, such as left child of the node or possibility of node’s key.

FileOperations.java file is also an utility file to doing file operations, such as read original file or write an object to specified file that you want.

Encode.java file is a leading file of this project. Because this is file which coding original file (This file is file.txt file. You can replace your file with it).

You can execute this file on your command line with the following commands:

Well, but how does it work? In other word how does Shannon-Fano Coding Algorithm work?

How does Shannon-Fano Algorithm work?

Shannon-Fano Coding Algorithm is a data compression algorithm. It uses entropy coding technique. That means for each letter can be represent with 0 and 1 as ASCII. But there is an import difference between ASCII and Shannon-Fano Algorithm. This difference is that ASCII table represents each symbol with a number according to its Alphabetical order. Shannon-Fano Algorithm represents according to frequency of this letter, in the whole file. To do this, Shannon-Fano Algorithm uses a tree.

We have a word that contain abcde letters and we want to coding this word. Frequency of this letters are;

At this point we should generate a balanced tree according as this freqeuncies and we have to sign left side of tree with zeros, right side of three with ones and also each subtree’s sides.

Finally we get codes for each letters.

If we had a word like aaabbccde, it was going to represent 00000001011010110111 or we had a word like bbccaaaed, it was going to represent 01011010000000111110.

End of all you will get a two file. First file is encoded file and second file is codes file.

Encoded file contains your compressed file and codes file contains each letter’s properties (node class) for using decoding operation.

Decode.java file do this decoding operation (It uses encode.txt and codes.bin files). To decode this encoded file, we are going to use codes in codes.bin file.

Our encoded file was 00000001011010110111 for aaabbccde. Let’s try turn this code to the original form.

Steps : 1- We begin first code.

2- We check code list to find letter which represent with our first code.

2.1- If there is no any letter that represent with our first code we take first two code and we turn step two. If still there is no, we take our first three code e.t.c.

2.2- If there is, we write our corresponding letter to the decode.txt file.

3- We remove codes that we have encoded and we continue through rest of codes.

We look at first code. First code is 0, but 0 not in our code list. Therefore, we look at first two code and this is 00. 00 equals a, thus our first letter a and we remove 00 from encoded file. Then again we look at first code and again first code not in the code list. Therefore, we look at first two code and first two code represent a. According as our first three letter aaa and we continue like that through encoded file.

End of the decoding, we get aaabbccde and our operation had finished.

To execute Decode.java file, write following commands on your command line:

You can also create documentation with the following commands:

javadoc **which file that you want to generate documentation** 

About

Implementation of Shannon-Fano Coding (also Decoding) Algorithm.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

F0RIS/ShannonFano-java-implementation

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Недавно искал для себя понятную реализацию данного алгоритма, но в итоге написал свою реализацию, кому нужно, пользуйтесь :) 

Some time ago searched for understandable implementation of this algorithm, in summary i wrote it by myself, if you need it, you can use it :) 

Источник