Trie-tietorakenne Javassa

Yleiskatsaus

Tietorakenteet ovat tärkeä apuväline tietokoneiden ohjelmoinnissa, ja on erittäin tärkeää tietää, milloin ja miksi niitä käytetään.

Tämä artikkeli on lyhyt johdatus trie-tietorakenteeseen, sen toteutukseen ja monimutkaisuusanalyysiin.

Trie

Trie on diskreetti tietorakenne, joka ei ole aivan tunnettu tai laajasti mainittu tyypillisillä algoritmikursseilla, mutta kuitenkin tärkeä.

Trie (joka tunnetaan myös nimellä digitaalinen puu) ja joskus jopa radix-puu tai prefix-puu (koska niitä voidaan hakea prefiksien avulla), on järjestetty puurakenne, joka käyttää hyväkseen tallentamiaan avaimia, jotka ovat yleensä merkkijonoja.

Solmun sijainti puussa määrittelee avaimen, johon kyseinen solmu liittyy, mikä tekee puista erilaisia verrattuna binäärihakupuihin, joissa solmuun tallennetaan avain, joka vastaa vain kyseistä solmua.

Kaikkien solmun jälkeläisten yhteisenä etuliitteenä on kyseiseen solmuun liittyvä merkkijono, kun taas juureen liittyy tyhjä merkkijono.

Tässä on esikatselu TrieNode-solmusta, jota tulemme käyttämään Trie-toteutuksessamme:

public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}

Voi olla tapauksia, joissa trie on binäärinen hakupuu, mutta yleisesti ottaen nämä ovat erilaisia. Sekä binäärihakupuut että trie:t ovat puita, mutta binäärihakupuiden jokaisella solmulla on aina kaksi lasta, kun taas trie:iden solmuilla voi olla useampia.

Trie:ssä jokainen solmu (juurisolmua lukuun ottamatta) tallentaa yhden merkin tai numeron. Kulkemalla trie alaspäin juurisolmusta tiettyyn solmuun n voidaan muodostaa merkkien tai numeroiden yhteinen etuliite, joka on yhteinen myös muille trien haaroille.

Kulkemalla trie ylöspäin lehtisolmusta juurisolmuun voidaan muodostaa merkkijono tai numerosarja.

Tässä on Trie-luokka, joka edustaa trie-tietorakenteen toteutusta:

public class Trie { private TrieNode root; //...}

Yleiset operaatiot

Katsotaan nyt, miten perusoperaatiot toteutetaan.

3.1. Trie-luokka. Elementtien lisääminen

Ensimmäinen operaatio, jonka kuvaamme, on uusien solmujen lisääminen.

Ennen kuin aloitamme toteutuksen, on tärkeää ymmärtää algoritmi:

1. Aseta nykyinen solmu juurisolmuksi
2. Aseta nykyinen kirjain sanan ensimmäiseksi kirjaimeksi
3. Jos nykyisessä solmussa on jo olemassa oleva viittaus nykyiseen kirjaimeen (jonkun ”lapset”-kentän elementin kautta), aseta nykyiseksi solmuksi tämä viitattu solmu. Muussa tapauksessa luodaan uusi solmu, asetetaan kirjain yhtä suureksi kuin nykyinen kirjain ja initialisoidaan myös nykyinen solmu tähän uuteen solmuun
4. Kertaa askelta 3, kunnes avain on käyty läpi

Tämän operaation monimutkaisuus on O(n), missä n edustaa avaimen kokoa.

Tässä on tämän algoritmin toteutus:

public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}

Katsotaan nyt, miten voimme käyttää tätä menetelmää uusien elementtien lisäämiseksi trieen:

private Trie createExampleTrie() { Trie trie = new Trie(); trie.insert("Programming"); trie.insert("is"); trie.insert("a"); trie.insert("way"); trie.insert("of"); trie.insert("life"); return trie;}

Voidaan testata, että trie on jo täytetty uusilla solmuilla seuraavasta testistä:

@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}

3.2. Testi:

@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}

3.2. Elementtien etsiminen

Lisätään nyt metodi, jolla voidaan tarkistaa, onko jokin tietty elementti jo olemassa trie:

1. Hakea juuren lapset
2. Kertaa läpi jokainen merkkijonon merkki
3. Tarkista, onko kyseinen merkki jo osa alitrietä. Jos sitä ei ole missään kolmiossa, lopeta haku ja palauta false
4. Kertaa toinen ja kolmas vaihe, kunnes merkkijonossa ei ole enää yhtään merkkiä jäljellä. Jos merkkijonon pää on saavutettu, palaa true

Tämän algoritmin monimutkaisuus on O(n), missä n edustaa avaimen pituutta.

Java-toteutus voi näyttää seuraavalta:

public boolean find(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } current = node; } return current.isEndOfWord();}

Ja käytännössä:

@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}

3.3. Elementin poistaminen

Elementin lisäämisen ja löytämisen lisäksi on selvää, että meidän on myös pystyttävä poistamaan elementtejä.

Poistamista varten meidän on noudatettava seuraavia vaiheita:

1. Tarkista, onko tämä elementti jo osa triestä
2. Jos elementti löytyy, poista se triestä

Tämän algoritmin monimutkaisuus on O(n), jossa n edustaa avaimen pituutta.

Katsotaanpa pikaisesti toteutusta:

public void delete(String word) { delete(root, word, 0);}private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char ch = word.charAt(index); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); if (shouldDeleteCurrentNode) { current.getChildren().remove(ch); return current.getChildren().isEmpty(); } return false;}

Ja toiminnassa:

@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}

Johtopäätös

Tässä artikkelissa olemme nähneet lyhyen johdannon trie-tietorakenteeseen ja sen yleisimpiin operaatioihin sekä niiden toteutukseen.