Java - поиск коллекции строк, содержащих первые несколько символов

Question

У меня есть коллекция строк, которые я хочу найти, используя только первые несколько символов.

Например, рассмотрим список строк: [Том, Томаз, Алиса, Толстой, Джон].Строка [to] приведет к появлению списка [tom, tomaz, tolstoy].

Производительность - это серьезная проблема, и список может быть очень большим.

Каков наилучший способ оптимизировать это?Индексы?Сортировка?Как?

Спасибо!

Answer 1

Trie - это универсальное решение, как уже было предложено, но если вы хотите легкое и относительно быстрое решение без внешних зависимостей, просто поместите всю строку в TreeSet и используйте tailSet(), чтобы найти первый элемент сопоставляя префикс, затем перебирайте набор хвостов, пока не найдете строку, которая не соответствует. (Примечание: это может быть даже первый элемент, если ни одна из ваших строк не соответствует префиксу.)

Если ваш список не превышает пары тысяч строк, этот метод достаточно хорош на практике.

Answer 2

Если вы настаиваете на использовании списка, ваши возможности ограничены. Это просто не подходит для такого рода вещей.

Структура данных, которая делает именно то, что вы пытаетесь сделать, называется Trie (Wikipedia Entry)

Быстрый Google вызывает эту реализацию Java из Университета Дьюка: http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

Answer 3

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

static int MAX_PREFIX = 3;
Map<String, List<String>> map = new HashMap<String, List<String>>();

public void addItem(String item) {
    for (int i = 0; i < MAX_PREFIX && i < item.length(); i++) {
        String prefix = item.substring(0, i);
        List<String> matches = map.get(prefix);
        if (matches == null) {
            matches = new ArrayList<String>();
            map.put(prefix, matches);
        }
        matches.add(item);
    }
}

public List<String> getMatches(String prefix) {
    List<String> matches = map.get(prefix);
    return matches == null ? Collections.<String>emptyList() : matches;
}

Это будет очень быстро, так как это всего лишь один Map поиск, чтобы перейти от вашего префикса String прямо к List<String> ваших желаемых результатов. Если ваш список настолько велик, что не умещается в памяти, вам нужно подумать о выходе из него. Как уже упоминалось, вы можете посмотреть на Lucene для локального индекса. Или базу данных, просто проиндексируйте столбец и выполните запрос LIKE 'prefix%'.

Answer 4

Если предположить, что ваш список достаточно мал для хранения в памяти, я бы использовал trie .

. Это даст вам время поиска, пропорциональное длине вашего префикса.*

Answer 5

Я рекомендую изучить , попытайтесь упорядочить ваши данные, если поиск подобным образом является приоритетным и не вызывает конфликтов с вашими другими требованиями.

Answer 6

Посмотрите на Solr и Lucene. Они выполняют поиск строк по индексу, или вы можете написать свой собственный, как предложили другие.

http://lucene.apache.org/solr/