<s> from __future__ import print_function <EOL> from __future__ import division <EOL> from math import log , exp <EOL> def getz ( r , nr ) : <EOL> z = [ <NUM_LIT:2> * nr [ <NUM_LIT:0> ] / r [ <NUM_LIT:1> ] ] <EOL> for i in xrange ( len ( nr ) - <NUM_LIT:2> ) : <EOL> z . append ( <NUM_LIT:2> * nr [ i + <NUM_LIT:1> ] / ( r [ i + <NUM_LIT:2> ] - r [ i ] ) ) <EOL> z . append ( nr [ - <NUM_LIT:1> ] / ( r [ - <NUM_LIT:1> ] - r [ - <NUM_LIT:2> ] ) ) <EOL> return z <EOL> def least_square ( x , y ) : <EOL> meanx = sum ( x ) / len ( x ) <EOL> meany = sum ( y ) / len ( y ) <EOL> xy = sum ( ( x [ i ] - meanx ) * ( y [ i ] - meany ) for i in range ( len ( x ) ) ) <EOL> square = sum ( ( x [ i ] - meanx ) ** <NUM_LIT:2> for i in range ( len ( x ) ) ) <EOL> b = xy / square <EOL> return ( meany - b * meanx , b ) <EOL> def main ( dic ) : <EOL> values = sorted ( dic . values ( ) ) <EOL> r , nr , prob = [ ] , [ ] , [ ] <EOL> for v in values : <EOL> if not r or r [ - <NUM_LIT:1> ] != v : <EOL> r . append ( v ) <EOL> nr . append ( <NUM_LIT:1> ) <EOL> else : <EOL> nr [ - <NUM_LIT:1> ] += <NUM_LIT:1> <EOL> rr = dict ( map ( lambda x : list ( reversed ( x ) ) , enumerate ( r ) ) ) <EOL> total = reduce ( lambda x , y : ( x [ <NUM_LIT:0> ] * x [ <NUM_LIT:1> ] + y [ <NUM_LIT:0> ] * y [ <NUM_LIT:1> ] , <NUM_LIT:1> ) , zip ( nr , r ) ) [ <NUM_LIT:0> ] <EOL> z = getz ( r , nr ) <EOL> a , b = least_square ( map ( lambda x : log ( x ) , r ) , map ( lambda x : log ( x ) , z ) ) <EOL> use_good_turing = False <EOL> nr . append ( exp ( a + b * log ( r [ - <NUM_LIT:1> ] + <NUM_LIT:1> ) ) ) <EOL> for i in xrange ( len ( r ) ) : <EOL> good_turing = ( r [ i ] + <NUM_LIT:1> ) * ( exp ( b * ( log ( r [ i ] + <NUM_LIT:1> ) - log ( r [ i ] ) ) ) ) <EOL> turing = ( r [ i ] + <NUM_LIT:1> ) * nr [ i + <NUM_LIT:1> ] / nr [ i ] if i + <NUM_LIT:1> < len ( r ) else good_turing <EOL> diff = ( ( ( ( r [ i ] + <NUM_LIT:1> ) ** <NUM_LIT:2> ) / nr [ i ] * nr [ i + <NUM_LIT:1> ] / nr [ i ] * ( <NUM_LIT:1> + nr [ i + <NUM_LIT:1> ] / nr [ i ] ) ) ** <NUM_LIT:0.5> ) * <NUM_LIT> <EOL> if not use_good_turing and abs ( good_turing - turing ) > diff : <EOL> prob . append ( turing ) <EOL> else : <EOL> use_good_turing = True <EOL> prob . append ( good_turing ) <EOL> sump = reduce ( lambda x , y : ( x [ <NUM_LIT:0> ] * x [ <NUM_LIT:1> ] + y [ <NUM_LIT:0> ] * y [ <NUM_LIT:1> ] , <NUM_LIT:1> ) , zip ( nr , prob ) ) [ <NUM_LIT:0> ] <EOL> for cnt , i in enumerate ( prob ) : <EOL> prob [ cnt ] = ( <NUM_LIT:1> - nr [ <NUM_LIT:0> ] / total ) * i / sump <EOL> return nr [ <NUM_LIT:0> ] / total / total , dict ( zip ( dic . keys ( ) , map ( lambda x : prob [ rr [ x ] ] , dic . values ( ) ) ) ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> print ( main ( { <NUM_LIT:1> : <NUM_LIT:1> , <NUM_LIT:2> : <NUM_LIT:1> , <NUM_LIT:3> : <NUM_LIT:1> , <NUM_LIT:4> : <NUM_LIT:2> , <NUM_LIT:5> : <NUM_LIT:2> , <NUM_LIT:6> : <NUM_LIT:3> , <NUM_LIT:7> : <NUM_LIT:1> , <NUM_LIT:8> : <NUM_LIT:2> , <NUM_LIT:9> : <NUM_LIT:3> } ) ) </s>
