tag:blogger.com,1999:blog-786333285568106173.post2890314425405524070..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: IOI Wrap-upMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-786333285568106173.post-44537754215064600972010-09-22T06:46:00.335-04:002010-09-22T06:46:00.335-04:00Hi Mihai,
I am anonymous September 12.
Sorry my d...Hi Mihai,<br />I am anonymous September 12.<br /><br />Sorry my description was imprecise.<br /><br />Let x be the unknown article and y be the concatenation of all articles that belong to say English.<br /><br />Your suffix tree method is often denoted LZ(x | y).<br /><br />You can also define appropriately EDM(x | y), which also gives a valid Lempel Ziv parsing. (Of course your algorithm gives the optimal LZ parsing. Still, one can show that EDM(x | y) is within log factor of it)<br /><br />The good thing is EDM metric is highly related to finding a small context free grammar that generates the string, which somehow works great for natural languages.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-89722239756274605872010-09-14T03:13:19.909-04:002010-09-14T03:13:19.909-04:00Awesome! Congratulations and good luck with your c...Awesome! Congratulations and good luck with your continued participation in IOI-running.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-71845613845642734622010-09-12T14:29:07.783-04:002010-09-12T14:29:07.783-04:00I don't understand. You apply "edit dista...I don't understand. You apply "edit distance with moves" to which 2 strings?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-1033278985822322542010-09-12T00:54:47.367-04:002010-09-12T00:54:47.367-04:00Here the "edit distance with moves" metr...Here the "edit distance with moves" metric of Muthukrishnan and Cormode can be helpful. It can be computed in linear time.<br /><br />This metric is always within log n factor of what Mihai proposed, but is known to perform very well for natural languages.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-17964982995696269022010-09-09T10:55:29.634-04:002010-09-09T10:55:29.634-04:00SODA results will be out in about a week. Hold you...SODA results will be out in about a week. Hold your horses.<br /><br />Yes, the most common solutions were based on q-grams. Note that the scores were scaled up, so if you got 98 points, it means you had about 88% accuracy.<br /><br />My intuition is that the suffix tree approach should be a generalization of q-grams, since it adapts the "q" to the entropy of the text... If some letters are frequent (low entry) you will catch longer patterns containing those letters.<br /><br />Still, it's not behaving significantly better than q-grams, so maybe this effect is not strong enough. Or maybe I'm doing something wrong in the tuning.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-53720665564033415092010-09-09T05:11:27.685-04:002010-09-09T05:11:27.685-04:00Hi Mihai,
for curiosity, did you try it against 3...Hi Mihai, <br />for curiosity, did you try it against 3- and 4-gram analysis? <br />On that data 4-gram scored 98 points..Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-83151727312122825282010-09-09T03:28:51.679-04:002010-09-09T03:28:51.679-04:00when is soda out btw?when is soda out btw?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-34370976783683937082010-09-08T13:44:17.808-04:002010-09-08T13:44:17.808-04:00David, you only have 200 examples in each language...David, you only have 200 examples in each language, each of 100 characters. You certainly require several to break the permutation of the alphabet (substitution cypher). Are you going to break it statistically? I would guess you need 1000 characters in each language or so, but maybe I'm overestimating.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-72762881054902447582010-09-07T20:49:40.756-04:002010-09-07T20:49:40.756-04:00Thanks, Mihai, for your contribution to Canda'...Thanks, Mihai, for your contribution to Canda's HSC. I've enjoyed your paraphrased presentation of the problems, too.<br /><br />1011110: here's an <a href="http://plg1.uwaterloo.ca/cgi-bin/cgiwrap/gvcormac/LL" rel="nofollow">on-line version</a> with no cypher to break.gvchttps://www.blogger.com/profile/18418030264104121131noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-39158223398101773422010-09-07T18:52:17.005-04:002010-09-07T18:52:17.005-04:00It's not really true that one starts with zero...It's not really true that one starts with zero knowledge in this problem, though, is it? The substitution cipher is trivial to break, probably even given a single example, after which you can match against known dictionaries, and the language ids can be deduced once you've found an example in each language. So I'd expect that with more care it should be possible to get around 99.5% accuracy: give up on getting the first of the 200 examples in each language, because until you guess wrong you don't know the language id, and after that get them all right.Anonymousnoreply@blogger.com