Haszowanie


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie

Podstawowe operacje na tablicach
Wyszukiwanie liniowe

 

Problem

W ciągu łańcuchów wyszukać zadany łańcuch w najkrótszym czasie.

 

Problemy tego typu pojawiają się często w bazach danych, gdzie szybko należy wyszukać rekord o zadanej zawartości (np. wg nazwiska). Zachodzi pytanie, czy dany łańcuch możemy znaleźć wśród innych łańcuchów w czasie porównywalnym z czasem stałym O(1). Rozwiązaniem jest haszowanie (ang. hashing). Wyobraźmy sobie, że posiadamy pewną funkcję, która dla danego łańcucha daje w wyniku liczbę całkowitą z zakresu od 0 do n-1. Tworzymy tablicę n elementową łańcuchów i łańcuchy umieszczamy w tej tablicy na pozycjach określonych przez naszą funkcję, którą będziemy nazywać funkcją haszującą (ang. hash function). Aby teraz znaleźć łańcuch w tablicy, wyznaczamy dla niego wartość funkcji haszującej i sięgamy do komórki o tym indeksie. Nie musimy wcale przeglądać reszty komórek. Brzmi wspaniale. Lecz rzeczywistość, niestety, nie jest aż tak idealna, co zaraz pokażemy.

Wyobraźmy sobie, że w tablicy T chcemy przechowywać 5 znakowe łańcuchy. Jeśli znaki będą w kodzie ASCII, to każdy z nich będzie składał się z 8 bitów. Nasza funkcja mogłaby po prostu łączyć bity tych znaków w ciąg 40 bitowy, który określałby indeks znaku. Jednak mamy tutaj problem - liczba 40 bitowa ma zakres od 0 do 240-1, a jest to naprawdę dużo, brakłoby nam pamięci w komputerze. Cóż zatem zrobić? Możemy naszą funkcję haszującą hf() ograniczyć za pomocą działania modulo. Na przykład: sumujemy kody znaków ASCII w łańcuchu, a wynik bierzemy modulo n. Wtedy łańcuchy mogą mieć dowolną długość. Sprawdźmy dla kilku łańcuchów ASCII:

 

Litera A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Kod ASCII 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

n = 10

s1 = "ALA" hf(s1) = (65 + 76 + 65) mod 10 = 6
s2 = "MA" hf(s2) = (77 + 65) mod 10 = 2
s3 = "KOTA" hf(s3) = (75 + 79 + 84 + 65) mod 10 = 3

 

Dla łańcuchów s1, s2, s3 otrzymaliśmy indeksy 6, 2 i 3. Łańcuchy te umieszczamy zatem w komórkach tablicy T o podanych indeksach:

 

T[0] = ""
T[1] = ""
T[2] = "MA"
T[3] = "KOTA"
T[4] = ""
T[5] = ""
T[6] = "ALA"
T[7] = ""
T[8] = ""
T[9] = ""

 

Załóżmy dalej, że chcemy do naszej tablicy T wstawić łańcuch BAR, hf("BAR") =  (66 + 65 + 82) mod 10 = 3. Mamy problem! Komórka T[3] jest już zajęta, ponieważ przechowuje łańcuch "KOTA". Natrafiliśmy na tzw. kolizyjność haszowania – wiele różnych łańcuchów posiada taką samą wartość funkcji haszującej (np. dla naszej funkcji haszującej te same wartości otrzymamy w słowach zbudowanych z tych samych liter – KOTA, KATO, AKOT, OKAT, RAB, ARB...). Jest to konsekwencją ograniczenia zbioru jej wartości. Problemu kolizji nie unikniemy, musimy go zatem rozwiązać. Możemy, co prawda, bardziej skomplikować funkcję haszującą lub zwiększyć zakres wartości. Dla pewnych łańcuchów otrzymamy wtedy różne wartości indeksu. Jednakże na dłuższą metę i tak natrafimy na problem kolizji, ponieważ jest on cechą wewnętrzną haszowania.

Prostym rozwiązaniem jest tzw. próbkowanie liniowe (ang. linear probing). Polega ono na tym, iż przy wstawianiu łańcuchów sprawdzamy, czy na pozycji wyliczonej przez funkcję haszującą jest wolne miejsce. Jeśli tak, to wstawiamy tam nasz łańcuch. Jeśli komórka jest już zajęta, to liniowo szukamy pierwszej wolnej, tzn. przeglądamy kolejne komórki tablicy, aż do napotkania komórki wolnej – po komórce T[n-1] następuje komórka T[0].

W naszym przykładzie łańcuch "BAR" umieszczamy w T[4]:

 

T[0] = ""
T[1] = ""
T[2] = "MA"
T[3] = "KOTA"
T[4] = "BAR"
T[5] = ""
T[6] = "ALA"
T[7] = ""
T[8] = ""
T[9] = ""

 

Gdyby znów pojawił się łańcuch, dla którego hf() = 3, to umieścilibyśmy go w T[5], następny w T[7] (ponieważ T[6] zajmuje już łańcuch "ALA") itd. Warunkiem powodzenia jest, aby tablica posiadała odpowiedni rozmiar. Gdy w tablicy jest już n łańcuchów, to próba dodania następnego spowoduje zapętlenie, ponieważ nie znajdziemy wolnej komórki. Wtedy należy dodatkowo sprawdzać, czy nie wróciliśmy do wyjściowej komórki i przerwać operację wstawiania, jeśli tak się stało.

Jeśli stosowaliśmy próbkowanie liniowe przy wstawianiu łańcuchów do tablicy, to przy wyszukiwaniu łańcucha musimy je również stosować. Zasada jest następująca:

 

Wyznaczamy indeks funkcją haszującą. Sprawdzamy, czy w komórce o podanym indeksie jest nasz łańcuch. Jeśli tak, to kończymy. Jeśli nie, to liniowo sprawdzamy kolejne komórki aż do momentu, gdy znajdziemy poszukiwany łańcuch lub natrafimy na komórkę pustą, lub wrócimy z powrotem do komórki o indeksie początkowym (zdarzy się to wtedy, gdy cała tablica jest zapełniona łańcuchami, a poszukiwanego łańcucha brak). W dwóch ostatnich przypadkach poszukiwanie powinno zwrócić wartość informującą o błędzie.

 

Przy próbkowaniu liniowym złożoność operacji wstawiania i wyszukiwania może się degenerować do klasy O(n). Z drugiej strony przy wstawianiu łańcucha szukamy jedynie pustej komórki, nie musimy porównywać łańcuchów ze sobą (chyba że chcemy wyeliminować duplikaty). Jeśli przy wstawianiu elementów nie wystąpiło dużo kolizji, to łańcuchy są rozmieszczone w tablicy w większości wg wartości funkcji haszującej, zatem klasa złożoności wyszukiwania jest bliska ideałowi O(1).

Drugą metodę haszowania przedstawiamy w rozdziale "Haszowanie z wykorzystaniem list jednokierunkowych".

 

Algorytm wstawiania łańcucha do tablicy haszowanej

Wejście
s  –  łańcuch do umieszczenia w tablicy haszowanej
T  – tablica łańcuchów
n  – rozmiar tablicy, n N
Wyjście:

Tablica T z wstawionym łańcuchem s, jeśli było dla niego wolne miejsce.

Elementy pomocnicze:
i  –  indeks, i N
h  – przechowuje wartość haszu, h N
hf(x,n)  – oblicza indeks w T na podstawie łańcucha x i liczby komórek n.
Lista kroków dla wersji z duplikatami:
K01: h ← hf(s,n) ; obliczamy indeks początkowy
K02: ih ; przeszukiwanie tablicy rozpoczynamy od wyliczonego indeksu
K03: Jeśli T[i] = "", to T[i] ← s i zakończ ; w puste miejsce zapisujemy łańcuch
K04: i ← (i + 1) mod n ; przechodzimy do następnej komórki
K05: Jeśli i = h, to zakończ ; Jeśli wróciliśmy w to samo miejsce, to kończymy
K06: Idź do K03 ; inaczej kontynuujemy pętlę
Lista kroków dla wersji bez duplikatów:
K01: h ← hf(s,n) ; obliczamy indeks początkowy
K02: ih ; przeszukiwanie tablicy rozpoczynamy od wyliczonego indeksu
K03: Jeśli T[i] = "", to T[i] ← s i zakończ ; w puste miejsce zapisujemy łańcuch
K04: Jeśli T[i] = s, to zakończ ; jeśli w tablicy już jest łańcuch s, to kończymy bez wstawiania
K05: i ← (i + 1) mod n ; przechodzimy do następnej komórki
K06: Jeśli i = h, to zakończ ; Jeśli wróciliśmy w to samo miejsce, to kończymy
K07: Idź do K03 ; inaczej kontynuujemy pętlę

 

Algorytm wyszukiwania łańcucha w tablicy haszowanej

Wejście
s  –  łańcuch do wyszukania w tablicy haszowanej
T  – tablica łańcuchów
n  – rozmiar tablicy, n N
Wyjście:

Indeks łańcucha w T lub -1, jeśli łańcucha nie ma w T.

Elementy pomocnicze:
i  –  indeks, i N
h  – przechowuje wartość haszu, h N
hf(x,n)  – oblicza indeks w T na podstawie łańcucha x i liczby komórek n.
Lista kroków:
K01: h ← hf(s,n) ; obliczamy indeks początkowy
K02: ih ; przeszukiwanie tablicy rozpoczynamy od wyliczonego indeksu
K03: Jeśli T[i] = "", to zakończ z wynikiem -1 ; brak łańcucha
K04: Jeśli T[i] = s, to zakończ z wynikiem i ; łańcuch odnaleziony
K05: i ← (i + 1) mod n ; przechodzimy na następną pozycję
K06: Jeśli i = h, to zakończ z wynikiem -1 ; powrót na pozycję wyjściową, czyli brak łańcucha
K07: Idź do K03 ; inaczej kontynuujemy pętlę

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program ma na celu przetestowanie efektywności haszowania z próbkowaniem liniowych. Tworzy on 10-cio elementową tablicę haszowaną łańcuchów. Następnie generuje 10 losowych łańcuchów 4-ro znakowych z liter A i B, po czym umieszcza je w tablicy haszowanej. Ponieważ łańcuchy są tworzone losowo, to będą się pojawiały duplikaty, których program nie umieści w tablicy, zatem część jej komórek pozostanie niezajęta. Również pojawią się łańcuchy o tej samej wartości funkcji haszującej. W takim przypadku próbkowanie liniowe umieści je w innych komórkach, niż wychodzi to z ich haszu.

Po wypełnieniu tablicy jej zawartość jest wyświetlana w oknie konsoli wraz z wartościami haszu. Jeśli wartość haszu różni się od indeksu tablicy, to dany łańcuch został zapisany w innej komórce, ponieważ jego komórka była zajęta przez inny łańcuch.

W drugiej części program generuje wszystkie łańcuchy 4-znakowe z liter A i B, a następnie wyszukuje je w tablicy haszowanej, wyświetlając kolejno: łańcuch, wartość haszu hf(), liczbę obiegów pętli wyszukującej c oraz informację o pozycji łańcucha w tablicy, jeśli się tam znajduje. Zwróć uwagę na pozycje, dla których liczba obiegów c jest równa zero – te łańcuchy znaleziono od razu za pierwszym podejściem.

 

Lazarus
// Haszowanie z próbkowaniem liniowym
// Data: 16.06.2013
// (C)2013 mgr Jerzy Wałaszek
//-----------------------------------

program hashing;

// Funkcja haszująca
//------------------
function hf(s : string) : integer;
var
  h,i : integer;
begin
  h := 0;
  for i := 1 to length(s) do
    h := 2 * h + 1 - (ord(s[i]) and 1);
  hf := h mod 10;
end;

// Funkcja tworzy łańcuch 4 znakowy z A i B
// na podstawie wartości bitów x
//-----------------------------------------
function s4(x : integer) : string;
var
  m : integer;
  s : string;
begin
  s := '';
  m := 8;  // Maska bitowa
  while m > 0 do
  begin
    if x and m = 0 then s := s + 'A' else s := s + 'B';
    m := m shr 1;
  end;
  s4 := s;
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************
var
  T : array[0..9] of string;
  i,j,h,c,p : integer;
  s : string;
begin
  randomize;

  // Zerujemy tablicę haszowaną
  for i := 0 to 9 do T[i] := '';

  // Tablicę wypełniamy łańcuchami
  for i := 0 to 9 do
  begin
    // Generujemy losowy łańcuch z 4 znaków A,B
    s := s4(random(16));

    // Łańcuch umieszczamy w tablicy haszowanej
    h := hf(s);
    j := h;
    while true do
    begin
      if T[j] = '' then
      begin
        T[j] := s;
        break;
      end;
      if T[j] = s then break;
      j := (j + 1) mod 10;
      if j = h then break;
    end;
  end;

  // Wyświetlamy zawartość tablicy wraz z wartością funkcji haszującej
  for i := 0 to 9 do
  begin
    write('T[',i,'] = ');
    if T[i] <> '' then writeln(T[i],' hf() = ',hf(T[i]))
    else               writeln('-');
  end;

  writeln;

  // Sprawdzamy obecność łańcuchów w tablicy haszowanej
  for i := 0 to 15 do
  begin
    s := s4(i);  // Łańcuch
    h := hf(s);  // Hasz łańcucha
    c := 0;      // Licznik obiegów
    j := h;
    p := -1;
    while true do
    begin
      if T[j] = '' then break;
      if T[j] = s then
      begin
        p := j; break;
      end;
      j := (j + 1) mod 10;
      if j = h then break;
      inc(c);
    end;

    // Wyświetlamy wyniki
    write(s,' hf() = ',h,' c = ',c,' ');
    if p > -1 then writeln('is in T[',p,']')
    else           writeln('-');
  end;
  writeln;
end.
Code::Blocks
// Haszowanie z próbkowaniem liniowym
// Data: 16.06.2013
// (C)2013 mgr Jerzy Wałaszek
//-----------------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Funkcja haszująca
//------------------
int hf(string s)
{
  unsigned int h,i;

  h = 0;
  for(i = 0; i < s.length(); i++)
    h = 2 * h + 1 - (s[i] & 1);
  return h % 10;
}

// Funkcja tworzy łańcuch 4 znakowy z A i B
// na podstawie wartości bitów x
//-----------------------------------------
string s4(int x)
{
  string s = "";
  int m = 8;  // Maska bitowa
  while(m)
  {
    s += (x & m)? 'B' : 'A';
    m >>= 1;
  }
  return s;
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************
int main()
{
  string T[10],s;
  int i,j,h,c,p;

  srand(time(NULL));

  // Zerujemy tablicę haszowaną
  for(i = 0; i < 10; i++) T[i] = "";

  // Tablicę wypełniamy łańcuchami
  for(i = 0; i < 10; i++)
  {
    // Generujemy losowy łańcuch z 4 znaków A,B
    s = s4(rand() % 16);

    // Łańcuch umieszczamy w tablicy haszowanej
    h = hf(s);
    j = h;
    while(true)
    {
      if(T[j] == "")
      {
        T[j] = s;
        break;
      }
      if(T[j] == s) break;
      j = (j + 1) % 10;
      if(j == h) break;
    }
  }

  // Wyświetlamy zawartość tablicy wraz z wartością funkcji haszującej
  for(i = 0; i < 10; i++)
  {
    cout << "T[" << i << "] = ";
    if(T[i] != "") cout << T[i] << " hf() = " << hf(T[i]);
    else           cout << "-";
    cout << endl;
  }

  cout << endl;

  // Sprawdzamy obecność łańcuchów w tablicy haszowanej
  for(i = 0; i < 16; i++)
  {
    s = s4(i);  // Łańcuch
    h = hf(s);  // Hasz łańcucha
    c = 0;      // Licznik obiegów
    j = h;
    p = -1;
    while(true)
    {
      if(T[j] == "") break;
      if(T[j] == s)
      {
        p = j; break;
      };
      j = (j + 1) % 10;
      if(j == h) break;
      c++;
    }

    // Wyświetlamy wyniki
    cout << s << " hf() = " << h << " c = " << c << " ";
    if(p > -1) cout << "is in T[" << p << "]";
    else       cout << "-";
    cout << endl;
  }

  cout << endl;

  return 0;
}
Free Basic
' Haszowanie z próbkowaniem liniowym
' Data: 16.06.2013
' (C)2013 mgr Jerzy Wałaszek
'-----------------------------------

' Funkcja haszująca
'------------------
Function hf(ByRef s As String) As Integer

  Dim As Integer h,i

  h = 0
  For i = 1 To Len(s)
    h = 2 * h + 1 - (Asc(Mid(s,i,1)) And 1)
  Next
  return h Mod 10
End Function

' Funkcja tworzy łańcuch 4 znakowy z A i B
' na podstawie wartości bitów x
'-----------------------------------------
Function s4(x As Integer) As String

  Dim As String s = ""
  Dim As Integer m = 8  ' Maska bitowa
  While m > 0
    If (x And m) = 0 Then
    	s += "A"
    Else
      s += "B"
    End If
    m Shr= 1
  Wend
  s4 = s
End Function

'**********************
'*** PROGRAM GŁÓWNY ***
'**********************

Dim As String T(9),s
Dim As Integer i,j,h,c,p

Randomize

' Zerujemy tablicę haszowaną
For i = 0 To 9: T(i) = "": Next

' Tablicę wypełniamy łańcuchami
For i = 0 To 9

  ' Generujemy losowy łańcuch z 4 znaków A,B
  s = s4(Int(Rnd() * 16))

  ' Łańcuch umieszczamy w tablicy haszowanej
  h = hf(s)
  j = h
  while 1
    If T(j) = "" Then
      T(j) = s
      Exit While
    End If
    If T(j) = s Then Exit While
    j = (j + 1) Mod 10
    If j = h Then Exit While
  Wend
Next

' Wyświetlamy zawartość tablicy wraz z wartością funkcji haszującej
For i = 0 To 9
  Print Using "T[&] = ";i;
  If T(i) <>  "" Then
   	Print Using "& hf() = &";T(i);hf(T(i))
  Else
      Print "-"
  End If
Next

Print

' Sprawdzamy obecność łańcuchów w tablicy haszowanej
For i = 0 To 15
  s = s4(i)  ' Łańcuch
  h = hf(s)  ' Hasz łańcucha
  c = 0      ' Licznik obiegów
  j = h
  p = -1
  While 1
    if T(j) = "" Then Exit While
    If T(j) = s Then
      p = j
      Exit While
    End If
    j = (j + 1) Mod 10
    If j = h Then Exit While
    c += 1
  Wend

  ' Wyświetlamy wyniki
  Print Using "& hf() = & c = & ";s;h;c;
  If p > -1 Then
  	 Print Using "is in T[&]";p
  Else
    Print "-"
  End If
Next

Print

End
Wynik
T[0] = AAAA hf() = 0
T[1] = -
T[2] = AABA hf() = 2
T[3] = AABB hf() = 3
T[4] = BBBA hf() = 4
T[5] = BBBB hf() = 5
T[6] = BBAB hf() = 3
T[7] = ABBB hf() = 7
T[8] = -
T[9] = -

AAAA hf() = 0 c = 0 is in T[0]
AAAB hf() = 1 c = 0 -
AABA hf() = 2 c = 0 is in T[2]
AABB hf() = 3 c = 0 is in T[3]
ABAA hf() = 4 c = 4 -
ABAB hf() = 5 c = 3 -
ABBA hf() = 6 c = 2 -
ABBB hf() = 7 c = 0 is in T[7]
BAAA hf() = 8 c = 0 -
BAAB hf() = 9 c = 0 -
BABA hf() = 0 c = 1 -
BABB hf() = 1 c = 0 -
BBAA hf() = 2 c = 6 -
BBAB hf() = 3 c = 3 is in T[6]
BBBA hf() = 4 c = 0 is in T[4]
BBBB hf() = 5 c = 0 is in T[5]

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.