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.