Как создать простой индекс префикса в Java? - PullRequest
Новая
       11

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

5 голосов
/ 27 марта 2012

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

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

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

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

[car, care, carrot,carrotville]->

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

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

Ответы [ 4 ]

2 голосов
/ 27 марта 2012

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

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

Две ссылки с примером реализаций .

1 голос
/ 19 июня 2013

Отличным альтернативным алгоритмом является троичное дерево поиска (более эффективное использование памяти) https://github.com/varunpant/TernaryTree/tree/master/TernaryTree

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

1 голос
/ 27 марта 2012

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

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

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

0 голосов
/ 09 июля 2014

Реализация 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();

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

...