Comment mapper 256 chaînes uniques aux entiers (0..255) avec une fonction sans mémoire

Je ne pense pas que ce que vous recherchez soit possible à moins que vous ne sachiez à l'avance ce que sont les 256 chaînes. En gros, voici une preuve de ceci:

Supposons qu'il existe des f: S ^ * → [0, 255] (note: S ^ * signifie toutes les chaînes de longueur finie) s.t. pour tous les sous-ensembles de 256 longueurs S ⊆ S ^ * , s_1, s_2 ∈ S, f (s_1) = f (s_2) <=> s_1 = s_2 . Étant donné que f ne doit contenir aucune mémoire d'entrées qu'il a vues, il doit mapper de manière déterministe les chaînes au même nombre dans [0, 255] , quel que soit le sous-ensemble dans lequel il se trouve .

Cependant, selon le principe de Pigeonhole , puisqu'il y a plus de 256 chaînes, nous devons avoir au moins deux chaînes qui correspondent à la même valeur entre [0, 255] . En particulier, cela signifie que si nous prenons un sous-ensemble S qui contient les deux chaînes, la propriété ci-dessus pour f est violée, une contradiction. Ainsi, f ne peut pas exister.

Si vous êtes autorisé à savoir quelles 256 chaînes hacher, cela est certainement possible. En général, vous recherchez une fonction de hachage parfaite .

Ce lien fournit un algorithme: https: // www. cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf (reportez-vous aux pages 56-57)

Citant:

Méthode 1: une solution d'espace O (N ^ 2)

Disons que nous sommes prêts à avoir une table dont la taille est quadratique dans la taille N de notre dictionnaire S . Ensuite, voici une méthode simple pour construire une fonction de hachage parfaite. Soit H universel et M = N ^ 2 . Ensuite, choisissez simplement un h aléatoire dans H et essayez-le! le affirme qu'il y a au moins 50% de chances qu'il n'y ait pas de collision.

Méthode 2: une solution d'espace O (N)

Nous allons d'abord hacher dans une table de taille N en utilisant le hachage universel. Cela produira des collisions (sauf si nous sommes extraordinairement chanceux). Cependant, nous allons ensuite reformuler chaque bac en utilisant la méthode 1, en mettant au carré la taille du bac pour obtenir zéro collision. Alors, la façon de penser ce schéma est que nous avons une fonction de hachage de premier niveau h et table de premier niveau A , puis N fonctions de hachage de deuxième niveau Tables de second niveau h_1, ..., h_N et N A_1, ..., A_N . À rechercher un élément x , nous calculons d'abord i = h (x) puis trouvons le élément dans A_i [h_i (x)] .

Sans simplement faire cela: […] qui dépendrait de l ' ordre dans lequel ils sont insérés.

L'ensemble des chaînes possibles est connu à l'avance.

Si vous êtes d'accord pour exiger que les chaînes soient connues d'avance, mais que vous n'aimez tout simplement pas l'arbitraire d'utiliser l'ordre dans lequel elles ont été insérées, alors une approche simple consiste à rassembler les chaînes dans un tableau, triez ce tableau (pour obtenir un ordre déterministe), puis utilisez l'ordre résultant:

var stringArray = [];
stringArray.push('foo');
stringArray.push('bar');
stringArray.push('baz');
// ...
stringArray = stringArray.sort();

var strings = {};
for (var i = 0; i < stringArray.length; ++i) {
    strings[stringArray[i]] = i;
}

Voici une esquisse d'une idée qui pourrait avoir de bons résultats pour une variété d'entrées. Le code ci-dessous suppose des lettres minuscules anglaises, pas d'espaces, et ne permet que jusqu'à 9 doublons de n'importe quelle lettre.

L'idée est que toute permutation de longueur n peut être mappée aux entiers modulo n en détectant combien de fois la permutation doit être appliquée à elle-même avant de se transformer en permutation d'identité. Son "pouvoir" si vous voulez. Le hic, c'est que toutes les permutations avec les mêmes cycles de permutation (la partition entière non ordonnée qui les décrit), se traduiront par la même "puissance", que nous utilisons comme hachage final.

Pour générer la permutation , chaque lettre est affectée à l'un des neuf compartiments de 26, selon s'il s'agit d'un doublon, et poussée vers un tableau, suivi des index manquants de 0 à 255.

Comme beaucoup de fonctions de hachage, cela peut entraîner des collisions (qui pourraient éventuellement être améliorées grâce à quelques indicateurs définis dans la fonction en fonction de l'analyse des entrées, bien que je n'ai pas encore examiné cela plus attentivement).

function seq(n){
  return [...Array(n)].map((_,i) => i);
}

function permute(p1, p){
  return p1.map(x => p[x]);
}

function areEqual(p1, p){
  for (let i=0; i<p.length; i++)
    if (p1[i] != p[i])
      return false;
  return true;
}

function findPower(p1){
  let count = 0;
  const p = seq(p1.length);
  let p2 = p1.slice();
  for (let i=0; i<p.length; i++){
    if (!areEqual(p, p2)){
      p2 = permute(p2, p1);
      count++;
    } else {
      return count;
    }
  }
  return count;
}

// Returns the permutation based on
// the string, s
function hash(s){
  // Each letter is in one of
  // 9 buckets of 26, depending
  // on if it's a duplicate.
  let fs = new Array(26).fill(0);
  let result = [];
  for (let i=0; i<s.length; i++){
    let k = s.charCodeAt(i) - 97;
    result.push(26 * fs[k] + k);
    fs[k]++;
  }
  const set = new Set(result);
  for (let i=0; i<256; i++)
    if (!set.has(i))
      result.push(i);

  return result;
}

function h(s){
  return findPower(hash(s));
}

var strings = [
  'foo',
  'bar',
  'baz',
  'hello',
  'world',
  'etc'];

for (let s of strings)
  console.log(`${ s }: ${ h(s) }`);