Comprendre la compression / l'encodage en temps linéaire

Je lis l'article NJ Larsson, A. Moffat: Compression basée sur un dictionnaire hors ligne , qui décrit un algorithme de compression qui, si je le comprends bien, est assez similaire au codage par paire d'octets .

Étant donné une chaîne de longueur , j'essaie de comprendre comment on peut la compresser en temps linéaire avec cette méthode de compression. Comment cela se fait-il exactement? J'ai lu le document, mais je ne comprends toujours pas comment ils atteignent le temps linéaire, alors peut-être que je comprendrais qu'il soit expliqué d'une manière différente. $S$ $n$ $\mathcal O (n)$

Ma première confusion survient dans la première étape de l'algorithme, où nous trouvons la paire la plus courante, par exemple dans abcababcabcla paire la plus courante abserait remplacée par un nouveau symbole, disons XcXXcXc. Je ne comprends pas comment trouver la paire la plus courante assez rapidement. Mon approche naïve serait de regarder d'abord la première paire ab, puis de compter le nombre d'occurrences, puis de regarder la paire suivante bcet de compter le nombre d'occurrences, etc. Cependant, cela donnerait déjà juste pour trouver la paire la plus courante une fois . $\mathcal O (n^2)$

Ensuite, même si j'ai compris comment trouver la paire la plus courante en temps . Mon prochain problème est que, ne devons-nous pas trouver la paire la plus courante jusqu'à fois? Et donc cela donnerait un temps total de ? $\mathcal O(n)$ $\mathcal O(n)$ $\mathcal O(n^2)$

algorithms algorithm-analysis runtime-analysis data-compression encoding-scheme Eff
la source

Vous devriez poser une question plus spécifique. La réitération d'un article dans des mots différents semble trop large pour ce site. Où dans l'article les auteurs vous perdent-ils?

adrianN

@adrianN J'ai écrit un peu plus sur ce qui me dérange spécifiquement.

Eff

Le papier a fait l'hypothèse qu'il utilisera la table de hachage et l'a compté comme , qui dans ce cas pourrait être wlog remplacé par un arbre de suffixes pour être . Je viens de parcourir le texte, votre question est toujours très exigeante, mais je ne vois pas vraiment pourquoi vous dépenseriez pour un seul article.

O (n)

$\mathcal O(n)$

O (n)

$\mathcal O(n)$

O (n^{2})

$\mathcal O(n^2)$

Evil

@Evil Donc vous dites que l'on pourrait construire un arbre de suffixes de en temps (BTW, je ne comprends toujours pas quand il est possible de construire un arbre de suffixes en temps linéaire et quand cela prend ). Ensuite, nous trouvons la sous-chaîne la plus fréquente dans l'arbre des suffixes en temps . Correct?

S

$S$

Θ (n)

$\Theta (n)$

O (n \log n)

$\mathcal O (n\log n)$

Θ (n)

$\Theta (n)$

Eff

Moi? Non. Mais Ukkonen en a dit quelques mots. pour l'alphabet de taille constante et en général. Ensuite, nous pouvons trier par fréquences dans ou même exploiter de petits nombres naturels pour compter le tri. Je ne sais pas si quelque chose 1 ~ n est , désolé aucune réponse pour cette partie.

O (n)

$\mathcal O(n)$

O (n \log n)

$\mathcal O(n\log n)$

O (n \log n)

$\mathcal O(n\log n)$

Θ (n)

$\Theta(n)$

Evil

Réponses:

J'ai vérifié le code, relu le document et il semble que l'algorithme ne fonctionne pas dans comme vous l'avez décrit. Les appels récursifs de recherche de paires fonctionnent dans $\mathcal O(n)$
$\mathcal O(n \log n)$ divisé par une constante si vous souhaitez l'emballer jusqu'au bout. En fait, la structure en dessous garde les pointeurs vers la première occurrence de la paire, divise la file d'attente des paires par les occurrences pour la rendre efficace, mais toujours linéaire. D'autre part en analysant le code écrit par Ph.D. élève de l'auteur, j'ai découvert plusieurs astuces - la longueur des paires (le nom d'origine) est donnée comme paramètre (la valeur par défaut est 2) et la récurrence est limitée par le paramètre, qui peut rejeter d'autres appels (la valeur par défaut est d'environ 5 niveaux), avec possibilité de faire un seul passage ou pousser jusqu'à la fin. Le code par défaut s'exécute dans , mais ne produira pas de compression optimale. Il y a aussi un interrupteur pour préférer la mémoire, le temps ou être neutre. $\mathcal O(n)$

Le papier et le code montrent l'utilisation de la table de hachage, qui ne fonctionne que dans le temps constant attendu, mais la fonction donnée fonctionne très bien avec les caractères. Le code limite également la longueur d'entrée par un codage en dur constant.

Changer la table de hachage en arbre de suffixes et réécrire la partie de la récurrence en paires partielles de bookkeepping pourrait donner de meilleurs résultats - je ne suis pas sûr que ce soit possible de le faire , ce serait probablement une question différente. $\mathcal O(n)$

Il existe également une astuce utilisée pour empêcher l'espace vide de traverser - le début du bloc vide pointe vers le premier caractère non vide, mais cela accélère uniquement la traversée, toujours avec un temps log-linéaire. La partie responsable de ce comportement remplace les paires par le nouveau caractère à chaque itération - conserver uniquement les règles de réécriture et les utiliser serait plus rapide, mais l'accès pour vérifier si de nouvelles paires ont été introduites nécessiterait de vérifier les règles de réécriture par rapport aux nouvelles - dans le cas où nous construisons un arbre binaire complet avec des paires aux feuilles de telle manière qu'après avoir remplacé la paire par un nouveau caractère et concédé avec le parent, nous avons obtenu de nouvelles paires aux feuilles jusqu'à la racine - il y a caractères puis paires, puis , $n$ $\frac{n}{2}$ $\frac{n}{4}$ $\frac{n}{8}$ , ... Vous voyez le modèle, il y a paires, mais selon la description de l'algorithme, cela prend prenant du temps uniquement les traversées d'entrée. $\frac{n}{16}$ $2n$ $\mathcal O(n\log n + n)$

Mal
la source