Відмінності між версіями «Реалізація префіксних дерев мовою Java»
м |
м |
||
| Рядок 1: | Рядок 1: | ||
[[Користувач:Кирило_Гавриленко|🔙Назад]] | [[Користувач:Кирило_Гавриленко|🔙Назад]] | ||
| − | + | [[Файл:400px-Trie example.png|справа|мини|200пкс|Префіксне дерево для ключів "A","to", "tea", "ted", "ten", "i", "in", and "inn".]] | |
| − | + | ||
| − | + | ||
| − | + | ||
Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса. | Префіксне дерево (англ. trie, або англ. prefix tree) — структура даних, дерево, в якому шлях від кореня до листа визначає рядок. Рядки з однаковими префіксами мають спільний шлях від кореня довжиною цього префікса. | ||
Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами. | Префіксне дерево дозволяє зберігати асоціативний масив, ключами якого є рядки. На відміну від бінарних дерев, в листі дерева не зберігається ключ. Значення ключа можна набути прогляданням всіх батьківських вузлів, кожний з яких зберігає один або кілька символів алфавіту. Корінь дерева пов'язаний з порожнім рядком. Таким чином, нащадки вузла мають загальний префікс, звідки і відбулася назва даного абстрактного типу даних. Значення, пов'язані з ключем, зазвичай не пов'язані з кожним вузлом, а тільки з листям і, можливо, деякими внутрішніми вузлами. | ||
| − | + | <br clear="all" /> | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
Для кожного вузла дерева нам знадобляться такі змінні: | Для кожного вузла дерева нам знадобляться такі змінні: | ||
Поточна версія на 18:25, 12 жовтня 2016
Префіксне дерево (англ. 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; 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.
