Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- datatype HuffmanTree =
- Node of (string * int) * HuffmanTree * HuffmanTree
- | Symbol of char * int;
- local
- fun unique [] = []
- | unique (x::xs) = x:: unique (List.filter (fn y => y<>x) xs);
- fun countLetterAux (x:string,a:char,i:int) = if i=size(x) then 0 else (if String.sub(x,i)=a then 1+countLetterAux(x,a,i+1) else countLetterAux(x,a,i+1));
- fun countLetter (x:string,a:char) = if size(x)=0 then 0 else countLetterAux(x,a,0);
- in
- fun computeHistogram "" = []
- | computeHistogram s = map (fn x => (x,countLetter(s,x))) (unique(explode s))
- end;
- local
- local
- fun merge _ [] [] = []
- | merge _ list [] = list
- | merge _ [] list = list
- | merge pred (x::xs) (y::ys) = if pred(x,y) then (y::(merge pred (x::xs) ys))
- else (x::(merge pred xs (y::ys)))
- in
- fun mergesort _ [] = []
- | mergesort _ [x] = [x]
- | mergesort pred l = merge pred
- (mergesort pred (List.take (l,((length l) div 2))))
- (mergesort pred (List.drop (l,((length l) div 2))))
- end;
- fun compareTuple ((x:string,n1),(y:string,n2)) = if n1=n2 then y<x else n2<n1
- fun compareTuple2 ((x:char,n1),(y:char,n2)) = compareTuple((str(x),n1),(str(y),n2))
- fun sortAndConvert lst = map (fn (x,n) => Symbol(x,n)) (mergesort compareTuple2 lst)
- fun buildHuffmanTreeAux (Symbol(x,n1)::Symbol(y,n2)::_) = Node(((str(x)^str(y)),(n1+n2)),Symbol(x,n1),Symbol(y,n2))
- | buildHuffmanTreeAux (Node((s,n1),T1,T2)::Symbol(y,n2)::_) = if compareTuple((s,n1),(str(y),n2))
- then Node((str(y)^s,n1+n2),Symbol(y,n2),Node((s,n1),T1,T2))
- else Node((s^str(y),n1+n2),Node((s,n1),T1,T2),Symbol(y,n2))
- fun buildHuffmanList (x::[]) = x
- | buildHuffmanList lst = buildHuffmanList((buildHuffmanTreeAux (List.take(lst,2)))::(List.drop(lst,2)))
- in
- fun buildHuffmanTree lst = buildHuffmanList (sortAndConvert lst)
- end;
- fun encodeMessage tree s =
- let
- fun LetterEncodingHist (Symbol(x,n),s) = [(x,s)]
- | LetterEncodingHist (Node(_,T1,T2),s) = (LetterEncodingHist (T1,s^"0"))@(LetterEncodingHist (T2,s^"1"))
- fun LetterEncoding ([],_) = ""
- | LetterEncoding ((y,s)::lst,x) = if y=x then s else LetterEncoding (lst,x)
- val hist = LetterEncodingHist(tree,"")
- in
- foldr op^ "" (map (fn c => LetterEncoding(hist,c)) (explode s))
- end;
- local
- fun decodeMessageAux (Symbol(a,n)) _ [] = str(a)
- | decodeMessageAux (Symbol(a,n)) T2 lst = str(a)^(decodeMessageAux T2 T2 lst)
- | decodeMessageAux (Node((x,n),TL,TR)) T2 lst = if (hd lst) = #"0" then decodeMessageAux TL T2 (tl lst)
- else decodeMessageAux TR T2 (tl lst)
- in
- fun decodeMessage tree s = decodeMessageAux tree tree (explode s)
- end;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement