#! /usr/bin/python
## map from fibonacci code to integer, but growing from the
## tail instead of the head. (cf Decode.py)
## David MacKay Dec 2005
## Reads binary fibo-strings from stdin and writes integers to stdout
from Fibo import * ## supplies Fibonacci
import sys, string
from Numeric import *
verbose=0
fibs=Fibonacci()
#for i in range(6):
# print i,fibs.calculate(i)
sortbynumber=1
class node:
 def __init__(self, index, name="", length=0,invP=1):
 self.index = index
 self.name = name 
 self.length = length
 self.invP = invP
 ## P(stop now) = 1/2
 self.iPX = invP * 2.0
 n = self.index
 ## this is a rubbish rule for P0 and P1; correct for binaryDecode but not fibo.
 ## P(child,0) = 1/2 * (n+1)/(2n+1)
 self.iP0 = self.iPX * (2 * n + 1.0)/(n+1.0)
 self.iP1 = self.iPX * (2 * n + 1.0)/(n)
 allnodes.append( self )
 def __cmp__(self, other):
 if sortbynumber :
 return cmp(self.index, other.index)
 else :
 return cmp(self.name, other.name)
 def report(self):
 if (self.index == 1 ) :
 print '#N Len\tCodewrd'
 print '%-4d %-3d %-10s %10.5g' % \
 (self.index,self.length,self.name+"_",self.iPX)
 def child(self,type) :
 length = self.length
 if(type==0):
 n = self.index + fibs.calculate(length)
 name = '0' + self.name 
 predecessor = self.index
 length = self.length + 1
 invP = self.iP0
 else:
 n = self.index + fibs.calculate(length+3)
 name = '1' + self.name 
 length = self.length + 2
 invP = self.iP1
 return node(n,name,length,invP)
if(0):
## Make first node
 one = node( 1 )
 for line in sys.stdin.readlines():
 if line[0] != '#' :
 words = string.split(line)
 for w in words :
 wl = list(w)
 wl.reverse()
 ch = one 
 for s in wl :
 ch = ch.child(int(s))
 print ch.index
if __name__ == '__main__':
 c=[]
 maxlength = 19
 for length in range(maxlength+2) :
 # print length
 c.append( [] )
 allnodes = [] 
## Make first node
 one = node( 1 )
 c[0] = [one]
 ## extend all words generated thus far 
 for length in range(maxlength) :
 if verbose:
 print "extending all with length",length
 for n in c[length] :
 for suffix in [0,1] :
 ch = n.child(suffix)
 chlen = ch.length
 c[chlen].append( ch )
 if verbose:
 print "# sorted by length" 
 for length in range(maxlength) :
 for n in c[length] :
 n.report()
 allnodes.sort() 
 print "# sorted by index"
 cum = 0.0 
 for n in allnodes :
 cum += 1.0/(n.invP)
 pass
 print "# CUM:", cum
 for n in allnodes :
 n.report()
 pass
 pass
pass
 
</div><div class="naked_ctrl">
<form action="/index.cgi/larger-text" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="http://www.inference.org.uk/mackay/python/fibonacci/TailDecode2.py">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="http://www.inference.org.uk/mackay/python/fibonacci/TailDecode2.py" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast">配色反転</option>
<option value="larger-text" selected="selected">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>