6 ms·

Please help!! , there is something fundamental I don't know how to achieve: Let's say you have a word. You want to compress it by making the smallest possible h

Please help!! , there is something fundamental I don't know how to achieve: Let's say you have a word. You want to compress it by making the smallest possible hash/UUID while being conflict free. Let's say we wanna compress the word "eating". I propose the following scheme: eating become: 1abc But it doesn't mean 1abc, let me explain: Here the 1 would be a char indicating a Metadata, this Metadata would denote a specific alphabet, such as Egyptian hieroglyphs. 1abc abc are the actual hash and a here denote the first letter of the hieroglyph alphabet. So first question: how to generate minimal hashes that leverage UTF8 symbols for reducing length. Also UTF8 non-base symbols weight 3-4 bytes which is not great and this is perfectly avoidable!! What a shame this concept is not widespread.. My goal is to have a string encoding that allow 255 distinct "ASCII tables", dynamically switched via the first letter encoding which table it refer to. Therefore any character in my encoding stay in one byte. The only limit is that therefore not all hieroglyphs can be encoded, only the 255 firsts but I don't care! I don't want to encode Egyptian, I want to generate maximally small hashes/UUID for normal text by going far beyond the standard alphabet symbols. How to achieve this?? This musy have already been done! (note ideally you could specify more that one character for language selection, which would massively increase the encoding compression but jjst one would be a good start!) Plz help TL;DR ASCII char encoding can only represent 255 1 byte characters My proposed scheme enable to have N * 255 * 255 1 byte characters. With a constant cost per string of 1 byte. This seems revolutionary.

estebarb 4y ago
It is impossible to create a perfect hash function, unless you have the complete dictionary (otherwise there is collision risk). If you have the full dictionary then there are perfect hash algorithms. So, in essence, you want to add metadata to switch dictionaries, it is feasible: {Dictionary}{id}. You would have to consider out of dictionary words too. By the way, note that UTF-8 is "compressed" (unlike UTF-32). Some languages don't use spaces to separate words, so you would have metadata problems in common languages like Chinese. What I have done, and works pretty well, is using dictionary compression: sort a dictionary by frequency, replace the word with the rank in the dictionary (in base64 or something high), use spaces to separate words and use a dedicated symbol to escape out of dictionary words. Oh, and I was compressing lower case, mostly Spanish words. It gave me around 50% compression AND it can be used to run NLP algorithms without decompressing the data (like word2vec or TF-IDF).
- deleted 4y ago
  [deleted]
- SemanticStrengh 4y ago
  Great answer, do you have a resource(tutorial)/code to share? (note that I assume I have the full dictiotnnary)
pyinstallwoes 4y ago
Sounds similar to: https://github.com/Cyan4973/FiniteStateEntropy https://github.com/Cyan4973/FiniteStateEntropy https://arxiv.org/abs/1311.2540 https://arxiv.org/abs/1311.2540 > The modern data compression is mainly based on two approaches to entropy coding: Huffman (HC) and arithmetic/range coding (AC). The former is much faster, but approximates probabilities with powers of 2, usually leading to relatively low compression rates. The latter uses nearly exact probabilities - easily approaching theoretical compression rate limit (Shannon entropy), but at cost of much larger computational cost. Asymmetric numeral systems (ANS) is a new approach to accurate entropy coding, which allows to end this trade-off between speed and rate: the recent implementation [1] provides about 50% faster decoding than HC for 256 size alphabet, with compression rate similar to provided by AC. This advantage is due to being simpler than AC: using single natural number as the state, instead of two to represent a range. Beside simplifying renormalization, it allows to put the entire behavior for given probability distribution into a relatively small table: defining entropy coding automaton. The memory cost of such table for 256 size alphabet is a few kilobytes. There is a large freedom while choosing a specific table - using pseudorandom number generator initialized with cryptographic key for this purpose allows to simultaneously encrypt the data. This article also introduces and discusses many other variants of this new entropy coding approach, which can provide direct alternatives for standard AC, for large alphabet range coding, or for approximated quasi arithmetic coding. Check out his other papers / the github project (looked super interesting and similar).
- SemanticStrengh 4y ago
  Great find! At first glance this looks similar! I wonder if he has explored the idea of using multiple numbers for increasing the number of distinct "ASCII" tables.
infinityio 4y ago
Re leveraging UTF-8 for encoding text to be visually small: if you have your conflict-free hash as a binary number, you could do this fairly easily by making an 'empty' UTF8 char of the right length and replacing all the data bits with your hash, and it would be converted to a potentially invalid, but still transmissible, character for you (if you have to make the characters valid, you may need a lookup table to jump over these) > My proposed scheme enable to have N * 255 * 255 1 byte characters. With a constant cost per string of 1 byte. This seems revolutionary. The main issue in this context would be limitations in encoding enough languages - there are too many characters (144k in unicode) to encode in 256 code pages (16k max). Additionally, frequently switching code pages (for example swapping back to ascii to use Latin chars / numbers) would incur a large cost on the size of the string Also note that some of the 'earlier' unicode symbols that don't fit into ascii are in 2 bytes as well, it's not just 1/3/4!
Etheryte 4y ago
This is a basic version of many commonly used ideas for string compression in golfing languages. Jelly [0] is a good example of a more practical and versatile approach that builds on ideas such as this. [0] https://github.com/DennisMitchell/jellylanguage/wiki/Tutorial#312string-literals https://github.com/DennisMitchell/jellylanguage/wiki/Tutoria...

estebarb 4y ago

It is impossible to create a perfect hash function, unless you have the complete dictionary (otherwise there is collision risk). If you have the full dictionary then there are perfect hash algorithms. So, in essence, you want to add metadata to switch dictionaries, it is feasible: {Dictionary}{id}. You would have to consider out of dictionary words too. By the way, note that UTF-8 is "compressed" (unlike UTF-32). Some languages don't use spaces to separate words, so you would have metadata problems in common languages like Chinese. What I have done, and works pretty well, is using dictionary compression: sort a dictionary by frequency, replace the word with the rank in the dictionary (in base64 or something high), use spaces to separate words and use a dedicated symbol to escape out of dictionary words. Oh, and I was compressing lower case, mostly Spanish words. It gave me around 50% compression AND it can be used to run NLP algorithms without decompressing the data (like word2vec or TF-IDF).

deleted 4y ago
[deleted]
SemanticStrengh 4y ago
Great answer, do you have a resource(tutorial)/code to share? (note that I assume I have the full dictiotnnary)

pyinstallwoes 4y ago

Sounds similar to: https://github.com/Cyan4973/FiniteStateEntropy https://github.com/Cyan4973/FiniteStateEntropy https://arxiv.org/abs/1311.2540 https://arxiv.org/abs/1311.2540 > The modern data compression is mainly based on two approaches to entropy coding: Huffman (HC) and arithmetic/range coding (AC). The former is much faster, but approximates probabilities with powers of 2, usually leading to relatively low compression rates. The latter uses nearly exact probabilities - easily approaching theoretical compression rate limit (Shannon entropy), but at cost of much larger computational cost. Asymmetric numeral systems (ANS) is a new approach to accurate entropy coding, which allows to end this trade-off between speed and rate: the recent implementation [1] provides about 50% faster decoding than HC for 256 size alphabet, with compression rate similar to provided by AC. This advantage is due to being simpler than AC: using single natural number as the state, instead of two to represent a range. Beside simplifying renormalization, it allows to put the entire behavior for given probability distribution into a relatively small table: defining entropy coding automaton. The memory cost of such table for 256 size alphabet is a few kilobytes. There is a large freedom while choosing a specific table - using pseudorandom number generator initialized with cryptographic key for this purpose allows to simultaneously encrypt the data. This article also introduces and discusses many other variants of this new entropy coding approach, which can provide direct alternatives for standard AC, for large alphabet range coding, or for approximated quasi arithmetic coding. Check out his other papers / the github project (looked super interesting and similar).

SemanticStrengh 4y ago
Great find! At first glance this looks similar! I wonder if he has explored the idea of using multiple numbers for increasing the number of distinct "ASCII" tables.

infinityio 4y ago

Re leveraging UTF-8 for encoding text to be visually small: if you have your conflict-free hash as a binary number, you could do this fairly easily by making an 'empty' UTF8 char of the right length and replacing all the data bits with your hash, and it would be converted to a potentially invalid, but still transmissible, character for you (if you have to make the characters valid, you may need a lookup table to jump over these) > My proposed scheme enable to have N * 255 * 255 1 byte characters. With a constant cost per string of 1 byte. This seems revolutionary. The main issue in this context would be limitations in encoding enough languages - there are too many characters (144k in unicode) to encode in 256 code pages (16k max). Additionally, frequently switching code pages (for example swapping back to ascii to use Latin chars / numbers) would incur a large cost on the size of the string Also note that some of the 'earlier' unicode symbols that don't fit into ascii are in 2 bytes as well, it's not just 1/3/4!

Etheryte 4y ago

This is a basic version of many commonly used ideas for string compression in golfing languages. Jelly [0] is a good example of a more practical and versatile approach that builds on ideas such as this. [0] https://github.com/DennisMitchell/jellylanguage/wiki/Tutorial#312string-literals https://github.com/DennisMitchell/jellylanguage/wiki/Tutoria...