20. Suppose we have a compression f

20. Suppose we have a compression function c, which takes a bit
string s to a compressed string c(s).
(a) Show that for any integer N there must be a string s of length
N for which length(c(s)) ≥ N; that is, no effective compression
is done.
(b) Compress some already compressed files (try compressing
with the same utility several times in sequence). What
happens to the file size?
(c) Given a compression function c as in (a), give a function c′
such that for all bit strings s,length(c′(s)) ≤ min(length(c(s)),
length(s))+1; that is, in the worst case, compression with c′
expands the size by only 1 bit.
21. Give an algorithm for run length encoding that requires only a
single byte to represent nonrepeated symbols.
22. Write a program to construct a dictionary of all “words,” defined to
be runs of consecutive nonwhitespace, in a given text file.We

ผลลัพธ์ (ไทย) 1:

20. สมมติว่า เรามีการรวมฟังก์ชัน c ซึ่งใช้เวลาบิตสายอักขระ s เพื่อ c(s) บีบอัดสาย(ก) แสดงว่า มีจำนวนเต็ม N มีต้อง s สายอักขระความยาวสำหรับที่ length(c(s)) ≥ N; N กล่าวคือ ไม่บีบอัดที่มีประสิทธิภาพแล้ว(ข) การบีบอัดแฟ้มบางแฟ้มการบีบอัดแล้ว (ลองบีบอัดด้วยเดียวกันโปรแกรมอรรถประโยชน์หลายครั้งตามลำดับ) อะไรนะเกิดขึ้นกับขนาดของแฟ้มหรือไม่(ค) ได้รับการรวมฟังก์ชัน c เป็นใน (a), ให้ c′ ฟังก์ชันให้สำหรับทุกบิตสตริ s,length(c′(s)) ≤ min(length(c(s))length(s)) + 1 ที่อยู่ ในกรณีเลวร้ายที่สุด รวมกับ c′ขยายขนาด โดยเฉพาะ 1 บิต21. ให้เป็นอัลกอริทึมสำหรับการเข้ารหัสความยาวใช้งานที่ต้องการเท่ากับไบต์เดี่ยวเพื่อแสดงสัญลักษณ์ nonrepeated22. เขียนโปรแกรมสร้างพจนานุกรมของคำทั้งหมด" กำหนดให้สามารถทำต่อเนื่อง nonwhitespace ในแฟ้มข้อความที่กำหนด เรา

ผลลัพธ์ (ไทย) 2:

20.
สมมติว่าเรามีฟังก์ชั่นการบีบอัดคซึ่งใช้เวลาบิตของสตริงคสตริงบีบอัด(s).
(ก) แสดงว่าไม่มีจำนวนเต็มใด ๆ
จะต้องมีสตริงของความยาวไม่มีข้อความที่มีความยาว(c (s )) ≥ไม่มี;
ที่ไม่มีการบีบอัดที่มีประสิทธิภาพจะทำ.
(ข) การบีบอัดไฟล์บีบอัดแล้วบาง
(ลองอัดกับยูทิลิตี้เดียวกันหลายครั้งในลำดับ)
สิ่งที่เกิดขึ้นกับขนาดไฟล์?
(ค) กำหนดคฟังก์ชั่นการบีบอัดตาม (ก) ให้ฟังก์ชั่น c
'เช่นว่าทุกบิตสตริงs ยาว (ค' (s)) ≤นาที (ความยาว (c (s ))
ระยะเวลา (s)) + 1; นั่นคือในกรณีที่เลวร้ายที่สุดที่มีการบีบอัด c
'ขยายขนาดเพียง1 บิต.
21 ให้ขั้นตอนวิธีการเข้ารหัสสำหรับการทำงานที่ต้องใช้ระยะเวลาเพียงหนึ่ง
byte เดียวที่จะเป็นตัวแทนสัญลักษณ์ nonrepeated.
22 จงเขียนโปรแกรมเพื่อสร้างพจนานุกรมทั้งหมดเป็น "คำพูด"
กำหนดให้เป็นวิ่งnonwhitespace ติดต่อกันในข้อความ file.We รับ

ผลลัพธ์ (ไทย) 3:

20 . สมมติว่าเรามีการบีบอัดฟังก์ชัน C ซึ่งใช้เวลานิดหน่อย
String เพื่ออัดสาย C ( S )
( ) แสดงให้เห็นว่าเป็นจำนวนเต็มใด ๆต้องมีสตริงของความยาว
n สำหรับความยาวที่ ( c ( s ) ≥ N ; นั่นคือ ไม่มีการบีบอัดที่มีประสิทธิภาพ
คือ ทำ .
( b ) การบีบอัดบีบอัดแล้วไฟล์ ( ลองอัด
กับอรรถประโยชน์เดียวกันหลายครั้งในลำดับ ) สิ่งที่
ขึ้นกับขนาดไฟล์ ?
( ค ) ได้รับการบีบอัดในฟังก์ชัน c ( ) ให้ฟังก์ชัน C
เช่นสำหรับสตริงบิตนั้นทั้งหมด ความยาว ( C ได้รับ ( s ) ≤มิน ( ความยาว ( C ( s ) ) ,
ความยาว ( s ) 1 ; นั่นคือ ในกรณีที่เลวร้ายที่สุด การบีบอัด กับ C นั้น
ขยายขนาดเพียง 1 บิต
21 ให้อัลกอริทึมสำหรับการเข้ารหัสความยาวที่ต้องใช้เพียงไบต์เดียวเพื่อแสดงสัญลักษณ์ nonrepeated
.
22เขียนโปรแกรมเพื่อสร้างพจนานุกรมของ " คำ " ที่กำหนดไว้

จะวิ่งติดต่อกัน nonwhitespace ในไฟล์ให้ข้อความเรา