Atau dia akan terengah-engah dan menghancurkan rumah Anda!
Itu sama sekali tidak relevan. Tantangan ini sebenarnya tentang pengkodean Huffman . Intinya adalah frekuensi karakter dalam teks yang diberikan digunakan untuk membuat representasi lebih pendek. Dengan kata lain, katakanlah alfabet kita adalah a
melalui z
dan ruang. Itu 27 karakter. Masing-masing dapat dikodekan secara unik hanya dalam 5 bit karena 5 bit memiliki ruang yang cukup untuk 32 karakter. Namun, dalam banyak situasi (seperti bahasa Inggris, atau bahasa pada umumnya), beberapa karakter lebih sering daripada yang lain. Kita dapat menggunakan bit lebih sedikit untuk karakter yang lebih sering dan (mungkin) lebih banyak bit untuk karakter yang lebih jarang. Dilakukan dengan benar, ada penghematan keseluruhan dalam jumlah bit dan teks asli masih dapat direkonstruksi secara unik.
Mari kita ambil "pertanyaan ini tentang pengodean huffman" sebagai contoh. Teks ini panjangnya 37 karakter, yaitu 37 * 8 = 296 bit secara normal, meskipun hanya 37 * 5 = 185 bit jika kita hanya menggunakan 5 bit untuk setiap karakter. Ingatlah itu.
Berikut adalah tabel (agak) dari setiap karakter dan frekuensi mereka dalam teks, diurutkan dari yang paling sering (di mana _ berarti spasi):
_ 5
i 4
n 3
o 3
s 3
t 3
u 3
a 2
f 2
h 2
b 1
c 1
d 1
e 1
g 1
m 1
q 1
Pengkodean optimal terkait dapat:
_ 101
i 011
n 1100
o 1101
s 1110
t 1111
u 001
a 10011
f 0001
h 0101
b 00000
c 00001
d 01000
e 01001
g 10000
m 10001
q 10010
Harus segera jelas bahwa ini akan menjadi pengkodean yang lebih baik daripada hanya menggunakan 5 bit untuk setiap karakter. Mari kita cari tahu seberapa jauh lebih baik!
145 bit , dibandingkan dengan 185! Itu penghematan 40 bit, atau lebih dari 20%! (Ini, tentu saja, dengan asumsi bahwa informasi tentang struktur tersedia untuk decoding.) Pengkodean ini optimal karena tidak ada lagi bit yang bisa dihapus dengan mengubah representasi karakter apa pun.
Tugas
- Tulis program atau fungsi dengan satu parameter yang ...
- Mengambil input dari STDIN (atau setara) atau sebagai argumen tunggal.
- Keluarkan kode Huffman yang optimal seperti di atas dengan karakter diurutkan berdasarkan frekuensi (urutan dalam kelas frekuensi tidak masalah).
- Anda dapat mengasumsikan bahwa karakter dalam input dibatasi untuk rentang ASCII
32..126
plus baris baru. - Anda dapat mengasumsikan input tidak lebih dari 10.000 karakter (idealnya, secara teori, input tidak boleh dibatasi).
- Kode Anda harus selesai dengan cepat. Contoh yang diberikan di atas seharusnya tidak lebih dari satu menit atau lebih buruk. (Ini dimaksudkan untuk mengesampingkan brute force.)
- Skor dalam byte.
Contohnya
x
---
x 0
xxxxxxxxx
---
x 0
xxxxxxxxy
---
x 0
y 1 (these may be swapped)
xxxxxyyyz
---
x 0
y 10
z 11
uuvvwwxxyyzz
--- (or)
u 000 000
v 001 001
w 100 010
x 101 011
y 01 10
z 11 11
this question is about huffman coding
---
101
i 011
n 1100
o 1101
s 1110
t 1111
u 001
a 10011
f 0001
h 0101
b 00000
c 00001
d 01000
e 01001
g 10000
m 10001
q 10010
Selamat coding!
Perhatikan bahwa pertanyaan serupa ini berkaitan erat, bahkan sampai pada titik bahwa ini adalah duplikat. Namun, konsensus sejauh ini pada Meta adalah bahwa yang lebih tua harus dianggap duplikat dari yang ini.
sumber
this question is about huffman coding
, saya menghitung jumlah bit menjadi 145 , bukan 136.Jawaban:
Pyth, 53 byte
Demonstrasi
Berikut adalah versi yang menunjukkan keadaan internal, sehingga Anda dapat melihat pengkodean sedang dibangun:
Demonstrasi
Salin output ke lingkungan dengan garis yang lebih luas untuk gambar yang lebih jelas.
sumber
Python 2, 299 byte
Inilah usaha saya untuk menjawab.
Kode Huffman berbeda dari contoh yang diberikan, tetapi harus tetap optimal.
sumber
Matlab, 116 byte
tabulate
membuat tabel frekuensi.huffmandict
mengambil daftar simbol dan probabilitas untuk setiap simbol, dan menghitung kodenya.sumber
Rubi,
189180 byteBekerja dalam proses.
Ini adalah fungsi anonim; menetapkan itu untuk sesuatu, misalnya
f
, dan menyebutnya denganyang mengembalikan hash seperti ini:
sumber
Haskell, 227 byte
Contoh penggunaan:
Bagaimana itu bekerja:
p
panggilanf
yang membangun tabel Huffman dalam bentuk daftar (karakter, pengodean) -pairs, misalnya[ ('a',"0"), ('b',"1") ]
, mengurutkan tabel berdasarkan panjang pengkodean, memformat setiap pasangan untuk output dan bergabung dengan baris baru di antara keduanya.f
pertama-tama periksa satu huruf dan kembalikan tabel yang sesuai. Kalau tidak, ia mengurutkan string input dan mengelompokkan urutan karakter yang sama (misalnya"ababa"
->["aaa","bb"]
) dan memetakannya menjadi pasangan(sequence , [(char, "")])
, (->[ ("aaa", [('a',"")]), ("bb", [('b', "")])]
. Elemen pertama digunakan untuk melacak frekuensi, elemen kedua adalah daftar pasangan karakter. dan itu encoding (yang awalnya kosong). Ini semua tabel elemen Huffman tunggal seperti yang diharapkan olehp
dan dikombinasikan olehg
danh
.g
mengurutkan daftar pasangan pada panjang elemen pertama, yaitu frekuensi dan panggilanh
.h
menggabungkan tabel Huffman dari dua elemen pertama, dengan menggabungkan frekuensi dan menempatkan a0
(1
) di depan setiap elemen dari tabel pertama (kedua). Gabungkan kedua tabel. Panggilg
lagi, berhenti ketika ada satu elemen yang tersisa, buang bagian frekuensi dan kembalikan tabel Huffman penuh.sumber
K (ngn / k) , 78 byte
Cobalah online!
mengembalikan daftar string untuk dicetak
h::0#'x
membuat daftar kosong untuk setiap karakter (secara teknis, itu membentuk kembali setiap karakter dengan panjang 0). kami akan menyimpan kode huffman terbalik di sana. kami menggunakan::
alih-alih:
untuk penugasan untuk menjadikanh
global sehingga terlihat di sub-fungsi..=x
adalah daftar daftar - indeks string yang dikelompokkan berdasarkan nilai karakter(#1_)
adalah fungsi yang mengembalikan kebenaran jika panjang argumen adalah> 1 (secara teknis "panjang 1 tetes ...")(#1_){
...}/
berarti: sementara argumen memiliki panjang> 1, tetap menerapkan fungsi kurung kurawalx@<#'x
urutkan argumen berdasarkan panjangnya0 2_
potong menjadi kepala 2-elemen dan ekor{h[x],:!2;y,,,/x}
memperbaruih
dengan menambahkan 0 dan 1 ke indeks yang ada di kepala; kembalikan ekor dengan kepala sebagai elemen tunggal(?,/'x,'" ",'|'$h)(?x)?>#'=x
membalikkan masing-masingh
, menyortir, unik, berkorespondensi karakter yang sesuai, dan memformat dengan baiksumber
JavaScript (ES6) 279
Intinya, algoritma dasar dari Wikipedia. Saya mungkin bisa melakukan yang lebih baik.
Lebih mudah dibaca di dalam cuplikan di bawah ini
sumber