3

我一直在使用三元搜索树作为实现自动完成下拉组合框的数据结构。这意味着，当用户键入“fo”时，将显示下拉组合框

foo 食品 足球

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

我的三元搜索树代码

但是，我正在寻找不区分大小写的三元搜索树，这意味着，当我输入“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");
4

3 回答 3

3

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

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() 将被转换为 UPPER-CASE ("ABC")。它将被插入到 TernarySearchTree。S1 将是 TernarySearchTree 的键和值。

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

当我尝试

engine.searchAll("a");

(1) TernarySearchTree 将返回“ABC”。

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

此解决方案有效。示例代码可以参考New TSTSearchEngine 示例代码

但是，这可能不是一个有效的解决方案，因为它需要两次搜索。我发现 C++ C++ Implementation of Case Insensitive Ternary Search Tree中有一个实现。因此，有机会将 C++ 代码移植到 Java。

于 2009-03-09T22:04:13.897 回答
1

我以前没有使用过 TST，但这不是在存储和查找期间都像小写或大写密钥一样简单吗？从您的代码片段看起来应该可以工作。

于 2009-03-06T09:00:52.027 回答
0

我已经实现了一个三元搜索树，你可以看看http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html 至于大小写不敏感，要么你映射 small 和 caps一个十六进制/十进制值或在获取前缀时，检查该值。

于 2010-05-20T14:08:23.340 回答