close

Вход

Забыли?

вход по аккаунту

...called for multiple programs that could interface with some

код для вставкиСкачать
Since the specifications called for multiple programs that could interface with
some of the same subroutines, I decided that it’d be best to create a library
module of all the Huffman encoding/decoding subs, functions, and data types.
Then, I could just call the subroutines from multiple test programs as needed.
My intent is to make these subprograms as efficient and modular as possible.
Unlike the build table program presented in class, I felt it was necessary to read
in all characters in a file, particularly linefeed and carriage-return characters. To
do this, I just open the file with direct access and a record length of 1 byte.
However, this is obviously incapable of correctly reading multibyte encoding
schemes. But, it should be robust enough for the given purposes.
To code the build_tree function, I first examined the illustrations in the book to
see if I could get any hints. I noticed almost immediately that the number of
parent nodes is always equal to the number of distinct characters minus 1. Since
I then knew exactly the number of nodes that could be in play and exactly the
number of steps to finish, I created an array of pointers to possible nodes that
would make searching easier (of size (distinct character count * two) - 1). Merely
testing pointer association will tell if a node is viable or still free. Once a node is
used as a child in the tree, its search table pointer is nullified.
Using the tree to generate the codes is fairly straightforward recursion. One
interesting problem does come up, though: how to get the tree nodes back into
an array. Certainly, the tree can’t be used when encoding a file. However, there
seems to be no elegant way to accomplish this but rather just to pass along a
pointer to an array through the whole recursion process.
Sadly, this is the point at which I realized that the program would only pretend to
do Huffman encoding. Since Fortran could only write raw bits incorporating
some hacks (like writing an integer with the same bit pattern as 16 bits of the
code), this omission is probably a good idea. The source text file was 2,337
bytes in size, which multiplied by 8 (to account for the pretend Huffman
encoding) is 18,696 bytes. The Huffman encoded file was 11,988 bytes or 64%
of the “original” file size.
The decode subprogram is incomplete. It only reads in the Huffman codes.
Instead of building a tree as in the book, I was planning on comparing the input
character array to substrings of the Huffman codes for matching. I believe
Fortran has functions for this, but its support for strings is by far the worst of any
language I’ve used, so it may still fail.
For some reason, I can’t connect to Delphi today. Previously, I had some
problems building the tree when compiled in GNU Fortran and run on Linux. It
wasn’t obvious where the logic was failing, however. Thus, I would recommend
testing on the Absoft compiler under Windows, if available.
A simple test file:
aaa
bb
cc
ddd
eeeee
The output from the build_table function (first two chars are LF and CR):
4 0.173913
4 0.173913
a 3 0.130435
b 2 8.695652E-02
c 2 8.695652E-02
d 3 0.130435
e 5 0.217391
The output from the build_tree function:
110
111
a
100
b
010
c
011
d
101
e
00
The encoded file:
10010010011111001001011111001101111111010110110111111000000
00000
Encoded file with LF and CR replaced:
100100100
010010
011011
101101101
0000000000
The large test file:
Puevf Unecre
Phone: 989-190-3259
Web: www.snakebytestudios.com
Email: [email protected]
Address: 876 Qnqr Fg. Perjr, IN 78485
Career Objective
To design user-friendly, yet feature-rich applications and systems that maintain resource
efficiency.
Key Qualifications
Programming
* Exceptional algorithm design capabilities that focus on efficient use of resources with
the best responsiveness for the user.
* At least 6 years of practical experience designing and implementing applications for a
variety of uses.
* Ability to adapt easily to new languages and technology.
Design
* Perpetual concern for the intuitiveness of user interfaces.
* At least 8 years of experience designing my personal website, always with pure code.
* At least 6 years of experience authoring impressive yet functional digital media,
including images, video, and audio.
Ambition
* Driven by the challenge to overcome the inherent difficulties in computing.
* Motivated with the desire to be better than the competition.
* Willing to go the extra mile when projects demand it.
Education
Associate, General Studies
2005
Southside Virginia Community College, Keysville, VA.
Graduated Magna Cum Laude.
B.S., Computer Science
Longwood University, Farmville, VA.
Senior Status. Expected Graduation in 2008.
Skills
* Programming: Visual Basic (6/.NET), C/C++, Java, TI-Basic
* Libraries/APIs/Etc: Windows APIs (kernel, shell, registry), DirectX 8/9, FMOD,
Threading, XML, Regex
* Web Programming: HTML, CSS, JavaScript, Perl, PHP, MySQL, Flash (ActionScript), SSI,
RSS
* Digital Media: Sound Editing (Adobe Audition), Image Editing (Corel Paint Shop Pro),
Video Editing/Production (Sony Vegas Video/Apple iMovie/DivX), Disc Authoring (Ahead
Nero/Indigo Rose Autoplay Menu Studio/Installshield)
* Office Productivity: Word, Excel, Access, PowerPoint, Outlook
* Platforms: Windows 3.1/9x/2000/XP, Linux Redhat, Mac OS9, MS-DOS
* Networking: Cisco CCNA course and personal experience with TCP/IP, UDP, IPX, routing,
Ethernet networks, wireless, FTP, HTTP, SSH, Telnet, OSI Model, EIA/TIA-232/449 wiring
Honors
* Longwood University. 1 of 10 students awarded - Transfer Student Scholarship
* Boy Scouts of America - Eagle Scout Rank
* Big Huge Games' Rise of Legends - Beta Tester
The Huffman Codes for the large test file
'
(
)
*
+
,
.
/
0
1
2
3
4
5
6
7
8
9
:
@
A
B
C
D
E
F
G
H
I
J
K
L
9
10
13
32
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
64
65
66
67
68
69
70
71
72
73
74
75
76
01011110
00100
00101
100
01111111010
111111110
111111111
1011010
0111111000
111110
10111000
1100100
0111110
10110111
000111010
00011000
110011110
101111101
0001101101
000110111
01111111011
000111001
101111100
10111010
0001101100
1100101
110011111
0111010
10111001
11111110
000111011
011101110
00011001
11001110
0111111001
0111111010
01011111
M
N
O
P
Q
R
S
T
U
V
W
X
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
r
s
t
u
v
w
x
y
77
78
79
80
81
82
83
84
85
86
87
88
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
114
115
116
117
118
119
120
121
10111111
011101111
00011010
1100110
0111111011
111111000
011100
11111101
000111000
01110110
111111001
011111111
11101
0001111
01100
01010
1101
000100
111100
101100
1010
0111111100
10110110
01101
010110
0000
0011
011110
11000
11100
0100
111101
0101110
1011110
10111011
000101
The final Huffman encoded large test file:
01110101011001100010101110010000011001111011100001111011011100000101001000010100100110011
01011000011000011011011101010010111110111001111010111110110111000000110111101111101000110
11011011100000011100101111111011101101111011111010101111000101001001111110011101000111110
11101010010111101011110101111011001001110000001110110110110110100011110001010100110111100
01001111010101010100011111001100100011000011010110010111100010100100111111100101101110110
10011011011101010011100000011101101101101101000110110011100000011101101101101101000111100
01010100110111100010011110101010101000111110011001000110000110101100010100100110010101010
01010110001101111001110010111010100110011110000110000001110101001011100111101010101101100
01110001001100100100011101011000110110111101101111110100011101101100101100000110001100111
10101111100110011110101101110010100100001010010000101001000111010111011100011011101110001
00000110100001111011111110011010110001001010010111011010010100100111111010011100010101101
11100101011110000001001111011110011011100010111000000100110001010110100000101001101000101
11111010000010111010100100000100110111101010011110111000110110111000110001010011001011001
00111010111100111100110110100110011101010010100011000011100100111010000010101001110000010
11110001001101010110111001000100101100111010100100010110111011010000001001110110100000100
11000110111100001111110111000011001101100110100010000010010100110010101101000001100000101
11001000010100100001010010000101001000111111010110100010110001111110111111011110101101101
00001001010011001110101001010001100001110000101001001100110110000011111100110001110101011
00101101010000011110000101001001011010100111111101011101101100110101111001001010001100001
11010110110011101011011111000011110001010010010110001011010001010110111100101011110000001
00011001110101111011101000111110100110110100100101011011110010001001011001110101001000001
00001101100111101111001000011000010011010001000001001010011001010110100000100100111101111
00110110000110001001001100011011110000111111011100001100110111100100101111010100100101100
10001001011001101100000111111011110001001001100011011110001111000110000111001010010111011
01000011011110011100100000100001111000100010010110011011001111011110011011100011001000010
10010010110101001100101010010001101110111101111000100100000110111100000101110111101110001
11001000011000100100011110110001110101100010010100110011101011011001101101110110111101101
11000101011010000011001101100010101101111001010111100000010100000111100100111010000010101
00101001011001111001101110101011011010000010010100000111100100111010111100111100110110100
11001110101001010001100001110010000010000111100010011101100010111011101110001010110101000
00101100001100010010011110111100110111100110010000101001001011010100110010100011111010011
01101001000001011000100001110011101010101110101111001001001101111011110010100110100010110
00100001110000001101101111010001101111010000111100111101111011111001101111001001110100000
10101000100110101100101100000000110110100111111000001011100100001010010000101001001011100
11101111001010111100000000101001001011010100110011011011100001111011010100111101111010110
11000110000110000011001101110000000100000100001111000100010010110011011001010000001001111
01101001001010010111011010000110111100111001000011000100100111101111001101110001001010000
00100110111000000100111010110011011110011001000010100100101101010011001010100100011011101
11101111000100100000111001100000101110111101110001110010000110001001001101101110110111101
10111000101011010000011001101100010101101111001010111100000010100000111100100010110000101
10001111011011100011100001100001110101101100101111011010001111111001010010011011111101001
11010110110111101110100010111100100101111010100100101100100011110111101110001101100011000
01101010110111001000010100100101101010011001010100100011011101111011110001001000001101111
00000101110111101110001110010000110001001001101101110110111101101110001010110100000110011
01100111011111010100101100001111000101000001111001001010010110011110110001101111001110010
10010111011011000001011101010010000010011110100000110001001010001100001110101101100010101
01011110010100100111010110110001011011010101010101110111111010010100000011000110111110101
01010100000111100100101001011011101111100110111100111110100010111010100101011010011111110
10011101000001010100111011111010101010100011110010000101001000010100100110010101011000011
11101001001010001100000010100100101101010010111001110001010010111011010000100000111100010
11000100101100110110001100101100111010110101101110100001111001101100010000111000011010111
01101110000110000110101101101100010010110011011001010000010110011011100011010000010010001
01010100001000001001010011001111010110101001010110111100100101000001000110000110101100111
10111101010010100000111100110010000101001001011010100101111110011010010100101110111010100
11010101010010111101010010010110010001001011001101100010101101111001010110001101100010000
11100000111111011000001111110101000100110111000100010010110011101000010001001011001101100
01100001101011001111011010100101001001010001100001100100001010010010110101001111110011010
01101011011010000011110010001000011100111100001110001001011001101100110110111011010011000
11101100010110101001101110110010111101011001101000010001111011000001101111111001101011000
10011100100010101101010110111010000010101001010010011001000010100100001010010000101001001
11111100101011110101100111010100101000110000010111100010100100110010111100111000011011001
01011101010011011111101000111011101101000011011100011101011011000111000100111101010101010
11011110001011110000110001011011110110111000110110100101001000111000011111101010010110011
10010100101011011000111011010101100011110010100000101011101100011101000110101100101101111
01000010100100000101100011101000110110101101110111110011011111101000111111010110100010111
10001011101010011010110111011111101000111011011001011100100100001010010001110111011000111
01010101111011110101001101010101001011111111101111100000011101100011101011110101011010001
01111111101111101010101101110010000101001000010100100110011111110010001110011001001111101
00011101000110101100111101111010100110111000100011100011001010110100000110011010101111000
10100100010111110011000011110010111100011001101010100000111000000010100101110110111000111
00101001000001011111101000001110111110111000010110010111010100110101101110111111010001110
11011001011100100100001010010001110011010000101000111100010001110001001110101001111011110
01100100100111111101011101101111011010110001001101010101000111011101100011101010101111011
11010100101000110000100101000001000001100010110111101101110001110011100100001010010000101
00100001010010001110010110110101001101011011110001011110010111100010100100101101010011001
10110000011111100110001110101011001011010100000111100101110101001000111011010101110011110
11110101101100110011111111011110010100110010011111111000011011101111101100100011101111111
11110111111011111111111111101000111010011111001110100111111000011111100011111010001111110
01111010101110111011111101001111110111001110101110001100111111110111100101001100001010010
01011010100010111111010000111111000111011100010101101111000111110110010111001101100111011
10001111101111111001000110010111010100111111001101000000101000111011110111001001100101110
01101100111011100100111111110101101101101110000000110101101111110100111001011001101011010
11011111101001100011011111001010111000100110000001011111111111111101001011100110101100011
01011000100011111111100000111001011111010111110011111010000011101110111111000110101011100
11111101001111110110110011000110111101010101010000011110011111010001111111110111111010111
11111110100111111000110111110011011011101100101001001011010100111111001110100011111001100
11011000001111110011000111010101100101101010000011110010111010100100000110011111110110111
11101011111111110100011101001110001110011111010001111110011110101011101110101110001100110
00101001111001001111101001100110110111000011011111101001100110000110011100110111110100101
11111000101011100011111101101011111111110100000111011011011110111100101100100111111110110
01010110001001010001100000111000110011000101001111001001111111111111101000111000111001100
11101111101001111110000111000111000010100100101101010010111001101011110010100100111010110
11001011111111010101010101110110111010100100011100001111110100000101010011111110010101010
01001010000011110010011111111011001010101000110001111110110011001011111010101010100100101
00011000011111111111111010011001110010110111011111001101100111111100101010100100101000001
11100100111111110011101000111100011010110110011001101110110100000010010001110010110000110
11110100110011011000001111111111111111010001110110101001010110100111001111111001010101001
00101000001111000111110110011011000001101010111101011000100101000110000100111111110011100
00110000000101100011101101101111100111011110010001110110101001010110100110111110110010101
11100111100110111011001010101111110011010111010101101011111010111001101001011100111111111
11111111111110100101110011010111000110010011001011111010100101100001111000101000001111001
00111111110110010110110011011110101010100011101111110111000001101111101100111000000101010
10111100001110011111100000111110011011001100101111101010000110111100110111101000101100101
11111110100001111011000111000100111101010101010001101111101100111000001110001001110101101
01101111001011001010110101101010101111111110010100100101101010000011010000100000100101001
10011011001100110110000011010101111010110001001010010111010100100000101101110101001001111
11001001111000010101111101001111111010111011011001101011011111101001100101011000110011011
11001110011111010011001100011101111011011100011001100011101000000100111110100000110101111
01010001101001100111011011000101001001011010100110011001101111010100000100001111000010110
11100101110101001001111110011010000001010001110111101110010011001111011001000001110100111
11010111110010111011011111000011000101101111011011110110111011111001111111111001101111101
00010111111010000011110110111011100111111000110101010101100111010100111110100101111111110
10110010000011010011100101111100111110100101111110111001011100010111001000110100111000010
10010010110101000111011111101010010111100011110001011011010100000111100101110101001000111
01010101110001100001110001110100111010011101111110010110001100001111110111000111001101100
11101000001010100011110110111000111000011000011101011011001101101110110111101101110001010
11010000011001101100101111010100100101100100111111010111010110011001111101100111011001101
11110100000111000101110011100110111110100110011101100110011111111111110100110000011111101
01001010000011110011111010011111110010010110011011100000001101010010000001101010010111100
01111000101101101110011111010010111101010110001101011011101111001110011111010000011101111
11110111001101111101000001100111111101111111011100110111110100011100011100000110011111101
00111111011101011010000110101001111101000001101001110011001110100101111110011010101101011
01111110100111111101100111011001010111110111111011100111011001011011100000011000110011110
00011000011111010111110110111110110111110010010111101010110001010000011110000101001000010
10010000101001000001100100110000001111000111000101111001011110001010010010110101000101111
10011000011110010111100011001101010100000111000000010100101110110111000111001010010000010
11100100100000111010100001100010010000011101010110111100111000100111101010101101000001001
11001001110110111101110111000010101101010101001011100010011111101110001110100001110000010
01101110001000111000100111101010101101000001001000111000110010110000110110111101110001110
01011001010011110001010010010110101001100111110011000101100011100011000011111101010011100
10000110001001001100101010110110111000101001100111011001011100010011111110111011111000110
11101100011100011000011111101010010011111100011101000010110110001010010010110101001100111
11101011110010000011001111101111100110110001110111011101010110110111100011111110101001111
11000101011100110110000110001001000101111111011111001101000001010111001001011100010011001
11111101010011101100111111011101111000100110111000
1/--страниц
Пожаловаться на содержимое документа