[HN Gopher] SymSpell: 1M times faster spelling correction
___________________________________________________________________
SymSpell: 1M times faster spelling correction
Author : mci
Score : 171 points
Date : 2022-03-06 10:15 UTC (12 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| tgv wrote:
| So, this is time vs memory?
| LordGrey wrote:
| Very much so.
|
| Edit: To determine the number of records created from permuting
| a single string, use this: for (r = 1; r <= e;
| r++) numRecs += (fact(n) / (fact(r) * fact(n - r)));
|
| where e = edit distance and n = length of string. fact() is
| your standard factorial function.
| idealmedtech wrote:
| This actually has a closed form!
|
| numRecs = -1 + 2^n + (n nCr e+1) * 2F1(1, e-n+1; e+2; -1)
|
| n nCr k combinatorial choice, 2F1 is the hypergeometric
| function
| cb321 wrote:
| In a dictionary with more than a few words, some "created
| corruptions" in the lookup table/index collide with each
| other. (EDIT: e.g. for "hand" and "and" the overlap of the
| deletion-corrupted sets is substantial.) You only know
| which/how many by running the algo against a concrete
| dictionary. So, these expressions are at best a rough
| guide.
| cb321 wrote:
| As jamra correctly points out in a sibling comment, the entry
| point to this (which gets a lot of traction on HN) is indeed
| attacking a strawman tutorial-written-on-an-airplane-in-Python
| algorithm. So, the 1M speed-up is very over-hyped.
|
| That said, the technique is not wholly without merit, but does
| carry certain "average-worst case" trade offs related to latency
| in the memory/storage system because of SymSpell's reliance upon
| large hash tables. For details see
| https://github.com/c-blake/suggest
|
| EDIT: Also - I am unaware of other implementations even saving
| the large, slow-to-compute index. The others I am aware of seem
| to rebuild the large index every time which seems kind of lame.
| EDIT2 - I guess there is a recent Rust one that is persistent as
| well as the "mmap & go" Nim one. Still, what should be standard
| is very rare.
| ccleve wrote:
| Links to the other implementations would be very helpful.
| cb321 wrote:
| There are many such links in the main article linked here,
| actually. That's where I just saw the Rust one using RocksDB.
| (No link to the Nim one, though...which has no external
| dependencies beyond the Nim stdlib.)
| danielscrubs wrote:
| It was a bit fun comparing the Haskell version and the C#
| version:
|
| https://github.com/wolfgarbe/SymSpell/blob/master/SymSpell/S...
|
| https://github.com/cbeav/symspell/blob/master/src/SymSpell.h...
| 0xcoffee wrote:
| I don't really see a reason why the C# version couldn't be
| written in a similar functional style as the Haskell version. I
| don't see them using linq anywhere. I see shallow clones,
| double constructors, no use of records. So I won't be too quick
| to judge. Would love to see someone try their hand at
| optimizing the C# version, using the full availability of
| modern c#.
| jamra wrote:
| This seems very suspicious to me. They're comparing performance
| to a tutorial blog post that is extremely inefficient.
|
| How about comparing it to. Levenshtein automaton or another state
| of the art approach?
| cb321 wrote:
| You are absolutely right to be suspicious.
| https://news.ycombinator.com/item?id=30580011
|
| The TL;DR is that on a "worst case" basis, it may be 10x faster
| or even 10x _slower_ than a non-indexed linear scan depending
| upon latency of backing stores. Physical memories in computers
| are pretty big these days, but this technique would have been a
| total non-starter just 10 years before the 2007 article by
| Norvig. Meanwhile its linear scan competitor would have worked
| fine. It is also not a great approach if you have a big
| dictionary of long words and want truly large edit distances (
| >>5, say). I would say "mid-size edit distances of 2-4" are
| SymSpell's sweet spot.
| kevincox wrote:
| This seems very focused on spelling. What I find is key for a
| good spell correction system is how the words sound. For example
| I find that Firefox often can't find the word I meant for it's
| suggestion list but pasting the misspelt word into Google gets
| the right result 99% of the time as the one provided option.
|
| I wonder how difficult it would be to adapt this to work on
| sounds or other frequent typos and misspelling sources instead of
| just characters. It seems it should he possible if you can define
| a decent "normalization" function.
| phkahler wrote:
| https://en.wikipedia.org/wiki/Soundex#:~:text=Soundex%20is%2...
| .
|
| Soundex is a rough phonetic "spelling" used for such things.
| It's also something I _never_ see mentioned.
| ok123456 wrote:
| Soundex was designed as a way to index last names before
| computers. It's primary benefit it that it's designed to do
| by hand. It performs pretty lousy as a general purpose
| natural language hashing scheme.
|
| The precision and recall is too bad to use as a spell
| checker.
| eloff wrote:
| It's also pretty simple, I'm sure there are much better
| options readily available as libraries these days.
| ChrisMarshallNY wrote:
| I used an old algorithm in a text search, called Metaphone[0].
| It works relatively well, for English (There's a Spanish
| version, too). I used Double Metaphone.
|
| [0] https://en.wikipedia.org/wiki/Metaphone
| faizshah wrote:
| There's a pretty cool python library with a huge number of
| these if you want to experiment (GPLv3):
| https://github.com/chrislit/abydos
| ars wrote:
| Metaphone is good if you typed in something that sounds like
| the correct word. But often spelling typos are missing
| letters, or pressing a nearby letter instead of the one you
| meant.
|
| For those the sound of the word isn't right, you need
| something that checks for nearby keys (I guess it needs to
| know the keyboard layout), and for missing or extra letters.
| ksec wrote:
| Same here, Apple often auto correct my word into something
| else, or failed to even suggest the correct word. I had to use
| Google to get a correct spelling. ( I am not sure if I am alone
| in this sometimes I dont think I can spell any more. )
| amelius wrote:
| Can this be used to match DNA sequences?
|
| Or sounds (like Shazam does)?
| injidup wrote:
| Slightly OT but trying to look up friends names using Android
| auto speech recognition whilst driving. I have two Austrian
| friend "Viktor" and "Patric". If I say. "Hey google, call Viktor"
| google says. "Sorry you have no Victor in your phone book. Same
| with Patric. "Sorry you have no Patrick" in your phone book. I'm
| surprised that there is not even basic scoring done when looking
| up names in the phone book with the most likely one offered.
|
| *EDIT* I just found a solution to this problem.
| https://support.google.com/assistant/thread/559644?hl=en&msg...
| You can supply a phonetic name and this helps google match. This
| seems a bit low tech though.
| wodenokoto wrote:
| It says it does fuzzy search as well. Wonder how it compares to
| fzf
| LordGrey wrote:
| What they are calling "Symmetric Delete" seems to be the same as
| an older concept called "deletion neighborhoods". It is a term
| coined in an academic paper written by Thomas Bocek, Ela Hunt,
| and Burkhard Stiller from the University of Zurich, titled "Fast
| Similarity Search in Large Dictionaries"[1]. The work described
| there was expanded in a paper written by Daniel Karch, Dennis
| Luxen, and Peter Sanders from the Karlsruhe Institute of
| Technology, titled "Improved Fast Similarity Search in
| Dictionaries"[2]. Both of these papers deal with efficient
| searching for similar string values, given a query string.
|
| LookupCompound and WordSegmentation, algorithms built on
| Symmetric Delete/Deletion Neighborhoods, are pretty interesting.
|
| [1]https://fastss.csg.uzh.ch/ifi-2007.02.pdf
| [2]https://arxiv.org/abs/1008.1191v2
| qorrect wrote:
| Amazing info, thank you.
| nicoburns wrote:
| I'd love to see better open source spell checking. The state of
| the art spell checkers (in say, MS Word or Google Search) are
| _excellent_ and more than good enough for my needs. And yet the
| spell checkers in browsers (e.g. Chrome and Firefox) and other
| apps tend to be terrible only catching very basic cases and often
| not being able to suggest the correct word.
|
| Does anyone have any insight into what's holding this back?
| thangalin wrote:
| I integrated JSymSpell[0] into KeenWrite[1], which is based on
| SymSpell[2]. The algorithm provides numerous suggestions for
| "plannin'", with "planning" being the first hit[3]. Despite the
| English lexicon[4] not including all words for all
| localizations (US/UK) the results have been adequate for my use
| so far.
|
| What open-source solutions have you been using that aren't
| working as well as you'd like?
|
| [0]: https://github.com/rxp90/jsymspell
|
| [1]: https://github.com/DaveJarvis/keenwrite/
|
| [2]: https://github.com/wolfgarbe/SymSpell
|
| [3]: https://i.ibb.co/Bs0W6w2/screenshot.png
|
| [4]:
| https://github.com/DaveJarvis/keenwrite/tree/master/src/main...
| 6510 wrote:
| privacy
| tootie wrote:
| Is this how modern spell checkers worked? I assumed they were
| more heuristic at this point. For example, Google's "did you
| mean" is based on mapping common misspellings to what people
| actually clicked on.
___________________________________________________________________
(page generated 2022-03-06 23:01 UTC)