Damaged BZip Files Are Difficult to Repair

摘要：

bzip is a program written by Julian Seward that is often used under Unix to compress single files. It splits the file into blocks which are compressed individually using a combination of the Burrows Wheeler-Transformation, the Move-To-Front algorithm, Huffman and Runlength encoding. The author himself stated that compressed blocks that are damaged, i.e., part of which are lost, are essentially nonrecoverable. This paper gives a formal proof that this is indeed true: focusing on the Burrows-WheelerTransformation, the problem of completing a transformed string, such that the decoded string obeys certain file format restrictions, is NP-hard.

作者: Christian Hundt Ulf Ochsenfahrt

作者单位: Fakultat fur Informatik und Elektrotechnik, Universitat Rostock, Germany Fakultat fur Informatik und Elektrotechnik,Universitat Rostock, Germany

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 12-21

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）