W przeciwnym razie będzie sapał i dmuchał i wysadził dom w powietrze!

To było zupełnie nieistotne. To wyzwanie dotyczy kodowania Huffmana . Jego istotą jest częstotliwość znaków w danym tekście wykorzystywana do skrócenia jego reprezentacji. Innymi słowy, powiedzmy, że nasz alfabet ma aszerokość zi przestrzeń. To 27 znaków. Każdy z nich może być jednoznacznie zakodowany w zaledwie 5 bitach, ponieważ 5 bitów ma wystarczająco dużo miejsca na 32 znaki. Jednak w wielu sytuacjach (takich jak angielski lub ogólnie języki) niektóre znaki występują częściej niż inne. Możemy użyć mniej bitów dla częstszych znaków i (być może) więcej bitów dla rzadszych znaków. Zrobione dobrze, istnieje ogólna oszczędność liczby bitów, a oryginalny tekst można nadal wyjątkowo odtworzyć.

Weźmy jako przykład „to pytanie dotyczy kodowania huffmana”. Ten tekst ma 37 znaków, czyli 37 * 8 = 296 bitów normalnie, choć tylko 37 * 5 = 185 bitów, jeśli użyjemy tylko 5 bitów na każdy znak. Miej to w pamięci.

Oto (sorta) tabela każdego znaku i ich częstotliwości w tekście, posortowana od najbardziej do najmniejszej (gdzie _ oznacza spację):

_ 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

Powiązane optymalne kodowanie może być:

_ 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

Od razu powinno być jasne, że będzie to lepsze kodowanie niż tylko użycie 5 bitów na każdy znak. Sprawdźmy jednak, o ile lepiej!

145 bitów , w porównaniu do 185! To oszczędność 40 bitów, czyli nieco ponad 20%! (To oczywiście zakłada, że ​​informacje o strukturze są dostępne do dekodowania.) To kodowanie jest optymalne, ponieważ nie można usunąć więcej bitów przez zmianę reprezentacji dowolnego znaku.

Zadanie

• Napisz program lub funkcję z jednym parametrem, który ...
• Pobiera dane wejściowe ze STDIN (lub odpowiednika) lub jako pojedynczy argument.
• Wypisuje optymalne kodowanie Huffmana, jak wyżej, przy użyciu znaków posortowanych według częstotliwości (kolejność w klasie częstotliwości nie ma znaczenia).
• Możesz założyć, że znaki na wejściu są ograniczone do zakresu ASCII 32..126plus nowego wiersza.
• Możesz założyć, że dane wejściowe nie mają więcej niż 10 000 znaków (najlepiej teoretycznie dane wejściowe powinny być nieograniczone).
• Twój kod powinien zakończyć się dość szybko. Powyższy przykład w najgorszym przypadku nie powinien zająć więcej niż minutę. (Ma to na celu wykluczenie brutalnej siły.)
• Punktacja jest w bajtach.

Przykłady

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

Miłego kodowania!

^{Zauważ, że to podobne pytanie jest ściśle powiązane, nawet do tego stopnia, że ​​jest to duplikat. Jednak dotychczasowy konsensus w sprawie Meta jest taki, że starszy należy uważać za duplikat tego.}

Pyth, 53 bajty

jo_/zhNee.WtHa>JohNZ2+shKC<J2]s.b+RYNeKU2m,/zd]+d\ {z

Demonstracja

Oto wersja pokazująca stan wewnętrzny, dzięki czemu można zobaczyć budowane kodowanie:

jo_/zhNee.WtHvp+`a>JohNZ2+shKC<J2]s.b+RYNeKU2bm,/zd]+d\ {z

Demonstracja

Skopiuj wydruk do środowiska z szerszymi liniami, aby uzyskać wyraźniejszy obraz.

Python 2, 299 bajtów

Oto moja próba odpowiedzi.

Kody Huffmana różnią się od podanych przykładów, ale nadal powinny być optymalne.

i=raw_input();m=n=[(c,i.count(c))for c in set(i)]
while n[1:]:n.sort(key=lambda x:(x[1]));(a,b),(c,d)=n[:2];n=[((a,c),b+d)]+n[2:]
n=n[0][0]
r=[]
def a(b,s):
 if b[1:]:a(b[0],s+'0');a(b[1],s+'1')
 else:r.append(b+(s if s[1:]else s+'0'))
a(n,' ')
for y in sorted(r,key=lambda x:-dict(m)[x[0]]):print y

Matlab, 116 bajtów

tabulatetworzy tabelę częstotliwości. huffmandictpobiera listę symboli i prawdopodobieństwa dla każdego symbolu i oblicza kod.

t=tabulate(input('')');
d=huffmandict(t(:,1),cell2mat(t(:,3))/100);
for i=1:size(d,1);disp([d{i,1},' ',d{i,2}+48]);end

Rubin, 189 180 bajtów

Praca w toku.

->s{m=s.chars.uniq.map{|c|[c,s.count(c)]}
while m[1]
(a,x),(b,y),*m=m.sort_by &:last
m<<[[a,b],x+y]
end
h={}
f=->q="",c{Array===c&&f[q+?0,c[0]]&&f[q+?1,c[1]]||h[c]=q}
f[m[0][0]]
h}

To anonimowa funkcja; na przykład przypisz to do czegoś fi wywołaj za pomocą

f["some test string"]`

która zwraca skrót taki jak ten:

{"t"=>"00", "g"=>"0100", "o"=>"0101", " "=>"011", "e"=>"100", "n"=>"1010", "i"=>"1011", "m"=>"1100", "r"=>"1101", "s"=>"111"}

Haskell, 227 bajtów

import Data.List
s=sortOn.(length.)
f x|[c]<-nub x=[(c,"0")]|1<2=g[(a,[(a!!0,"")])|a<-group$sort x]
g=h.s fst
h[x]=snd x
h((a,b):(c,d):e)=g$(a++c,map('0'#)b++map('1'#)d):e
n#(a,b)=(a,n:b)
p=unlines.map(\(a,b)->a:" "++b).s snd.f

Przykład użycia:

*Main> putStr $ p "this question is about huffman coding"
u 000
i 011
  101
a 0010
f 0011
h 1000
s 1100
t 1101
n 1110
o 1111
d 01000
e 01001
b 01010
c 01011
q 10010
g 100110
m 100111

Jak to działa:

pwywołań, fktóre budują tabelę Huffmana w postaci listy par (znak, kodowanie), np. [ ('a',"0"), ('b',"1") ]sortuje tabelę według długości kodowania, formatuje każdą parę pod kątem danych wyjściowych i łączy się z nowymi wierszami pomiędzy nimi.

fnajpierw sprawdza pojedynczą literę i zwraca odpowiednią tabelę. W przeciwnym razie sortuje ciąg wejściowy i grupuje sekwencje równych znaków (np. "ababa"-> ["aaa","bb"]) i odwzorowuje je na pary (sequence , [(char, "")]), (-> [ ("aaa", [('a',"")]), ("bb", [('b', "")])]. Pierwszy element służy do śledzenia częstotliwości, drugi element jest listą par znaku i to kodujący (który początkowo jest pusta). te wszystkie pojedyncze tabele elementem Huffmana, zgodnie z oczekiwaniami p, łączy się je przez gah .

gsortuje listę par według długości pierwszego elementu, tj. częstotliwości i wywołań h. hłączy tabele Huffmana pierwszych dwóch elementów, łącząc częstotliwości i umieszczając 0( 1) przed każdym elementem pierwszego (drugiego) stołu. Połącz obie tabele. Zadzwoń gponownie, zatrzymaj się, gdy pozostanie jeden element, wyrzuć część częstotliwości i zwróć pełny stół Huffmana.

K (ngn / k) , 78 bajtów

{h::0#'x;(#1_){{h[x],:!2;y,,,/x}.0 2_x@<#'x}/.=x;(?,/'x,'" ",'|'$h)(?x)?>#'=x}

Wypróbuj online!

zwraca listę ciągów do wydrukowania

h::0#'xtworzy pustą listę dla każdego znaku (technicznie zmienia kształt każdego znaku na długość 0). tam przechowamy odwrócone kody huffmana. używamy ::zamiast :do wykonania zadaniah globalnym, aby było widoczne w podfunkcjach.

.=x to lista list - indeksy łańcucha pogrupowane według wartości znakowej

(#1_) jest funkcją, która zwraca prawdę, jeśli długość argumentu wynosi> 1 (technicznie „długość 1 kropli ...”)

(#1_){... }/oznacza: gdy argument ma długość> 1, nadal stosuj funkcję nawiasu klamrowego

x@<#'x posortuj argument według długości

0 2_ pokroić w 2-elementową głowę i ogon

{h[x],:!2;y,,,/x}aktualizacja hprzez dodanie 0 i 1 do wskaźników zawartych w głowie; zwróć ogon z głową jako pojedynczy element

(?,/'x,'" ",'|'$h)(?x)?>#'=xodwróć każdy z h, sortuj, unikatowy, poprzedzaj odpowiednie znaki i ładnie formatuj

JavaScript (ES6) 279

Zasadniczo podstawowy algorytm z Wikipedii. Prawdopodobnie dam radę lepiej.

f=s=>{for(n=[...new Set(s)].map(c=>({c:c,f:[...s].filter(x=>x==c).length}));n[1];n.push({l:a=n.pop(),r:b=n.pop(),f:a.f+b.f,c:a.c+b.c}))n.sort((a,b)=>b.f-a.f);t=(n,b)=>(n.b=b,n.r)?(t(n.l,b+0),t(n.r,b+1)):o.push(n);t(n[0],'',o=[]);return o.sort((a,b)=>b.f-a.f).map(x=>x.c+' '+x.b)}

Bardziej czytelny wewnątrz fragmentu poniżej

f=s=>{
  for(n=[...new Set(s)].map(c=>({c:c,f:[...s].filter(x=>x==c).length}));
      n[1];
      n.push({l:a=n.pop(),r:b=n.pop(),f:a.f+b.f,c:a.c+b.c}))
    n.sort((a,b)=>b.f-a.f);
  t=(n,b)=>(n.b=b,n.r)?(t(n.l,b+0),t(n.r,b+1)):o.push(n);
  t(n[0],'',o=[]);
  return o.sort((a,b)=>b.f-a.f).map(x=>x.c+' '+x.b)
}

//TEST
console.log=x=>O.innerHTML+=x+'\n'

test=['xxxxxxxxy','uuvvwwxxyyzz','this question is about huffman coding']
.forEach(t=>console.log(t+'\n'+f(t).join`\n`+'\n'))

<pre id=O></pre>