鉴于单词的列表 - 这将是在Java字完成一个好的算法? 权衡:速度/效率/内存占用(Given

2019-09-22 14:51发布

我探索硬件/软件需求(最终目标是移动Java应用程序),一个潜在的免费/付费应用程序。

该应用程序将使用这个简单的目标开始:给定的数据库中的相关单词的列表,以便能够做一个字符串输入字完成。

换句话说,我已经知道了数据库的内容 - 但该算法的内存占用/速度/搜索效率将决定支持的数据量。

我已经开始使用基于后缀树搜索的开始,但我想知道如果任何人有这个简单的方法的速度/内存的大小权衡体验与在会议正在谈论的更复杂的。

说实话,最初的应用只有在上下文中大概不到500字,所以可能没有关系,但最终的应用程序可能会扩大到几万或几十万的记录 - 从而左右的速度与内存占用的问题。

我想我可以用一些简单的开始,后来切换,但我希望能够更早了解权衡!

Answer 1:

字补全建议,要找到所有以给定前缀开头的单词。

尝试 ,如果您添加或删除元素有利于这一点,特别好-其他节点并不需要被重新分配。

如果字典是相当静态的,检索是重要的,考虑一个简单得多的数据结构:把你的话在一个有序的载体! 你可以做的二进制搜索来发现候选人开始用正确的前缀,以及线性搜索的每侧发现所有其他候选人。



文章来源: Given a list of words - what would be a good algorithm for word completion in java? Tradeoffs: Speed/efficiency/memory footprint