不区分大小写的三元搜索树

我一直在使用三元搜索树 http://en.wikipedia.org/wiki/Ternary_search_tree有一段时间，作为数据结构来实现一个自动完成下拉组合框。这意味着，当用户输入“fo”时，将显示下拉组合框

富 食物 足球

问题是，我当前使用的三元搜索树是区分大小写的。我的实现如下。它已被现实世界使用了大约 1++ 年。因此，我认为这是相当可靠的。

我的三元搜索树代码 http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TernarySearchTree.java?view=markup

但是，我正在寻找一个不区分大小写的三元搜索树，这意味着，当我输入“fo”时，下拉组合框将显示

FOO 食物 足球

以下是 TST 的一些关键接口，我希望新的不区分大小写的 TST 也能有类似的接口。

    /** 
 * Stores value in the TernarySearchTree. The value may be retrieved using key.
 * @param key A string that indexes the object to be stored.
 * @param value The object to be stored in the tree.
 */    
public void put(String key, E value) {
    getOrCreateNode(key).data = value;
}

/**
 * Retrieve the object indexed by key.
 * @param key A String index.
 * @return Object The object retrieved from the TernarySearchTree.
 */
public E get(String key) {
    TSTNode<E> node = getNode(key);
    if(node==null) return null;
    return node.data;
}

使用示例如下。 TSTSearchEngine 使用 TernarySearchTree 作为核心骨干。

// There is stock named microsoft and MICROChip inside stocks ArrayList.
TSTSearchEngine<Stock> engine = TSTSearchEngine<Stock>(stocks);
// I wish it would return microsoft and MICROCHIP. Currently, it just return microsoft.
List<Stock> results = engine.searchAll("micro"); 

使我当前的三元搜索树难以支持不区分大小写的搜索的关键因素之一是，我的底层数据结构是一对一映射。请看下面的测试代码：

public void testPut() {
    System.out.println("put");
    Name name0 = new Name("abc");
    Name name1 = new Name("abc");
    TernarySearchTree<Name> instance = new TernarySearchTree<Name>();
    instance.put(name0.toString(), name0);
    instance.put(name1.toString(), name1);
    assertEquals(2, instance.matchPrefix("a").size()); // fail here. Result is 1
}

我当前的短期解决方案是，我使用 TSTSearchEngine 来包装整个 TernarySearchTree。 TSTSearchEngine 由以下部分组成

(1) 一个三元搜索树，为映射提供大写键。

(2) String-To-ArrayList 映射。

这是我执行时发生的情况：

TSTSearchEngine<Name> engine = TSTSearchEngine<Name>();
engine.put(name0); // name0 is new Name("Abc");
engine.put(name1); // name0 is new Name("aBc");

(1) name0.toString() 将转换为大写（“ABC”）。它将被插入到 TernarySearchTree 中。 “ABC”将是 TernarySearchTree 的键和值。

(2) “ABC”将作为map的键，将name0插入到数组列表中。

(3) name1.toString() 将转换为大写（“ABC”）。它将被插入到 TernarySearchTree 中。 S1 将是 TernarySearchTree 的键和值。

(4) “ABC”将作为map的键，将name1插入到数组列表中。

当我尝试

engine.searchAll("a");

(1) TernarySearchTree 将返回“ABC”。

(2)“ABC”将用作访问地图的密钥。 Map 将返回一个数组列表，其中包含 name0 和 name1。

这个解决方案有效。示例代码可以参考新 TSTSearchEngine 的示例代码 http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TSTSearchEngine.java?view=markup

然而，这可能不是一个有效的解决方案，因为它需要两次搜索。我发现有一个C++实现不区分大小写的三元搜索树的C++实现 http://www.abc.se/~re/code/tst/tst_docs/tst_usage.html#usage_custom_comp。因此，C++ 代码有机会移植到 Java。