Java:让前缀树记住最后一个不为空的值
Java: make prefix tree remember last value that was not null
我有这样的前缀树 (Trie) 代码:
public class Trie<V> {
Entry<V> entry;
char key;
Map<Character, Trie<V>> childrens;
public Trie() {
this.childrens = new HashMap<Character, Trie<V>>(10);
entry = new Entry<V>();
}
/** non-public, used by _put() */
Trie(char key) {
this.childrens = new HashMap<Character, Trie<V>>(10);
this.key = key;
entry = new Entry<V>();
}
public void put(String key, V value) {
_put(new StringBuffer(key), new StringBuffer(""), value);
}
void _put(StringBuffer remainder, StringBuffer prefix, V value) {
if (remainder.length() > 0) {
char keyElement = remainder.charAt(0);
Trie<V> t = null;
try {
t = childrens.get(keyElement);
} catch (IndexOutOfBoundsException e) {
}
if (t == null) {
t = new Trie<V>(keyElement);
childrens.put(keyElement, t);
}
prefix.append(remainder.charAt(0));
t._put(remainder.deleteCharAt(0), prefix, value);
} else {
this.entry.value = value;
this.entry.prefix = prefix.toString();
}
}
/**
* Retrieves element from prefix table matching as a prefix to provided key.
* E.g. is key is "abcde" and prefix table has node "ab" then this call will
* return "ab"
*
* @param key
* a string which starts with prefix to be searched in the table
* (e.g. phone number)
* @return an Object assosiated with matching prefix (i.e if key is a phone
* number it may return a corresponding country name)
*/
public V get(String key) {
return _get(new StringBuffer(key), 0);
}
/**
* Returns true if key has matching prefix in the table
*/
public boolean hasPrefix(String key) {
return ((this.get(key) != null) ? true : false);
}
V _get(StringBuffer key, int level) {
if (key.length() > 0) {
Trie<V> t = childrens.get(key.charAt(0));
if (t != null) {
return t._get(key.deleteCharAt(0), ++level);
} else {
return (level > 0) ? entry.value : null;
}
} else {
return entry.value;
}
}
@Override
public String toString() {
return "Trie [entry=" + entry + ", key=" + key + ", childrens="
+ childrens + "]";
}
static public class Entry<V> {
String prefix;
V value;
public Entry() {
}
public Entry(String p, V v) {
prefix = p;
value = v;
}
public String prefix() {
return prefix;
}
public V value() {
return value;
}
@Override
public String toString() {
return "Entry [prefix=" + prefix + ", value=" + value + "]";
}
}
}
插入是这样的:
private static Trie<String> trie = new Trie<>();
trie.put("7", "Some country");
trie.put("77", "Some other country");
trie.put("745", "Entirely different place");
搜索过程如下:
String result = trie.get("746878788");
System.out.println(result);
此搜索结果为空,因为 74 没有值。
我的问题是: 我如何修改 Trie class 中的 _get 方法,以便它记住最后一个不为 null 的值。所以当它以 74 结束时,它会记住 7 有一些值 "Some country",所以它会 return 而不是 null。
有什么解决办法吗?
感谢任何帮助!
首先,我修改了Trie 的toString() 方法以获得一些更好的调试信息。实现您所要求的唯一重要行是 _get 方法中的这些:
V result = t._get(key.deleteCharAt(0), ++level);
return result == null ? entry.value : result;
如果子条目的值为 null,则 trie 现在更喜欢当前条目的值。
整个代码修改:
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Trie<V> {
Entry<V> entry;
char key;
Map<Character, Trie<V>> children;
public Trie() {
this.children = new HashMap<Character, Trie<V>>(10);
entry = new Entry<V>();
}
/** non-public, used by _put() */
Trie(char key) {
this.children = new HashMap<Character, Trie<V>>(10);
this.key = key;
entry = new Entry<V>();
}
public void put(String key, V value) {
_put(new StringBuffer(key), new StringBuffer(""), value);
}
void _put(StringBuffer remainder, StringBuffer prefix, V value) {
if (remainder.length() > 0) {
char keyElement = remainder.charAt(0);
Trie<V> t = null;
try {
t = children.get(keyElement);
} catch (IndexOutOfBoundsException e) {
}
if (t == null) {
t = new Trie<V>(keyElement);
children.put(keyElement, t);
}
prefix.append(remainder.charAt(0));
t._put(remainder.deleteCharAt(0), prefix, value);
} else {
this.entry.value = value;
this.entry.prefix = prefix.toString();
}
}
/**
* Retrieves element from prefix table matching as a prefix to provided key.
* E.g. is key is "abcde" and prefix table has node "ab" then this call will
* return "ab"
*
* @param key
* a string which starts with prefix to be searched in the table
* (e.g. phone number)
* @return an Object assosiated with matching prefix (i.e if key is a phone
* number it may return a corresponding country name)
*/
public V get(String key) {
return _get(new StringBuffer(key), 0);
}
/**
* Returns true if key has matching prefix in the table
*/
public boolean hasPrefix(String key) {
return ((this.get(key) != null) ? true : false);
}
V _get(StringBuffer key, int level) {
if (key.length() > 0) {
Trie<V> t = children.get(key.charAt(0));
if (t != null) {
V result = t._get(key.deleteCharAt(0), ++level);
return result == null ? entry.value : result;
} else {
return (level > 0) ? entry.value : null;
}
} else {
return entry.value;
}
}
@Override
public String toString() {
Iterator<Character> it = children.keySet().iterator();
StringBuffer childs = new StringBuffer();
while (it.hasNext()) {
Character key = it.next();
childs.append(String.format("\n%s\n",
// adding a tab to the beginning of every line to create a visual tree
String.format("%s: %s", key, children.get(key)).toString().replaceAll("(?m)(^)", "\t")));
}
return String.format("Trie [entry=%s, children=%s]", entry, childs);
}
static public class Entry<V> {
String prefix;
V value;
public Entry() {
}
public Entry(String p, V v) {
prefix = p;
value = v;
}
public String prefix() {
return prefix;
}
public V value() {
return value;
}
@Override
public String toString() {
return "Entry [prefix=" + prefix + ", value=" + value + "]";
}
}
}
我有这样的前缀树 (Trie) 代码:
public class Trie<V> {
Entry<V> entry;
char key;
Map<Character, Trie<V>> childrens;
public Trie() {
this.childrens = new HashMap<Character, Trie<V>>(10);
entry = new Entry<V>();
}
/** non-public, used by _put() */
Trie(char key) {
this.childrens = new HashMap<Character, Trie<V>>(10);
this.key = key;
entry = new Entry<V>();
}
public void put(String key, V value) {
_put(new StringBuffer(key), new StringBuffer(""), value);
}
void _put(StringBuffer remainder, StringBuffer prefix, V value) {
if (remainder.length() > 0) {
char keyElement = remainder.charAt(0);
Trie<V> t = null;
try {
t = childrens.get(keyElement);
} catch (IndexOutOfBoundsException e) {
}
if (t == null) {
t = new Trie<V>(keyElement);
childrens.put(keyElement, t);
}
prefix.append(remainder.charAt(0));
t._put(remainder.deleteCharAt(0), prefix, value);
} else {
this.entry.value = value;
this.entry.prefix = prefix.toString();
}
}
/**
* Retrieves element from prefix table matching as a prefix to provided key.
* E.g. is key is "abcde" and prefix table has node "ab" then this call will
* return "ab"
*
* @param key
* a string which starts with prefix to be searched in the table
* (e.g. phone number)
* @return an Object assosiated with matching prefix (i.e if key is a phone
* number it may return a corresponding country name)
*/
public V get(String key) {
return _get(new StringBuffer(key), 0);
}
/**
* Returns true if key has matching prefix in the table
*/
public boolean hasPrefix(String key) {
return ((this.get(key) != null) ? true : false);
}
V _get(StringBuffer key, int level) {
if (key.length() > 0) {
Trie<V> t = childrens.get(key.charAt(0));
if (t != null) {
return t._get(key.deleteCharAt(0), ++level);
} else {
return (level > 0) ? entry.value : null;
}
} else {
return entry.value;
}
}
@Override
public String toString() {
return "Trie [entry=" + entry + ", key=" + key + ", childrens="
+ childrens + "]";
}
static public class Entry<V> {
String prefix;
V value;
public Entry() {
}
public Entry(String p, V v) {
prefix = p;
value = v;
}
public String prefix() {
return prefix;
}
public V value() {
return value;
}
@Override
public String toString() {
return "Entry [prefix=" + prefix + ", value=" + value + "]";
}
}
}
插入是这样的:
private static Trie<String> trie = new Trie<>();
trie.put("7", "Some country");
trie.put("77", "Some other country");
trie.put("745", "Entirely different place");
搜索过程如下:
String result = trie.get("746878788");
System.out.println(result);
此搜索结果为空,因为 74 没有值。
我的问题是: 我如何修改 Trie class 中的 _get 方法,以便它记住最后一个不为 null 的值。所以当它以 74 结束时,它会记住 7 有一些值 "Some country",所以它会 return 而不是 null。
有什么解决办法吗?
感谢任何帮助!
首先,我修改了Trie 的toString() 方法以获得一些更好的调试信息。实现您所要求的唯一重要行是 _get 方法中的这些:
V result = t._get(key.deleteCharAt(0), ++level);
return result == null ? entry.value : result;
如果子条目的值为 null,则 trie 现在更喜欢当前条目的值。
整个代码修改:
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Trie<V> {
Entry<V> entry;
char key;
Map<Character, Trie<V>> children;
public Trie() {
this.children = new HashMap<Character, Trie<V>>(10);
entry = new Entry<V>();
}
/** non-public, used by _put() */
Trie(char key) {
this.children = new HashMap<Character, Trie<V>>(10);
this.key = key;
entry = new Entry<V>();
}
public void put(String key, V value) {
_put(new StringBuffer(key), new StringBuffer(""), value);
}
void _put(StringBuffer remainder, StringBuffer prefix, V value) {
if (remainder.length() > 0) {
char keyElement = remainder.charAt(0);
Trie<V> t = null;
try {
t = children.get(keyElement);
} catch (IndexOutOfBoundsException e) {
}
if (t == null) {
t = new Trie<V>(keyElement);
children.put(keyElement, t);
}
prefix.append(remainder.charAt(0));
t._put(remainder.deleteCharAt(0), prefix, value);
} else {
this.entry.value = value;
this.entry.prefix = prefix.toString();
}
}
/**
* Retrieves element from prefix table matching as a prefix to provided key.
* E.g. is key is "abcde" and prefix table has node "ab" then this call will
* return "ab"
*
* @param key
* a string which starts with prefix to be searched in the table
* (e.g. phone number)
* @return an Object assosiated with matching prefix (i.e if key is a phone
* number it may return a corresponding country name)
*/
public V get(String key) {
return _get(new StringBuffer(key), 0);
}
/**
* Returns true if key has matching prefix in the table
*/
public boolean hasPrefix(String key) {
return ((this.get(key) != null) ? true : false);
}
V _get(StringBuffer key, int level) {
if (key.length() > 0) {
Trie<V> t = children.get(key.charAt(0));
if (t != null) {
V result = t._get(key.deleteCharAt(0), ++level);
return result == null ? entry.value : result;
} else {
return (level > 0) ? entry.value : null;
}
} else {
return entry.value;
}
}
@Override
public String toString() {
Iterator<Character> it = children.keySet().iterator();
StringBuffer childs = new StringBuffer();
while (it.hasNext()) {
Character key = it.next();
childs.append(String.format("\n%s\n",
// adding a tab to the beginning of every line to create a visual tree
String.format("%s: %s", key, children.get(key)).toString().replaceAll("(?m)(^)", "\t")));
}
return String.format("Trie [entry=%s, children=%s]", entry, childs);
}
static public class Entry<V> {
String prefix;
V value;
public Entry() {
}
public Entry(String p, V v) {
prefix = p;
value = v;
}
public String prefix() {
return prefix;
}
public V value() {
return value;
}
@Override
public String toString() {
return "Entry [prefix=" + prefix + ", value=" + value + "]";
}
}
}