Dove trovo un’implementazione cartografica basata su Trie standard in Java?

Ho un programma Java che memorizza molti mapping da stringhe a vari oggetti.

Al momento, le mie opzioni sono di fare affidamento sull’hash (tramite HashMap) o sulle ricerche binarie (tramite TreeMap). Mi chiedo se esista un’implementazione di mappa efficiente e standard basata su trie in una libreria di raccolte di qualità e popolare?

Ho scritto il mio in passato, ma preferirei andare con qualcosa di standard, se disponibile.

Chiarificazione rapida: mentre la mia domanda è generale, nel progetto corrente mi sto occupando di molti dati che sono indicizzati dal nome di class pienamente qualificato o dalla firma del metodo. Quindi, ci sono molti prefissi condivisi.

    Potresti voler esaminare l’ implementazione di Trie che Limewire sta contribuendo a Google Guava.

    Non esiste una struttura dati trie nelle librerie Java principali.

    Ciò può essere dovuto al fatto che i tentativi di solito sono progettati per memorizzare stringhe di caratteri, mentre le strutture di dati Java sono più generali, di solito contengono qualsiasi Object (che definisce l’uguaglianza e un’operazione di hash), sebbene a volte siano limitati a oggetti Comparable (definendo un ordine). Non esiste un’astrazione comune per “una sequenza di simboli”, sebbene CharSequence sia adatto per le stringhe di caratteri, e suppongo che tu possa fare qualcosa con Iterable per altri tipi di simboli.

    Ecco un altro punto da considerare: quando si tenta di implementare un trie convenzionale in Java, si viene rapidamente confrontati con il fatto che Java supporti Unicode. Per avere qualsiasi tipo di efficienza dello spazio, devi limitare le stringhe nel tuo trie a qualche sottoinsieme di simboli, o abbandonare l’approccio convenzionale di memorizzare i nodes figli in una matrice indicizzata dal simbolo. Questo potrebbe essere un altro motivo per cui i tentativi non sono considerati sufficientemente generici per l’inclusione nella libreria principale e qualcosa da tenere a mente se si implementa il proprio o si utilizza una libreria di terze parti.

    Controlla anche gli alberi concomitanti . Supportano entrambi gli alberi Radix e Suffix e sono progettati per ambienti ad alta concorrenza.

    Apache Commons Collections v4.0 ora supporta le strutture trie.

    Vedi le informazioni sul pacchetto org.apache.commons.collections4.trie per maggiori informazioni. In particolare, controlla la class PatriciaTrie :

    Implementazione di un PATRICIA Trie (Algoritmo pratico per recuperare informazioni codificate in alfanumerico).

    A PATRICIA Trie è un Trie compresso. Invece di memorizzare tutti i dati ai bordi del Trie (e con nodes interni vuoti), PATRICIA memorizza i dati in ogni nodo. Ciò consente operazioni di attraversamento, inserimento, eliminazione, predecessore, successore, prefisso, intervallo e selezione (object) molto efficienti. Tutte le operazioni vengono eseguite nel peggiore dei casi nel tempo O (K), dove K è il numero di bit nell’elemento più grande nell’albero. In pratica, le operazioni richiedono effettivamente il tempo O (A (K)), dove A (K) è il numero medio di bit di tutti gli elementi nell’albero.

    Ho scritto e pubblicato qui un’implementazione semplice e veloce.

    Quello che ti serve è org.apache.commons.collections.FastTreeMap , penso.

    Collezioni di Apache’s commons: org.apache.commons.collections4.trie.PatriciaTrie

    Potresti anche guardare questo TopCoder (è richiesta la registrazione …).

    Se hai richiesto una mappa ordinata, allora vale la pena provare. Se non lo fai allora hashmap è migliore. Hashmap con chiavi di stringa può essere migliorato rispetto all’implementazione standard di Java: Array hash map

    Se non sei preoccupato di inserire la libreria di Scala, puoi usare questa implementazione efficiente in termini di spazio che ho scritto di un burst trie .

    https://github.com/nbauernfeind/scala-burst-trie

    Di seguito è una implementazione di base di HashMap di un Trie. Alcune persone potrebbero trovare questo utile …

     class Trie { HashMap root; public Trie() { root = new HashMap(); } public void addWord(String word) { HashMap node = root; for (int i = 0; i < word.length(); i++) { Character currentLetter = word.charAt(i); if (node.containsKey(currentLetter) == false) { node.put(currentLetter, new HashMap()); } node = node.get(currentLetter); } } public boolean containsPrefix(String word) { HashMap node = root; for (int i = 0; i < word.length(); i++) { Character currentLetter = word.charAt(i); if (node.containsKey(currentLetter)) { node = node.get(currentLetter); } else { return false; } } return true; } } 

    ecco la mia implementazione, divertitevi tramite: GitHub – MyTrie.java

     /* usage: MyTrie trie = new MyTrie(); trie.insert("abcde"); trie.insert("abc"); trie.insert("sadas"); trie.insert("abc"); trie.insert("wqwqd"); System.out.println(trie.contains("abc")); System.out.println(trie.contains("abcd")); System.out.println(trie.contains("abcdefg")); System.out.println(trie.contains("ab")); System.out.println(trie.getWordCount("abc")); System.out.println(trie.getAllDistinctWords()); */ import java.util.*; public class MyTrie { private class Node { public int[] next = new int[26]; public int wordCount; public Node() { for(int i=0;i<26;i++) { next[i] = NULL; } wordCount = 0; } } private int curr; private Node[] nodes; private List allDistinctWords; public final static int NULL = -1; public MyTrie() { nodes = new Node[100000]; nodes[0] = new Node(); curr = 1; } private int getIndex(char c) { return (int)(c - 'a'); } private void depthSearchWord(int x, String currWord) { for(int i=0;i<26;i++) { int p = nodes[x].next[i]; if(p != NULL) { String word = currWord + (char)(i + 'a'); if(nodes[p].wordCount > 0) { allDistinctWords.add(word); } depthSearchWord(p, word); } } } public List getAllDistinctWords() { allDistinctWords = new ArrayList(); depthSearchWord(0, ""); return allDistinctWords; } public int getWordCount(String str) { int len = str.length(); int p = 0; for(int i=0;i 0; } public void insert(String str) { int len = str.length(); int p = 0; for(int i=0;i 

    Ho appena provato la mia implementazione Concurrent TRIE ma non basata su caratteri, è basata su HashCode. Ancora Possiamo usare questo avendo Mappa della Mappa per ogni codice di identificazione CHAR.
    Puoi testarlo usando il codice @ https://github.com/skanagavelu/TrieHashMap/blob/master/src/TrieMapPerformanceTest.java https://github.com/skanagavelu/TrieHashMap/blob/master/src/TrieMapValidationTest.java

     import java.util.concurrent.atomic.AtomicReferenceArray; public class TrieMap { public static int SIZEOFEDGE = 4; public static int OSIZE = 5000; } abstract class Node { public Node getLink(String key, int hash, int level){ throw new UnsupportedOperationException(); } public Node createLink(int hash, int level, String key, String val) { throw new UnsupportedOperationException(); } public Node removeLink(String key, int hash, int level){ throw new UnsupportedOperationException(); } } class Vertex extends Node { String key; volatile String val; volatile Vertex next; public Vertex(String key, String val) { this.key = key; this.val = val; } @Override public boolean equals(Object obj) { Vertex v = (Vertex) obj; return this.key.equals(v.key); } @Override public int hashCode() { return key.hashCode(); } @Override public String toString() { return key +"@"+key.hashCode(); } } class Edge extends Node { volatile AtomicReferenceArray array; //This is needed to ensure array elements are volatile public Edge(int size) { array = new AtomicReferenceArray(8); } @Override public Node getLink(String key, int hash, int level){ int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Node returnVal = array.get(index); for(;;) { if(returnVal == null) { return null; } else if((returnVal instanceof Vertex)) { Vertex node = (Vertex) returnVal; for(;node != null; node = node.next) { if(node.key.equals(key)) { return node; } } return null; } else { //instanceof Edge level = level + 1; index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Edge e = (Edge) returnVal; returnVal = e.array.get(index); } } } @Override public Node createLink(int hash, int level, String key, String val) { //Remove size for(;;) { //Repeat the work on the current node, since some other thread modified this node int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Node nodeAtIndex = array.get(index); if ( nodeAtIndex == null) { Vertex newV = new Vertex(key, val); boolean result = array.compareAndSet(index, null, newV); if(result == Boolean.TRUE) { return newV; } //continue; since new node is inserted by other thread, hence repeat it. } else if(nodeAtIndex instanceof Vertex) { Vertex vrtexAtIndex = (Vertex) nodeAtIndex; int newIndex = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, vrtexAtIndex.hashCode(), level+1); int newIndex1 = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level+1); Edge edge = new Edge(Base10ToBaseX.Base.BASE8.getLevelZeroMask()+1); if(newIndex != newIndex1) { Vertex newV = new Vertex(key, val); edge.array.set(newIndex, vrtexAtIndex); edge.array.set(newIndex1, newV); boolean result = array.compareAndSet(index, vrtexAtIndex, edge); //REPLACE vertex to edge if(result == Boolean.TRUE) { return newV; } //continue; since vrtexAtIndex may be removed or changed to Edge already. } else if(vrtexAtIndex.key.hashCode() == hash) {//vrtex.hash == hash) { HERE newIndex == newIndex1 synchronized (vrtexAtIndex) { boolean result = array.compareAndSet(index, vrtexAtIndex, vrtexAtIndex); //Double check this vertex is not removed. if(result == Boolean.TRUE) { Vertex prevV = vrtexAtIndex; for(;vrtexAtIndex != null; vrtexAtIndex = vrtexAtIndex.next) { prevV = vrtexAtIndex; // prevV is used to handle when vrtexAtIndex reached NULL if(vrtexAtIndex.key.equals(key)){ vrtexAtIndex.val = val; return vrtexAtIndex; } } Vertex newV = new Vertex(key, val); prevV.next = newV; // Within SYNCHRONIZATION since prevV.next may be added with some other. return newV; } //Continue; vrtexAtIndex got changed } } else { //HERE newIndex == newIndex1 BUT vrtex.hash != hash edge.array.set(newIndex, vrtexAtIndex); boolean result = array.compareAndSet(index, vrtexAtIndex, edge); //REPLACE vertex to edge if(result == Boolean.TRUE) { return edge.createLink(hash, (level + 1), key, val); } } } else { //instanceof Edge return nodeAtIndex.createLink(hash, (level + 1), key, val); } } } @Override public Node removeLink(String key, int hash, int level){ for(;;) { int index = Base10ToBaseX.getBaseXValueOnAtLevel(Base10ToBaseX.Base.BASE8, hash, level); Node returnVal = array.get(index); if(returnVal == null) { return null; } else if((returnVal instanceof Vertex)) { synchronized (returnVal) { Vertex node = (Vertex) returnVal; if(node.next == null) { if(node.key.equals(key)) { boolean result = array.compareAndSet(index, node, null); if(result == Boolean.TRUE) { return node; } continue; //Vertex may be changed to Edge } return null; //Nothing found; This is not the same vertex we are looking for. Here hashcode is same but key is different. } else { if(node.key.equals(key)) { //Removing the first node in the link boolean result = array.compareAndSet(index, node, node.next); if(result == Boolean.TRUE) { return node; } continue; //Vertex(node) may be changed to Edge, so try again. } Vertex prevV = node; // prevV is used to handle when vrtexAtIndex is found and to be removed from its previous node = node.next; for(;node != null; prevV = node, node = node.next) { if(node.key.equals(key)) { prevV.next = node.next; //Removing other than first node in the link return node; } } return null; //Nothing found in the linked list. } } } else { //instanceof Edge return returnVal.removeLink(key, hash, (level + 1)); } } } } class Base10ToBaseX { public static enum Base { /** * Integer is represented in 32 bit in 32 bit machine. * There we can split this integer no of bits into multiples of 1,2,4,8,16 bits */ BASE2(1,1,32), BASE4(3,2,16), BASE8(7,3,11)/* OCTAL*/, /*BASE10(3,2),*/ BASE16(15, 4, 8){ public String getFormattedValue(int val){ switch(val) { case 10: return "A"; case 11: return "B"; case 12: return "C"; case 13: return "D"; case 14: return "E"; case 15: return "F"; default: return "" + val; } } }, /*BASE32(31,5,1),*/ BASE256(255, 8, 4), /*BASE512(511,9),*/ Base65536(65535, 16, 2); private int LEVEL_0_MASK; private int LEVEL_1_ROTATION; private int MAX_ROTATION; Base(int levelZeroMask, int levelOneRotation, int maxPossibleRotation) { this.LEVEL_0_MASK = levelZeroMask; this.LEVEL_1_ROTATION = levelOneRotation; this.MAX_ROTATION = maxPossibleRotation; } int getLevelZeroMask(){ return LEVEL_0_MASK; } int getLevelOneRotation(){ return LEVEL_1_ROTATION; } int getMaxRotation(){ return MAX_ROTATION; } String getFormattedValue(int val){ return "" + val; } } public static int getBaseXValueOnAtLevel(Base base, int on, int level) { if(level > base.getMaxRotation() || level < 1) { return 0; //INVALID Input } int rotation = base.getLevelOneRotation(); int mask = base.getLevelZeroMask(); if(level > 1) { rotation = (level-1) * rotation; mask = mask << rotation; } else { rotation = 0; } return (on & mask) >>> rotation; } } 

    Puoi provare la libreria Completely Java, con un’implementazione PatriciaTrie . L’API è piccola e facile da avviare ed è disponibile nel repository centrale di Maven .