案例不敏感的三元搜索树

Question

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

FOO 餐饮 足球

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

我的三元搜索树代码

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

FOO 餐饮 足球

以下是TST的一些关键接口，我希望新案例insentive 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"); 

Answer 1

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

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）一个TernarySearchTree，提供UPPER-CASE键进行映射。搜索结果 （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（）将转换为UPPER-CASE（“ABC”）。它将被插入TernarySearchTree。 ＆QUOT; ABC＆QUOT;将是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。 结果

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

然而，这可能不是一个有效的解决方案，因为它需要两次搜索。我发现在C ++中有一个实现案例的C ++实现不敏感的三元搜索树。因此，C ++代码有可能移植到Java。

Answer 2

之前我没有使用过TST，但是在存储和查找期间，这不是简单的下限或大写键吗？从你的代码片段看起来应该可行。

Answer 3

我已经实现了三元搜索树，您可以查看 http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html 在不区分大小写的情况下，要么将small和caps映射到一个十六进制/十进制值，要么在获取前缀时，请检查该值。