Понимание хеширования функций

10

Википедия предоставляет следующий пример при описании хеширования функций ; но отображение не соответствует определенному словарю

Например, toдолжен быть преобразован в 3соответствии со словарем, но он закодирован как 1вместо.

Есть ли ошибка в описании? Как работает функция хеширования?

Тексты:

John likes to watch movies. Mary likes too.
John also likes to watch football games.

можно конвертировать, используя словарь

{"John": 1, "likes": 2, "to": 3, "watch": 4, "movies": 5, "also": 6, 
"football": 7, "games": 8, "Mary": 9, "too": 10}

к матрице

[[1 2 1 1 1 0 0 0 1 1]
 [1 1 1 1 0 1 1 1 0 0]]
feature-construction мистифицировать
источник

Ответы:

10

Матрица строится следующим образом:

  • строки представляют собой линии
  • столбцы представляют особенности

и каждая матрица входа (i, j) = k означает:

В строке i слово с индексом j появляется k раз.

Так toотображается на индекс 3. Он появляется ровно один раз в строке 1. Итак, m (1,3) = 1.

Больше примеров

  • likesотображается на индекс 2. Он появляется ровно два раза в первой строке. Итак, м (1,2) = 2
  • also сопоставляется с индексом 6. Он не появляется в строке 1, но один раз в строке 2. Итак, m (1,6) = 0 и m (2,6) = 1.
Штеффен
источник
В контексте хеширования функций у нас нет словаря. У нас есть только хеш-функция. Работает ли это аналогично в том смысле, что вы (1) вычисляете значение хеш-функции объекта и (2) увеличиваете индекс, заданный хэш-функцией, на 1 каждый раз, когда вы видите точку данных? Например, как @ user20370 утверждает ниже, если вы решите закодировать свои функции с 13 битами, а значение хеша «лайков» равно 5674, то увеличивается ли индекс 5674 на 1? И если вы используете меньше битов, вы просто модифицируете 5674 на 2 ^ (# бит) и увеличиваете этот индекс?
Вивек Субраманян
1
@ VivekSubramanian да. Задача состоит в том, чтобы найти хэш-функцию без коллизий (т. Е. Других слов, но с одинаковым хеш-значением) или с коллизиями, возникающими редко. Это область исследований в области компьютерных наук ( en.wikipedia.org/wiki/Perfect_hash_function ).
Штеффен
4

Как указал Штеффен, пример матрицы кодирует количество раз, когда слово появляется в тексте. Положение кодирования в матрице задается словом (позиция столбца в матрице) и текстом (положение строки в матрице).

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

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

Таким образом, вам не нужно создавать словарь, прежде чем анализировать текст. Если вы будете использовать разреженную матрицу в качестве текстовой матрицы, вам даже не нужно будет точно определять, какой будет размер матрицы. Просто сканируя текст на лету, вы будете преобразовывать слова в позиции столбцов с помощью функции хеширования, и ваша текстовая матрица будет заполняться данными (частотами, т. Е.) В соответствии с тем, какой документ вы анализируете постепенно (положение строки).

user20370
источник