Как отобразить 256 уникальных строк в целые числа (0..255) с помощью функции без памяти

Question

Скажем, у меня есть строки типа foo, bar, baz, hello, world и т. Д., До 256 уникальных строк, так что их не так много.С таким же успехом это может быть 200 или 32 строки для любых целей и задач.Надеемся, что решение сможет обработать наборы произвольного размера.

Итак, вы берете эту строку и каким-то образом отображаете ее в целое число 0-255.Без этого:

strings[currentString] = ID++
// strings['foo'] = 0
// strings['bar'] = 1
// strings['baz'] = 2
// ...

, который будет зависеть от порядка , в который они вставлены.В идеале они были бы сгенерированы уникально, возможно, из хеша отдельных символов или байтов, я не уверен.Но это была бы функция без памяти , которая берет произвольную строку из набора известного размера и отображает ее в целое число, так что больше похоже на:

// strings['foo'] = 6 + 15 + 15 = 36
// strings['bar'] = 2 + 1 + 16 = 19
// ...

Хотя это не будетработать из-за столкновений.Я не уверен, как разработать такую ​​хэш-функцию, как эта.Так что как-то еще будет работать там, где никогда не будет столкновений , о которых стоит беспокоиться.

function hash(string, size) {
  // return unique integer within size
}

hash('foo', 256) // something like 123
hash('bar', 256) // something like 101

hash('foo', 100) // something else like 50
hash('bar', 100) // something else like 25

Мне было бы интересно узнать слишком широко, как идти о создании такой функции, потому что это кажется очень трудным, но не строго необходимым для вопроса.

Кроме того, мы пытаемся сделать это с помощью базового JavaScript, а не каких-либо специальных вспомогательных методов или вещей, специфичных для браузера.

Набор возможных строк известен заранее.

Answer 1

Без этого: […] который будет зависеть от порядка , в который они вставлены.

Наборо возможных строках известно заранее.

Если вы согласны с требованием, чтобы строки были известны заранее, но вам просто не нравится произвольность использования порядка, в котором они оказываютсяпосле вставки, один простой подход - собрать строки в массив, отсортировать этот массив (чтобы получить детерминированный порядок), а затем использовать результирующий порядок:

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;
}

Answer 2

Вот набросок идеи, которая может дать хорошие результаты для различных входных данных.Приведенный ниже код предполагает использование строчных букв английского алфавита без пробелов и допускает использование до 9 дубликатов любой буквы.

Идея состоит в том, что любая перестановка длины n может быть сопоставлена ​​с целыми числами по модулю nобнаруживая, сколько раз перестановка должна быть применена к себе перед преобразованием в перестановку идентичности.Это «сила», если хотите.Подвох в том, что любые перестановки с одинаковыми циклами перестановок (неупорядоченное целочисленное разбиение, которое их описывает) приведут к той же «мощности», которую мы используем в качестве окончательного хэша.

Чтобы сгенерировать перестановку,каждая буква присваивается одному из девяти сегментов по 26, в зависимости от того, является ли она дубликатом, и помещается ли в массив, за которым следуют отсутствующие индексы от 0 до 255.

Как и многие хеш-функции, это может привести кстолкновения (которые, возможно, могут быть улучшены с помощью нескольких флагов, установленных в функции на основе анализа входных данных, хотя мне еще предстоит рассмотреть это более тщательно).

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) }`);

Answer 3

Я не верю, что то, что вы ищете, возможно, если вы не знаете, что все 256 строк опережают время.Грубо, вот доказательство этого:

Предположим, что существует какой-то f : S^* → [0, 255] (примечание: S^* означает все строки конечной длины) st для всех подмножеств 256-длины S ⊆ S^*, s_1, s_2 ∈ S, f(s_1) = f(s_2) <=> s_1 = s_2.* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *> 100% * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 100 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * может НЕТ.Принцип Pigeonhole , поскольку существует более 256 строк, у нас должно быть как минимум две строки, которые отображаются в одно и то же значение между [0, 255].В частности, это означает, что если мы возьмем подмножество S, содержащее обе строки, указанное выше свойство для f нарушается, противоречие.Таким образом, f не может существовать.

---

Если вам разрешено знать, какие 256 строк хэшировать, это определенно возможно.В общем, вам нужна совершенная хеш-функция .

Эта ссылка обеспечивает алгоритм: https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf (см. Стр. 56-57)

Цитирование:

Метод 1: решение O(N^2) -пространства

Допустим, мы хотим иметь таблицу, размер которой в квадратичном видеразмер N нашего словаря S.Тогда вот простой метод построения идеальной хеш-функции.Пусть H будет универсальным и M=N^2.Тогда просто выберите случайный h из H и попробуйте!Утверждение состоит в том, что есть как минимум 50% -ная вероятность того, что у него не будет коллизий.

Метод 2: O(N) -пространственное решение

Сначала мы будем хэшировать втаблица размером N с использованием универсального хеширования.Это приведет к некоторым столкновениям (если только нам не повезет).Однако затем мы перефразируем каждый бин, используя метод 1, возводя в квадрат размер бина, чтобы получить нулевые коллизии.Итак, способ думать об этой схеме состоит в том, что у нас есть хеш-функция первого уровня h и таблица первого уровня A, а затем N хеш-функции второго уровня h_1, ..., h_N и N second-таблицы уровней A_1, ..., A_N.Чтобы найти элемент x, мы сначала вычисляем i=h(x), а затем находим элемент в A_i[h_i(x)].