案例不敏感的三元搜索树
我一直在使用三元搜索树 ，作为实现自动完成下拉combobox的数据结构。 这意味着，当用户键入“fo”时，将显示下拉combobox
foo食品足球
问题是，我目前使用的三元搜索树区分大小写。 我的实施如下。 它已被现实世界用于大约1 ++年。 因此，我认为它非常可靠。
我的三元搜索树代码
但是，我正在寻找一个不区分大小写的三元搜索树，这意味着，当我键入“fo”时，下拉combobox将显示给我
食物fooTBall
以下是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 node = getNode(key); if(node==null) return null; return node.data; } 使用示例如下。 TSTSearchEngine使用TernarySearchTree作为核心骨干。
三元搜索树的示例用法
// There is stock named microsoft and MICROChip inside stocks ArrayList. TSTSearchEngine engine = TSTSearchEngine(stocks); // I wish it would return microsoft and MICROCHIP. Currently, it just return microsoft. List results = engine.searchAll("micro");
使我当前的三元搜索树难以支持不区分大小写搜索的关键因素之一是，我的基础数据结构是一对一映射。 请查看以下测试代码：
public void testPut() { System.out.println("put"); Name name0 = new Name("abc"); Name name1 = new Name("abc"); TernarySearchTree instance = new TernarySearchTree (); 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 engine = TSTSearchEngine (); engine.put(name0); // name0 is new Name("Abc"); engine.put(name1); // name0 is new Name("aBc");
（1）name0.toString（）将转换为UPPER-CASE（“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。
该解决方案有效。 示例代码可以参考新TSTSearchEngine的示例代码
但是，这可能不是一个有效的解决方案，因为它需要两次搜索。 我发现在Case Insensitive三元搜索树的 C ++ C ++实现中有一个实现。 因此，C ++代码有可能移植到Java。
我之前没有使用过TST，但是在存储和查找过程中，这不是简单的下限或大写你的密钥吗？ 从您的代码片段看起来应该可行。
我已经实现了一个三元搜索树，你可以查看http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html。在不区分大小写的情况下，要么将小图和大写映射到一个hex/十进制值或获取前缀时，检查值。