Реалізація префіксних дерев мовою Java

🔙Назад

Префіксне дерево для ключів "A","to", "tea", "ted", "ten", "i", "in", and "inn".

Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса.

Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами.

Для кожного вузла дерева нам знадобляться такі змінні:

private static final int ALPHABET_SIZE = 26;
    private static final int BUFFER_SIZE = 1024;
    private TrieNode[] children;
    private TrieNode parent; // used to back track nodes to form the word
    private char character;
    private boolean isWord;
    private boolean isLeaf;

При інициалізації нам потрібно встановити булеві змінні, вказуючи, що вузол - лист, а не кінець слова:

public TrieNode() {
        this.setChildren(new TrieNode[ALPHABET_SIZE]);
        this.setWord(false); // if there no character then it's a leaf, not a word (end of loop)
        this.setLeaf(true);
    }

При вставці елементів у дерево використаємо можливість користуватися кодами символів як індексами масиву дітей:

public void add(String word) {
        int limit = word.length(),
                letter, index;
        TrieNode t = this;
 
        word = word.toLowerCase();
        for (int i = 0; i < limit; i++) {
            letter = word.charAt(i);
            index = letter - 'a';
            if (!isLetter(letter)) continue;
            if (t.children[index] == null) {
                t.children[index] = new TrieNode();
                t.children[index].character = (char) letter;
            }
            t.children[index].setLeaf(false); // it's a word if there is character
            t.children[index].parent = t;
            t = t.children[index];
        }
        t.setWord(true);
    }
public void addAll(String[] words) {
        for (String s : words)
            add(s);
    }
 
private boolean isLetter(int letter) {
        return Character.isAlphabetic(letter);
    }

Перевірка на присутність у дереві реалізується за тим же принципом:

public boolean contains(String s) {
        TrieNode t = this;
        int limit = s.length();
        for (int i = 0; i < limit; i++) {
            int letter = s.charAt(i);
            int index = letter - 'a';
            if (t.children[index] == null)
                return false;
            t = t.children[index];
        }
        return t.isWord();
    }

Пошук задовільняючих префікс слів виконується у зазначеному нижче коді:

public List<String> getWords() {
        TrieNode t = this; // tail
        List<String> words = new ArrayList<>();
 
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (t.children[i] != null)
                words.addAll(t.getChildren()[i].findAndSaveWords());
        }
        return words;
    }
 
public List<String> findAndSaveWords() {
        List<String> words = new ArrayList<>();
        TrieNode t = this;
        if (t.isWord())
            words.add(t.getWord());
        if (!t.isLeaf()) {
            for (int i = 0; i < t.children.length; i++) {
                if (t.children[i] != null)
                    words.addAll(children[i].findAndSaveWords());
            }
        }
        return words;
    }
 
 public String getWord() {
        TrieNode t = this;
        char[] buffer = new char[BUFFER_SIZE];
        StringBuilder res = new StringBuilder();
 
        int i = 0;
        while (!t.isLeaf()) {
            buffer[i] = t.character;
            t = t.parent;
            i++;
        }
        res.append(buffer);
        return res.reverse().toString().trim();
 
    }

Також потрібно не забути додати до свого коду геттери та сеттери властивостей, і для зручності написати клас-обгортку над TrieNode. Повноцінний код, який працює на Java 8, а також словник на 20 тисяч слів можна переглянути на github.