Re: About Doug McIlroy's "Development of a Spelling List"
"Nadav Har'El" <nyh-TS7m/[email protected]> Wed, 6 Jan 2010 09:39:17 +0200
| Newsgroups | gmane.culture.hackers.israel |
|---|---|
| Message-ID | <[email protected]> |
--0IkFSrHmEyOOvardhoNztLEZD6jZvGpW91k3CYQ Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit On Sun, Dec 27, 2009, Shlomi Fish wrote about "[hackers-il] About Doug McIlroy's "Development of a Spelling List"": > In: > > http://tech.groups.yahoo.com/group/hackers-il/message/2532 > > Nadav mentioned this paper: > > http://www.cs.dartmouth.edu/~doug/spell.ps.gz Funny, 8 years ago I mentioned a paper which was 20 year old at the time, and now we talk about it again ;-) > For a long time I've intended to read it as I wanted to seek wisdom about > sophisticated and/or compact data structures and algorithms. A few days ago I > finally took some time to read it and finished it in one day. Here is my > impression of it: > > To sum up, I found it disappointing. There was very little of substance there > regarding data structures and algorithms. McIlroy only briefly discussed it. I think you missed the point. McIlroy did not invent any new magical algorithm. Heck, this is a 28 year old paper - any algorithm he used is bound to be old by now, by definition ;-) And of course, not the entire paper is about saving memory - which in those days wasn't a novelty, as all computers had very little memory! But if you read the paper (and I have to admit I haven't done so in 10 years, so I don't remember any of the details) you get the sense of all the hoops he had to jump through to use less than a few dozen Ks. Nowadays, do you think that anybody would even bother with those things? You'd just create a hash-table (which is probably the biggest data structure you can imagine for a word list) an fill it with 30,000 words, and take roughly 1 MB. In a paper, you wouldn't even bother mention how you did it, Who cares about 1MB? Back then, people cared. He wanted to sqeeze it in 52 K. Nowadays, if you run "aspell" for English it takes 1.7 MB. "hunspell" for English it takes 6 MB. Does it have to be this way? No. Of course that this article, written 28 years ago, doesn't spell-out (pun intended) why - but it can give you a few ideas on what people focused on back then, and what they focus-on now - for better and for worse. > Most of it was just about creating the word list, and how the English stems > and transformations were implemented, and normally, that would have interested > me, but that's not what I was looking for in that particular article given > Nadav's introduction. I agree that calling it "An interesting paper about the problems people faced on older computers with very limited memories" was not accurate - it's not *about* the problems, it's about writing a spell-checker, but the problem of limited memory shows through many of his design decisions and throughout the discussion. You didn't expected an article about how to write a spell-checker to be just, or even mainly, about how to save memory, did you? I hope you at least learned new things and ideas while reading it. Maybe one day you'll want to write a spell-checker, and can apply some of these ideas. Stranger things have happened... > I should also note that like most scientific papers I finished reading, I > found that it avoided giving all the relevant details, which left me with too > little understanding to implement them myself. Maybe scientific papers are not > really intended to be a technical specification, but it's still a bit > dissapointing to be hanging in mid-air like that. I disagree. Scientific papers indeed often do not give you a line-by-line recipe of how to do something. The code is for that (like all of AT&T's Unix code, spell's source code *was* available for anybody who really looked for it). But the paper better explains *why* things were done the way they were done. And if you want to write something like this yourself, even if it doesn't spoon-feed you every detail, it can at least save you a lot of time by pointing you at the right direction. -- Nadav Har'El | Wednesday, Jan 6 2010, 20 Tevet 5770 nyh-TS7m/[email protected] |----------------------------------------- Phone +972-523-790466, ICQ 13349191 |The world is coming to an end ... SAVE http://nadav.harel.org.il |YOUR BUFFERS!!! --0IkFSrHmEyOOvardhoNztLEZD6jZvGpW91k3CYQ Content-Type: text/html; charset=US-ASCII Content-Transfer-Encoding: 7bit <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> </head> <body style="background-color: #fff;"> <span style="display:none"> </span> <!--~-|**|PrettyHtmlStartT|**|-~--> <div id="ygrp-mlmsg" style="position:relative;"> <div id="ygrp-msg" style="z-index: 1;"> <!--~-|**|PrettyHtmlEndT|**|-~--> <div id="ygrp-text" > <p>On Sun, Dec 27, 2009, Shlomi Fish wrote about "[hackers-il] About Doug McIlroy's "Development of a Spelling List"":<br> > In:<br> > <br> > <a href="http://tech.groups.yahoo.com/group/hackers-il/message/2532">http://tech.<wbr>groups.yahoo.<wbr>com/group/<wbr>hackers-il/<wbr>message/2532</a><br> > <br> > Nadav mentioned this paper:<br> > <br> > <a href="http://www.cs.dartmouth.edu/~doug/spell.ps.gz">http://www.cs.<wbr>dartmouth.<wbr>edu/~doug/<wbr>spell.ps.<wbr>gz</a><br> <br> Funny, 8 years ago I mentioned a paper which was 20 year old at the<br> time, and now we talk about it again ;-)<br> <br> > For a long time I've intended to read it as I wanted to seek wisdom about <br> > sophisticated and/or compact data structures and algorithms. A few days ago I <br> > finally took some time to read it and finished it in one day. Here is my <br> > impression of it:<br> > <br> > To sum up, I found it disappointing. There was very little of substance there <br> > regarding data structures and algorithms. McIlroy only briefly discussed it. <br> <br> I think you missed the point. McIlroy did not invent any new magical<br> algorithm. Heck, this is a 28 year old paper - any algorithm he used is<br> bound to be old by now, by definition ;-) And of course, not the entire paper<br> is about saving memory - which in those days wasn't a novelty, as all<br> computers had very little memory!<br> <br> But if you read the paper (and I have to admit I haven't done so in 10<br> years, so I don't remember any of the details) you get the sense of all the<br> hoops he had to jump through to use less than a few dozen Ks.<br> Nowadays, do you think that anybody would even bother with those things?<br> You'd just create a hash-table (which is probably the biggest data structure<br> you can imagine for a word list) an fill it with 30,000 words, and take<br> roughly 1 MB. In a paper, you wouldn't even bother mention how you did it,<br> Who cares about 1MB? Back then, people cared. He wanted to sqeeze it in 52 K.<br> <br> Nowadays, if you run "aspell" for English it takes 1.7 MB. "hunspell" for<br> English it takes 6 MB. Does it have to be this way? No. Of course that this<br> article, written 28 years ago, doesn't spell-out (pun intended) why - but<br> it can give you a few ideas on what people focused on back then, and what<br> they focus-on now - for better and for worse.<br> <br> > Most of it was just about creating the word list, and how the English stems <br> > and transformations were implemented, and normally, that would have interested <br> > me, but that's not what I was looking for in that particular article given <br> > Nadav's introduction.<br> <br> I agree that calling it "An interesting paper about the problems people<br> faced on older computers with very limited memories" was not accurate -<br> it's not *about* the problems, it's about writing a spell-checker, but<br> the problem of limited memory shows through many of his design decisions<br> and throughout the discussion.<br> <br> You didn't expected an article about how to write a spell-checker to be<br> just, or even mainly, about how to save memory, did you?<br> I hope you at least learned new things and ideas while reading it. Maybe<br> one day you'll want to write a spell-checker, and can apply some of these<br> ideas. Stranger things have happened...<br> <br> > I should also note that like most scientific papers I finished reading, I <br> > found that it avoided giving all the relevant details, which left me with too <br> > little understanding to implement them myself. Maybe scientific papers are not <br> > really intended to be a technical specification, but it's still a bit <br> > dissapointing to be hanging in mid-air like that.<br> <br> I disagree. Scientific papers indeed often do not give you a line-by-line<br> recipe of how to do something. The code is for that (like all of AT&T's<br> Unix code, spell's source code *was* available for anybody who really looked<br> for it). But the paper better explains *why* things were done the way they<br> were done. And if you want to write something like this yourself, even if<br> it doesn't spoon-feed you every detail, it can at least save you a lot of<br> time by pointing you at the right direction.<br> <br> -- <br> Nadav Har'El | Wednesday, Jan 6 2010, 20 Tevet 5770<br> <a href="mailto:nyh%40math.technion.ac.il">nyh-TS7m/[email protected]<wbr>ac.il</a> |-----------<wbr>---------<wbr>---------<wbr>---------<wbr>---<br> Phone +972-523-790466, ICQ 13349191 |The world is coming to an end ... SAVE<br> <a href="http://nadav.harel.org.il">http://nadav.<wbr>harel.org.<wbr>il</a> |YOUR BUFFERS!!!<br> </p> </div> <!--~-|**|PrettyHtmlStart|**|-~--> <div style="color: #fff; height: 0;">__._,_.___</div> <div id="ygrp-actbar" style="clear: both; margin-bottom: 10px; white-space: nowrap; color: #666; padding-top: 15px;"> <div> <a href="mailto:nyh-TS7m/[email protected]?subject=Re: [hackers-il] About Doug McIlroy's "Development of a Spelling List""> Reply to <span style="font-weight: 700;">sender</span></a> | <a href="mailto:[email protected]?subject=Re: [hackers-il] About Doug McIlroy's "Development of a Spelling List""> Reply to <span style="font-weight: 700;">group</span></a> </div> <a href="http://groups.yahoo.com/group/hackers-il/message/5101;_ylc=X3oDMTM0Z2pzZzdtBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzUxMDIEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMjYyNzYzNTg0BHRwY0lkAzUxMDE-">Messages in this topic</a> (<span style="font-weight: 700;">2</span>) </div> <!------- Start Nav Bar ------> <!-- |**|begin egp html banner|**| --> <div id="ygrp-vital" style="background-color: #e0ecee; font-family: Verdana; font-size: 10px; margin-bottom: 10px; padding: 10px;"> <span id="vithd" style="font-weight: bold; color: #333; text-transform: uppercase; ">Recent Activity:</span> <ul style="list-style-type: none; margin: 0; padding: 0; display: inline;"> <li style="border-right: 1px solid #000; font-weight: 700; display: inline; padding: 0 5px; margin-left: 0;"> <span class="cat"><a href="http://groups.yahoo.com/group/hackers-il/members;_ylc=X3oDMTJmYzlzNm9kBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEyNjI3NjM1ODQ-?o=6" style="text-decoration: none;">New Members</a></span> <span class="ct" style="color: #ff7900;">3</span> </li> </ul> <div style="clear: both; padding-top: 2px; color: #1e66ae;"> <a href="http://groups.yahoo.com/group/hackers-il;_ylc=X3oDMTJlMGo2OHFrBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTI2Mjc2MzU4NA--" style="border-right: 1px solid #000; padding-right: 5px; margin-right: 2px; text-decoration: none;">Visit Your Group</a> <a href="http://groups.yahoo.com/group/hackers-il/post;_ylc=X3oDMTJlYWU3c3ZuBF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTI2Mjc2MzU4NA--" style="font-weight: 700; text-decoration: none;">Start a New Topic</a> </div> </div> <div id="ygrp-mkp" style="border: 1px solid #d8d8d8; clear: both; float: left; font-family: Arial; margin: 5px 0 10px 0; padding: 0 10px;"> <div id="hd" style="color: #628c2a; font-size: 85%; font-weight: 700; line-height: 122%; margin: 10px 0;">MARKETPLACE</div> <div id="ads" style="margin-bottom: 10px;"> <div class="ad" style="color: #628C2A; font-family: Arial; font-weight: 700; padding: 0 0;"> <p><a href="http://us.ard.yahoo.com/SIG=14kuri6vb/M=493064.13814333.13821539.13298430/D=groups/S=1705006764:MKP1/Y=YAHOO/EXP=1262770784/L=/B=Jn3njkPDhCk-/J=1262763584278785/K=1Z5DFevft54IZs2.TOuGtw/A=5922843/R=0/SIG=11ckn2mo6/*http://advision.webevents.yahoo.com/green/">Going Green: Your Yahoo! Groups resource for green living</a></p> </div> </div> </div> <div id="ft" style="font-family: Arial; font-size: 11px; margin-top: 5px; padding: 0 2px 0 0; clear: both;"> <a href="http://groups.yahoo.com/;_ylc=X3oDMTJkNnVoZjl2BF9TAzk3MzU5NzE0BGdycElkAzE4NTczMzIEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMjYyNzYzNTg0" style="float: left;"><img src="http://l.yimg.com/a/i/us/yg/logo/us.gif" height="15" width="137" alt="Yahoo! Groups" style="border: 0;"/></a> <div style="color: #747575; float: right;">Switch to: <a href="mailto:[email protected]?subject=Change Delivery Format: Traditional" style="text-decoration: none;">Text-Only</a>, <a href="mailto:[email protected]?subject=Email Delivery: Digest" class="margin-rt" style="text-decoration: none;">Daily Digest</a> • <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> • <a href="http://docs.yahoo.com/info/terms/" style="text-decoration: none;">Terms of Use</a></div> </div> <!-- |**|end egp html banner|**| --> </div> <!-- ygrp-msg --> <!-- Sponsor --> <!-- |**|begin egp html banner|**| --> <div id="ygrp-sponsor" style="width:160px; float:right; clear:none; margin:0 0 25px 0; background: #fff;"> <!-- Start Recommendations --> <div id="ygrp-reco"> </div> <!-- End Recommendations --> </div> <!-- |**|end egp html banner|**| --> <div style="clear:both; color: #FFF; font-size:1px;">.</div> </div> <img src="http://geo.yahoo.com/serv?s=97359714/grpId=1857332/grpspId=1705006764/msgId=5102/stime=1262763584/nc1=4507179/nc2=3848640/nc3=5733769" width="1" height="1"> <br> <div style="color: #fff; height: 0;">__,_._,___</div> <!--~-|**|PrettyHtmlEnd|**|-~--> </body> <!--~-|**|PrettyHtmlStart|**|-~--> <head> <style type="text/css"> <!-- #ygrp-mkp { border: 1px solid #d8d8d8; font-family: Arial; margin: 10px 0; padding: 0 10px; } #ygrp-mkp hr { border: 1px solid #d8d8d8; } #ygrp-mkp #hd { color: #628c2a; font-size: 85%; font-weight: 700; line-height: 122%; margin: 10px 0; } #ygrp-mkp #ads { margin-bottom: 10px; } #ygrp-mkp .ad { padding: 0 0; } #ygrp-mkp .ad a { color: #0000ff; text-decoration: none; } #ygrp-sponsor #ygrp-lc { font-family: Arial; } #ygrp-sponsor #ygrp-lc #hd { margin: 10px 0px; font-weight: 700; font-size: 78%; line-height: 122%; } #ygrp-sponsor #ygrp-lc .ad { margin-bottom: 10px; padding: 0 0; } a { color: #1e66ae; } #actions { font-family: Verdana; font-size: 11px; padding: 10px 0; } #activity { background-color: #e0ecee; float: left; font-family: Verdana; font-size: 10px; padding: 10px; } #activity span { font-weight: 700; } #activity span:first-child { text-transform: uppercase; } #activity span a { color: #5085b6; text-decoration: none; } #activity span span { color: #ff7900; } #activity span .underline { text-decoration: underline; } .attach { clear: both; display: table; font-family: Arial; font-size: 12px; padding: 10px 0; width: 400px; } .attach div a { text-decoration: none; } .attach img { border: none; padding-right: 5px; } .attach label { display: block; margin-bottom: 5px; } .attach label a { text-decoration: none; } blockquote { margin: 0 0 0 4px; } .bold { font-family: Arial; font-size: 13px; font-weight: 700; } .bold a { text-decoration: none; } dd.last p a { font-family: Verdana; font-weight: 700; } dd.last p span { margin-right: 10px; font-family: Verdana; font-weight: 700; } dd.last p span.yshortcuts { margin-right: 0; } div.attach-table div div a { text-decoration: none; } div.attach-table { width: 400px; } div.file-title a, div.file-title a:active, div.file-title a:hover, div.file-title a:visited { text-decoration: none; } div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div.photo-title a:visited { text-decoration: none; } div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts { font-family: Verdana; font-size: 10px; font-weight: normal; } .green { color: #628c2a; } .MsoNormal { margin: 0 0 0 0; } o { font-size: 0; } #photos div { float: left; width: 72px; } #photos div div { border: 1px solid #666666; height: 62px; overflow: hidden; width: 62px; } #photos div label { color: #666666; font-size: 10px; overflow: hidden; text-align: center; white-space: nowrap; width: 64px; } #reco-category { font-size: 77%; } #reco-desc { font-size: 77%; } .replbq { margin: 4px; } #ygrp-actbar div a:first-child { /* border-right: 0px solid #000;*/ margin-right: 2px; padding-right: 5px; } #ygrp-mlmsg { font-size: 13px; font-family: Arial, helvetica,clean, sans-serif; *font-size: small; *font: x-small; } #ygrp-mlmsg table { font-size: inherit; font: 100%; } #ygrp-mlmsg select, input, textarea { font: 99% Arial, Helvetica, clean, sans-serif; } #ygrp-mlmsg pre, code { font:115% monospace; *font-size:100%; } #ygrp-mlmsg * { line-height: 1.22em; } #ygrp-mlmsg #logo { padding-bottom: 10px; } #ygrp-mlmsg a { color: #1E66AE; } #ygrp-msg p a { font-family: Verdana; } #ygrp-msg p#attach-count span { color: #1E66AE; font-weight: 700; } #ygrp-reco #reco-head { color: #ff7900; font-weight: 700; } #ygrp-reco { margin-bottom: 20px; padding: 0px; } #ygrp-sponsor #ov li a { font-size: 130%; text-decoration: none; } #ygrp-sponsor #ov li { font-size: 77%; list-style-type: square; padding: 6px 0; } #ygrp-sponsor #ov ul { margin: 0; padding: 0 0 0 8px; } #ygrp-text { font-family: Georgia; } #ygrp-text p { margin: 0 0 1em 0; } #ygrp-text tt { font-size: 120%; } #ygrp-vital ul li:last-child { border-right: none !important; } --> </style> </head> <!--~-|**|PrettyHtmlEnd|**|-~--> </html> <!-- end group email --> --0IkFSrHmEyOOvardhoNztLEZD6jZvGpW91k3CYQ--