Общее·количество·просмотров·страницы

Java Dev Notes - разработка на Java (а также на JavaScript/Python/Flex и др), факты, события из АйТи

Архив блога

пятница, 17 сентября 2010 г.

Префиксное дерево (trie)

Префиксное дерево (trie) - структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. См. статьи в Wikipedia: trie, префиксное дерево.

Префиксное дерево используется для множества приложений: вместо других структур данных (например, хеш-таблиц), представление словарей, сортировка, полнотекстовый поиск, битовые и сжатые деревья. Алгоритм Ахо-Корасик (используется для поиска подстроки в строке) строит префиксное дерево в процессе своей работы.

Реализация префиксного дерева на Java:

import java.util.*;
 
public class Trie {
static class TrieNode {
Map<Character, TrieNode> children = new TreeMap<Character, TrieNode>();
boolean leaf;
}
 
TrieNode root = new TrieNode();
 
public void put(String s) {
TrieNode v = root;
for (char ch : s.toLowerCase().toCharArray()) {
if (!v.children.containsKey(ch)) {
v.children.put(ch, new TrieNode());
}
v = v.children.get(ch);
}
v.leaf = true;
}
 
public boolean find(String s) {
TrieNode v = root;
for (char ch : s.toLowerCase().toCharArray()) {
if (!v.children.containsKey(ch)) {
return false;
} else {
v = v.children.get(ch);
}
}
return true;
}
 
static Map<Integer,String> levelSpacesMap = new HashMap<Integer,String>();
 
static String getSpace(int level) {
String result = levelSpacesMap.get(level);
if (result == null) {
StringBuilder sb = new StringBuilder();
for (int i=0; i<level; i++) {
sb.append(" ");
}
result = sb.toString();
levelSpacesMap.put(level,result);
}
return result;
}
 
public static void printSorted(TrieNode node) {
printSorted2(node,0);
}
 
private static void printSorted2(TrieNode node, int level) {
for (Character ch : node.children.keySet()) {
System.out.println(getSpace(level)+ch);
printSorted2(node.children.get(ch), level+1);
}
if (node.leaf) {
System.out.println();
}
}
 
// Usage example
public static void main(String[] args) {
Trie trie = new Trie();
trie.put("hello");
trie.put("house");
trie.put("hell");
trie.put("world");
System.out.println(trie.find("hello"));
printSorted(trie.root);
}
}

Комментариев нет:

Отправить комментарий

Постоянные читатели