Lekce 11 - Optimalizované vyhledávání v poli - princip děr
V minulé lekci, Hashovací tabulka, jsme si popsali princip a implementaci algoritmu rychlého vyhledávání pomocí datové struktury nazývané hashovací tabulka, neboli tabulka s rozptýlenými hodnotami.
Optimalizované vyhledávání v poli funguje na principu
děr. Z daného slova se vypočítá hash - číslo
indikující index v poli. Pokud je na dané pozici díra (null
)
zapíše se daná hodnota. Pokud je již obsazeno, jde na další pozici do té
doby, dokud není volná.
Pokud ve slovníku hledám, vypočítám hash slova. Najdu si jej v poli a zkontroluji, zda odpovídá hledanému slovu. Pokud ho najdu, vrátím ho. Pokud ne, podívám se na další pozici a hledám do té doby, než narazím na díru. Toto optimalizuje rychlost vyhledávání.
Příkladné použití - třída Slovník
:
public class Dictionary { // pole pro ukládání slovíček String[][] dictionary; // kapacita pole int capacity; /** * Konstruktor slovníku. Vytvoří slovník o dané kapacitě. * @param capacity Velikost slovníku - počet slov, které se do něj vejdou */ public Dictionary(int capacity) { this.capacity = capacity; dictionary = new String[capacity][2]; } /** * Vrátí hash daného slova. Sečte jednotlivá písmena (jejich ascii hodnoty) číslo je v rozmezí kapacity - hash mod kapacita. * @param word Slovo, jehož hash chceme získat * @return Celočíselný Hash daného slova */ private int hash(String word) { int hash = 0; for (char letter : word.toCharArray()) { hash += (int)letter; } return hash % capacity; } /** * Přidá slovo do slovníku. Pokud tam již není a pokud je ve slovníku místo. * @param czech České slovo * @param english Anglický ekvivalent * @return Úspěch při ukládání */ public boolean addWord(String czech, String english) { int position = hash(czech); while (dictionary[position][0] != null) { if ((dictionary[position][0]).equals(czech)) return false; position = ++position % capacity; } dictionary[position][0] = czech; dictionary[position][1] = english; return true; } /** * Najde ve slovníku pomocí hashe daný ekvivalent slova. Pokud tam není vrátí "Not found" - "Nenalezeno" * @param czech České slovo, které chceme přeložit * @return Anglický ekvivalent zadaného slova */ public String translate(String czech) { int position = hash(czech); while (dictionary[position][0] != null) { if (dictionary[position][0].equals(czech)) return dictionary[position][1]; position = ++position % capacity; } return "Nenalezeno"; } }
Zdrojové kódy jsou v jazyce Java.
Ukázka použití výše uvedené třídy:
Dictionary dic = new Dictionary(5); System.out.println("úspěch při vložení: " + dic.addWord("pes", "dog")); System.out.println("úspěch při vložení: " + dic.addWord("kočka", "cat")); System.out.println("úspěch při vložení: " + dic.addWord("kůň", "horse")); System.out.println(dic.translate("kočka")); System.out.println(dic.translate("kůň")); System.out.println(dic.translate("davos"));
Aby byla zachována rychlost vyhledávání, je třeba vždy mít pole o dostatečné velikosti. Tzn. s dostatečným počtem volných děr. Tedy z uvedené kapacity pole by se mělo zaplnit maximálně kolem 75 %. Pokud se použije více, bude málo děr, tím pádem při vyhledávání prvku, který v poli není nebo koliduje (má stejný hash a proto byl posunut) se bude muset prohledat větší část pole (pokud bude plné, tak i celé pole) a algoritmus pak nebude mít smysl.
V další lekci, Algoritmus internetového vyhledávače - Stromy a StopSlova, si popíšeme principy internetového vyhledávače.