Codeword generator
A method for generating codewords, the method may include obtaining an input tree, converting the input tree to a modified tree in which each symbol score is a power of two, wherein the conversion is responsive to a relationship between the aggregate count of symbols of the input tree and to a certain power to two that is a smallest power of two that exceeds the aggregate count of symbols; and assigning a codeword to each symbol based at least on the symbol counts associated with the leaves of the modified tree.
1. A method for generating codewords, the method comprises:
obtaining an input tree, wherein the input tree comprises leaves, a root, and multiple intermediate nodes; wherein each leaf is associated with a unique symbol and a symbols count of the symbol within an information entity; wherein each intermediate node is associated with a unique combination of at least two symbols and an accumulated count of the members of unique combination; wherein the root is associated with an aggregate count of symbols associated with any of the leaves;
converting the input tree to a modified tree in which each symbol score is a power of two, wherein the conversion is responsive to a relationship between the aggregate count of symbols of the input tree and to a certain power to two that is a smallest power of two that exceeds the aggregate count of symbols; and
assigning a codeword to each symbol based at least on the symbol counts associated with the leaves of the modified tree.
2. The method according to claim 1 wherein the converting comprises:
for each symbol, modifying a symbol count of the symbol by multiplying the symbol count by a ratio between the certain power of two and the aggregate count of symbols of the input tree, and applying a rounding operation on an outcome of multiplying to provide an updated count.
3. The method according to claim 2 comprising updating each updated count that is not a power of two to equal a power of two.
4. The method according to claim 2 comprising calculating a leftover that represents a difference between (a) the smallest power of two that exceeds the aggregate count of symbols, minus (b) a sum of updated counts generated by the applying of the rounding operation.
5. The method according to claim 4 wherein the rounding is rounding down.
6. The method according to claim 4 comprising determining whether one or more updated counts may be doubled, and selectively doubling the one or more updated counts based on the determining.
7. The method according to claim 6 wherein the determining is based on a value of the leftover calculated under an assumption that the one or more updated counts are doubled.
8. The method according to claim 6 wherein the determining comprises maintaining a non-negative value of the leftover.
9. The method according to claim 4 comprising doubling one or more updated counts regardless of a value of the leftover, and revising at least one updated counts, following the doubling, to comply with a constraint regarding the value of the leftover.
10. The method according to claim 4 comprising selecting updated counts to be doubled by scanning a data structures in which updated counts are grouped by value.
11. The method according to claim 1 comprising encoding the information entity using the codewords.
12. A non-transitory computer readable medium that stores instructions that once executed by a computer result in:
obtaining an input tree, wherein the input tree comprises leaves, a root, and multiple intermediate nodes; wherein each leaf is associated with a unique symbol and a symbols count of the symbol within an information entity; herein each intermediate node is associated with a unique combination of at least two symbols and an accumulated count of the members of unique combination; wherein the root is associated with an aggregate count of symbols associated with any of the leaves;
converting the input tree to a modified tree in which each symbol score is a power of two, wherein the conversion is responsive to a relationship between the aggregate count of symbols of the input tree and to a certain power to two that is a smallest power of two that exceeds the aggregate count of symbols; and
assigning a codeword to each symbol based at least on the symbol counts associated with the leaves of the modified tree.
13. The non-transitory computer readable medium according to claim 12 wherein the converting comprises: for each symbol, modifying a symbol count of the symbol by multiplying the symbol count by a ratio between the certain power of two and the aggregate count of symbols of the input tree, and applying a rounding operation on an outcome of multiplying to provide an updated count.
14. The non-transitory computer readable medium according to claim 13 that stores instructions that once executed by a computer result in updating each updated count that is not a power of two to equal a power of two.
15. The non-transitory computer readable medium according to claim 13 that stores instructions that once executed by a computer result in calculating a leftover that represents a difference between (a) the smallest power of two that exceeds the aggregate count of symbols, minus (b) a sum of updated counts generated by the applying of the rounding operation.
16. The non-transitory computer readable medium according to claim 15 wherein the rounding is rounding down.
17. The non-transitory computer readable medium according to claim 16 that stores instructions that once executed by a computer result in determining whether one or more updated counts may be doubled, and selectively doubling the one or more updated counts based on the determining.
18. The non-transitory computer readable medium according to claim 17 wherein the determining is based on a value of the leftover calculated under an assumption that the one or more updated counts are doubled.
19. The non-transitory computer readable medium according to claim 17 wherein the determining comprises maintaining a non-negative value of the leftover.
20. The non-transitory computer readable medium according to claim 19 that stores instructions that once executed by a computer result in doubling one or more updated counts regardless of a value of the leftover, and revising at least one updated counts, following the doubling, to comply with a constraint regarding the value of the leftover.
21. The non-transitory computer readable medium according to claim 19 that stores instructions that once executed by a computer result in selecting updated counts to be doubled by scanning a data structures in which updated counts are grouped by value.
22. The non-transitory computer readable medium according to claim 12 that stores instructions that once executed by a computer result in encoding the information entity using the codewords.