Существуют ли более эффективные способы реализации поиска по мере ввода в Java с довольно небольшим набором данных?

Question

У меня есть около 2500 коротких фраз в файле. Я хочу быть в состоянии найти фразы, поскольку я печатаю возможные их подстроки. Мое приложение имеет текстовое поле и список фраз. Текстовое поле изначально пустое, а список содержит все 2500 фраз, поскольку пустая строка является подстрокой для всех из них. Когда я набираю текстовое поле, список обновляется, так что он всегда содержит только фразы, которые содержат значение текстового поля в качестве подстроки.

На данный момент у меня есть одно из мультимапов Google, а именно:

LinkedHashMultimap<String, String>

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

Есть ли способ, которым я мог бы сделать это с другой структурой данных или стратегией, которая была бы быстрее загружаться и занимать меньше места (возможно, за счет скорости поиска)?

Answer 1

Вы захотите изучить использование структуры данных Trie .

Answer 2

Если ваш список содержит только 2500 элементов, простой цикл и проверка содержит () для всех из них должны быть достаточно быстрыми.

Если он становится больше и / или слишком медленным, вы можете применить несколько простых оптимизаций:

• Не ищите сразу, когда пользователь печатает каждый символ, но вводите некоторую задержку. Поэтому, если он набирает «foobar» очень быстро, вы ищете только «foobar», а не сначала «f», затем «fo», а затем «foo», ...
• Повторно используйте ваши предыдущие результаты: если пользователь сначала вводит «foo», а затем расширяет его до «foobar», не ищите во всем исходном списке снова, а ищите в результатах «foo» (потому что все, что содержит "foobar" должен содержать "foo").

По моему опыту, эти базовые оптимизации уже достаточно далеко продвинули вас.

Теперь, если список станет настолько большим, что даже это будет слишком медленно, потребуются некоторые "более умные" оптимизации, как предложено в других ответах здесь (попытки, деревья суффиксов, ...).

Answer 3

Попробуйте просто перебрать весь список и вызвать contains() - делать это 2500 раз, вероятно, совершенно незаметно.

Answer 4

Вам определенно нужно Дерево суффиксов .. ( wiki )

(я думаю, что эта реализация может быть в порядке: ссылка )

EDIT:

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

Вам разрешено это делать? В противном случае лучшим способом является создание автоматов для каждой фразы или использование аналогичных алгоритмов (например, алгоритм поиска строки Карпа-Рабина ).

Answer 5

У Wouter Coekaerts хороший подход, но я бы пошел немного дальше.

1. Не вызывать ничего, когда текстовое поле содержит один символ. Результаты не будут полезны. Вы можете обнаружить, что это верно и для двух символов.
2. Предварительный подсчет результатов для двух символов. Когда есть два символа, вызовите предварительно вычисленный список.
3. Когда добавляется третий символ, выполните поиск «содержит» в списке, который вы в данный момент отображаете (все, что не содержит c1c2, не может содержать c1c2c3). К настоящему времени список должен быть достаточно маленьким, чтобы «содержать» имело совершенно адекватную производительность.
4. Аналогично для четырех символов и т. Д.
5. Как сказано выше, перед началом поиска вставьте небольшую задержку. Или еще лучше организовать поиск, который будет убит, если другой символ будет напечатан до его завершения.