Zrozumienie funkcji mieszania funkcji

10

Wikipedia podaje następujący przykład opisujący skrót funkcji ; ale mapowanie nie wydaje się spójne ze zdefiniowanym słownikiem

Na przykład tonależy przekonwertować na 3zgodnie ze słownikiem, ale 1zamiast tego jest zakodowany .

Czy w opisie jest błąd? Jak działa funkcja mieszania funkcji?

Teksty:

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

można przekonwertować za pomocą słownika

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

do matrycy

[[1 2 1 1 1 0 0 0 1 1]
 [1 1 1 1 0 1 1 1 0 0]]
Josh
źródło

Odpowiedzi:

10

Macierz jest konstruowana w następujący sposób:

  • wiersze reprezentują linie
  • kolumny reprezentują funkcje

a każda macierz wejściowa (i, j) = k oznacza:

W wierszu i słowo z indeksem j pojawia się k razy.

Więc tojest odwzorowany na indeks 3. Pojawia się dokładnie raz w linii 1. Więc m (1,3) = 1.

Więcej przykładów

  • likesjest odwzorowany na indeks 2. Pojawia się dokładnie dwa razy w pierwszym wierszu. Więc m (1,2) = 2
  • also jest odwzorowany na indeks 6. Nie pojawia się w linii 1, ale jeden raz w linii 2. Zatem m (1,6) = 0 i m (2,6) = 1.
steffen
źródło
Jednak w kontekście mieszania funkcji nie mamy słownika. Mamy tylko funkcję skrótu. Czy działa to podobnie w tym sensie, że (1) obliczasz wartość skrótu funkcji i (2) zwiększasz indeks podany przez funkcję skrótu o 1 za każdym razem, gdy widzisz punkt danych? Na przykład, jak stwierdza poniżej @ user20370, jeśli zdecydujesz się zakodować swoje funkcje za pomocą 13 bitów, a wartość skrótu „polubień” wynosi 5674, to czy indeks 5674 zostanie zwiększony o 1? A jeśli używasz mniejszej liczby bitów, czy modyfikujesz 5674 o 2 ^ (# bitów) i zwiększasz ten indeks?
Vivek Subramanian
1
@VivekSubramanian tak. Wyzwanie polega na znalezieniu funkcji skrótu bez kolizji (tj. Różnych słów, ale o tej samej wartości skrótu) lub z kolizjami występującymi rzadko. Jest to obszar badań w dziedzinie informatyki ( en.wikipedia.org/wiki/Perfect_hash_function ).
steffen
4

Jak wskazał Steffen, przykładowa matryca koduje liczbę wystąpień słowa w tekście. Pozycję kodowania w matrycy określa słowo (pozycja kolumny na matrycy) i tekst (pozycja wiersza na matrycy).

Teraz sztuczka haszująca działa w ten sam sposób, chociaż nie musisz początkowo definiować słownika zawierającego pozycję kolumny dla każdego słowa.

W rzeczywistości jest to funkcja skrótu, która da ci zakres możliwych pozycji kolumny (funkcja skrótu da ci minimalną i maksymalną możliwą wartość) oraz dokładną pozycję słowa, które chcesz zakodować w macierzy. Wyobraźmy sobie na przykład, że słowo „polubienia” jest mieszane przez naszą funkcję haszującą do liczby 5674, wówczas kolumna 5674 będzie zawierać kodowanie względem słowa „polubienia”.

W ten sposób nie będziesz musiał budować słownika przed analizą tekstu. Jeśli użyjesz rzadkiej matrycy jako matrycy tekstowej, nie będziesz nawet musiał dokładnie określać, jaki będzie jej rozmiar. Wystarczy zeskanować tekst w locie, aby przekształcić słowa w pozycje kolumny za pomocą funkcji skrótu, a macierz tekstowa zostanie zapełniona danymi (częstotliwościami, tj.) Zgodnie z tym, jaki dokument analizujesz stopniowo (pozycja wiersza).

użytkownik20370
źródło