$30
Assignment 1 Move-to-Front Coding (MTF)
Software Engineering 265
Software Development Methods
Assignment 1
)
Programming environment
For this assignment please ensure your work executes correctly on the Linux
machines in ELW B238. You are welcome to use your own laptops and desktops for
much of your programming; if you do this, give yourself a few days before the due
date to iron out any bugs in the C program you have uploaded to the BSEng
machines. (Bugs in this kind of programming tend to be platform specific, and
something that works perfectly at home may end up crashing on a different
hardware configuration.)
Objectives of this assignment
• Understand a problem description, along with the role used by sample input
and output for providing such a description.
• Use the C programming language to write the first implementation of a file
encoder named “text2mtf” (and do this without using dynamic memory).
• Learn more about the ASCII encoding of text.
• Use Unix commands such as “diff” and “hexdump” to support your testing
and coding.
• Use git to manage changes in your source code and annotate the evolution of
your solution with “messages” given to commits.
• Test your code against the provided test cases.
Page 2 of 5
This assignment: “text2mtf.c”
Move-to-Front Coding (MTF) is an adaptive coding scheme sometimes used for
lossless compression of text. Words appearing frequently in a source file are
encoded with integers that are smaller than encodings for words appearing less
frequently. (An insight here is that fewer bits are needed to represent smaller
integers than larger integers, and we could exploit this as a form of compression.)
However, for this assignment all of our codes will be of the same size. If compression
is achieved then it will be the result of substituting a one-byte code for a multiplecharacter word. (In later assignments we will experiment with differing code
lengths.) In this assignment we are simply exploring MTF coding; if the resulting
files are smaller then that is a happy result.
MTF behaves in a manner similar to the way we might use a vertical stack of books.
If we need a book from the middle of the pile, we retrieve it and when finished put
the book back on top of the pile. The figure below shows a sequence of input words
(taken from Dr. Seuss’s “The Cat in the Hat”), along with the order in which words
appear in the word list after each input word is processed, and finally the output
generated by the encoding. Notice the cases when a word is moved from a position
within the word list to the top of that list.
When a new word appears in the input we (a) output the code corresponding to the
first unused position in the list and (b) follow this with characters in the word. A
decoder can read the output and not only build the word list on the fly, but also use
codes (i.e., the “5 5 3” sequence above) to retrieve a word already in the list. (Such a
code represents the position of the word in the list before it is moved to the top.)
Codes vs. characters?
The output in the figure above is a mixture of codes and characters. For this
assignment, however, we will make these assumptions:
• Only ASCII codes less than or equal to 127 can make up input words.
• ASCII codes greater than or equal to 128 will indicate output codes.
• An output code of i will be represented by ASCII character 128 + i.
i sat there with sally we sat there we two
i sat there
i sat
i
there
sat
i
with
there
sat
i
with
sally
there
sat
i
with
sally
we
there
sat
i
with
sally
we
there
sat
i
with
sally
we
there
sat
i
with
sally
we
there
sat
i
with
sally
we
two
1 i 2 sat 3 there 4 with 5 sally 6 we 5 5 3 7 two
input words
word list
output coding
Page 3 of 5
• Code numbering starts at 1 (i.e., the code 0 is never used) and the maximum
code value will be 120. This means our scheme will only be able to encode
files having at most 120 unique words (although those words may be
repeated throughout the text).
• No input word will be greater than 20 characters in length.
As the C language permits us to treats character values as integers, we can easily
perform arithmetic on ASCII codes.
Spaces and newlines?
The output in the figure is silent on what happens to spaces and newlines. For this
assignment we make these two assumptions:
• Spaces between words within the same line are implied in the output coding.
Therefore all inputs used for testing will only have single spaces between
words.
• New lines (i.e., the ‘\n’ character or ASCII 10 or 0x0a) appearing in the input
will be written to the output without any encoding.
Magic numbers
Although your assignment solution is only meant to provide an MTF encoding for a
test file (i.e., we will write a decoder in Assignment #2) we should somehow
indicate that our output file is special. We will do this with a magic number. This is a
byte sequence at the start of a file used to indicate that file’s type. (The Unix
command “file” utilizes magic numbers.) The four-byte sequence for our MTF magic
number files is 0xba 0x5e 0xba 0x11.
Our actual MTF encoding
The words in our example (i.e., the figure above) are contained in
/home/zastre/seng265/a1/tests/test00.txt and the MTF encoding following our
assumptions and descriptions at that same directory in test00.mtf. What follows is a
representation of the contents of test00.mtf (using the Unix utility hexdump):
$ ./text2mtf tests/test00.txt
$ hexdump -C tests/test00.mtf
00000000 ba 5e ba 11 81 69 82 73 61 74 83 74 68 65 72 65 |.....i.sat.there|
00000010 84 77 69 74 68 85 73 61 6c 6c 79 86 77 65 85 85 |.with.sally.we..|
00000020 83 87 74 77 6f 0a |..two.|
00000026
The 0x81 value appearing at byte 5 in the dump is the same as the decimal value
129, i.e., a code value of 1 to which was added 128. (One ASCII char equals one byte.)
At byte 5 is the ASCII character for “i”. The seventh byte is the code value for 2,
following which are the ASCII codes for “s”, “a” and “t”. Then follows more MTF
Page 4 of 5
codes and ASCII chars with values less than 128. Our example has only one line and
at byte 38 we see the newline character (ASCII 0x0a); other text files could have
multiple lines, and their resulting encodings reflect this (i.e., 0x0a at several places
in the hexdump output for that file’s MTF encoding).
Exercises for this assignment
1. If you have not already done so, ensure your git project is checked out from
the repository. Within the project create an “a1” subdirectory. Ensure all
directories and program files you create are placed under git control. (You
need not add the test directory to git control unless you wish to do so.) Test
files are available on ELW B238 machines in the directory
/home/zastre/seng265/a1/tests.
2. Write your program. Amongst other tasks you will need to:
• obtain a filename argument from the command line;
• create a new filename based on the old file name (i.e., replace “.txt”
ending the input filename with “.mtf” ending the output filename);
• read text input from a file, line by line, and the words within those lines
• write output to a file, char by char
• store words in a statically-allocated string table
3. Do not use “malloc”, “calloc” or any of the dynamic memory functions.
For this assignment you can assume that the longest input line will have 80
characters, and no input file will have more than 100 lines. No word will be
longer than 20 characters. There is no need for you to first read in the whole
input file before generating an encoding (but you should probably perform
the encoding input-line-by-input-line.)
4. Keep all of your code in one file for this assignment. In later assignments we
will use separable compilation available in C.
5. Use the test files to guide your implementation effort. Start with the simple
example in test 01 and move onto 02, 03, etc. in order. (You may want to
avoid test00 until you have significant functionality already completed.)
Refrain from writing the program all at once, and budget time to
anticipate when things go wrong! Use the Unix command diff to compare
your output with what is expected.
6. For this assignment you can assume all test inputs will be well-formed (i.e.,
our teaching assistant will not test your submission for handling of input or
for arguments containing errors). Later assignments might specify errorhandling as part of their requirements.
Page 5 of 5
What you must submit
• A single C source file named “text2mtf.c” within your git remote repository
(in the “a1” subdirectory) containing a solution to Assignment #1.
• No dynamic memory-allocation routines are to be used for Assignment
#1.
Evaluation
For this first assignment students will demonstrate their work to a member of the
course’s teaching team. Instructions on demo-slot signup will be provided a few
days before the due-date; each demo will require from 10 to 15 minutes.
Our grading scheme is relatively simple.
• “A” grade: An exceptional submission demonstrating creativity and initiative.
“text2mtf” runs without any problems. The program is clearly written and
uses functions appropriately (i.e., is well structured).
• “B” grade: A submission completing the requirements of the assignment.
“text2mtf” runs without any problems. The program is clearly written.
• “C” grade: A submission completing most of the requirements of the
assignment. “text2mtf” runs with some problems.
• “D” grade: A serious attempt at completing requirements for the assignment.
“text2mtf” runs with quite a few problems.
• “F” grade: Either no submission given, or submission represents very little
work.
