如何在Java中创建简单的前缀索引？ [英] How to create a simple prefix index in Java?
问题描述
我有大量网址，我想实现自动完成功能。我不喜欢天真方法的复杂性，因为它与设置大小呈线性关系：
I have big set of urls and I want to implement an autocompletion. I don't like the complexity of the naive approach as it is linear with the set size:
for(String url: urls) if(url.startsWith(input) {doSomething();}
现在我知道了散列集，函数contains（）在O（1）中工作，但没有containsPrefix（）。有没有像Lucene这样的大型库或自己编写的简单方法？我没有问题这样做但是对于这样一个简单的问题似乎有点过头了所以我想知道是否有一个现有的简单解决方案： - ）
Now I know that in a Hash Set, the function "contains()" works in "O(1)" but there is no "containsPrefix()". Is there a simple way without using a big library like Lucene or coding it myself? I would have no problem doing it but it seems overkill for such a simple problem so I want to know if there is an existing simple solution :-)
从我的计算机科学课我记得一棵树它由字符串片段组成，但我忘了它是如何调用的。它的工作原理如下：
From my computer science classes I remember a tree which consists of string fragments but I forget how it was called. It worked like this:
[car, care, carrot,carrotville]->
car
|
-/
-e
-rrot
|
----ville
PS：如何调用返回所有字符串的方法一个字符串是前缀？就像a是b的前缀，b是什么？
P.S.: How do I call the methods that returns all strings that a string is prefix of? Like if a is prefix of b, what is b to a?
推荐答案
如果你需要有效地找到字符串的前缀，请使用 Trie ，一种专为此目的而设计的数据结构：
If you need to efficiently find prefixes of strings, use a Trie, a data structure designed precisely for that purpose:
trie或前缀树是一种有序树数据结构，用于存储关键数组，其中键通常是字符串。与二叉搜索树不同，树中没有节点存储与该节点关联的密钥;相反，它在树中的位置定义了与之关联的键。节点的所有后代都具有与该节点关联的字符串的公共前缀，并且根与空字符串相关联
A trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string
这篇关于如何在Java中创建简单的前缀索引？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
