나이브 압축
Oct 28 2020
접두사 길이 코드 사용
텍스트에서 해당 문자의 빈도에 따라 각 문자를 바이너리 코드로 간단히 대체하여 텍스트 (문자열, 배열 / 문자 / 바이트 목록)를 압축 할 것입니다. 더 자주 발생하는 문자는 더 짧은 코드로 대체됩니다. 결과 비트 배열은 길이가 8 인 청크로 분할됩니다.
코드
길이가 3 인 접두사 길이 코드는 접두사-뒤에 오는 필드의 길이를 나타내는 3 비트와 필드로 구성된 코드입니다. 8 (2 ^ 3) 개의 서로 다른 접두사에는 3 비트면 충분합니다. n차례로 각 접두사 는 2 ^ n 개의 서로 다른 필드를 설명하며 0에서 2 ^ n-1까지 열거됩니다.
n = 0; 항목 1 개 (2 ^ 0)
000 – field with length 0;
n = 1; 항목 2 개 (2 ^ 1)
001|0 (`|` is put for clarity)
001|1
n = 2; 4 개 항목 (2 ^ 2)
010|00
010|01
010|10
010|11
…
n = 7; 128 개 항목 (2 ^ 7)
111 | 0000000 111 | 0000001 111 | 0000010 … 111 | 1111111
다음은 0에서 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│ │
└──┴────────┴─────────┴─────────┴──────────┴──────────┴──────────┴──────────┴──────────┘
과정
먼저 텍스트의 모든 고유 문자를 빈도에 따라 내림차순으로 정렬해야합니다. 그런 다음 우리는 각 캐릭터에게 코드를 할당합니다 - 가장 자주 하나 얻을 것이다 000, 다음 중 하나를 - 0010등등. 이제 텍스트를 탐색하고 각 문자를 해당 코드로 바꿀 차례입니다. 마지막에 결과 바이너리 목록을 8 비트 짱 크로 분할하고 10 진수 (또는 16 진수) 정수로 변환합니다. 마지막 청크는 8 비트보다 짧을 수 있으므로 8 비트로 채워야합니다. 채우기는 중요하지 않으므로 원하는 값 (모두 0, 모두 1 또는 1과 0의 조합)을 사용할 수 있습니다. 압축 된 데이터를 압축 해제 할 수 있으려면 원본 메시지의 길이를 추적해야합니다. 정렬 된 문자 목록도 있습니다.
작업
두 가지 기능 (또는 전체 프로그램)을 작성합니다.
Compress는 문자열을 입력으로 받아 압축 된 데이터를 반환합니다. 압축 된 데이터에는 10 진수 또는 16 진수 정수의 압축 된 목록 / 배열, 원래 입력 길이 및 정렬 된 문자 목록이 포함되어야합니다. 이 세 가지는 임의의 순서로 나열 될 수 있으며 목록, 배열, 튜플 또는 기타 구조로 저장 될 수 있습니다. 예를 들어 J의 테스트 코드는 3 개의 박스 값 배열을 반환합니다.
compress 'Hello World' ┌──┬────────┬────────────────┐ │11│loredWH │90 0 38 20 70 18│ └──┴────────┴────────────────┘
** 참고 : 압축 해제 기의 원래 입력 길이가 필요하지 않은 경우 압축 해제에 저장하거나 인쇄 할 필요가 없습니다.
- 압축 해제는 압축 된 데이터를 가져와 압축 해제 후 문자열을 반환합니다.
득점 및 우승 기준
점수는 두 함수의 길이 (바이트)의 합계입니다. 모든 언어에서 가장 낮은 점수가 승리합니다.
테스트 케이스
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
노트
압축 된 데이터는 동일한 빈도의 문자에 대해 정렬이 작동하는 방식으로 인해 언어마다 다를 수 있습니다. 압축 해제 코드가 올바르게 작동한다면 이는 문제가되지 않습니다.
답변
5 KevinCruijssen Oct 28 2020 at 16:09
05AB1E , 94 89 71 64 63 61 (29 + 32) 바이트
-25.5 덕분 바이트 @ovs을 . @Neil
덕분에 -2 바이트 .
압축기:
ÙΣ¢}R=āεb¦Dgb₄+¦ì}‡¤_9׫8ô¨C,
온라인으로 시도 하거나 모든 테스트 사례를 확인하십시오 .
압축 해제 기 :
b₁b+€¦J¤Ü[D3£C3+ôć3.$1ìC<Isè?J¤F
첫 번째 입력은 정수 목록입니다. 두 번째 입력은 문자열입니다. meta에 따라 허용되는
올바른 결과를 출력 한 후 오류와 함께 프로그램을 중지합니다 .
온라인으로 시도 하거나 모든 테스트 사례를 확인하십시오 .
내 압축기와 압축 해제 기 모두 길이를 사용하지 않습니다.
압축기에서 결과 바이너리 문자열의 길이를 8로 나눌 수있는 경우 출력 목록에 후행 no-op 정수를 추가합니다. (압축 해제 기는 분명히 여전히 이것과 8로 나눌 수없는 바이너리 문자열을 올바르게 처리합니다.)
설명:
압축기:
Ù # 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 # 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
4 coltim Oct 29 2020 at 21:48
k4 , 69 + 90 = 159 바이트
compress:{|(0b/:'8#'0N 8#,/(,/,/:'[c 3;c:7{,/x,/:\:01b}\,()])e?x;e:>#:'=x;#x)}
c:7{,/x,/:\:01b}\,()그 길이별로 그룹화 유효한 접미사의 목록을 구축 (예(,();(,0b;,1b);(00b;01b;10b;11b);...))- 접두사 (
c 3)는 접미사 앞에 추가됩니다.,/:'[c 3;c:...] e:>#:'=xx빈도에 따라 (안정적으로) 정렬 된 문자를 내림차순으로 반환합니다.- 비트 패턴은에 의해 색인화됩니다
e?x. 즉,e각 문자에 대한 색인x 0N 8#,/압축 된 입력을 바이트 목록으로 변환하여8#'각 청크 (마지막 포함)에 전체 8 비트가 포함되도록합니다.0b/:'8 비트의 각 청크를 16 진수 바이트 표현으로 변환합니다 (즉, 세 번째 출력 인 바이트 목록).
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}
- 다음을 사용하여 입력 (바이트 목록)을 비트 / 부울 목록으로 변환합니다.
z:,/0b\:'z - 압축되지 않은 입력 (으로 전달되는 총 개수)의 각 문자에 대해
x처음 3 비트를 벗겨 내고 몇 개의 추가 비트가 포함되는지 확인합니다.(d:+/3,4 2 1*3#z) - (예를 들어 인덱스를 검색하는 비트 코드 테이블의 압축 비트 코드를 조회
000b => 0, 0010b => 1, ...); 이 결과를 사용하여 정렬 된 문자 목록 (y) 을 색인화합니다. - 압축되지 않은 문자를 출력에 추가 한
o다음 입력 (z) 에서 압축 된 문자를 삭제 하여 다음do반복 을 준비합니다.
3 Neil Oct 29 2020 at 02:51
목탄 , 71 64 + 32 = 96 바이트
압축기, 64 바이트 :
≔Ｅθ⟦№θιι⟧ηＷ⁻ηυ⊞υ⌈ιＵＭυ⊟ι⭆¹⟦Ｌθ⪫υωＥ⪪⭆Ｅθ⍘⊕⌕υλ !⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ⁸⍘◨λ⁸ !
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 설명:
≔Ｅθ⟦№θιι⟧η
모든 입력 문자를 해당 주파수와 페어링합니다.
Ｗ⁻ηυ
모든 쌍이 정렬되고 중복 제거 될 때까지 반복합니다.
⊞υ⌈ι
가장 높은 (가장 빈번한) 나머지 쌍을 미리 정의 된 빈 목록으로 푸시합니다.
ＵＭυ⊟ι
정렬되고 중복 제거 된 목록에서 빈도를 삭제합니다.
⭆¹⟦
목록을 문자열 화 ...
Ｌθ
... 입력 길이, ...
⪫υω
... 빈도의 내림차순으로 문자 연결 및 :
Ｅθ⍘⊕⌕υλ !
입력 문자열의 각 문자에 대해 인기도 인덱스 (1 인덱스가 지정되어 있으므로 증가해야 함)를 찾아 사용자 지정 숫자를 사용하여 기본 2로 변환합니다.
⭆...⭆⟦⍘⁺⁷Ｌλ !λ⟧Φνρ
변환 된 각 문자에 대해 길이에 7을 더하고 사용자 지정 숫자를 사용하여 기본 2로 변환 한 다음 해당 목록과 변환 된 문자열을 만듭니다. 모든 문자열을 참수하고 시체를 연결하십시오.
Ｅ⪪...⁸⍘◨λ⁸ !
문자열을 길이가 8 인 부분 문자열로 자르고, 마지막 부분을 오른쪽으로 채우고, 사용자 지정 기본 문자를 사용하여 각 부분 문자열을 기본 2로 디코딩합니다 (특히 오른쪽 채우기는 공백을 사용하므로 0에 대한 사용자 지정 기본 문자 여야 함). .
이 버전의 압축기는 이전 버전에서 선택한 첫 번째 모습의 문자가 아닌 가장 높은 서수를 가진 문자를 가져 와서 관계를 해결합니다. 그에 따라 압축 해제 기 링크에 대한 입력을 업데이트했습니다.
압축 해제 기, 32 바이트 :
Ｆ⮌ζＦ⁸⊞υ﹪÷ιＸ²κ²⭆θ§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다.
Ｆ⮌ζ
바이트를 반대로 반복합니다.
Ｆ⁸
각 비트를 반대로 반복합니다.
⊞υ﹪÷ιＸ²κ²
미리 정의 된 빈 목록으로 비트를 푸시합니다.
⭆θ
각 인덱스에 매핑하고 조인하고 암시 적으로 인쇄합니다.
§η⊖⍘⁺1⭆↨Ｅ³⊟υ²⊟υ²
목록에서 3 비트를 팝하고,베이스 2로 디코딩하고, 목록에서 많은 비트를 팝하고, prefix 1,베이스 2로 디코딩하고, 문자열로 인덱스합니다 (0- 인덱싱되므로 감소해야 함). (내가 사용할 수도 BaseString및 StringMap두 번.)
3 Arnauld Oct 28 2020 at 18:50
JavaScript (Node.js) , 223 + 126 = 349 바이트
압축기, 223 바이트
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))]
온라인으로 시도하십시오!
어떻게?
a[]고유 문자 의 정렬 된 목록 생성 :
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()
단일 BigInt로 바이트 스트림 생성 :
[...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()
BigInt를 바이트 목록으로 분할 :
(... << 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
압축 해제 기, 126 바이트
@Neil로 19 바이트 절약!
(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``)
온라인으로 시도하십시오!
어떻게?
바이트 스트림을 이진 문자열로 변환 :
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
출력 생성 :
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
3 Noodle9 Oct 29 2020 at 22:34
Python 3 , 190 + 128 = 318 바이트
ovs 덕분에 무려 28 41 55 57 82 바이트를 절약했습니다 (그리고 400 미만이 되었습니다 !). Neil
덕분에 10 바이트 절약 !!!
압축기
Python 3 , 190 바이트
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
온라인으로 시도하십시오!
압축 해제 기
Python 3 , 128 바이트
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
온라인으로 시도하십시오!
압축 해제는 원래 문자열의 길이를 사용합니다.
2 DominicvanEssen Oct 29 2020 at 00:55
껍질 , 119 (103) 95 (40 + 55) 바이트
편집 : Neil 덕분에 -8 바이트
압축기 (55 바이트) :
,₁¹B256ḋS+ö`R0%8_Lṁ!ṁλm+tḋ+8¹(motḋ→½ŀ`^2→))ŀ8m€₁¹
↔Ö#¹u
온라인으로 시도하십시오!
압축 해제 기 (40 바이트) :
mö!²ḋ:1↓3↑I¡λ§,↓↑+3ḋ↑3¹)Ṡ+ö`R0%8_LḋB256⁰
온라인으로 시도하십시오!
어떻게 작동합니까?
압축기:
- 빈도별로 문자 정렬 (도우미 기능
₁) :
↔Ö#¹u
- 빈도 별 순위로 문자 대체 :
m€₁
- 접두사 길이 코드 생성 :
ṁ ŀ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
- 각 문자 순위에서 각 접두사 길이 코드를 찾습니다.
ṁ!
- 8의 배수까지 숫자로 끝 채우기 :
S+ö`R0%8_L
- 바이너리에서 base-256으로 변환 :
B256ḋ
- 마지막으로 빈도별로 정렬 된 문자와 쌍을 이룹니다.
,₁¹
압축 해제 기 :
- 첫 번째 인수를 base-256에서 이진수로 변환합니다.
ḋB256⁰
- 최대 8의 배수로 시작하는 패드 :
Ṡ+ö`R0%8_L
- 접두사 길이 코드를 순차적으로 가져옵니다.
¡λ ) # 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
- 각 요소를 숫자로 변환 :
↓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
- 두 번째 인수의 편지를 찾으십시오.
mö!²
1 xash Oct 29 2020 at 08:05
J , 70 + 95 = 165 바이트
인코더는 length;table;bytes설명에서와 같이 반환합니다 . 마지막 청크의 채우기는 마지막으로 생성 된 비트입니다.
#;[(];[:#.@($~8,~#>.@%8:)@;(~.(128#3+i.8)<@$"0 1#:i.4^5){~i.~)~.\:#/.
입력에 정확히 동일한 형식을 사용하는 디코더 :
>@{.$>@{~&1({~(~.(128#3+i.8)<@$"0 1#:i.4^5)i.l<@{.])"1[:(}.~l=:3+3#.@{.])^:(<_)128,@}.@#:@,>@{:
온라인으로 시도하십시오!
대략적인 작동 원리
둘 다에서 사용되는 코드 테이블 :
#:i.4^50… 1024 이진수.128#3+i.83… 11의 모든 숫자를 128 회 반복<@$"00… 127의 경우 처음 3 자리, 128… 255의 경우 처음 4 자리,…~.결과의 고유 한 요소를 가져옵니다.
인코더 :
~.\:#/.발생에 따라 입력의 고유 문자를 정렬합니다. 그것이 문자표입니다.(table){~i.~입력을 문자 테이블 위치에 매핑하고 해당 코드를 가져옵니다.($~8,~#>.@%8:)@;모든 코드를 함께 연결하고 8 개의 청크로 분할합니다.#;…];#.@다시 정수로 변환하고 문자 테이블과 길이를 앞에 추가하십시오.
디코더 :
128,@}.@#:@,>@{바이트를 가져 와서 다시 비트로 변환합니다. 결과를 8 비트로 채우려면 임시로 128을 앞에 추가해야합니다.[:(}.~l=:3+3#.@{.])^:(<_)처음 3 비트를 구문 분석하고 비트 배열에서 해당 비트n와 다음n비트를 제거합니다 . 비트 배열이 비워 질 때까지이 작업을 수행하십시오. 모든 중간 결과를 반환합니다 (따라서 코드의 시작 위치).(table)i.l<@{.]다시 시작 비트를 구문 분석하고 코드 테이블에서 조회합니다.>@{~&1({~문자표에서 색인을 찾습니다.>@{.$출력을 문자열의 길이로 줄입니다.
1 KjetilS. Oct 29 2020 at 03:04
Perl 5 , 354 바이트
@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]}
온라인으로 시도하십시오!
함수 c ()로 압축하고 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";
산출:
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|
1 MarcMush Nov 26 2020 at 23:01
Julia , 331 바이트
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
온라인으로 시도하십시오!
기능 p과 s둘 다를 사용하기 때문에 압축과 압축 해제를 분리하고 싶지 않습니다 .
c 압축 용이며 정렬 된 문자와 압축 된 문자열을 반환합니다 (누락 된 비트는 1로 채워짐).
d압축 해제를위한 것이며 원래 문자열의 길이가 필요하지 않습니다 (마지막 유효하지 않은 caracter를 버림).