1

有趣的算法我想得到社区的意见。如果数组中存在以某些字符开头的字符串，我希望循环遍历布尔结果的排序。 ArrayList<String>

前任。大批{"he", "help", "helpless", hope"}

search character = h 
Result: true
search character = he
Result: true
search character = hea
Result: false

现在我的第一印象是我应该将二进制搜索与正则表达式结合起来，但如果我离题了，请告诉我。虽然 trie 将是最好的实现，但我需要一个最小化堆内存（在 android 上开发）的解决方案，因为这个数组实际上将包含 ~10,000-20,000 个条目（字）。

我有一个包含约 200,000 个单词的数据库。我正在获取一个以集合字母开头的子集（在我的示例中为 h），其中将包含约 20,000 个条目并将它们插入到数组中。然后，我使用这个子集执行 ~100-1,000 次查找/包含。我的方法的想法是增加性能时间（而不是数据库查询），同时尽量减少对内存的命中（数组而不是 trie 树）

也许DAWG会优化查找，但是我不确定这个结构的大小要求是否会比 ArrayList 大得多？

4

2 回答 2

2

If you really want to avoid a trie, this should fit your needs:

NavigableSet<String> tree = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
tree.addAll(Arrays.asList("he", "help", "helpless", "hope"));
String[] queries = {"h", "he", "hea"};
for (String query : queries) {
    String higher = tree.ceiling(query);
    System.out.println(query + ": " + higher.startsWith(query));
}

prints

h: true
he: true
hea: false
于 2013-07-15T18:55:40.250 回答
0

您应该考虑将http://en.wikipedia.org/wiki/Skip_list作为一个选项。许多 java 实现都是现成的

于 2013-07-15T22:34:59.650 回答