Quelle est la différence entre les méthodes de compression globale et universelle?

12

Je comprends que les méthodes de compression peuvent être divisées en deux ensembles principaux:

  1. global
  2. local

Le premier ensemble fonctionne indépendamment des données en cours de traitement, c'est-à-dire qu'ils ne s'appuient sur aucune caractéristique des données et n'ont donc pas besoin d'effectuer de prétraitement sur aucune partie de l'ensemble de données (avant la compression elle-même). D'un autre côté, les méthodes locales analysent les données, en extrayant des informations qui améliorent généralement le taux de compression.

En lisant certaines de ces méthodes, j'ai remarqué que la méthode unaire n'est pas universelle , ce qui m'a surpris car je pensais que "globalité" et "universalité" se référaient à la même chose. La méthode unaire ne repose pas sur les caractéristiques des données pour produire son codage (c'est-à-dire qu'il s'agit d'une méthode globale), et donc elle devrait être globale / universelle, n'est-ce pas?

Mes principales questions:

  • Quelle est la différence entre les méthodes universelles et globales?
  • Ces classifications ne sont-elles pas synonymes?
classification algorithms encoding Rubens
la source
2
Pouvez-vous lier à / référence où vous lisez que la méthode unaire n'est pas universelle? Le contexte peut aider.
Air
3
Je ... ne sais pas comment cela se rapporte à la science des données. Cela semble hors sujet pour cet échange de pile. Pourriez-vous éventuellement relier cela à la science des données?
Slater Victoroff
@SlaterTyranus Je ... je ne suis pas trop sûr (et cela m'a fait penser à deux autres questions que j'ai postées). Mon idée était d'ajouter cette question car les méthodes de compression sont largement utilisées dans la recherche d'informations (principalement lors de l'indexation). En général, je trouve cela lié à l'efficacité, et cela peut être mis dans le domaine des compétences de piratage de ce diagramme de Venn . Quoi qu'il en soit, je suppose que ce serait bien de discuter si ce genre de question est sur le sujet.
Rubens
@Rubens Cela semble être une discussion raisonnable, dans mon esprit, les discussions sur l'efficacité s'inscrivent beaucoup plus dans quelque chose comme CS théorique que dans les compétences de piratage explicites . Dans mon esprit, les compétences de piratage sont beaucoup plus liées à des choses comme les bases de données, le déploiement et la connaissance des outils.
Slater Victoroff
1
@SvanBalen Deux points principaux: 1. La théorie de l'information est importante dans certaines approches de la science des données, mais non pertinente dans beaucoup d'autres. 2. Les principes fondamentaux sont intrinsèquement hors sujet, poser une question détaillée sur les statistiques ou l'algèbre linéaire serait également hors sujet même si les deux sont strictement nécessaires pour une science des données utile.
Slater Victoroff

Réponses:

3

Considérez le bloc de données suivant:

1010010110100101

Universel - ce sont des algorithmes de compression génériques qui sont indépendants des données. Une version grossière de l' encodage de la longueur de course tomberait dans cette catégorie. L'avantage est qu'il est très rapide de compresser et de décompresser. L'inconvénient est qu'il peut être extrêmement inefficace en fonction des données à compresser.

1111111111111111 -> 16 1 (porte-bonheur)

1010010110100101 -> 1010010110100101 (malchanceux)

Local - cette méthode considérerait des segments plus petits d'une longueur fixe, disons 4, rechercherait des motifs et les compresserait. Par exemple. Ces données ne contiennent que ces deux types de modèles - 1010 et 0101. Ces modèles peuvent être représentés comme des 0 et des 1 et les données globales seront un tableau représentant les mappages, et quelque chose comme 0101. Cela a le potentiel d'entraîner une réduction beaucoup plus faible taille compressée.

1010010110100101 -> 1010 0101 1010 0101 -> 0101 (0 = 1010,1 = 0101)

Global - cette méthode examinerait l'ensemble des données et trouverait les modèles optimaux / bien meilleurs pour compresser les données. Les données d'exemple contiennent un seul motif 10100101 et le représentent comme 00 avec la table de mappage. Cela a le potentiel d'obtenir la taille compressée la plus petite possible, mais c'est aussi le plus lourd sur le plan informatique.

1010010110100101 -> 10100101 10100101 -> 00 (0 = 10100101)

doodhwala
la source