News for hackers. Stuff that matters.
Re:SymSpell: 1M times faster spelling correction by LordGrey on Sunday March 06, 2022 @10:16AM (#30578075)
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.
Re:SymSpell: 1M times faster spelling correction by idealmedtech on Sunday March 06, 2022 @01:56PM (#30580048)
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

Re:SymSpell: 1M times faster spelling correction by cb321 on Sunday March 06, 2022 @02:27PM (#30580345)
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.