java – 在排序文件中使用二进制搜索的超快速自动完成(300000行)

发布时间：2020-12-15 02:02:46 所属栏目：Java 来源：网络整理

导读：在我的 Android应用中,我想要一个带自动完成功能的输入字段.项目数量约为300000.最佳解决方案似乎是将项目放入文件(在SD卡上),每行一个项目,每行将具有相同的字符数,以便我可以寻找特定的行号.如果用户在文本字段中输入内容,我将二进制搜索(通过RandomAccess

在我的 Android应用中,我想要一个带自动完成功能的输入字段.项目数量约为300000.最佳解决方案似乎是将项目放入文件(在SD卡上),每行一个项目,每行将具有相同的字符数,以便我可以寻找特定的行号.如果用户在文本字段中输入内容,我将二进制搜索(通过RandomAccessFile)文件并显示建议.

我希望自动完成能够超快(理想情况下不到100毫秒,但我想这是不可能的),我可以做什么优化？

更新1：
我将使用空格将用户输入转换为小写英文字符(a-z).因此’A / b’将转换为’a b’,然后进行搜索.

Uodate 2：
我现在意识到我需要额外的东西 – 搜索单词起始子串.

解决方法

你所寻找的东西叫做TRIE

http://forums.sun.com/thread.jspa?threadID=5295936

在计算机科学中,trie或前缀树是有序树数据结构,用于存储关键数组,其中键通常是字符串.与二叉搜索树不同,树中没有节点存储与该节点关联的密钥;相反,它在树中的位置显示了与之关联的键.节点的所有后代都具有与该节点关联的字符串的公共前缀,并且根与空字符串相关联.值通常不与每个节点相关联,只与叶子和一些与感兴趣的键对应的内部节点相关联.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!