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

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

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

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

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

[car, care, carrot,carrotville]->

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

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

 Android Killer27 мар. 2012 г., 12:31
что ты хочешь делать ? автоматически добавлять текст в начале каждой строки?
 Konrad Höffner27 мар. 2012 г., 12:47
Я хочу знать, для каких строк моя строка является префиксом, поэтому я могу дать их в качестве предложений по автозаполнению.

Ответы на вопрос(4)

ь префиксы:

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();

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

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

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

 mdakin27 мар. 2012 г., 12:52
Np, компактная версия использует примерно на 50% меньше узлов (по крайней мере, для турецких слов в словаре). Это тестовый код, так что вы можете увидеть его в действии, надеюсь, ошибок нет :)code.google.com/p/triebag/source/browse/trunk/test/triebag/...
 Konrad Höffner27 мар. 2012 г., 12:49
Это здорово! Я не против, если это один узел на персонажа, но я оставлю вопрос открытым на тот случай, если у кого-то будет один с несколькими.
 Konrad Höffner27 мар. 2012 г., 13:43
Я опробовал ваш SimpleTrie, но он мне не подходит. Сначала конструктор не был общедоступным, и после того, как я его изменил, следующий тест ничего не дал:SimpleTrie<String> trie = new SimpleTrie<>(); trie.add("x","x"); trie.add("xy","xy"); Iterator it = trie.getItemsWithPrefix("x"); while(it.hasNext()) System.out.println(it.next());
Решение Вопроса

Trieструктура данных, разработанная специально для этой цели:

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

Две ссылки собразец реализации.

 Konrad Höffner27 мар. 2012 г., 13:49
Отлично! Я использовал один изforums.oracle.com/forums/thread.jspa?messageID=8787521 и это сработало с первой попытки!

Ваш ответ на вопрос