java - 修改Java中的Tries代码

Question

我正在使用 Tries 数据结构根据号码前缀确定电话号码属于哪个国家/地区。

我正在使用 Vladimir Kroz 创建的 Tries 实现，效果非常好:here

这就是我填充 Tries map 的方式:

private static Trie<Country> trie = new Trie<>();
trie.put("7", new Country(countryID, country));
trie.put("794", new Country(countryID, country));

如您所见，Tries 将电话号码前缀作为键，将国家/地区对象作为值。

这就是我执行搜索的方式:

Country country = trie.get("79519637944");
String CountryName = country.getName();

如您所见，我使用电话号码作为关键字。现在，Tries 正在尝试查找该号码的匹配前缀。尝试将从第一个数字开始尽可能深地爬行。如果它在树中找不到任何匹配的数字，那么它将返回该特定前缀的值。

它工作得很好，但需要一些调整。

假设我有前缀 7 和前缀 746。

现在，当我尝试查找电话号码 74568706987069 时，Tries 将返回 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 + "]";
    }

}
}

感谢任何帮助!

Answer 1

我找到了解决方案。修改后的代码为:

package tiesImpl;

import java.util.HashMap;
import java.util.Iterator;
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
 * https://vkroz.wordpress.com/2012/03/23/prefix-table-trie-implementation-in-java/
 */
public class Trie<V> {

Entry<V> entry;
char key;
Map<Character, Trie<V>> children;

public Trie() {
    this.children = new HashMap<>(10);
    entry = new Entry<>();
}

/**
 * non-public, used by _put()
 */
Trie(char key) {
    this.children = new HashMap<>(10);
    this.key = key;
    entry = new Entry<>();
}

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<>(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. if key is "37251656565" and prefix table has node "372" then
 * this call will return the value of "372"
 *
 * @param key a string which starts with prefix to be searched in the table
 * (e.g. phone number)
 * @return an Object associated 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
 *
 * @param key
 * @return
 */
public boolean hasPrefix(String key) {
    return this.get(key) != null;
}

V _get(StringBuffer key, int level) {
    if (key.length() > 0) {
        Trie<V> t = children.get(key.charAt(0));
        if (t != null) {
            //FYI: modified code to return deepest with value instead of returning null if prefix doesn't have corresponding value.
            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
//For debugging
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)).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 + "]";
    }

}
}

希望对其他人也有帮助!干杯!