Java: Как найти в массиве часть строки

Question

У меня есть arraylist<string> слов. Я сортирую это используя Collections.sort(wordsList);

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

Как мне искать в этом массиве префикс строки, скажем, пользователь вводит слово «mount», а массив содержит слово «гора», как мне искать этот массив и возвращать похожие значения.

Вот мой код:

public List<Interface> returnSuggestedList(String prefix) {

        String tempPrefix = prefix;

        suggestedPhrases.clear();
        //suggestedPhrases = new ArrayList<Interface>();
        //Vector<String> list = new Vector<String>();

        //List<Interface> interfaceList = new ArrayList<Interface>();
        Collections.sort(wordsList);
        System.out.println("Sorted Vector contains : " + wordsList);
        int i = 0;
        while( i != wordsList.size() ) {




            int index = Collections.binarySearch(wordsList,prefix);

            String tempArrayString = wordsList.get(index).toString();

            if( tempArrayString.toLowerCase().startsWith(prefix.toLowerCase()) ) {

                ItemInterface itemInt = new Item(tempArrayString);
                suggestedPhrases.add(itemInt);
                 System.out.println(suggestedPhrases.get(i).toString());
                 System.out.println("Element found at : " + index);
            }

            i++;
        }



        return suggestedPhrases;

    }

Заранее спасибо.

Answer 1

Для этой задачи есть лучшие структуры данных, чем отсортированный массив строк.Например, вы можете посмотреть DAWG (Направленный ациклический граф слов) .

Answer 2

Самым базовым подходом будет

List<String> result = new ArrayList<String>();
for(String str: words){
  if(str.contains(keyword){
    result.add(str);
  }
}

. Вы можете улучшить эту версию, если вас интересует только startWith вместо contains, тогда вы можете распределять слова в HashMap, и у вас будет суженопоиск

Answer 3

Также см. Структуру данных trie . Этот вопрос содержит полезную информацию. Я должен подумать, что getPrefixedBy() будет более эффективным, чем все, что вы можете быстро бросить вручную.

Конечно, это будет работать только для поиска по префиксу. Содержит поиск совсем другого зверя.

Answer 4

Как @Jiri говорит, что вы можете использовать DAWG, но если вы не хотите заходить так далеко, вы можете сделать несколько простых и полезных вещей.

Использовать сортировку

• Если вы хотите отсортировать массив слов, сделайте это ранее. не сортируйте это каждый раз
• После сортировки вы можете найти первое и последнее слово в списке, которые совпадают. Используйте list.subList (from, to) для возврата подсписка. Немного более оптимальным является добавление каждого из них.

Использовать предварительно отсортированную структуру

• Используйте TreeSet<String> для хранения строк (они будут отсортированы внутри).
• Затем используйте treeSet.subSet(from, true, to, false);

Где from - префикс, а to - «префикс плюс один символ». Например, если вы ищете abc, to должно быть abd. Если вы все равно не хотите выполнять преобразование символов, вы можете запросить treeSet.headSet(from) и повторять его, пока не прекратятся префиксы.

Это особенно полезно, если вы читаете больше, чем пишете. Возможно, заказ струн стоит немного дороже, но после заказа вы можете найти их очень быстро (O(log n)).

Сравнение без учета регистра

Вы можете предоставить Comparator<String> для набора деревьев, чтобы указать, как он должен упорядочить строки. Вы можете реализовать его, или, может быть, есть встроенный компаратор без учета регистра.

В любом случае его код должен быть:

int compare(String a, String b) {
   return a.toLowerCase().compareTo(b.toLowerCase());
}

Answer 5

Если wordList фиксировано (не меняется от одного вызова метода к другому), вы должны отсортировать его где-нибудь еще, потому что сортировка стоит дорого, и хранить его в нижнем регистре.

В остальной частиметод вы бы сделали что-то вроде:

List<String> selected = new ArrayList<String>();

for(String w:wordList){
    if(w.startsWith(prefix.toLower())) // or .contains(), depending on 
        selected.add(w);     // what you want exactly 
}

return selected;

Answer 6

Вот аналогичный пример:

-> http://samuelsjoberg.com/archive/2009/10/autocompletion-in-swing