La compression

1. Table de symbole A
2. Matrice M
3. Les fonctions spéciales

Table de symbole A

• C'est un objet ayant pour clé les symboles et pour valeur leur index (par exemple: {a:0,b:1} ).
• On utilise la fonction g pour le compresser.

Matrice M

• M est initialement un tableau de tableaux.
• Chaque index i de M est un nom détat.
  • 0 : état Not Found.
  • 1 : état initial.
• Chaque index j du tableau M[i] est un index de symbole de l'alphabet.
• On accède à l'état suivant avec M[i][j] donc M[i] peut-être un objet.
  {1:10} est plus court que [,10,,,,,,,,,,,,,]
  mais ici [,10] est encore plus court.
• Si un tableau M[i] est composé principalement d'une certaine valeur, on utilise la fonction h.
  Pour l'exemple précédant on a h(15,0,1,10).

Les fonctions spéciales

Ces fonctions servent à compresser la taille des automates, c'est pour cela que leur nom est si court !

La fonction f

Renvoie une fonction ayant comme arguments symb et state.

• elle renvoie state si le symb ∈ sCharSet et bIn == true sinon -1
• elle renvoie state si le symb ∉ sCharSet et bIn == false sinon -1

var f =function( sCharSet, bIn ){
	var cache = {}
	for(var i=0, ni=sCharSet.length; i < ni; i++ ) cache[ sCharSet[i]] = -1
	return bIn
		? function(symb,state){ return cache[symb] ? state : -1 }
		: function(symb,state){ return cache[symb] || state }
	}

La fonction g

Renvoie un objet ayant comme clé les symboles et comme valeur un index.

var g =function( sSymb1 /*,  sSymb2, ... */ ){ 
	var o = {}
	for(var i=0, ni=arguments.length; i < ni; i++ ) o[ arguments[i]] = i
	return o
	}

La fonction h

Renvoie un tableau :

• de longueur nLength
• ayant comme valeur par défaut nDefaultValue
• la valeur nValue1 à l'index nIndex1
• ...

var h =function( nLength, nDefaultValue, nIndex1, nValue1 /*,  nIndex2, nValue2, ...*/ ){
	var a = []
	var o = {}
	for(var i=2, ni=arguments.length; i < ni; i=i+2 ) o[ arguments[i]] = arguments[i+1]
	for(var i=0; i < nLength; i++ ) a[i] = o[i] || nDefaultValue
	return a
	}