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

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(Створення)
 
Рядок 1: Рядок 1:
 
[[Користувач:Кирило_Гавриленко|🔙Назад]]
 
[[Користувач:Кирило_Гавриленко|🔙Назад]]
 +
 +
{|align="left"
 +
|-valign="top"
 +
|[[Файл:400px-Trie example.png|мини|250пкс|Префіксне дерево для ключів "A","to", "tea", "ted", "ten", "i", "in", and "inn".]]
 +
|}
 +
 +
Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса.
 +
 +
Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами.
 +
 +
Для кожного вузла дерева нам знадобляться такі змінні:
 +
 +
 +
 +
<source lang="java">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;</source>
 +
 +
При інициалізації нам потрібно встановити булеві змінні, вказуючи, що вузол - лист, а не кінець слова:
 +
 +
<source lang="java">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);
 +
    }</source>
 +
 +
При вставці елементів у дерево використаємо можливість користуватися кодами символів як індексами масиву дітей:
 +
 +
<source lang="java">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);
 +
    }
 +
  </source>
 +
 +
Перевірка на присутність у дереві реалізується за тим же принципом:
 +
 +
 +
<source lang="java">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();
 +
    }</source>
 +
 +
 +
Пошук задовільняючих префікс слів виконується у зазначеному нижче коді:
 +
 +
<source lang="java">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();
 +
 +
    }</source>
 +
 +
Також потрібно не забути додати до свого коду геттери та сеттери властивостей, і для зручності написати клас-обгортку над TrieNode. Повноцінний код, який працює на Java 8, а також словник на 20 тисяч слів можна переглянути на [https://github.com/robben1234/triedictionary github].

Версія за 18:07, 12 жовтня 2016

🔙Назад

Префіксне дерево для ключів "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.

Отримано з https://wiki.cusu.edu.ua/index.php?title=Реалізація_префіксних_дерев_мовою_Java&oldid=242151