1
我正在使用嘗試數據結構來根據數字前綴來確定語音號碼屬於哪個國家。在Java中修改嘗試代碼
我使用的弗拉基米爾Kroz創造了嘗試次數的實現，它的作品真的很好：here
這是我如何填充嘗試次數圖：
private static Trie<Country> trie = new Trie<>();
trie.put("7", new Country(countryID, country));
trie.put("794", new Country(countryID, country));
正如你所看到的嘗試次數保存電話號碼前綴鍵和國家對象作爲價值。
這是我如何執行搜索：
Country country = trie.get("79519637944");
String CountryName = country.getName();
正如你可以看到我使用一個電話號碼爲關鍵字。現在嘗試嘗試爲此號碼找到匹配的前綴。嘗試將盡可能從第一個數字開始抓取。如果它在樹中找不到任何匹配的數字，那麼它將返回該特定前綴的值。
它工作得很好，但需要稍微調整一下。
比方說，我有前綴7和前綴746
現在，當我試圖找到電話NR 74568706987069，然後嘗試將返回null，因爲它會爬到樹這樣7-> 4->將嘗試找到5，但它不會返回與前綴74相關的值而不是7.
如何使它記住最後一個前綴的值不爲空。
嘗試次數代碼如下（搜索發生在_GET方法的地方）：
import java.util.HashMap;
import java.util.Map;
/**
* Prefix table based on trie structure. Allows to perform incremental lookup
* and match based on search key prefixes (classic example - determine phone
* area code for given phone number)
*
* @param <V>
* a type of value object to be stored along with prefix (e.g when
* key is a country name, the value could be a name of the country)
*
* @author Vladimir Kroz
*/
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 + "]";
}
}
}
任何幫助表示讚賞！