Как создать простой префиксный индекс в Java?

Question

У меня есть большой набор URL-адресов, и я хочу реализовать автозаполнение. Мне не нравится сложность наивный подход, как она линейна с заданным размером:

for(String url: urls) if(url.startsWith(input) {doSomething();} 

Теперь я знаю, что в хэш-набор, функция «содержит()» работает в «O (1) «но нет« containsPrefix() ». Есть ли простой способ без использования большой библиотеки, такой как Lucene, или ее кодирования? У меня не было бы проблем с этим, но это кажется излишним для такой простой проблемы, поэтому я хочу знать, существует ли существующее простое решение :-)

Из моих классов компьютерных наук я помню дерево, состоящее из фрагментов строки, но Я забываю, как это называлось. Он работал следующим образом:

[car, care, carrot,carrotville]-> 

car 
| 
-/ 
-e 
-rrot 
    | 
    ----ville 

P.S .: Как я могу назвать методы, возвращающие все строки, для которых является префиксом строки? Например, если a является префиксом b, что такое b для a?

Answer 1

Если вам нужно эффективно находить префиксы строк, используйте Trie, структуру данных, предназначенную именно для этой цели:

A синтаксического дерева, или префикс дерева, представляет собой упорядоченную структуру данных дерева, которое используется для хранить ассоциативный массив, где ключи обычно являются строками. В отличие от дерева двоичного поиска ни один узел в дереве не сохраняет ключ, связанный с этим узлом; вместо этого его позиция в дереве определяет ключ, с которым он связан. Все потомки узла имеют общий префикс строки, связанную с этим узлом, и корень связан с пустой строкой

Две связи с sampleimplementations.

Answer 2

Долгое время назад я поставил простую реализацию TRIE здесь:

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

Однако это не компактный Trie, поэтому он создает один узел на символ, создавая компактный один немного сложнее.

Answer 3

Отличная альтернатива алго является ternary search tree (меньше памяти) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree

вот Trie в Java http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Answer 4

Regexp java.util.regex.Pattern реализация может эффективно обрабатывать префиксы:

StringBuilder buffer = new StringBuilder(); 
for (String prefix : prefixes) { 
    if (buffer.length() > 0) 
     buffer.append("|"); 
    buffer.append(prefix); 
} 
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")"); 

Вы можете проверить все префиксы:

boolean containsPrefix = prefixPattern.matcher(stringToTest).find(); 

Примечание: для простоты префиксные строки не экранированы. Регулярные символы [,], \, *,?, $, ^, (,), {,} И | должны иметь префикс \.