Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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.


 

Předchozí článek
Hashovací tabulka
Všechny články v sekci
Vyhledávací algoritmy
Přeskočit článek
(nedoporučujeme)
Algoritmus internetového vyhledávače - Stromy a StopSlova
Článek pro vás napsal David Jančík
Avatar
Uživatelské hodnocení:
6 hlasů
Autor je vášnivý programátor. Nezná slovo "nelze", nebojí se zkoušet nepoznané a pronikat do nových technologií.
Aktivity