An examination of the sub-optimality of the state-sorting algorithm in tabled asymmetric numeral systems
Bibliographic record
Abstract
La croissance rapide des données dans différentes applications telles que la communication en temps réel, les systèmes automobiles et la visioconférence a souligné la nécessité de techniques efficaces de compression des données. La compression des données réduit les besoins de stockage et de transmission des données. La codification d'entropie, qui est une compression de données sans perte, est une méthode largement utilisée. La codification d'entropie consiste à coder des symboles d'une séquence d'entrée en utilisant moins de bits pour les représenter, ce qui réduit la taille totale des données. La codification de Huffman, qui est une technique rapide de codage d'entropie, est utilisée pour sa vitesse et son accélération matérielle. Cependant, son taux de compression n'est pas toujours optimal. Cela devient évident lorsqu'il s'agit de petits alphabets et de symboles avec des probabilités d'occurrence élevées. La codification arithmétique, une méthode alternative, offre de meilleurs taux de compression, mais elle a une complexité computationnelle élevée. Les systèmes de numération asymétriques (ANS), qui sont une approche de codage d'entropie, visent à approcher la limite théorique de la compression des données tout en maintenant une complexité computationnelle inférieure par rapport à la codification arithmétique. ANS comprend deux versions principales : ANS à plage et ANS tabulé. Ce dernier, appelé tANS, utilise une table pour les procédures de codage et de décodage, ce qui le rend plus adapté à une implémentation matérielle. Cependant, bien qu'ANS présente des avantages, des défis subsistent. Trouver une table de codage appropriée, ou un segment clé, pour tANS est important pour son efficacité. Des recherches récentes explorent différentes techniques pour concevoir des segments clés optimaux, en tenant compte de facteurs tels que les probabilités des symboles, l'alphabet source et la taille de la table souhaitée. Le défi consiste à construire un segment clé qui satisfait aux conditions de codage et qui conduit à une longueur moyenne minimale des codes. La technique de tri d'états proposée par Yokoo et Dubé vise à optimiser les segments clés en triant les états en fonction de leurs probabilités stationnaires. Cependant, cette méthode est sous-optimale dans certains cas. L'objectif de cette recherche est d'étudier les limitations et la sous-optimalité de l'algorithme de tri des états en présentant un exemple dans lequel la stratégie de Yokoo et Dubé ne créera pas le segment optimal. Cela permettra une meilleure compréhension des complexités de la conception de clés tANS optimales. Cette étude contribue à l'avancement des techniques de compression des données en abordant les défis et les améliorations possibles dans le contexte du codage d'entropie, en particulier dans le cadre d'ANS et de ses variantes. Cette recherche vise à améliorer notre compréhension de la conception de clés pour tANS et à ouvrir la voie à des solutions plus efficaces pour la compression et la transmission des données dans le paysage numérique en constante évolution.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".