zverok
commented
3 years ago Hey!
Thanks for your kind words about my work. The question of linearizing the dictionary (Hunspell and its predecessors call this "unmunching" for some reason) is a quirky one.
Basically, if we ignore word compounding, it is more or less trivial: look at word flags, see which suffixes and prefixes it might have, produce all valid combinations". Here is proof-of-concept Spylls-based script for doing so: https://gist.github.com/zverok/c574b7a9c42cc17bdc2aa396e3edd21a I haven't tested it extensively, but it seems to work and produce valid results, so you can try to use it for your idea!
The problem is, this script can be made universal to handle any possible dictionary because of word compounding. In languages with word compounding, the "potentially possible" words list is incredibly huge. (The topic is covered in this article).
For example, in nb_NO (one of two variants of Norwegian) dictionary, there are 11k words with COMPOUNDFLAG. This means that "theoretically possible" is any combination of those 11k words (not only every pair but also three, four, ... in a row). The dictionary contains enough information to tell "whether this is the valid compound word", but not enough to produce all really existing/used compounds (see example in the article I've linked: “røykfritt” (“smoke-free” = “non-smoking”) and “frittrøyk” are both "valid" for Hunspell, but the second one is actually not an existing word... But I assume some poet might use it, and Norvegian readers might understand what they mean in the context.)
That's why "unmunching" the list of words for languages with compounding is impossible—so, to have just a list of "all actually existing Norwegian words" Hunspell's dictionary is useless.
Another curious example: English dictionary have "compounding rules" used to check numerals, like "11th is valid, and 10000011th is valid, but 10000011nd is not". Attempt to produce "all possible" combinations from this rule will obviously lead to an infinite loop :)
As far as I understand, that's the biggest obstacle for "full list"-based spellcheckers: AFAIK, LanguageTool grammar checking project uses morfologik spellchecker which encodes word lists with FSA very efficiently but falls back to Hunspell for languages like German or Norwegian due to compounding.
fabiospampinato
Hello there, first of all thanks a lot for writing
Spylls, all the documentation and the blog series, I haven't read it all in depth yet but so far it has been wonderfully informative and from what I've seen it's the best sort of documentation on how Hunspell works available, andSpyllsitself is probably the best port of Hunspell to another language.I have a use case where I need to perform spell-checking on the browser basically, and from what I've seen, mainly from playing around with
nspell, an Hunspell-like approach to spell-checking would be pretty prohibitive for my use case, for some languages at least, it takes too long to generate words or even just parse dictionaries, plus keeping all those strings in memory can blow up memory usage fairly rapidly which is a concern for my use case.I think it's possible to approach the problem differently, pre-parsing dictionaries into a compact ~binary representation and working with that directly, trading some lookup performance, hopefully not too much performance, for amazing memory usage and startup times. There's some shallow documentation about that here but I think you alluded to something like this in a blog post when mentioning another spell checker so you might already be familiar with this.
Anyway I'd like to spend some time implementing something like that, for doing that I would first of all need to extract all valid words from all dictionaries, and that sounds like a task
Spyllscould be well suited to address, it's not a problem if it'll take hours for some dictionary, I care more about extracting all valid words as correctly as possible than doing it quickly.So could
Spyllsexpose an API for doing that?