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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java-不区分大小写的三元搜索树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2811字，纯文字阅读大概需要5分钟。

内容图文

我一直在使用Ternary Search Tree,因为它是实现自动完成下拉组合框的数据结构.这意味着,当用户键入“ fo”时,将显示下拉组合框

富
餐饮
足球

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

My Ternary Search Tree code

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

O
餐饮
足球

这是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作为核心骨干.

Example usage of Ternary Search Tree

// 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)TernarySearchTree,提供要映射的大写键.
(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中.对于TernarySearchTree,“ ABC”既是键又是值.
(2)“ ABC”将用作映射的键??,以将name0插入到数组列表中.
(3)name1.toString()将被转换为大写(“ ABC”).它将插入到TernarySearchTree中. S1将是TernarySearchTree的键和值.
(4)“ ABC”将用作映射的键??,以将name1插入到数组列表中.

当我尝试

engine.searchAll("a");

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

此解决方案有效.示例代码可以参考Sample Code for New TSTSearchEngine

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

内容总结

以上是互联网集市为您收集整理的java-不区分大小写的三元搜索树全部内容，希望文章能够帮你解决java-不区分大小写的三元搜索树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端