” 辅导COMP9319程序设计、 写作C/C++语言编程COMP9319 2021T2 Assignment 2: Searching Decoding BWT Encoded FileYour task in this assignment is to create a simple search program that implements BWT backward search, whichcan efficiently search a BWT encoded file. The program also has the capability to decode the BWT encoded fileback to its original file in a lossless manner. The original file (before BWT) contains text in multiple lines and mayinclude characters with ASCII values 10 and 32 to 126 (inclusively). There will be at least one newline character justbefore the end of file (to make sure that every line of text is ended with a newline character). Each line beginswith a line number. All line numbers of a file have the same number of digits (packed with leading zeros asappropriate).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 beavailable when we test your submission.Although you do not need to submit a BWT encoder, it is recommended that you will implement a simple BWTencoding program (this will help you in understanding the lecture materials and assist in testing yourassignment).Your C/C++ program, called bwtsearch, accepts an optional flag; the path to a BWT encoded file; the path to anindex file; and one quoted, non-empty query string as commandline input arguments. Using the given querystring, it will perform a backward search on the given BWT encoded file and output all the lines that contain theinput query string to the standard output. The search results are sorted according to their line numbers inascending order.Since each line is ended with a newline character, your output will naturally be displayed as one line (ending witha \n) for each match. No line will be output more than once, i.e., if there are multiple matches in one line, thatline will only be output once.If an optional flag -m is specified, given a query string, bwtsearch will output the total number of matchingsubstrings (count duplicates) to the standard output. The output is the total number, with an ending newlinecharacter. 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 filenameneeds to be specified, a reverse BWT is performed and the original file (before BWT) is output (created, oroverwritten 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 giveninput BWT file, plus an extra 2048 bytes. If your index file is larger than half of the size of the input BWT file plus2048 bytes, you will receive zero points for the tests that use that file. You may assume that the index file will notbe deleted during all the tests for a given BWT file, and all the test BWT files are uniquely named. Therefore, tosave time, you only need to generate the index file when it does not exist yet.ExampleConsider one of the given sample files tiny.bwt. You can find the file by logging into CSE machines and going tofolder ~cs9319/a2. The original file (tiny.txt) before BWT is also provided in that folder. The following are someexamples using tiny.bwt.%wagner bwtsearch -m ~cs9319/a2/tiny.bwt ./tiny.idx ana2%wagner bwtsearch -n ~cs9319/a2/tiny.bwt ./tiny.idx ana1%wagner bwtsearch ~cs9319/a2/tiny.bwt ./tiny.idx ana01 banana%wagner bwtsearch -m ~cs9319/a2/tiny.bwt ./tiny.idx erry3%wagner bwtsearch -n ~cs9319/a2/tiny.bwt ./tiny.idx erry3%wagner bwtsearch ~Cs9319/a2/tiny.bwt ./tiny.idx erry10 raspberry11 cherry13 blackberry%wagner bwtsearch -o ~cs9319/a2/tiny.bwt ./tiny.idx tiny.decoded.txt2021/7/4 COMP9319 2021T2 Assignment 2 httpss://www.cse.unsw.edu.au/~wong/cs9319-21a2.html 2/4%wagner diff ~cs9319/a2/tiny.txt tiny.decoded.txt%wagnerMore examples:%wagner bwtsearch -n ~cs9319/a2/6MB.bwt ./6MB.idx compilers1%wagner bwtsearch -m ~cs9319/a2/6MB.bwt ./6MB.idx compilers1%wagner bwtsearch -m ~cs9319/a2/6MB.bwt ./6MB.idx compiler8%wagner bwtsearch -n ~cs9319/a2/6MB.bwt ./6MB.idx compiler8%wagner bwtsearch ~cs9319/a2/6MB.bwt ./6MB.idx compiler020266 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 machines123034 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 pounds002001 the stake will be some 30,000 pounds; and for you, Jones, it will004503 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 pounds3%wagner bwtsearch -n ~cs9319/a2/sherlock.bwt ./SL.index ,000 pounds3%wagnerWe will use the make command below to compile your solution. Please provide a makefile and ensure that thecode you submit can be Compiled. Solutions that have compilation errors will receive zero points for the entireassignment.makeYour solution will be compiled and run on a typical CSE Linux machine e.g. grieg. Your solution should not writeout any external files other than the index file. Any solution that writes out external files other than the index filewill receive zero points for the entire assignment.PerformanceYour solution will be marked based on space and runtime performance. Your soluton will not be tested againstany BWT encoded files that are larger than 100MB.Runtime memory is assumed to be always less than 16MB. Any solution that violates this memory requirementwill receive zero points for that query test. Runtime memory consumption will be measured by valgrind massif withthe option –pages-as-heap=yes, i.e., all the memory used by your program will be measured. Your code may bemanually inspected to check if memory is allocated in a way that avoids the valgrind detection and exceeds theabove limit.Any solution that runs for more than 60 seconds on a machine with similar specification as grieg for the firstquery 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 bekilled, and will receive zero points for that query test. We will use the time command (i.e., /usr/bin/time) and countboth 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 assumethat at least one query will be run before hand for a given test file, and you will have up to 90 seconds beforeyour running process is killed.DocumentationAlthough the assignment is based on auto marking, your source code may be inspected and marks may bededucted if your code has poor readability and is very difficult to understand.2021/7/4 COMP9319 2021T2 Assignment 2 httpss://www.cse.unsw.edu.au/~wong/cs9319-21a2.html 3/4Notes1. Same as Assignment 1, it does not matter if your program needs to be executed as ./bwtsearch instead ofbwtsearch.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 lessthan 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 donot have write permissions.5. Marks will be deducted for the output of any extra text, other than the required correct answers (in the rightorder). This extra information includes (but not limited to) debugging messages, line numbers and so on. Asanity testscript based on some examples in this spec is available (so you can check that your output formatis correct). You can run the sanity testscript by:%wagner ~cs9319/a2/sanityRunning bwtsearch on tiny.bwt…Search 1 passedSearch 2 passedSearch 3 passedSearch 4 failedSearch 5 passedSearch 6 passedSearch 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 BWTfile ends with a newline char.7. Empty lines may exist in the original files (before BWT). However, these lines will never be matched duringsearching because the empty string will not be used when testing your program.MarkingThis assignment is worth 100 points (later scaled to 35% of the total for the course). Below is an indicativemarking scheme:Component PointsAuto marking (small test files up to 7MB) 60Auto marking (large test files up to 100MB) 40BonusBonus marks of 10 points will be awarded for the solution that achieves 100 points and runs the fastest overall forsearching (i.e., the shortest total time to finish all the backward search tests excluding those tests that index filesare expected to be generated). In addition, bonus marks of 5 points will be awarded for the solution that achieves100 points and runs the fastest overall for generating index (i.e., the shortest total time to finish all the backwardsearch tests in which index files are expected to be generated). Note: regardless of the bonus marks you receivein this assignment, the maximum final mark for the subject is capped at 100.SubmissionDeadline: Friday 30th July 17:00 (AEST). Late submissions will have marks deducted from the maximumachievable mark at the rate of 1% of the total mark per hour that they are late (i.e., 24% per day), and nosubmissions will be accepted after 3 days late.Use the give command below to submit the assignment:give cs9319 a2 makefile *.c *.cpp *.hNote 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.Plagiarism2021/7/4 COMP9319 2021T2 Assignment 2 httpss://www.cse.unsw.edu.au/~wong/cs9319-21a2.html 4/4The work you submit must be your own work. Submission of work partially or completely derived from any otherperson or jointly written with any other person is not permitted. The penalties for such an offence may includenegative marks, automatic failure of the course and possibly other academic discipline. Assignment submissionswill be examined both automatically and manually for such submissions.Relevant scholarship authorities will be informed if students holding scholarships are involved in an incident ofplagiarism 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 fromit is submitted you may be penalized, Even if the work was submitted without your knowledge or consent. Thismay apply even if your work is submitted by a third party unknown to you.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
