Nén ngây thơ
sử dụng mã độ dài tiền tố
Chúng tôi sẽ thực hiện nén văn bản (chuỗi, mảng / danh sách ký tự / byte) bằng cách thay thế đơn giản từng ký tự bằng mã nhị phân, dựa trên tần suất của ký tự đó trong văn bản. Các ký tự xuất hiện thường xuyên hơn sẽ được thay thế bằng các mã ngắn hơn. Dãy bit kết quả sẽ được chia thành các đoạn có độ dài 8.
Mật mã
Độ dài tiền tố Mã có độ dài 3 là mã bao gồm tiền tố - 3 bit cho biết độ dài của trường theo sau và một trường. 3 bit là đủ cho 8 (2 ^ 3) tiền tố khác nhau. Mỗi tiền tố nlần lượt mô tả 2 ^ n trường khác nhau, được liệt kê từ 0 đến 2 ^ n-1.
n = 0; 1 mục nhập (2 ^ 0)
000 – field with length 0;
n = 1; 2 mục nhập (2 ^ 1)
001|0 (`|` is put for clarity)
001|1
n = 2; 4 mục nhập (2 ^ 2)
010|00
010|01
010|10
010|11
…
n = 7; 128 mục nhập (2 ^ 7)
111 | 0000000 111 | 0000001 111 | 0000010 … 111 | 1111111
Đây là bảng tất cả các mã, được liệt kê từ 0 đến 254
┌──┬────────┬─────────┬─────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ │0 │32 │64 │96 │128 │160 │192 │224 │
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│0 │000 │10100001 │110000001│110100001 │1110000001│1110100001│1111000001│1111100001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│1 │0010 │10100010 │110000010│110100010 │1110000010│1110100010│1111000010│1111100010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│2 │0011 │10100011 │110000011│110100011 │1110000011│1110100011│1111000011│1111100011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│3 │01000 │10100100 │110000100│110100100 │1110000100│1110100100│1111000100│1111100100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│4 │01001 │10100101 │110000101│110100101 │1110000101│1110100101│1111000101│1111100101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│5 │01010 │10100110 │110000110│110100110 │1110000110│1110100110│1111000110│1111100110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│6 │01011 │10100111 │110000111│110100111 │1110000111│1110100111│1111000111│1111100111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│7 │011000 │10101000 │110001000│110101000 │1110001000│1110101000│1111001000│1111101000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│8 │011001 │10101001 │110001001│110101001 │1110001001│1110101001│1111001001│1111101001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│9 │011010 │10101010 │110001010│110101010 │1110001010│1110101010│1111001010│1111101010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│10│011011 │10101011 │110001011│110101011 │1110001011│1110101011│1111001011│1111101011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│11│011100 │10101100 │110001100│110101100 │1110001100│1110101100│1111001100│1111101100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│12│011101 │10101101 │110001101│110101101 │1110001101│1110101101│1111001101│1111101101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│13│011110 │10101110 │110001110│110101110 │1110001110│1110101110│1111001110│1111101110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│14│011111 │10101111 │110001111│110101111 │1110001111│1110101111│1111001111│1111101111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│15│1000000 │10110000 │110010000│110110000 │1110010000│1110110000│1111010000│1111110000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│16│1000001 │10110001 │110010001│110110001 │1110010001│1110110001│1111010001│1111110001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│17│1000010 │10110010 │110010010│110110010 │1110010010│1110110010│1111010010│1111110010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│18│1000011 │10110011 │110010011│110110011 │1110010011│1110110011│1111010011│1111110011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│19│1000100 │10110100 │110010100│110110100 │1110010100│1110110100│1111010100│1111110100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│20│1000101 │10110101 │110010101│110110101 │1110010101│1110110101│1111010101│1111110101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│21│1000110 │10110110 │110010110│110110110 │1110010110│1110110110│1111010110│1111110110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│22│1000111 │10110111 │110010111│110110111 │1110010111│1110110111│1111010111│1111110111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│23│1001000 │10111000 │110011000│110111000 │1110011000│1110111000│1111011000│1111111000│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│24│1001001 │10111001 │110011001│110111001 │1110011001│1110111001│1111011001│1111111001│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│25│1001010 │10111010 │110011010│110111010 │1110011010│1110111010│1111011010│1111111010│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│26│1001011 │10111011 │110011011│110111011 │1110011011│1110111011│1111011011│1111111011│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│27│1001100 │10111100 │110011100│110111100 │1110011100│1110111100│1111011100│1111111100│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│28│1001101 │10111101 │110011101│110111101 │1110011101│1110111101│1111011101│1111111101│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│29│1001110 │10111110 │110011110│110111110 │1110011110│1110111110│1111011110│1111111110│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│30│1001111 │10111111 │110011111│110111111 │1110011111│1110111111│1111011111│1111111111│
├──┼────────┼─────────┼─────────┼──────────┼──────────┼──────────┼──────────┼──────────┤
│31│10100000│110000000│110100000│1110000000│1110100000│1111000000│1111100000│ │
└──┴────────┴─────────┴─────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
Quá trình
Đầu tiên, chúng ta cần sắp xếp tất cả các ký tự duy nhất trong văn bản theo thứ tự giảm dần theo tần suất của chúng. Sau đó, chúng tôi sẽ gán cho mỗi ký tự một mã - mã thường xuyên nhất sẽ nhận được 000, mã tiếp theo - 0010v.v. Bây giờ đã đến lúc duyệt qua văn bản và thay thế từng ký tự bằng mã tương ứng của nó. Cuối cùng, chúng tôi chia danh sách nhị phân kết quả thành các chinks 8 bit và chuyển đổi chúng thành số nguyên thập phân (hoặc thập lục phân). Đoạn cuối cùng có thể ngắn hơn 8 bit, vì vậy nó nên được lấp đầy thành 8 bit. Việc điền là không quan trọng, vì vậy bạn có thể sử dụng bất kỳ giá trị nào bạn muốn - tất cả 0, tất cả 1 hoặc bất kỳ kết hợp nào của 1 và 0. Để dữ liệu nén có thể được giải nén, chúng tôi cần theo dõi độ dài của thư gốc, cũng như danh sách các ký tự đã được sắp xếp.
Nhiệm vụ
Viết hai hàm (hoặc hoàn thành chương trình):
Nén, lấy một chuỗi làm đầu vào và trả về dữ liệu đã nén. Dữ liệu được nén phải bao gồm danh sách / mảng được nén gồm các số nguyên thập phân hoặc thập lục phân, độ dài của dữ liệu đầu vào ban đầu và danh sách các ký tự đã được sắp xếp. Ba có thể theo thứ tự tùy ý và có thể được lưu trữ dưới dạng danh sách, mảng, tuple hoặc bất kỳ cấu trúc nào khác, thuận tiện cho bạn. Ví dụ: mã thử nghiệm của tôi trong J trả về một mảng gồm 3 giá trị được đóng hộp:
compress 'Hello World' ┌──┬────────┬────────────────┐ │11│loredWH │90 0 38 20 70 18│ └──┴────────┴────────────────┘
** Lưu ý: Nếu bạn không cần độ dài của dữ liệu đầu vào ban đầu cho trình giải nén của mình, bạn không cần lưu / in nó trong máy nén của mình.
- Giải nén, lấy dữ liệu nén và trả về chuỗi sau khi giải nén.
Tiêu chí chấm điểm và chiến thắng
Điểm của bạn là tổng độ dài tính bằng byte của hai hàm. Điểm thấp nhất trong mọi ngôn ngữ sẽ thắng.
Các trường hợp thử nghiệm
compress 'Hello World'
┌──┬────────┬────────────────┐
│11│loredWH │90 0 38 20 70 18│
└──┴────────┴────────────────┘
decompress 11;'loredWH ';90 0 38 20 70 18
Hello World
compress 'Code Golf Stack Exchange is a site for recreational programming competitions'
┌──┬───────────────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│76│ oieatrncsmgplfxkhdSGEC│142 80 208 34 147 207 136 138 75 48 68 104 12 194 75 14 32 27 65 33 163 82 3 228 176 180 50 180 37 70 76 37 224 234 201 197 165 182 205 135 3 36 219 168 81 168 201 134 128│
└──┴───────────────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
decompress 76;' oieatrncsmgplfxkhdSGEC'; 142 80 208 34 147 207 136 138 75 48 68 104 12 194 75 14 32 27 65 33 163 82 3 228 176 180 50 180 37 70 76 37 224 234 201 197 165 182 205 135 3 36 219 168 81 168 201 134 128
Code Golf Stack Exchange is a site for recreational programming competitions
compress 'GFFEEEDDDDCCCCCBBBBBBAAAAAAA'
┌──┬───────┬────────────────────────────────────────────────┐
│28│ABCDEFG│90 148 148 165 8 66 12 204 204 136 136 136 0 0 0│
└──┴───────┴────────────────────────────────────────────────┘
decompress 28;'ABCDEFG';90 148 148 165 8 66 12 204 204 136 136 136 0 0 0
GFFEEEDDDDCCCCCBBBBBBAAAAAAA
Ghi chú
Dữ liệu nén có thể khác nhau giữa các ngôn ngữ do cách sắp xếp hoạt động trên các ký tự có tần suất bằng nhau. Đây không phải là vấn đề, miễn là mã giải nén của bạn hoạt động chính xác.
Trả lời
05AB1E , 94 89 71 64 63 61 (29 + 32) byte
-25,5 byte nhờ @ovs .
-2 byte nhờ @Neil .
Máy nén:
ÙΣ¢}R=āεb¦Dgb₄+¦ì}‡¤_9׫8ô¨C,
Hãy thử trực tuyến hoặc xác minh tất cả các trường hợp thử nghiệm .
Bộ giải nén:
b₁b+€¦J¤Ü[D3£C3+ôć3.$1ìC<Isè?J¤F
Đầu vào đầu tiên là danh sách số nguyên; đầu vào thứ hai là chuỗi.
Dừng chương trình với lỗi sau khi nó xuất ra kết quả chính xác, được phép theo meta .
Hãy thử trực tuyến hoặc xác minh tất cả các trường hợp thử nghiệm .
Cả máy nén và bộ giải nén của tôi đều không sử dụng chiều dài.
Nếu độ dài của chuỗi nhị phân kết quả trong máy nén chia hết cho 8, nó sẽ thêm một số nguyên no-op theo sau vào danh sách đầu ra. (Trình giải nén rõ ràng vẫn xử lý cả điều này và các chuỗi nhị phân không chia hết cho 8, một cách chính xác.)
Giải trình:
Máy nén:
Ù # Uniquify the characters of the (implicit) input-string
Σ # Sort these characters by:
¢ # Their count in the (implicit) input-string
}R # After the sort: reverse it so the order is from most to least frequent
= # Output this string with trailing newline (without popping the string)
ā # Push a list in the range [1,string-length] (without popping the string)
ε # Map each integer to:
b # Convert it to a binary-string
¦ # Remove its first digit
Dg # Create a copy, and pop and push its length
b # Convert this length to binary
# Pad it to length 3 with leading 0s by:
₄+ # Adding 1000
¦ # And then removing the first digit
ì # Prepend this in front of the binary-string we've duplicated
}‡ # After the map: transliterate all sorted unique characters with these
# strings in the (implicit) input-string
¤ # Push its last digit (without popping the string)
_ # Invert the boolean (1 becomes 0; 0 becomes 1)
9× # Repeat that 9 times as string
« # And append it to the big string
8ô # Then split it into parts of size 8
¨ # Remove the trailing part
C # Convert each part from binary to an integer
, # And pop and output it as well
Bộ giải nén:
b # Convert each integer in the (implicit) input-list to a binary-string
# Pad each to length 8 with leading 0s by:
₁b # Pushing 256, and converting it to binary as well: 100000000
+ # Adding it to each binary string
€¦ # And then removing the first digit of each string
J # Join all binary-strings together to a single string
¤ # Push its last digit (without popping the string)
Ü # And right-strip all those trailing digits
[ # Loop indefinitely:
D # Duplicate the binary-string
3£ # Pop the copy, and push its first 3 digits
C # Convert that from binary to an integer
3+ # Add 3
ô # Split the binary-string into parts of that size
ć # Extract head; pop the remainder-list and first item separately
3.$ # Remove the first 3 digits of this first item
1ì # Prepend a 1
C # Convert it from binary to an integer as well
< # And decrease it by 1
I # Then push the second input-string
s # Swap so the integer is at the top of the stack
è # (0-based) index it into the input-string
? # Pop and output this character (without trailing newline)
J # And join the remainder-list back to a string
¤ # Push its first character (without popping the string),
# which will be either 0, 1, or an empty string
F # Loop that many times, which will error for the empty string to exit the
# program
k4 , 69 + 90 = 159 byte
compress:{|(0b/:'8#'0N 8#,/(,/,/:'[c 3;c:7{,/x,/:\:01b}\,()])e?x;e:>#:'=x;#x)}
c:7{,/x,/:\:01b}\,()xây dựng danh sách các hậu tố hợp lệ, được nhóm theo độ dài của chúng (ví dụ(,();(,0b;,1b);(00b;01b;10b;11b);...):)- các tiền tố (
c 3) được thêm vào trước các hậu tố với,/:'[c 3;c:...] e:>#:'=xtrả về các ký tự trongx(ổn định) được sắp xếp theo tần số của chúng, giảm dần- các mẫu bit được lập chỉ mục bởi
e?x, tức là các chỉ sốecho mỗi ký tự trongx 0N 8#,/chuyển đổi đầu vào đã nén thành danh sách các byte,8#'đảm bảo mỗi đoạn (bao gồm cả đoạn cuối) chứa đầy đủ 8 bit0b/:'chuyển đổi từng đoạn 8 bit thành biểu diễn byte thập lục phân (tức là danh sách các byte, là đầu ra thứ ba)
decompress:{z:,/0b\:'z;o:"";do[x;o,:y(,/,/:'[c 3;c:7{,/x,/:\:01b}\,()])?(d:+/3,4 2 1*3#z)#z;z:d_z];o}
- chuyển đổi đầu vào (danh sách các byte) thành danh sách các bit / boolean bằng cách sử dụng
z:,/0b\:'z - đối với mỗi ký tự trong đầu vào không nén (tổng số trong số đó được chuyển vào dưới dạng
x), bóc 3 bit đầu tiên và xác định xem có bao nhiêu bit bổ sung là một phần của nó với(d:+/3,4 2 1*3#z) - tra cứu mã bit nén trong bảng mã bit để lấy chỉ số của nó (ví dụ
000b => 0, 0010b => 1, ...); sử dụng kết quả này để lập chỉ mục vào danh sách các ký tự đã được sắp xếp (y) - nối ký tự không nén vào đầu ra
o, sau đó thả ký tự đã nén khỏi đầu vào (z) để chuẩn bị chodolần lặp tiếp theo
Than củi , 71 64 + 32 = 96 byte
Máy nén, 64 byte:
≔Ｅθ⟦№θιι⟧ηＷ⁻ηυ⊞υ⌈ιＵＭυ⊟ι⭆¹⟦Ｌθ⪫υωＥ⪪⭆Ｅθ⍘⊕⌕υλ !⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ⁸⍘◨λ⁸ !
Hãy thử nó trực tuyến! Liên kết là phiên bản dài của mã. Giải trình:
≔Ｅθ⟦№θιι⟧η
Ghép nối tất cả các ký tự đầu vào với tần số của chúng.
Ｗ⁻ηυ
Lặp lại cho đến khi tất cả các cặp đã được sắp xếp và loại bỏ trùng lặp.
⊞υ⌈ι
Đẩy cặp còn lại cao nhất (tức là thường xuyên nhất) vào danh sách trống được xác định trước.
ＵＭυ⊟ι
Bỏ tần số khỏi danh sách đã sắp xếp, loại bỏ trùng lặp.
⭆¹⟦
Xâu chuỗi danh sách ...
Ｌθ
... độ dài của đầu vào, ...
⪫υω
... sự nối các ký tự theo thứ tự tần suất giảm dần và:
Ｅθ⍘⊕⌕υλ !
Đối với mỗi ký tự trong chuỗi đầu vào, hãy tìm chỉ số phổ biến (được lập chỉ mục 1, vì vậy tôi phải tăng dần) và chuyển đổi nó thành cơ số 2 bằng cách sử dụng các chữ số tùy chỉnh.
⭆...⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ
Đối với mỗi ký tự được chuyển đổi, hãy thêm 7 vào độ dài của nó, chuyển đổi ký tự đó thành cơ số 2 bằng cách sử dụng các chữ số tùy chỉnh và tạo danh sách ký tự đó và chuỗi đã chuyển đổi. Cắt đầu tất cả các dây và nối các phần thân lại.
Ｅ⪪...⁸⍘◨λ⁸ !
Cắt chuỗi thành các chuỗi con có độ dài 8, nhấn chuột phải vào chuỗi cuối cùng và giải mã từng chuỗi con dưới dạng cơ số 2 bằng cách sử dụng các ký tự cơ sở tùy chỉnh (đặc biệt, phần đệm bên phải sử dụng dấu cách, vì vậy đây phải là ký tự cơ sở tùy chỉnh cho 0) .
Lưu ý rằng phiên bản này của máy nén giải quyết các mối quan hệ bằng cách lấy ký tự có thứ tự cao nhất, thay vì ký tự có lần xuất hiện đầu tiên mà phiên bản trước đã chọn. Tôi đã cập nhật đầu vào cho liên kết trình giải nén tương ứng.
Bộ giải nén, 32 byte:
Ｆ⮌ζＦ⁸⊞υ﹪÷ιＸ²κ²⭆θ§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²
Hãy thử nó trực tuyến! Liên kết là phiên bản dài của mã.
Ｆ⮌ζ
Lặp lại các byte ngược lại.
Ｆ⁸
Lặp lại từng bit ngược lại.
⊞υ﹪÷ιＸ²κ²
Đẩy bit vào danh sách trống được xác định trước.
⭆θ
Ánh xạ qua từng chỉ mục, nối và in ngầm:
§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²
Bật 3 bit từ danh sách, giải mã dưới dạng cơ sở 2, bật nhiều bit đó từ danh sách, tiền tố 1, giải mã dưới dạng cơ sở 2, lập chỉ mục vào chuỗi (được lập chỉ mục 0, vì vậy tôi phải giảm dần). (Tôi có thể đã sử dụng BaseStringvà StringMaphai lần.)
JavaScript (Node.js) , 223 + 126 = 349 byte
Máy nén, 223 byte
s=>[s.length,a=[...new Set(s)].sort(g=(a,b)=>a?1/s.split(a).length-g(b):0),([...s].reduce((q,c)=>q<<3n+(x=(B=BigInt)(31-Math.clz32(i=a.indexOf(c)+1)))|x<<x|B(i)^1n<<x,1n)<<7n).toString(2).match(/\B.{8}/g).map(x=>+('0b'+x))]
Hãy thử nó trực tuyến!
Làm sao?
Tạo danh sách a[]các ký tự duy nhất đã được sắp xếp :
a = [...new Set(s)] // get the array of unique characters
.sort(g = (a, b) => // for each pair (a, b) of characters to be sorted:
a ? // if a is defined:
1 / s.split(a).length // compute 1 / (N + 1),
// where N is the number of occurrences of a in s
- g(b) // subtract the result of a recursive call
// with a = b and b undefined
: // else:
0 // stop the recursion
) // end of sort()
Tạo luồng byte dưới dạng một BigInt duy nhất:
[...s].reduce((q, c) => // for each character c in s, using q as the accumulator:
q << // left-shift q by:
3n + // 3 + x positions,
(x = (B = BigInt)( // where x is the number of bits required to write ...
31 - Math.clz32( //
i = a.indexOf(c) + 1 // ... the 1-indexed position i of c in a[]
) //
)) //
| // bitwise OR with:
x << x // x, left-shifted by x positions
| // bitwise OR with:
B(i) ^ 1n << x, // i without the most significant bit
1n // start with q = 1 to preserve leading 0's
) // end of reduce()
Tách BigInt thành một danh sách các byte:
(... << 7n) // left-shift the final result to add 7 trailing 0's
.toString(2) // convert to binary
.match(/\B.{8}/g) // split by groups of 8 binary digits, ignoring the 1st one
.map(x => +('0b' + x)) // convert each group back to decimal
Bộ giải nén, 126 byte
19 byte được lưu bởi @Neil!
(n,a,b)=>(g=s=>n--?a['0b1'+s[S](3,x=2-~('0b'+s[S](0,3)))-1]+g(s[S](x)):'')(b.map(v=>(256+v).toString(2)[S='slice'](1)).join``)
Hãy thử nó trực tuyến!
Làm sao?
Chuyển luồng byte thành một chuỗi nhị phân:
b.map(v => // for each byte v in b[]:
(256 + v) // force a leading '1'
.toString(2) // convert to binary
[S = 'slice'](1) // remove the leading '1'
).join`` // end of map(); join all strings together
Tạo đầu ra:
g = s => // s = binary string
n-- ? // decrement n; if it was not equal to 0:
a[ // pick the next character from a[]:
'0b1' + // the index of the character is 2 ** x + V - 1
s[S]( // where V is defined
3, // as the x-bit value
x = 2 -~( // whose length x (+3)
'0b' + s[S](0, 3) // is stored in the 3 leading bits
) //
) - 1 //
] + // end of character lookup
g(s[S](x)) // recursive call with all processed bits removed
: // else:
'' // stop the recursion
Python 3 , 190 + 128 = 318 byte
Đã lưu một con số khổng lồ 28 41 55 57 82 byte (và dưới 400!) Nhờ ovs !!!
Đã tiết kiệm 10 byte nhờ Neil !!!
Máy nén
Python 3 , 190 byte
def c(r):j=''.join;s=j(sorted({*r},key=r.count))[::-1];i=s.index;g=j(f'{len(bin(i(c)+1)[3:]):03b}'+bin(i(c)+1)[3:]for c in r)+8*'0';return[int(g[a:a+8],2)for a in range(0,len(g),8)],len(r),s
Hãy thử nó trực tuyến!
Bộ giải nén
Python 3 , 128 byte
def d(a,l,s):
d=''.join(f'{d:08b}'for d in a);r=''
while len(r)<l:b=3+int(d[:3],2);r+=s[~-int('1'+d[3:b],2)];d=d[b:]
return r
Hãy thử nó trực tuyến!
Giải nén sử dụng độ dài của chuỗi ban đầu.
Husk , 119 103 95 (55 + 40) byte
Chỉnh sửa: -8 byte nhờ Neil
Máy nén (55 byte):
,₁¹B256ḋS+ö`R0%8_Lṁ!ṁλm+tḋ+8¹(motḋ→½ŀ`^2→))ŀ8m€₁¹
↔Ö#¹u
Hãy thử nó trực tuyến!
Bộ giải nén (40 byte):
mö!²ḋ:1↓3↑I¡λ§,↓↑+3ḋ↑3¹)Ṡ+ö`R0%8_LḋB256⁰
Hãy thử nó trực tuyến!
Làm thế nào nó hoạt động?
Máy nén:
- Sắp xếp các chữ cái theo tần suất (chức năng trợ giúp
₁):
↔Ö#¹u
- Thay thế các chữ cái theo thứ hạng của chúng theo tần suất:
m€₁
- Tạo mã độ dài tiền tố:
ṁ ŀ8 # for each integer x from 0 to 7
λm+ # join
tḋ+8¹ # zero-padded binary digits of x to
(motḋ→½ŀ`^2→)) # zero-padded binary digits of 1..x
- Tra cứu từng mã độ dài tiền tố từ mỗi thứ hạng chữ cái:
ṁ!
- Pad kết thúc bằng các chữ số đến bội số 8:
S+ö`R0%8_L
- Chuyển đổi từ nhị phân sang cơ số 256:
B256ḋ
- Và cuối cùng ghép nối với các chữ cái được sắp xếp theo tần suất:
,₁¹
Bộ giải nén:
- Chuyển đổi đối số đầu tiên từ cơ số 256 sang chữ số nhị phân:
ḋB256⁰
- Bàn phím bắt đầu bằng các chữ số lên đến bội số 8:
Ṡ+ö`R0%8_L
- Tuần tự nhận mã độ dài tiền tố:
¡λ ) # apply function repeatedly:
3ḋ↑3¹ # remove first 3 digits & convert to number
§,↓↑+ # split remaining list at this position
# (this keeps going forever, so the list ends-up
# with a lot of empty elements)
↑I # finally, just keep the truthy prefixes
- Chuyển đổi từng phần tử thành một số:
↓3 # discard the first 3 digits
:1 # and add a '1' at the start
# (equivalent to converting the 3 digits
# to a value from binary and adding it: Thanks Neil! )
ḋ # and convert it all to a value from binary
- Tra cứu chữ cái từ đối số thứ hai:
mö!²
J , 70 + 95 = 165 byte
Bộ mã hóa trả về length;table;bytesgiống như trong mô tả. Phần lấp đầy cho đoạn cuối cùng là bit được tạo cuối cùng.
#;[(];[:#.@($~8,~#>.@%8:)@;(~.(128#3+i.8)<@$"0 1#:i.4^5){~i.~)~.\:#/.
Bộ giải mã sử dụng cùng một định dạng cho đầu vào:
>@{.$>@{~&1({~(~.(128#3+i.8)<@$"0 1#:i.4^5)i.l<@{.])"1[:(}.~l=:3+3#.@{.])^:(<_)128,@}.@#:@,>@{:
Hãy thử nó trực tuyến!
Đại khái nó hoạt động như thế nào
Bảng mã được sử dụng trong cả hai:
#:i.4^50… 1024 trong hệ nhị phân.128#3+i.8lặp lại mọi số trong 3… 11 cho 128 lần<@$"0cho 0… 127 lấy 3 chữ số đầu tiên, cho 128… 255 lấy 4 chữ số đầu tiên,…~.lấy các phần tử duy nhất của kết quả.
Mã hoá:
~.\:#/.sắp xếp các ký tự duy nhất trong đầu vào dựa trên số lần xuất hiện. Đó là bảng ký tự.(table){~i.~ánh xạ đầu vào cho các vị trí bảng ký tự và nhận mã tương ứng.($~8,~#>.@%8:)@;nối tất cả các mã lại với nhau và chia chúng thành các đoạn 8.#;…];#.@chuyển đổi lại thành số nguyên và thêm trước bảng ký tự và độ dài.
Bộ giải mã:
128,@}.@#:@,>@{lấy byte và chuyển đổi chúng trở lại thành bit. Tạm thời phải thêm 128 để đệm kết quả thành 8 bit.[:(}.~l=:3+3#.@{.])^:(<_)phân tích cú pháp 3 bit đầu tiênn, và loại bỏ chúng và cácnbit tiếp theo khỏi mảng bit. Làm điều này cho đến khi mảng bit trống. Trả về tất cả các kết quả trung gian (vì vậy vị trí bắt đầu cho các mã).(table)i.l<@{.]một lần nữa, phân tích cú pháp các bit bắt đầu và tra cứu chúng trong bảng mã.>@{~&1({~và tra cứu chỉ mục trong bảng ký tự.>@{.$cắt đầu ra xuống theo độ dài của chuỗi.
Perl 5 , 354 byte
@c=map{$c=$_;map{sprintf"%0*b%0*b",$c?3:2,$c,$c,$_}0..2**$c-1}0..7; sub c{$_=pop;my%f;$f{$_}++for/./g;my%c;@c{@f=sort{$f{$b}<=>$f{$a}}keys%f}=@c;y///c,join('',@f),map oct(substr"0b$_".'0'x7,0,10),join('',@c{/./g})=~/.{1,8}/g} sub d{($l,$f,@i)=@_;@d{@c}=0..255;join'',map$f=~/^.{$d{$_}}(.)/,(join('',map sprintf('%08b',$_),@i)=~/@{[join'|',@c]}/g)[0..$l-1]}
Hãy thử nó trực tuyến!
Chạy nó để nén với hàm c () và giải nén với d ().
my @c1 = c('Hello World');
my @c2 = c('Code Golf Stack Exchange is a site for recreational programming competitions');
print join('|',@c1)."\n";
print join('|',@c2)."\n";
print "Bytes in 1st compression: ".(@c1-2)."\n";
print "Bytes in 2nd compression: ".(@c2-2)."\n";
print d(@c1)."|\n";
print d(@c2)."|\n";
Đầu ra:
11|loredWH |90|0|38|20|70|18
76| oieatrncsmgplfxkhdSGEC|142|80|208|34|147|207|136|138|75|48|68|104|12|194|75|14|32|27|65|33|163|82|3|228|176|180|50|180|37|70|76|37|224|234|201|197|165|182|205|135|3|36|219|168|81|168|201|134|128
Bytes in 1st compression: 6
Bytes in 2nd compression: 49
Hello World|
Code Golf Stack Exchange is a site for recreational programming competitions|
Julia , 331 byte
p(s)=Meta.parse("0b"*s)
s(n,p)=last(bitstring(n),p)
b(i,n=0,B=2^n)=2B<=i ? b(i,n+1) : s(n,3)s(i-B,n)
c(s,u=sort(unique(s),by=x->count(==(x),s),rev=0<1))=join(u),p.(i.match for i=eachmatch(r".{8}",join(b.(findlast(==(i),u) for i=s))*'1'^7))
d(u,N,s=join(s.(N,8)),n=p(s[1:3]))=u[n<1||2^n+p(s[4:3+n])]*try d(u,0,s[4+n:end])catch;""end
Hãy thử nó trực tuyến!
Tôi không muốn tách biệt nén và giải nén vì tôi sử dụng các chức năng pvà scho cả hai.
c là để nén, trả về các chữ cái đã được sắp xếp và chuỗi nén (các bit bị thiếu được điền bằng 1s)
dlà để giải nén, không cần độ dài của chuỗi gốc (nó loại bỏ ký tự không hợp lệ cuối cùng)