Noções básicas sobre hash de recursos

10

A Wikipedia fornece o seguinte exemplo ao descrever o hash de recursos ; mas o mapeamento não parece consistente com o dicionário definido

Por exemplo, todeve ser convertido para de 3acordo com o dicionário, mas é codificado como 1alternativa.

Existe um erro na descrição? Como funciona o hash de recursos?

Os textos:

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

pode ser convertido usando o dicionário

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

para a matriz

[[1 2 1 1 1 0 0 0 1 1]
 [1 1 1 1 0 1 1 1 0 0]]
feature-construction Josh
fonte

Respostas:

10

A matriz é construída da seguinte maneira:

  • linhas representam linhas
  • colunas representam recursos

e toda matriz de entrada (i, j) = k significa:

Na linha i, a palavra com o índice j aparece k vezes.

Então, toé mapeado para o índice 3. Ele aparece exatamente uma vez na linha 1. Então m (1,3) = 1.

Mais exemplos

  • likesé mapeado para o índice 2. Ele aparece exatamente duas vezes na primeira linha. Então m (1,2) = 2
  • also é mapeado para o índice 6. Ele não aparece na linha 1, mas uma vez na linha 2. Então m (1,6) = 0 e m (2,6) = 1.
Steffen
fonte
No entanto, no contexto do hash de recursos, não temos um dicionário. Temos apenas uma função hash. Isso funciona da mesma maneira no sentido de que você (1) calcula o valor de hash do recurso e (2) incrementa o índice fornecido pela função de hash em 1 cada vez que vê um ponto de dados? Por exemplo, como @ user20370 afirma abaixo, se você decidir codificar seus recursos com 13 bits e o valor do hash de "curtidas" for 5674, o índice 5674 será incrementado em 1? E se você usa menos bits, modifica 5674 por 2 ^ (# bits) e aumenta esse índice?
Vivek Subramanian
11
@VivekSubramanian yes. O desafio é encontrar uma função de hash sem colisões (ou seja, palavras diferentes, mas o mesmo valor de hash) ou com colisões ocorrendo raramente. Esta é uma área de pesquisa em ciência da computação ( en.wikipedia.org/wiki/Perfect_hash_function ).
Steffen
4

Como Steffen apontou, a matriz de exemplo codifica o número de vezes que uma palavra aparece em um texto. A posição da codificação na matriz é dada pela palavra (posição da coluna na matriz) e pelo texto (posição da linha na matriz).

Agora, o truque de hash funciona da mesma maneira, embora você não precise definir inicialmente o dicionário que contém a posição da coluna para cada palavra.

De fato, é a função de hash que fornecerá o intervalo de posições possíveis da coluna (a função de hash fornecerá um valor mínimo e máximo possível) e a posição exata da palavra que você deseja codificar na matriz. Então, por exemplo, vamos imaginar que a palavra "curtidas" seja dividida por nossa função de hash no número 5674, e a coluna 5674 conterá as codificações relativas à palavra "curtidas".

Dessa forma, você não precisará criar um dicionário antes de analisar o texto. Se você usar uma matriz esparsa como sua matriz de texto, nem precisará definir exatamente qual será o tamanho da matriz. Apenas digitalizando o texto, em tempo real, você converterá palavras em posições de coluna pela função hash e sua matriz de texto será preenchida com dados (frequências, ie) de acordo com o documento que você está analisando progressivamente (posição da linha).

user20370
fonte