import string
import numpy as np

MARKOV_THRESHOLD = -0.005

BIGRAM_COUNTS_CORPUS = [
    ["th", 100272945963],
    ["he", 86697336727],
    ["in", 68595215308],
    ["er", 57754162106],
    ["an", 55974567611],
    ["re", 52285662239],
    ["on", 49570981965],
    ["at", 41920838452],
    ["en", 41004903554],
    ["nd", 38129777631],
    ["ti", 37856196209],
    ["es", 37766388079],
    ["or", 35994097756],
    ["te", 33973261529],
    ["of", 33130341561],
    ["ed", 32937140633],
    ["is", 31817918249],
    ["it", 31672532308],
    ["al", 30662410438],
    ["ar", 30308513014],
    ["st", 29704461829],
    ["to", 29360205581],
    ["nt", 29359771944],
    ["ng", 26871805511],
    ["se", 26282488562],
    ["ha", 26103411208],
    ["as", 24561944198],
    ["ou", 24531132241],
    ["io", 23542263265],
    ["le", 23382173640],
    ["ve", 23270129573],
    ["co", 22384167777],
    ["me", 22360109325],
    ["de", 21565300071],
    ["hi", 21520845924],
    ["ri", 20516398905],
    ["ro", 20491179118],
    ["ic", 19701195496],
    ["ne", 19504235770],
    ["ea", 19403941063],
    ["ra", 19332539912],
    ["ce", 18367773425],
    ["li", 17604626629],
    ["ch", 16854985236],
    ["ll", 16257360474],
    ["be", 16249257887],
    ["ma", 15938689768],
    ["si", 15509759748],
    ["om", 15402602484],
    ["ur", 15303657594],
    ["ca", 15174413181],
    ["el", 14952716079],
    ["ta", 14941000711],
    ["la", 14874551789],
    ["ns", 14350320288],
    ["di", 13899990598],
    ["fo", 13753006196],
    ["ho", 13672603513],
    ["pe", 13477683504],
    ["ec", 13457763533],
    ["pr", 13378480175],
    ["no", 13099447521],
    ["ct", 12997849406],
    ["us", 12808517567],
    ["ac", 12625666388],
    ["ot", 12465822481],
    ["il", 12167821320],
    ["tr", 12006693396],
    ["ly", 11983948242],
    ["nc", 11722631112],
    ["et", 11634161334],
    ["ut", 11423899818],
    ["ss", 11421755201],
    ["so", 11214705934],
    ["rs", 11180732354],
    ["un", 11121118166],
    ["lo", 10908830081],
    ["wa", 10865206430],
    ["ge", 10861045622],
    ["ie", 10845731320],
    ["wh", 10680697684],
    ["ee", 10647199443],
    ["wi", 10557401491],
    ["em", 10536054813],
    ["ad", 10375130449],
    ["ol", 10305660447],
    ["rt", 10198055461],
    ["po", 10189505383],
    ["we", 10176141608],
    ["na", 9790855551],
    ["ul", 9751225781],
    ["ni", 9564648232],
    ["ts", 9516029773],
    ["mo", 9498813191],
    ["ow", 9318366591],
    ["pa", 9123652775],
    ["im", 8959759181],
    ["mi", 8957825538],
    ["ai", 8922759715],
    ["sh", 8888705287],
    ["ir", 8886799024],
    ["su", 8774129154],
    ["id", 8332214014],
    ["os", 8176085241],
    ["iv", 8116349309],
    ["ia", 8072199471],
    ["am", 8032259916],
    ["fi", 8024355222],
    ["ci", 7936922442],
    ["vi", 7600241898],
    ["pl", 7415349106],
    ["ig", 7189051323],
    ["tu", 7187510085],
    ["ev", 7184041787],
    ["ld", 7122648226],
    ["ry", 6985436186],
    ["mp", 6743935008],
    ["fe", 6670566518],
    ["bl", 6581097936],
    ["ab", 6479202253],
    ["gh", 6414827751],
    ["ty", 6408447994],
    ["op", 6313536754],
    ["wo", 6252724050],
    ["sa", 6147356936],
    ["ay", 6128842727],
    ["ex", 6035335807],
    ["ke", 6027536039],
    ["fr", 6011200185],
    ["oo", 5928601045],
    ["av", 5778409728],
    ["ag", 5772552144],
    ["if", 5731148470],
    ["ap", 5719570727],
    ["gr", 5548472398],
    ["od", 5511014957],
    ["bo", 5509918152],
    ["sp", 5392724233],
    ["rd", 5338083783],
    ["do", 5307591560],
    ["uc", 5291161134],
    ["bu", 5214802738],
    ["ei", 5169898489],
    ["ov", 5021440160],
    ["by", 4975814759],
    ["rm", 4938158020],
    ["ep", 4837800987],
    ["tt", 4812693687],
    ["oc", 4692062395],
    ["fa", 4624241031],
    ["ef", 4588497002],
    ["cu", 4585165906],
    ["rn", 4521640992],
    ["sc", 4363410770],
    ["gi", 4275639800],
    ["da", 4259590348],
    ["yo", 4226720021],
    ["cr", 4214150542],
    ["cl", 4201617719],
    ["du", 4186093215],
    ["ga", 4175274057],
    ["qu", 4160167957],
    ["ue", 4158448570],
    ["ff", 4125634219],
    ["ba", 4122472992],
    ["ey", 4053144855],
    ["ls", 3990203351],
    ["va", 3946966167],
    ["um", 3901923211],
    ["pp", 3850125519],
    ["ua", 3844138094],
    ["up", 3835093459],
    ["lu", 3811884104],
    ["go", 3725558729],
    ["ht", 3670802795],
    ["ru", 3618438291],
    ["ug", 3606562400],
    ["ds", 3560125353],
    ["lt", 3486149365],
    ["pi", 3470838749],
    ["rc", 3422694015],
    ["rr", 3404547067],
    ["eg", 3370515965],
    ["au", 3356322923],
    ["ck", 3316660134],
    ["ew", 3293529190],
    ["mu", 3231856188],
    ["br", 3145611704],
    ["bi", 3005679357],
    ["pt", 2982699529],
    ["ak", 2952167845],
    ["pu", 2947681332],
    ["ui", 2852182384],
    ["rg", 2813274913],
    ["ib", 2780268452],
    ["tl", 2775935006],
    ["ny", 2760941827],
    ["ki", 2759841743],
    ["rk", 2736041446],
    ["ys", 2730343336],
    ["ob", 2725791138],
    ["mm", 2708822249],
    ["fu", 2706168901],
    ["ph", 2661480326],
    ["og", 2651165734],
    ["ms", 2617582287],
    ["ye", 2612941418],
    ["ud", 2577213760],
    ["mb", 2544901434],
    ["ip", 2515455253],
    ["ub", 2497666762],
    ["oi", 2474275212],
    ["rl", 2432373251],
    ["gu", 2418410978],
    ["dr", 2409399231],
    ["hr", 2379584978],
    ["cc", 2344219345],
    ["tw", 2322619238],
    ["ft", 2302659749],
    ["wn", 2227183930],
    ["nu", 2217508482],
    ["af", 2092395523],
    ["hu", 2077887429],
    ["nn", 2051719074],
    ["eo", 2044268477],
    ["vo", 2004982879],
    ["rv", 1953555667],
    ["nf", 1894270041],
    ["xp", 1885334638],
    ["gn", 1850801359],
    ["sm", 1838392669],
    ["fl", 1830098844],
    ["iz", 1814164135],
    ["ok", 1813376076],
    ["nl", 1798491132],
    ["my", 1753447198],
    ["gl", 1709752272],
    ["aw", 1689436638],
    ["ju", 1655210582],
    ["oa", 1620913259],
    ["eq", 1614312175],
    ["sy", 1602829285],
    ["sl", 1575646777],
    ["ps", 1538723474],
    ["jo", 1516687319],
    ["lf", 1507867867],
    ["nv", 1466426243],
    ["je", 1463052212],
    ["nk", 1455100124],
    ["kn", 1450401608],
    ["gs", 1443474876],
    ["dy", 1421751251],
    ["hy", 1412343465],
    ["ze", 1402290616],
    ["ks", 1339590722],
    ["xt", 1315669490],
    ["bs", 1292319275],
    ["ik", 1209994695],
    ["dd", 1205446875],
    ["cy", 1176324279],
    ["rp", 1173542093],
    ["sk", 1112771273],
    ["xi", 1111463633],
    ["oe", 1089254517],
    ["oy", 1020190223],
    ["ws", 989253674],
    ["lv", 984229060],
    ["dl", 911886482],
    ["rf", 909634941],
    ["eu", 878402090],
    ["dg", 874188188],
    ["wr", 867361010],
    ["xa", 834649781],
    ["yi", 812619095],
    ["nm", 782441941],
    ["eb", 763383542],
    ["rb", 753194669],
    ["tm", 746621025],
    ["xc", 746076293],
    ["eh", 742240059],
    ["tc", 736955048],
    ["gy", 731420025],
    ["ja", 729206855],
    ["hn", 726288117],
    ["yp", 702499946],
    ["za", 702199296],
    ["gg", 697999944],
    ["ym", 667551857],
    ["sw", 663415953],
    ["bj", 654853039],
    ["lm", 649112313],
    ["cs", 643530723],
    ["ii", 642384029],
    ["ix", 621227893],
    ["xe", 614533122],
    ["oh", 602121281],
    ["lk", 555883002],
    ["dv", 537221821],
    ["lp", 536595562],
    ["ax", 531206960],
    ["ox", 523764012],
    ["uf", 522547858],
    ["dm", 512522701],
    ["iu", 490874936],
    ["sf", 483979931],
    ["bt", 482272940],
    ["ka", 478095427],
    ["yt", 470429861],
    ["ek", 464449289],
    ["pm", 449910017],
    ["ya", 444542870],
    ["gt", 434302509],
    ["wl", 429185823],
    ["rh", 426095630],
    ["yl", 416082307],
    ["hs", 414044112],
    ["ah", 384694919],
    ["yc", 380670476],
    ["yn", 372595315],
    ["rw", 359714599],
    ["hm", 359316447],
    ["lw", 356374125],
    ["hl", 355049620],
    ["ae", 349540062],
    ["zi", 341671190],
    ["az", 334669428],
    ["lc", 333338045],
    ["py", 331698156],
    ["aj", 331384552],
    ["iq", 318727904],
    ["nj", 312598990],
    ["bb", 308276690],
    ["nh", 306883963],
    ["uo", 300484143],
    ["kl", 298033281],
    ["lr", 283411884],
    ["tn", 282266629],
    ["gm", 277966576],
    ["sn", 258702825],
    ["nr", 258048421],
    ["fy", 256535008],
    ["mn", 247850339],
    ["dw", 230152384],
    ["sb", 223212317],
    ["yr", 219696469],
    ["dn", 213431654],
    ["sq", 209894196],
    ["zo", 202480511],
    ["oj", 196696657],
    ["yd", 192245315],
    ["lb", 188643782],
    ["wt", 184446342],
    ["lg", 171657388],
    ["ko", 171324962],
    ["np", 170186564],
    ["sr", 168896339],
    ["nq", 167770304],
    ["ky", 167761726],
    ["ln", 165509578],
    ["nw", 163456000],
    ["tf", 159626603],
    ["fs", 155349948],
    ["cq", 154363546],
    ["dh", 153344431],
    ["sd", 148275222],
    ["vy", 138085211],
    ["dj", 134832736],
    ["hw", 134615178],
    ["xu", 134528161],
    ["ao", 130442323],
    ["ml", 129888836],
    ["uk", 129819900],
    ["uy", 128782521],
    ["ej", 128194584],
    ["ez", 127540198],
    ["hb", 123778334],
    ["nz", 123192934],
    ["nb", 122258836],
    ["mc", 121591374],
    ["yb", 121220723],
    ["tp", 121089391],
    ["xh", 117618666],
    ["ux", 110947766],
    ["tz", 108527540],
    ["bv", 108385069],
    ["mf", 107664447],
    ["wd", 99767462],
    ["oz", 97904996],
    ["yw", 95070267],
    ["kh", 89811517],
    ["gd", 89087728],
    ["bm", 88228719],
    ["mr", 87580303],
    ["ku", 85313841],
    ["uv", 82252351],
    ["dt", 81648332],
    ["hd", 80544316],
    ["aa", 79794787],
    ["xx", 79068246],
    ["df", 78347492],
    ["db", 78190243],
    ["ji", 77899882],
    ["kr", 76743394],
    ["xo", 76097183],
    ["cm", 75144874],
    ["zz", 75012595],
    ["nx", 73899576],
    ["yg", 73102462],
    ["xy", 72645837],
    ["kg", 72267691],
    ["tb", 71746167],
    ["dc", 71030077],
    ["bd", 69761165],
    ["sg", 69588685],
    ["wy", 68368953],
    ["zy", 66473188],
    ["aq", 63283982],
    ["hf", 63249924],
    ["cd", 62905910],
    ["vu", 62384927],
    ["kw", 61416538],
    ["zu", 60692846],
    ["bn", 59062122],
    ["ih", 58966344],
    ["tg", 55522877],
    ["xv", 55076715],
    ["uz", 53873803],
    ["bc", 53278096],
    ["xf", 52374239],
    ["yz", 51097953],
    ["km", 50449220],
    ["dp", 48855638],
    ["lh", 45643026],
    ["wf", 45330551],
    ["kf", 44759608],
    ["pf", 41022263],
    ["cf", 39704311],
    ["mt", 38538709],
    ["yu", 37436235],
    ["cp", 37067423],
    ["pb", 36901495],
    ["td", 36539510],
    ["zl", 35456851],
    ["sv", 35005005],
    ["hc", 34631551],
    ["mg", 34537023],
    ["pw", 34037460],
    ["gf", 33962536],
    ["pd", 33798376],
    ["pn", 33536129],
    ["pc", 33156666],
    ["rx", 32990613],
    ["tv", 32805751],
    ["ij", 31324465],
    ["wm", 30732232],
    ["uh", 30097154],
    ["wk", 30095733],
    ["wb", 29929113],
    ["bh", 29797934],
    ["oq", 29227658],
    ["kt", 29132180],
    ["rq", 28152573],
    ["kb", 25406204],
    ["cg", 24975673],
    ["vr", 24701238],
    ["cn", 24249641],
    ["pk", 23099462],
    ["uu", 22006895],
    ["yf", 21246637],
    ["wp", 20982546],
    ["cz", 20601701],
    ["kp", 20492678],
    ["dq", 19927900],
    ["wu", 19601657],
    ["fm", 19340776],
    ["wc", 19008254],
    ["md", 18929019],
    ["kd", 18894758],
    ["zh", 18782710],
    ["gw", 18260884],
    ["rz", 17993128],
    ["cb", 17751935],
    ["iw", 17611969],
    ["xl", 16728256],
    ["hp", 16696129],
    ["mw", 16465357],
    ["vs", 16263248],
    ["fc", 16254390],
    ["rj", 15598009],
    ["bp", 15427250],
    ["mh", 15033898],
    ["hh", 14730425],
    ["yh", 14682887],
    ["uj", 14548024],
    ["fg", 14424524],
    ["fd", 13966832],
    ["gb", 13944852],
    ["pg", 13354952],
    ["tk", 13081991],
    ["kk", 12782664],
    ["hq", 11925353],
    ["fn", 11823066],
    ["lz", 11767790],
    ["vl", 11621019],
    ["gp", 11612944],
    ["hz", 10729982],
    ["dk", 9494027],
    ["yk", 9292584],
    ["qi", 8954617],
    ["lx", 8612462],
    ["vd", 8430332],
    ["zs", 8395904],
    ["bw", 8319869],
    ["xq", 8225536],
    ["mv", 8172535],
    ["uw", 7824504],
    ["hg", 7789748],
    ["fb", 7730842],
    ["sj", 7621847],
    ["ww", 7377619],
    ["gk", 7338894],
    ["uq", 7235727],
    ["bg", 7203255],
    ["sz", 7041052],
    ["jr", 6846578],
    ["ql", 6708919],
    ["zt", 6627349],
    ["hk", 6595610],
    ["vc", 6570845],
    ["xm", 6569222],
    ["gc", 6455066],
    ["fw", 6451511],
    ["pz", 6382200],
    ["kc", 6326022],
    ["hv", 6292998],
    ["xw", 6292525],
    ["zw", 6279286],
    ["fp", 6262895],
    ["iy", 6247588],
    ["pv", 6222096],
    ["vt", 6181932],
    ["jp", 6129447],
    ["cv", 5869407],
    ["zb", 5858211],
    ["vp", 5510046],
    ["zr", 5320518],
    ["fh", 5166165],
    ["yv", 5115763],
    ["zg", 4726653],
    ["zm", 4713608],
    ["zv", 4618705],
    ["qs", 4448602],
    ["kv", 4414960],
    ["vn", 4317772],
    ["zn", 4300522],
    ["qa", 4298294],
    ["yx", 4211192],
    ["jn", 4150888],
    ["bf", 4108696],
    ["mk", 3956883],
    ["cw", 3909223],
    ["jm", 3659540],
    ["lq", 3582930],
    ["jh", 3541869],
    ["kj", 3471162],
    ["jc", 3447571],
    ["gz", 3431194],
    ["js", 3329038],
    ["tx", 3328898],
    ["fk", 3293208],
    ["jl", 3192327],
    ["vm", 3178223],
    ["lj", 3169833],
    ["tj", 3169658],
    ["jj", 2979950],
    ["cj", 2962048],
    ["vg", 2960268],
    ["mj", 2923325],
    ["jt", 2917850],
    ["pj", 2810773],
    ["wg", 2751783],
    ["vh", 2691078],
    ["bk", 2639491],
    ["vv", 2622571],
    ["jd", 2615147],
    ["tq", 2517400],
    ["vb", 2496014],
    ["jf", 2421784],
    ["dz", 2200704],
    ["xb", 2164724],
    ["jb", 2126115],
    ["zc", 2100797],
    ["fj", 2065436],
    ["yy", 1993017],
    ["qn", 1859810],
    ["xs", 1804740],
    ["qr", 1744325],
    ["jk", 1740133],
    ["jv", 1719726],
    ["qq", 1712219],
    ["xn", 1613611],
    ["vf", 1550317],
    ["px", 1473468],
    ["zd", 1415016],
    ["qt", 1385505],
    ["zp", 1361846],
    ["qo", 1324363],
    ["dx", 1296277],
    ["hj", 1282370],
    ["gv", 1192366],
    ["jw", 1165914],
    ["qc", 1127399],
    ["jy", 1120221],
    ["gj", 1093028],
    ["qb", 1083443],
    ["pq", 1075049],
    ["jg", 1034900],
    ["bz", 1007374],
    ["mx", 994334],
    ["qm", 989868],
    ["mz", 970282],
    ["qf", 947879],
    ["wj", 914179],
    ["zq", 913036],
    ["xr", 907409],
    ["zk", 906537],
    ["cx", 876736],
    ["fx", 812116],
    ["fv", 807297],
    ["bx", 778622],
    ["vw", 742188],
    ["vj", 724370],
    ["mq", 708424],
    ["qv", 635514],
    ["zf", 608389],
    ["qe", 572443],
    ["yj", 561334],
    ["gx", 557030],
    ["kx", 555422],
    ["xg", 542548],
    ["qd", 519921],
    ["xj", 511074],
    ["sx", 503772],
    ["vz", 501189],
    ["vx", 449854],
    ["wv", 389123],
    ["yq", 384882],
    ["bq", 346506],
    ["gq", 345624],
    ["vk", 337545],
    ["zj", 309029],
    ["xk", 281255],
    ["qp", 272180],
    ["hx", 263997],
    ["fz", 263860],
    ["qh", 263509],
    ["qj", 236928],
    ["jz", 220675],
    ["vq", 212856],
    ["kq", 187242],
    ["xd", 168263],
    ["qw", 163292],
    ["jx", 161750],
    ["qx", 159505],
    ["kz", 150760],
    ["wx", 150637],
    ["fq", 149430],
    ["xz", 136521],
    ["zx", 108224],
    ["jq", 0],
    ["qg", 0],
    ["qk", 0],
    ["qy", 0],
    ["qz", 0],
    ["wq", 0],
    ["wz", 0]
]
COMPANY_NAMES = """3 Round Stones, Inc.
48 Factoring Inc.
5PSolutions
Abt Associates
Accela
Accenture
AccuWeather
Acxiom
Adaptive
Adobe Digital Government
Aidin
Alarm.com
Allianz
Allied Van Lines
AllState Insurance Group
Alltuition
Altova
Amazon Web Services
American Red Ball Movers
Amida Technology Solutions
Analytica
Apextech LLC
Appallicious
Aquicore
Archimedes Inc.
AreaVibes Inc.
Arpin Van Lines
Arrive Labs
ASC Partners
Asset4
Atlas Van Lines
AtSite
Aunt Bertha, Inc.
Aureus Sciences (*Now part of Elsevier)
AutoGrid Systems
Avalara
Avvo
Ayasdi
Azavea
BaleFire Global
Barchart
Be Informed
Bekins
Berkery Noyes MandASoft
Berkshire Hathaway
BetterLesson
BillGuard
Bing
Biovia
BizVizz
BlackRock
Bloomberg
Booz Allen Hamilton
Boston Consulting Group
Boundless
Bridgewater
Brightscope
BuildFax
Buildingeye
BuildZoom
Business and Legal Resources
Business Monitor International
Calcbench, Inc.
Cambridge Information Group
Cambridge Semantics
CAN Capital
Canon
Capital Cube
Cappex
Captricity
CareSet Systems
Careset.com
CARFAX
Caspio
Castle Biosciences
CB Insights
Ceiba Solutions
Center for Responsive Politics
Cerner
Certara
CGI
Charles River Associates
Charles Schwab Corp.
Chemical Abstracts Service
Child Care Desk
Chubb
Citigroup
CityScan
CitySourced
Civic Impulse LLC
Civic Insight
Civinomics
Civis Analytics
Clean Power Finance
ClearHealthCosts
ClearStory Data
Climate Corporation
CliniCast
Cloudmade
Cloudspyre
Code for America
Code-N
Collective IP
College Abacus, an ECMC initiative
College Board
Compared Care
Compendia Bioscience Life Technologies
Compliance and Risks
Computer Packages Inc
CONNECT-DOT LLC.
ConnectEDU
Connotate
Construction Monitor LLC
Consumer Reports
CoolClimate
Copyright Clearance Center
CoreLogic
CostQuest
Credit Karma
Credit Sesame
CrowdANALYTIX
Dabo Health
DataLogix
DataMade
DataMarket
Datamyne
DataWeave
Deloitte
DemystData
Department of Better Technology
Development Seed
Docket Alarm, Inc.
Dow Jones & Co.
Dun & Bradstreet
Earth Networks
EarthObserver App
Earthquake Alert!
Eat Shop Sleep
Ecodesk
eInstitutional
Embark
EMC
Energy Points, Inc.
Energy Solutions Forum
Enervee Corporation
Enigma.io
Ensco
Environmental Data Resources
Epsilon
Equal Pay for Women
Equifax
Equilar
Ernst & Young LLP
eScholar LLC.
Esri
Estately
Everyday Health
Evidera
Experian
Expert Health Data Programming, Inc.
Exversion
Ez-XBRL
Factset
Factual
Farmers
FarmLogs
Fastcase
Fidelity Investments
FindTheBest.com
First Fuel Software
FirstPoint, Inc.
Fitch
FlightAware
FlightStats
FlightView
Food+Tech Connect
Forrester Research
Foursquare
Fujitsu
Funding Circle
FutureAdvisor
Fuzion Apps, Inc.
Gallup
Galorath Incorporated
Garmin
Genability
GenoSpace
Geofeedia
Geolytics
Geoscape
GetRaised
GitHub
Glassy Media
Golden Helix
GoodGuide
Google Maps
Google Public Data Explorer
Government Transaction Services
Govini
GovTribe
Govzilla, Inc.
gRadiant Research LLC
Graebel Van Lines
Graematter, Inc.
Granicus
GreatSchools
GuideStar
H3 Biomedicine
Harris Corporation
HDScores, Inc
Headlight
Healthgrades
Healthline
HealthMap
HealthPocket, Inc.
HelloWallet
HERE
Honest Buildings
HopStop
Housefax
How's My Offer?
IBM
ideas42
iFactor Consulting
IFI CLAIMS Patent Services
iMedicare
Impact Forecasting (Aon)
Impaq International
Import.io
IMS Health
InCadence
indoo.rs
InfoCommerce Group
Informatica
InnoCentive
Innography
Innovest Systems
Inovalon
Inrix Traffic
Intelius
Intermap Technologies
Investormill
Iodine
IPHIX
iRecycle
iTriage
IVES Group Inc
IW Financial
JJ Keller
J.P. Morgan Chase
Junar, Inc.
Junyo
Jurispect
Kaiser Permanante
karmadata
Keychain Logistics Corp.
KidAdmit, Inc.
Kimono Labs
KLD Research
Knoema
Knowledge Agency
KPMG
Kroll Bond Ratings Agency
Kyruus
Lawdragon
Legal Science Partners
(Leg)Cyte
LegiNation, Inc.
LegiStorm
Lenddo
Lending Club
Level One Technologies
LexisNexis
Liberty Mutual Insurance Cos.
Lilly Open Innovation Drug Discovery
Liquid Robotics
Locavore
LOGIXDATA, LLC
LoopNet
Loqate, Inc.
LoseIt.com
LOVELAND Technologies
Lucid
Lumesis, Inc.
Mango Transit
Mapbox
Maponics
MapQuest
Marinexplore, Inc.
MarketSense
Marlin & Associates
Marlin Alter and Associates
McGraw Hill Financial
McKinsey
MedWatcher
Mercaris
Merrill Corp.
Merrill Lynch
MetLife
mHealthCoach
MicroBilt Corporation
Microsoft Windows Azure Marketplace
Mint
Moody's
Morgan Stanley
Morningstar, Inc.
Mozio
MuckRock.com
Munetrix
Municode
National Van Lines
Nationwide Mutual Insurance Company
Nautilytics
Navico
NERA Economic Consulting
NerdWallet
New Media Parents
Next Step Living
NextBus
nGAP Incorporated
Nielsen
Noesis
NonprofitMetrics
North American Van Lines
Noveda Technologies
NuCivic
Numedii
Oliver Wyman
OnDeck
OnStar
Ontodia, Inc
Onvia
Open Data Nation
OpenCounter
OpenGov
OpenPlans
OpportunitySpace, Inc.
Optensity
optiGov
OptumInsight
Orlin Research
OSIsoft
OTC Markets
Outline
Oversight Systems
Overture Technologies
Owler
Palantir Technologies
Panjiva
Parsons Brinckerhoff
Patently-O
PatientsLikeMe
Pave
Paxata
PayScale, Inc.
PeerJ
People Power
Persint
Personal Democracy Media
Personal, Inc.
Personalis
Peterson's
PEV4me.com
PIXIA Corp
PlaceILive.com
PlanetEcosystems
PlotWatt
Plus-U
PolicyMap
Politify
Poncho App
POPVOX
Porch
PossibilityU
PowerAdvocate
Practice Fusion
Predilytics
PricewaterhouseCoopers (PWC)
ProgrammableWeb
Progressive Insurance Group
Propeller Health
ProPublica
PublicEngines
PYA Analytics
Qado Energy, Inc.
Quandl
Quertle
Quid
R R Donnelley
RAND Corporation
Rand McNally
Rank and Filed
Ranku
Rapid Cycle Solutions
realtor.com
Recargo
ReciPal
Redfin
RedLaser
Reed Elsevier
REI Systems
Relationship Science
Remi
Retroficiency
Revaluate
Revelstone
Rezolve Group
Rivet Software
Roadify Transit
Robinson + Yu
Russell Investments
Sage Bionetworks
SAP
SAS
Scale Unlimited
Science Exchange
Seabourne
SeeClickFix
SigFig
Simple Energy
SimpleTuition
SlashDB
Smart Utility Systems
SmartAsset
SmartProcure
Smartronix
SnapSense
Social Explorer
Social Health Insights
SocialEffort Inc
Socrata
Solar Census
SolarList
Sophic Systems Alliance
S&P Capital IQ
SpaceCurve
SpeSo Health
Spikes Cavell Analytic Inc
Splunk
Spokeo
SpotCrime
SpotHero.com
Stamen Design
Standard and Poor's
State Farm Insurance
Sterling Infosystems
Stevens Worldwide Van Lines
STILLWATER SUPERCOMPUTING INC
StockSmart
Stormpulse
StreamLink Software
StreetCred Software, Inc
StreetEasy
Suddath
Symcat
Synthicity
T. Rowe Price
Tableau Software
TagniFi
Telenav
Tendril
Teradata
The Advisory Board Company
The Bridgespan Group
The DocGraph Journal
The Govtech Fund
The Schork Report
The Vanguard Group
Think Computer Corporation
Thinknum
Thomson Reuters
TopCoder
TowerData
TransparaGov
TransUnion
TrialTrove
TrialX
Trintech
TrueCar
Trulia
TrustedID
TuvaLabs
Uber
Unigo LLC
United Mayflower
Urban Airship
Urban Mapping, Inc
US Green Data
U.S. News Schools
USAA Group
USSearch
Verdafero
Vimo
VisualDoD, LLC
Vital Axiom | Niinja
VitalChek
Vitals
Vizzuality
Votizen
Walk Score
WaterSmart Software
WattzOn
Way Better Patents
Weather Channel
Weather Decision Technologies
Weather Underground
WebFilings
Webitects
WebMD
Weight Watchers
WeMakeItSafer
Wheaton World Wide Moving
Whitby Group
Wolfram Research
Wolters Kluwer
Workhands
Xatori
Xcential
xDayta
Xignite
Yahoo
Zebu Compliance Solutions
Yelp
YourMapper
Zillow
ZocDoc
Zonability
Zoner
Zurich Insurance (Risk Room)"""
ALPHABET_LENGTH = 28

ALPHABET = string.ascii_lowercase + '#$'
ALPH_IND_DICT = {c: i for i, c in enumerate(ALPHABET)}
CHAR_ALPH_DICT = {i: i.lower() for i in string.ascii_lowercase+string.ascii_uppercase}
CHAR_ALPH_DICT.update({i: '#' for i in '0123456789'})

CHAR_LIKELIHOODS = np.ones(ALPHABET_LENGTH)
TRANSITION_PROBS = np.ones((ALPHABET_LENGTH, ALPHABET_LENGTH))


def char_to_alph(i):
    return CHAR_ALPH_DICT.get(i, '$')


def encode_string(s):
    return [char_to_alph(i) for i in s]


company_names_array = COMPANY_NAMES.split('\n')
bigrams_corpus = np.zeros((ALPHABET_LENGTH, ALPHABET_LENGTH))
for p in BIGRAM_COUNTS_CORPUS:
    bigrams_corpus[ALPH_IND_DICT[p[0][0]]][ALPH_IND_DICT[p[0][1]]] += p[1]
bigrams_company = np.zeros((ALPHABET_LENGTH, ALPHABET_LENGTH))
for s in map(encode_string, company_names_array):
    for i in range(len(s)-1):
        bigrams_company[ALPH_IND_DICT[char_to_alph(s[i])]][ALPH_IND_DICT[char_to_alph(s[i+1])]] = \
            bigrams_company[ALPH_IND_DICT[char_to_alph(s[i])]][ALPH_IND_DICT[char_to_alph(s[i + 1])]] + 1


bigrams_corpus += 10e-6
bigrams_company += 10e-6
bigrams_corpus = bigrams_corpus.T
bigrams_company = bigrams_company.T
bigrams_corpus /= bigrams_corpus.sum(axis=0)
bigrams_company /= bigrams_company.sum(axis=0)
bigrams_corpus = bigrams_corpus.T
bigrams_company = bigrams_company.T

bigrams = (bigrams_company + bigrams_corpus) / 2
unigrams = bigrams.sum(axis=0)/bigrams.sum()


def get_log_likelihood(s):
    s = encode_string(s)
    ll = np.log(unigrams[ALPH_IND_DICT[s[0]]])
    for i in range(1, len(s)):
        ll += np.log(bigrams[ALPH_IND_DICT[s[i-1]]][ALPH_IND_DICT[s[i]]])
    ll /= len(s)
    return ll


def pred_hash(s, verbose=False):
    if verbose:
        print(get_log_likelihood(s) + np.log(ALPHABET_LENGTH))
    return get_log_likelihood(s) + np.log(ALPHABET_LENGTH) > MARKOV_THRESHOLD
    
def clean(name, verbose=False):
    cleaned = ""
    for word in name.split():
        if pred_hash(word):
            if cleaned == "":
                cleaned = word
            else:
                cleaned = cleaned + ' ' + word
    if verbose:
        print(cleaned)
    return cleaned


if __name__ == '__main__':
    pred_hash('asdasdsadq324q', True)
    pred_hash("McDonald's", True)
    pred_hash("oq37e89's", True)
    pred_hash("SF**POOL**", True)
    clean("Uber 072515 SF**POOL**", True)
    clean("ACH Electronic CreditGUSTO PAY 123456", True)
    clean("Tectra Inc", True)
    
