MrWook
commented
6 months ago Hey @lifthrasiir,
First off, thank you very much for your thorough analysis of the issue with the dictionaries. It would greatly benefit this package to reduce the size of these dictionaries.
Since you've already conducted benchmarks, could you please share the code for Rank Quantization with a repository, a random JavaScript site, or any other resource? This would greatly enhance my understanding of the process and how to implement it into this package.
The Delta coding already has a code example, which makes it quite easy to grasp. However, it's important to note that the implementation needs to support different kinds of written languages, such as Polish or German special characters, which may not be covered by the current regex pattern /([A-Z])/g.
Additionally, we should not assume that the dictionaries are already sorted alphabetically, as they ideally should be sorted by occurrence. Unfortunately, not every government provides a neat open-source list of such data online, so we've sourced some of the data from other places, which is then hosted on GitHub.
You don't need to worry about inversion transformation during startup, as the dictionaries are already built at that time, which only takes a few milliseconds. Adding one small script more wouldn't make much of a difference, and it would justify this step to some extent.
This would be the perfect opportunity to implement such changes, as I'm currently working on the next major version, and this would definitely be a breaking change if we transition from JSON files to JavaScript files with a long string inside that needs to be parsed. A good place for implementation would be directly inside the List Generator. The inversion part could be handled within setRankedDictionaries in the Options file. The only downside is that we wouldn't provide simple JSON files for others to import anymore.
I'm always happy to have more contributors on board!
lifthrasiir
mimi89999
In my knowledge, the size of word lists remains a major pain point for the original zxcvbn (e.g. dropbox/zxcvbn#196, dropbox/zxcvbn#268, dropbox/zxcvbn#285, dropbox/zxcvbn#338). Even though Brotli
Content-Encodingdoes allow for more compression than gzip, it is significant enough that it is worthwhile to fix in the library itself as well.I have written two concrete proposals that can significantly reduce the size footprint of the built-in dictionary. I believe they are easy to review and apply without any specialized knowledge about compression. Both also present some decisions for maintainers to make, so I tried to give enough information to aid that process.
Rank quantization
For example,
packages/languages/en/src/commonWords.jsonstarts with the following:...and ends with the following:
This list of 26,758 words is automatically generated from the frequency list of top 50K words. The cutoff is currently set to at least 500 occurrences, so the final entry
kochshould have occurred exactly 500 times. But there are many other words with the exactly same number of occurrences; in fact it's the case for all words shown above. Data compression algorithms don't and can't realize that and try to reproduce the exact order---you need to preprocess the data in the way that algorithms can work with an easier data.Furthermore, while the public API does return the exact rank as a part of
Feedback, it is probably meaningless for the aforementioned reason. We can for example imagine that ranks for first 100 words are exact, but next 100 words have the same rank (to be displayed as "101–200th common word"), and so on. This kind of rank quantization allows for an arbitrary reordering within the same rank and can greatly improve the compression without any additional code.Benchmarks
I've experimented with several quantization schemes. I assumed that the relative rank of first 100 words is significant enough and never altered that. After that point, each tested scheme has the following quantized ranks:
Words with the same quantized rank have been simply sorted in the Unicode codepoint order, so that similar words can be placed much more closely. While other shuffling is possible, this is good enough for our purpose and also helps the next proposal.
I also wanted to make sure that this optimization is visible throughout different compression algorithms and parameters, so I have used the following methods:
Results for
@zxcvbn-ts/language-en:Combined results for all
@zxcvbn-ts/language-*packages:The uncompressed size remains identical because the only change here is reordering. Still, it is possible to reduce the compressed size by 10% with a reasonable rank quantization, and that reduction is more or less consistent for all tested parameters. (There is a reason for this consistency, but that's way too technical to explain here.)
Delta coding
It should be noted that
packages/languages/en/src/firstnames.jsonamong others is already sorted:...and many consecutive words share the same prefix (for example, 6 words start with
abb). We can exploit this by simple delta coding like this:Here the number of preceding underscores represents the number of first characters to retain. And it's not necessary to repeat each underscore; we can use some reserved character for two consecutive underscores, some other for three, and so on. Since uppercase letters are removed during the generation, let's use them in place of two or more underscores:
At this point we don't even need any comma, because those reserved characters can only occur at the beginning of each word. So we can further simplify the scheme by replacing a lone
,withA,,_withB,,__withCand so on instead:While compression algorithms can pick this kind of repetitions by themselves, we already know the list is sorted so we can make use of that fact much more efficiently in this case.
Benchmarks
Results for
@zxcvbn-ts/language-en:Combined results for all
@zxcvbn-ts/language-*packages:In general this delta coding scheme reduces another 1–20% of compressed data on top of rank quantization. The best case results in 50% reduction!
Caveats
It should be noted that such transformation has to be inversed every time the script is being loaded. The following is the actual code for delta coding I've used, and you can see that it returns an immediately invoked function that does the job.
In my testing they are not very slow, but not extremely quick either. For
@zxcvbn-ts/language-enboth browsers I've tested (Firefox and Chrome) took 5–10 ms to undo the transformation, even with some additional optimization to avoid memory allocation.Amazingly enough, Chrome's V8 does seem to specially handle
String.splitwith a string argument and it was 10,000x faster than any other tested code, whileString.splitwas only ~3x faster in Firefox. I haven't tested a direct character-wise iteration but I doubt it would be as fast asString.splitin V8, so that's one thing to take account for.Raw data for benchmarks