16 ms·
I read an article where a software engineer was about to go on a long plane flight, so he downloaded a file of all english words and tried to write a spell chec
by knodi123 4y ago
I read an article where a software engineer was about to go on a long plane flight, so he downloaded a file of all english words and tried to write a spell checker during his flight, with no internet access, just as an exercise. And when he landed, he had finished, and his algorithm was beautiful, simple, elegant, easy to understand, and never something I'd have come up with in a million years.
It was actually a little depressing - it made me realize that some people just have a "something" that I'm not going to get through hard work or whatnot.
*edit: ah, found it. https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html
- andersource 4y agoTo be fair, Peter Norvig [0] isn't just another software engineer, he's a hardcore CS researcher, co-authored the most popular (pre-DL) AI textbook, was head of NASA's Computational Sciences Division, etc. [0] https://en.wikipedia.org/wiki/Peter_Norvig https://en.wikipedia.org/wiki/Peter_Norvig
- e_i_pi_2 4y agoI think what they're saying is that some people are Peter Norvig and got lucky, and other people won't get there with any amount of study or practice. He's definitely not an average engineer, and as a result most people shouldn't expect to have the same level of ability I had the same thought - read the URL and then said "Oh well that's Peter Norvig he's just weird in a cool way"
- some_furry 4y agoMy aspiration as a programmer and security engineer is to one day be regarded as "just weird in a cool way". Until that day comes, I keep working at it.
- e_i_pi_2 4y agoThat's also how I live my life haha, much less stress about people judging you if you can write it off as "yeah but I'm cool in other ways"
- eointierney 4y agoHa! Love this. Bet you're already weird in a wonderful way :)
- celim307 4y agoI’m conflicted on calling him “lucky”, and I don’t think you mean to discredit him, but yeah he’s had genetic and societal gifts but I’m sure his work ethic is what makes him exceptional
- e_i_pi_2 4y agoFor a measured response - yes I agree, it's a combo of luck and effort, but the effort can't compensate for the luck. For my true response that probably isn't as popular - he may have an amazing work ethic but that's also just coming from how he was raised, so it's still luck, the same person born in a different environment wouldn't have done the same things - both nature and nurture are external forces
- LoRaBlood 4y agoI don't think his work ethic comes from his upbringing - our parents didn't push us that hard and my work ethic is average. It may come from the fact that he found what he loves to do early in his career, it may come from my Dad's genes (his work ethic was pretty good), or a combo of both
- navane 4y agoIf he is halve the genes given to him, halve what his environment has given to him, does he even exist? Do any of us exist?
- chii 4y agoOnly if you conflate the meaning of your own existence with the achievements you make.
- bruce343434 4y agowe exist as water in a river
- WalterBright 4y agoGeez, I've been told I have an unfair advantage because I have a predilection for working hard. At what point should people stop making excuses and claiming to be a victim?
- rbancroft 4y agoAnd he was probably one of the worlds foremost experts on this at the time given his position at google, haha.
- stevenspasbo 4y agoYou're in for a bad time if you're going to be comparing yourself to Peter Norvig.
- feoren 4y agoThese ideas are extremely powerful. I built a spell-checker largely based on this article, by parsing English Wikipedia. At scale it needs a trie and a distance metric with better-scaling performance metric, but it works really well. These go together: your error metric is a priority-based multi-headed traversal of your trie -- this emulates comparing your word to every word in your dictionary; you can compare against a few million words very quickly. Because it's based on Wikipedia, it can correct proper names too. It's very extensible: by changing the error model, you can get fuzzy auto-complete that can look at "Shwarz" and suggest "Schwarzenegger" (even though you missed the 'c'). You can extend it to looking at multiple words instead of just letters, for correcting common word-use issues as well.
- agencies 4y agoIs the code or expanded explanation available?
- feoren 4y agoUnfortunately I did this for work so I can't open-source the code without some awkward conversations (which may be possible and worth it, but I haven't yet). I'm sure I could write a blog post on it, but I don't have a blog, so ... sorry. Peter Norvig's post plus my point about tries and an efficient comparison algorithm at least give you a head start.
- abecedarius 4y agoNorvig wrote a similar expansion in his chapter for the book Beautiful Data (along with several other small programs to do fun things with natural language corpus data). You can find it with a web search. (His version didn't use a trie, because Python's built-in dicts are much more efficient than a trie in Python, even with the extra redundancy that a trie eliminates.)
- WalterBright 4y agoI built a spell checker in the D compiler, where the dictionary consists of the symbols in scope. It is very satisfactory.
- pixel_tracing 4y agoTo be fair even Norvig’s implementation wasn’t great for a mobile device. It can be improved with a more efficient trie structure…
- Xeoncross 4y agoDo you have any links?
- jpollock 4y agoThe hard part in the early spellcheckers wasn't figuring out that you want to find a set of words with a minimum edit distance from the input. The hard part was fitting the dictionary in memory, and then searching all possible strings 1 and 2 edits away from the input to find the candidates. The progress is that we don't have to care about storing 2.5MBytes (they ran on machines with 640k!) in RAM, or searching it 100,000 times (e.g. edits2('something')).
- pixel_tracing 4y agoYou do care about the 2.5 MB if memory is a concern and are limited by process where there is a very concrete threshold :) Try fitting GIFs, Videos, images + spellchecker & autocorrection into that process
- pixel_tracing 4y agoSomewhere in my email if my look back long enough haha… try searching for tightly packed tries on Google
- teshigahara 4y agoIf it makes you feel any better the original is not the same as what is displayed now[0] so it did not take just one flight to achieve elegance, and also included some bugs which were mentioned in the errata later[1]. [0] - https://web.archive.org/web/20070410053746/http://norvig.com/spell-correct.html https://web.archive.org/web/20070410053746/http://norvig.com... [1] - https://web.archive.org/web/20150906100448/http://www.norvig.com/spell-correct.html https://web.archive.org/web/20150906100448/http://www.norvig... : ctrl+f "Update"
- nottathrowaway3 4y agoThat "something" is basically passion and motivation, a child-like fascination with computers and the powers they can give you. People like this are so valuable and great to work with not because they have some innate power to understand algorithms, but because they sell a brand of optimism reminiscent of the "old" tech industry, the American postwar optimism of the 90s, where new things actually were revolutionary. Let's be real, in 5-6 hours he designed a very nice, simple algorithm to produce likely words from a dictionary based on frequency analysis, and produced 30 lines of Python code implementing it. A lot of engineers today could have done this. The "specialness" was that he did it on his own time and enjoyed it. There was an xkcd relevant here about enjoying Python: https://xkcd.com/353/ https://xkcd.com/353/
- aflag 4y agoMany developers would come up with that once they know the answer. Not as many will find the answer.
- deleted 4y ago[deleted]
- WalterBright 4y agoTrue genius is coming up with something so obvious everyone thinks "that's nothing, I could have done that." Complexity is the product of lesser stars in the firmament.
- deleted 4y ago[deleted]
- projektfu 4y agoThe optimism of the 90s. That's a strange one I hadn't heard before.
- deleted 4y ago[deleted]
- cortesoft 4y agoIt is a bit strange to me that it would be surprising that there are people way better at programming than you. The chance that you would be at the far right of the bell curve for any skill is pretty small, by definition. Almost everyone is going to not be the best at your thing. I don’t know why it would be depressing to not be the best.
- addaon 4y ago> any skill is pretty small, by definition I challenge this, especially the "by definition" part. It depends on how many skills you recognize. The chance of being the best artist (to the extent that such a statement is reasonable) might be one in eight billion. The chance of being the best automotive sharpie artist is, similarly, one in eight billion. The chance of being the best artist /of some particular skill set/ is, then, much higher -- if you recognize only a few thousand distinct skills here, you're already at one in a million. Then realize that those who are likely to be surprised that there are better programmers than them are /not/ likely to be surprised that there are better artists than them. So we're assessing across all skills. The chance of being on the far right of the bell curve of a specific skill is pretty small. The chance of being on the far right of the bell curve for /any/ skill is quite high, with only eight billion people around. Find what you do better than anyone else, embrace it, and enjoy it.
- azurelake 4y agoI mean, he definitely knew about the concept of edit distance: https://en.wikipedia.org/wiki/Edit_distance https://en.wikipedia.org/wiki/Edit_distance before writing this code, which is the most difficult part. Here's a practice problem: https://leetcode.com/problems/edit-distance/ https://leetcode.com/problems/edit-distance/. So in this case, the special "something" he has is quite literally the amount of hard work he put in to learn this stuff. And if you take this opportunity to learn about edit distance, you'll be one step closer to that special someone you want to be.
- pasquinelli 4y agomaybe someday i'll finally be the person i want to be, and then i can really start to live.
- TedDoesntTalk 4y agoAre you being sarcastic?
- JoshCole 4y agoYou know how there is that joke about reasoning about multi-dimensional structures? "To deal with hyper-planes in a 14-dimensional space, visualize a 3-D space and say 'fourteen' to yourself very loudly. Everyone does it." – Geoffrey Hinton, A geometrical view of perceptrons Well, you actually can come up with Norvig's spellchecker very easily with a similar trick. Just tell yourself: to deal with a really hard problem, just argmax with an okayish heuristic. Everyone does it. Solutions like this seem impossibly elegant because they tolerate a whole lot of error, but they are actually extremely obvious when you tolerate error.
- notfish 4y agoThat quote is incredible, and now I know what coffee feels like leaving my nose
- ddalex 4y agoDid you visualize water leaving your nose, and then said loudly "coffee" ?
- freilanzer 4y agoWhen you're not performing your duties do they keep you in a little box? Cells.
- TacticalCoder 4y agoIt's really nice and I'm a fan of the man but... Even back then it was a really simple spellchecker. Back then stuff like the "metaphone" and "double metaphone" algorithms already existed (suggesting candidates based on similarly sounding words). Fun algorithms 'em metaphones I'd say. Relatively easy to implement/port (been there, done that). I'm sure there's better stuff now. Also it's possible to better ranks candidates to fix typos by taking into account the layout of the keyboard (e.g. on a QWERTY keyboard is you see "wery" it is, despite having an edit distance of 1, highly unlikely the person typing meant to type "very". "weary" is much more likely). So just sorting by edit distance and then suggesting the most common word often doesn't result in the best candidate being shown first. And then context. Ah, context. I type this and my browser isn't aware I'm talking about algorithms and not only says "metaphone" is incorrect but suggests "megaphone". So... The matter still isn't settled if you ask me.
- WalterBright 4y agoSoundex is an earlier method.
- kqr 4y agoThat is a word I read once and then forgot but kept looking for! Thanks.
- alfalfasprout 4y agoDon't get me wrong, Peter Norvig is awesome, but if you're already familiar with levenshtein or even hamming distances, it's pretty straightforward to hack together a spellchecker.
- armatav 4y agoYeah and that “something” is a deep interest. You can do similar things in domains where you’re so interested you can’t think of doing anything else.
- corobo 4y agoDo you allow yourself to be bored at all? I recently realised I've been missing my "something" for a while.. ya I've not had a dopamine free moment since doom scrolling became a thing. Not comparing somethings, I probably couldn't write a spell checker much less a beautiful one, but my creative juices are much less clogged up since allowing myself to get bored. I believe it's being able to combine a learned skillset with raw creativity (boredom) that gives a person that something you refer to.
- andai 4y agoFor me it's largely "the joy of finding things out". If I know there's a standard solution to a problem, I'll avoid the "spoilers" because I want to see how far I can get on my own. (And yeah, sometimes I just get bored of doomscrolling... Building things is a much more satisfying way to spend my time!) I often avoid things because I think they'll be hard, but then discover that they turn out to be easy. "Why didn't anyone tell me how easy this was! I could have done this ages ago!" was a running theme for me for a good while. Of course, sometimes things are actually harder than you thought. But they're still doable! Whereas I have this cognitive bias where "difficult" is (emotionally) equivalent to "impossible", which is just really unfortunate. I'm sort of starting to see through that, that everything's made of atoms, and once you break a task down far enough, the individual steps are trivial.
- corobo 4y agoAt least in my career so far all of the tasks I've been told are "impossible" just need another 5 minutes of thought - to the point I'm wondering if people do it on purpose so that I take over the task haha
- knicholes 4y agoI used it to apply to a job at Twitch, as they tasked me on creating a spellchecker. Thanks, Peter! Also, they didn't give me an offer.
- rjh29 4y agoWorth noting he did not perform the "major feat of software engineering" like the OP says (given 256k ram or lower). He just put all the words into a hash. The main key is knowing about edit distance, if you know that, you can probably write the solution. So yes he's very talented, but if you study enough computer science, you can also do it. Or don't. It's totally fine to be interested in other parts of engineering instead.
- wheels 4y agoThe prowess here is greatly overstated. His implementation would be pretty obvious for anyone that had read an Information Retrieval textbook any time in the couple decades between when these methods were devised and when he wrote that post. That's kind of like watching someone use Red-Black Trees and assuming that they intuited them out of thin air. It's just remembering a basic algorithm that would be familiar to anyone in his particular field.
- deleted 4y ago[deleted]
- GuB-42 4y agoThis kind of feat is the exact opposite of what the article is about. This code is very simple, very short, very unoptimized and done in a few hours, free solo. The kind of code the article could have linked as an example of how simple it is now to write a spellchecker, in fact it explicitly talks about how you can do it in a few lines of Python, i.e. this. What the article is about is complex, highly optimized code that took months to do, because computers at the time didn't even have enough space to store the complete word list uncompressed, neither in storage nor in memory, and even with compression, you had to be clever.
- chii 4y agoso a question that could be asked today is: what could be achieved, if only the same cleverness was applied to the utilization of the massive resources available today? One potential answer is indeed the recent developments in AI (generative stuff like GPT & stable diffusion etc).
- anu7df 4y agoLeft the punchline for the link huh? Peter Norvig was the "a software engineer" nuf said, Mike drop and all that.
- smohare 4y ago[dead]
- devoutsalsa 4y agoI’d bet you have a “something” that isn’t obvious to you, or that people don’t compliment you on. And even if you don’t, comparing one’s self to anyone is sure to be depressing.
- deleted 4y ago[deleted]
- 2143 4y agoPeter Norvig is at god-tier, comparable perhaps to Torvalds, van Rossum, Wozniak, Stallman, ESR, Kernighan, Ritchie, Gates, Cormen, and many others I've left out.
- Waterluvian 4y agoYou are a very big fish when measured against countless ponds.
- technological 4y agoIf you realize that how hard you try you won’t able to do certain things, do ppl keep trying or accept the limitations ?
- yieldcrv 4y agoThe guy making revenue is a better developer than the guy making elegant algorithms Very few of us actually want to be the guy accumulating accolades for their engineering, we want to take flights to things we actually want to be doing, not opening our laptop once or even bringing it Everything in between is a coping mechanism
- rzimmerman 4y agoReminds me of a dumb project I did that takes a person's name and returns a name that is close, but not quite right: https://github.com/rzimmerman/shitty-autoreply https://github.com/rzimmerman/shitty-autoreply The idea was to set up an auto-reply to my email that looked automated, but surely couldn't be because it messed up the sender's name. Not nearly as clever as Peter Norvig's program and even less useful. I'd say the bias toward common American names is a bug, but given that the goal of the project is to be obnoxious it's probably a feature.
- kachurovskiy 4y agoI've come to accept the fact that there are millions of people better than me at something. It's depressing and hopeless trying to be the best, there isn't even an objective measure. My goal is instead to be useful.