代写COMP9319程序设计、代做C/C++语言编程

日期：2021-07-06 10:49

COMP9319 2021T2 Assignment 2: Searching &

Decoding BWT Encoded File

Your task in this assignment is to create a simple search program that implements BWT backward search, which

can efficiently search a BWT encoded file. The program also has the capability to decode the BWT encoded file

back to its original file in a lossless manner. The original file (before BWT) contains text in multiple lines and may

include characters with ASCII values 10 and 32 to 126 (inclusively). There will be at least one newline character just

before the end of file (to make sure that every line of text is ended with a newline character). Each line begins

with a line number. All line numbers of a file have the same number of digits (packed with leading zeros as

appropriate).

Sample input files (BWT encoded) have been provided in the folder ~cs9319/a2. To help in testing your program,

the corresponding original files (after reverse BWT) are also included in that folder. These original files will not be

available when we test your submission.

Although you do not need to submit a BWT encoder, it is recommended that you will implement a simple BWT

encoding program (this will help you in understanding the lecture materials and assist in testing your

assignment).

Your C/C++ program, called bwtsearch, accepts an optional flag; the path to a BWT encoded file; the path to an

index file; and one quoted, non-empty query string as commandline input arguments. Using the given query

string, it will perform a backward search on the given BWT encoded file and output all the lines that contain the

input query string to the standard output. The search results are sorted according to their line numbers in

ascending order.

Since each line is ended with a newline character, your output will naturally be displayed as one line (ending with

a '\n') for each match. No line will be output more than once, i.e., if there are multiple matches in one line, that

line will only be output once.

If an optional flag -m is specified, given a query string, bwtsearch will output the total number of matching

substrings (count duplicates) to the standard output. The output is the total number, with an ending newline

character. Similarly, bwtsearch will output the total number of unique matching records (do not count duplicates)

if -n is specified. If -o is specified, no query string is required in the commandline. Instead, a output filename

needs to be specified, a reverse BWT is performed and the original file (before BWT) is output (created, or

overwritten if already exists) to the specified output file.

Your solution can write out one external index file at any time that is no larger than half of the size of the given

input BWT file, plus an extra 2048 bytes. If your index file is larger than half of the size of the input BWT file plus

2048 bytes, you will receive zero points for the tests that use that file. You may assume that the index file will not

be deleted during all the tests for a given BWT file, and all the test BWT files are uniquely named. Therefore, to

save time, you only need to generate the index file when it does not exist yet.

Example

Consider one of the given sample files tiny.bwt. You can find the file by logging into CSE machines and going to

folder ~cs9319/a2. The original file (tiny.txt) before BWT is also provided in that folder. The following are some

examples using tiny.bwt.

%wagner> bwtsearch -m ~cs9319/a2/tiny.bwt ./tiny.idx "ana"

2

%wagner> bwtsearch -n ~cs9319/a2/tiny.bwt ./tiny.idx "ana"

1

%wagner> bwtsearch ~cs9319/a2/tiny.bwt ./tiny.idx "ana"

01 banana

%wagner> bwtsearch -m ~cs9319/a2/tiny.bwt ./tiny.idx "erry"

3

%wagner> bwtsearch -n ~cs9319/a2/tiny.bwt ./tiny.idx "erry"

3

%wagner> bwtsearch ~cs9319/a2/tiny.bwt ./tiny.idx "erry"

10 raspberry

11 cherry

13 blackberry

%wagner> bwtsearch -o ~cs9319/a2/tiny.bwt ./tiny.idx tiny.decoded.txt

2021/7/4 COMP9319 2021T2 Assignment 2

https://www.cse.unsw.edu.au/~wong/cs9319-21a2.html 2/4

%wagner> diff ~cs9319/a2/tiny.txt tiny.decoded.txt

%wagner>

More examples:

%wagner> bwtsearch -n ~cs9319/a2/6MB.bwt ./6MB.idx "compilers"

1

%wagner> bwtsearch -m ~cs9319/a2/6MB.bwt ./6MB.idx "compilers"

1

%wagner> bwtsearch -m ~cs9319/a2/6MB.bwt ./6MB.idx "compiler"

8

%wagner> bwtsearch -n ~cs9319/a2/6MB.bwt ./6MB.idx "compiler"

8

%wagner> bwtsearch ~cs9319/a2/6MB.bwt ./6MB.idx "compiler"

020266 Verification of the C0 compiler implementation on the source code level.

021834 A framework for intelligent speculative compiler optimizations and its application to memory accesses.

035239 A compiler backend for generic programming with arrays.

044877 C compiler aided design of application specific instruction set processors using the machine description language LISA.

052175 Semantics-directed generation of compilers and abstract machines

123034 Evaluating compiler technology for control-flow optimizations for multimedia extension architectures.

123777 Design and implementation of a queue compiler.

125902 Hardware-compiler co-design for adjustable data power savings.

%wagner>

%wagner> bwtsearch ~cs9319/a2/sherlock.bwt ./SL.index ",000 pounds"

002001 the stake will be some 30,000 pounds; and for you, Jones, it will

004503 of some 14,000 pounds, which lay to his credit at the bank."

010537 50,000 pounds at once. I could, of course, borrow so trifling a

%wagner> bwtsearch -m ~cs9319/a2/sherlock.bwt ./SL.index ",000 pounds"

3

%wagner> bwtsearch -n ~cs9319/a2/sherlock.bwt ./SL.index ",000 pounds"

3

%wagner>

We will use the make command below to compile your solution. Please provide a makefile and ensure that the

code you submit can be compiled. Solutions that have compilation errors will receive zero points for the entire

assignment.

make

Your solution will be compiled and run on a typical CSE Linux machine e.g. grieg. Your solution should not write

out any external files other than the index file. Any solution that writes out external files other than the index file

will receive zero points for the entire assignment.

Performance

Your solution will be marked based on space and runtime performance. Your soluton will not be tested against

any BWT encoded files that are larger than 100MB.

Runtime memory is assumed to be always less than 16MB. Any solution that violates this memory requirement

will receive zero points for that query test. Runtime memory consumption will be measured by valgrind massif with

the option --pages-as-heap=yes, i.e., all the memory used by your program will be measured. Your code may be

manually inspected to check if memory is allocated in a way that avoids the valgrind detection and exceeds the

above limit.

Any solution that runs for more than 60 seconds on a machine with similar specification as grieg for the first

query on a given BWT file will be killed, and will receive zero points for the queries for that BWT file. After that,

any solution that runs for more than 15 seconds for any one of the subsequent queries on that BWT file will be

killed, and will receive zero points for that query test. We will use the time command (i.e., /usr/bin/time) and count

both the user and system time as runtime measurement.

When testing for reverse BWT (i.e., decoding the BWT encoded file back to the original text file), you may assume

that at least one query will be run before hand for a given test file, and you will have up to 90 seconds before

your running process is killed.

Documentation

Although the assignment is based on auto marking, your source code may be inspected and marks may be

deducted if your code has poor readability and is very difficult to understand.

2021/7/4 COMP9319 2021T2 Assignment 2

https://www.cse.unsw.edu.au/~wong/cs9319-21a2.html 3/4

Notes

1. Same as Assignment 1, it does not matter if your program needs to be executed as ./bwtsearch instead of

bwtsearch.

2. To avoid a long output time, none of the testcases for marking will result in outputting more than 500 lines.

3. A line in the original file will not be unreasonably long, e.g., you can safely assume that a line is always less

than 500 chars.

4. The input filename is a path to the given BWT encoded file. Please open the file as read-only, in case you do

not have write permissions.

5. Marks will be deducted for the output of any extra text, other than the required correct answers (in the right

order). This extra information includes (but not limited to) debugging messages, line numbers and so on. A

sanity testscript based on some examples in this spec is available (so you can check that your output format

is correct). You can run the sanity testscript by:

%wagner> ~cs9319/a2/sanity

Running bwtsearch on tiny.bwt...

Search 1 passed

Search 2 passed

Search 3 passed

Search 4 failed

Search 5 passed

Search 6 passed

Search 7 failed

%wagner>

%wagner> cat ~cs9319/a2/sanity

...

You can check the detail of each test by the cat command as shown above.

6. You can assume that every line (including the last line) of the original file corresponding to the input BWT

file ends with a newline char.

7. Empty lines may exist in the original files (before BWT). However, these lines will never be matched during

searching because the empty string will not be used when testing your program.

Marking

This assignment is worth 100 points (later scaled to 35% of the total for the course). Below is an indicative

marking scheme:

Component Points

Auto marking (small test files up to 7MB) 60

Auto marking (large test files up to 100MB) 40

Bonus

Bonus marks of 10 points will be awarded for the solution that achieves 100 points and runs the fastest overall for

searching (i.e., the shortest total time to finish all the backward search tests excluding those tests that index files

are expected to be generated). In addition, bonus marks of 5 points will be awarded for the solution that achieves

100 points and runs the fastest overall for generating index (i.e., the shortest total time to finish all the backward

search tests in which index files are expected to be generated). Note: regardless of the bonus marks you receive

in this assignment, the maximum final mark for the subject is capped at 100.

Submission

Deadline: Friday 30th July 17:00 (AEST). Late submissions will have marks deducted from the maximum

achievable mark at the rate of 1% of the total mark per hour that they are late (i.e., 24% per day), and no

submissions will be accepted after 3 days late.

Use the give command below to submit the assignment:

give cs9319 a2 makefile *.c *.cpp *.h

Note that the give command is available on any CSE linux machines (such as wagner) but not on grieg. Finally,

please use classrun to check your submission to make sure that you have submitted all the necessary files.

Plagiarism

2021/7/4 COMP9319 2021T2 Assignment 2

https://www.cse.unsw.edu.au/~wong/cs9319-21a2.html 4/4

The work you submit must be your own work. Submission of work partially or completely derived from any other

person or jointly written with any other person is not permitted. The penalties for such an offence may include

negative marks, automatic failure of the course and possibly other academic discipline. Assignment submissions

will be examined both automatically and manually for such submissions.

Relevant scholarship authorities will be informed if students holding scholarships are involved in an incident of

plagiarism or other misconduct.

Do not provide or show your assignment work to any other person - apart from the teaching staff of this subject.

If you knowingly provide or show your assignment work to another person for any reason, and work derived from

it is submitted you may be penalized, even if the work was submitted without your knowledge or consent. This

may apply even if your work is submitted by a third party unknown to you.