Hi, all, bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.). It is intended to show how people with disabilities similar to Stephen Hawking's (i.e., good cognitive hability, but very few movements) can write text. http://hackage.haskell.org/package/bitspeak http://bitbucket.org/mauricio/bitspeak/wiki/Home Best, Maurício
On 21.06.2010 23:50, Maurício CA wrote:
Hi, all,
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.).
Looks cool! Did you forget any dependencies tho? I get the following error: 0:16 nils` cabal update Downloading the latest package list from hackage.haskell.org 0:17 nils` cabal install bitspeak Resolving dependencies... Configuring bitspeak-0.0.1... Preprocessing executables for bitspeak-0.0.1... Building bitspeak-0.0.1... src/Main.hs:7:7: Could not find module `Corpora': Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: bitspeak-0.0.1 failed during the building phase. The exception was: ExitFailure 1 Thx, Nils
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.).
Looks cool! Did you forget any dependencies tho? I get the following error:
Oops... Three modules ended up missing in .cabal file. Just uploaded 0.0.2 to hackage, it should work. Thanks! Maurício
On Mon, 21 Jun 2010, Maurício CA wrote:
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.).
Looks cool! Did you forget any dependencies tho? I get the following error:
Oops... Three modules ended up missing in .cabal file. Just uploaded 0.0.2 to hackage, it should work.
Two this end, before uploading a package to Hackage I run a script in order to check whether the package can build: $ cat cabal-test package=`basename $1 .tar.gz` tar xfz ./dist/$package.tar.gz --directory=/tmp/ cd /tmp/$package/ runhaskell Setup configure --user runhaskell Setup build runhaskell Setup haddock echo echo "'cabal check' says" cabal check echo echo "After running tests you may want to call:" echo rm -r /tmp/$package/ Run it like $ cabal-test dist/bitspeak-0.0.1.tar.gz
2010/6/21 Maurício CA
Hi, all,
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.). It is intended to show how people with disabilities similar to Stephen Hawking's (i.e., good cognitive hability, but very few movements) can write text.
Neat! Have you looked at Dasher? http://www.inference.phy.cam.ac.uk/dasher/
On Mon, Jun 21, 2010 at 06:50:41PM -0300, Maurício CA wrote:
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.). It is intended to show how people with disabilities similar to Stephen Hawking's (i.e., good cognitive hability, but very few movements) can write text.
There is a parallel between data compression algorithms and this sort of task, expressing a sentence in the minimal number of bits via compression also minimized the number of yes/no questions that need to be asked. In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.).
There is a parallel between data compression algorithms and this sort of task, expressing a sentence in the minimal number of bits via compression also minimized the number of yes/no questions that need to be asked.
In particular, a Huffman coding:
Sure, Huffman was actually my first tought. But I couldn't think of a pratical display for the result of Huffman encoding that could be easily followed by a human looking at the screen. Since it's an optimal code, letters would not be grouped in alphabetical order. Thinking again, this could be easily accomplished... I could just list the alphabet and the next bit to be choosed below each letter. TODO for 0.1. Thanks! Maurício
On Mon, 21 Jun 2010, Maurício CA wrote:
bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.).
There is a parallel between data compression algorithms and this sort of task, expressing a sentence in the minimal number of bits via compression also minimized the number of yes/no questions that need to be asked.
In particular, a Huffman coding:
Sure, Huffman was actually my first tought. But I couldn't think of a pratical display for the result of Huffman encoding that could be easily followed by a human looking at the screen.
http://www.inference.phy.cam.ac.uk/dasher/
Tony.
--
f.anthony.n.finch
On Jun 22, 2010, at 1:26 PM, Maurí cio CA wrote:
Sure, Huffman was actually my first tought. But I couldn't think of a pratical display for the result of Huffman encoding that could be easily followed by a human looking at the screen. Since it's an optimal code, letters would not be grouped in alphabetical order.
There is a compromise. There is such a thing as an ORDERED Huffman code. Consider a set of strings. If they call begin with the same first letter, assume that letter and consider the suffixes instead. Otherwise, choose a letter L such that as close as possible to half of the strings begin with a letter preceding L in the alphabet as close as possible to half of the strings begin with the letter L or a later letter.
Sure, Huffman was actually my first tought. But I couldn't think of a pratical display for the result of Huffman encoding that could be easily followed by a human looking at the screen. Since it's an optimal code, letters would not be grouped in alphabetical order.
There is a compromise. There is such a thing as an ORDERED Huffman code. Consider a set of strings. If they call begin with the same first letter, assume that letter and consider the suffixes instead. Otherwise, choose a letter L such that as close as possible to half of the strings begin with a letter preceding L in the alphabet as close as possible to half of the strings begin with the letter L or a later letter.
I believe that's what I've done. I use this file to give weight to letters: http://bitbucket.org/mauricio/bitspeak/src/tip/src/Corpora.hs After each letter is selected I keep only sufixes after that letter, and then I use 'splitData' to find the point where I'll separate both halves: http://bitbucket.org/mauricio/bitspeak/src/tip/src/Main.hs Best, Maurício
John Meacham wrote:
In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too.
Interestingly, Huffman coding is one of those problems with a trivially simple mathematical expression, which none the less turns out to be difficult to express succinctly in Haskell. Oh, you can *do* it. It just seems to take a surprising amount of typing...
On Tue, Jun 22, 2010 at 06:24:22PM +0100, Andrew Coppin wrote:
John Meacham wrote:
In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too.
Interestingly, Huffman coding is one of those problems with a trivially simple mathematical expression, which none the less turns out to be difficult to express succinctly in Haskell. Oh, you can *do* it. It just seems to take a surprising amount of typing...
Hmmm.... Do I hear a challenge? :) Actually, I can't find my huffman code at the moment, I would be curious what others take on the problem was. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/
john:
On Tue, Jun 22, 2010 at 06:24:22PM +0100, Andrew Coppin wrote:
John Meacham wrote:
In particular, a Huffman coding: http://en.wikipedia.org/wiki/Huffman_coding is ideal for this (assuming you just are taking advantage of frequency analysis). A dynamic Huffman Tree will even adapt as it is being used to whatever the current language is. Huffman Trees are easy and fun to implement too.
Interestingly, Huffman coding is one of those problems with a trivially simple mathematical expression, which none the less turns out to be difficult to express succinctly in Haskell. Oh, you can *do* it. It just seems to take a surprising amount of typing...
Hmmm.... Do I hear a challenge? :)
Actually, I can't find my huffman code at the moment, I would be curious what others take on the problem was.
http://hackage.haskell.org/package/huffman A simple and pure Haskell implementation of the Huffman encoding algorithm. Google turns up a lot of results.
Don Stewart wrote:
http://hackage.haskell.org/package/huffman
A simple and pure Haskell implementation of the Huffman encoding algorithm.
What the...? Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-) Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had.
On Tue, Jun 22, 2010 at 4:18 PM, Andrew Coppin
What the...?
Oh, I see. It uses another package to handle the tricky sorting and
searching stuff. Well, yeah, that would make the code a bit shorter... ;-)
Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had.
I would argue that quicksort is considerably simpler, as it doesn't have to maintain an explicit tree, lookup and merge values, deal with bits, etc. For something, perhaps closer in spirit to quicksort, and still compression-oriented, I have an implementation of LZ78 for decompressing streams directly into a monoid, rather than reconstituting the result, which also winds up remarkably terse and a great deal more general than its imperative counter-parts. ;) http://hackage.haskell.org/packages/archive/monoids/0.1.36/doc/html/src/Data... -Edward Kmett
On Tue, Jun 22, 2010 at 10:18 PM, Andrew Coppin
Don Stewart wrote:
http://hackage.haskell.org/package/huffman
A simple and pure Haskell implementation of the Huffman encoding algorithm.
What the...?
Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-)
Quicksort is naturally expressed using filter and (++), etc. Huffman coding is naturally expressed in terms of priority queues, etc. Why is using the right vocabulary OK in one case and not in the other? This seems like an example of list-chauvinism -- what Chris Okasaki calls a communal blind spot of the FP community in Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design -- http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps --Max
G'day all.
Quoting Andrew Coppin
What the...?
Oh, I see. It uses another package to handle the tricky sorting and searching stuff. Well, yeah, that would make the code a bit shorter... ;-)
Even so, it's not nearly as elegant to behold as, say, the quicksort algorithm, despite being of roughly similar complexity. Still, it's shorter than what I had.
Ah, but the famous Haskell quicksort algorithm is optimised for brevity. It's an executable specification of quicksort, not a practical sort algorithm. But honestly, it's just not that hard to do in linear time, assuming the symbols are sorted by frequency: data HuffmanTree a = Empty | Node (HuffmanTree a) (HuffmanTree a) | Leaf a deriving Show huffmanTree :: (Ord w, Num w) => [(w,a)] -> HuffmanTree a huffmanTree = build . map (id &&& Leaf) . sortBy (comparing fst) where build [] = Empty build [(_,t)] = t build ((w1,t1):(w2,t2):wts) = build $ insertBy (comparing fst) (w1+w2, Node t1 t2) wts Now if you want a real challenge, implement length-limited Huffman codes. Here's a suggested interface: -- There really should be a better traits typeclass for bit hackery, -- but there isn't. class (Integral w, Bits w) => WordType w where { wordBits :: w -> Int } instance WordType Word8 where { wordBits = 8 } instance WordType Word16 where { wordBits = 16 } instance WordType Word32 where { wordBits = 32 } instance WordType Word64 where { wordBits = 64 } minimalRedundancyCode :: (Ord w, Num w, WordType word) => [(w,a)] -> [(a,Int,word)] -- minimalRedundancyCode returns an optimal prefix-free minimal-redundancy -- code such that every code fits in a word of size w. An entry (a,b,w) -- in the result means that the code for a is stored in the b least -- significant bits of w. Andrew Bromage
Andrew Bromage wrote:
But honestly, it's just not that hard to do in linear time, assuming the symbols are sorted by frequency:
Or maybe not so easy.
But not much harder. data Tree a = Branch (Tree a) (Tree a) | Leaf a deriving Show huffmanTree :: (Ord a, Num a) => [(a, b)] -> Tree b huffmanTree [] = error "huffmanTree: empty code" huffmanTree xs = let xs' = sortBy (comparing fst) [(a, Leaf b) | (a, b) <- xs] branches ((a, l) : (b, r) : ts) = (a+b, Branch l r) : branches ts merged = merge (-1 :: Int) xs' (branches merged) merge n [] ys = take n ys merge n (x:xs) ys | n <= 0 = x : merge (n+1) xs ys merge n (x:xs) (y:ys) = case comparing fst x y of GT -> y : merge (n-1) (x:xs) ys _ -> x : merge (n+1) xs (y:ys) in snd $ last merged regards, Bertram
Hello ajb, Wednesday, June 23, 2010, 6:58:30 AM, you wrote:
build ((w1,t1):(w2,t2):wts) = build $ insertBy (comparing fst) (w1+w2, Node t1 t2) wts
this algo is O(n^2). to be O(n) you should handle separate lists of leafs and nodes, adding new nodes to the tail of second list -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
participants (15)
-
ajb＠spamcop.net -
Andrew Bromage
-
Andrew Coppin -
Bertram Felgenhauer -
Bulat Ziganshin -
Don Stewart -
Edward Kmett -
Henning Thielemann -
John Meacham -
Maurício CA -
Max Rabkin -
Nils Schweinsberg -
Richard O'Keefe -
Tom Hawkins -
Tony Finch