Быстрый Строковый Поиск, как StartWith () не равно ()

Question

У меня есть упорядоченный список (словарь - 100 тыс. Слов) и много слов для поиска в этом списке часто.Так что производительность - это проблема.Я знаю, что HashSet.contains (theWord) или Collections.binarySearch (sortedList, theWord) работают очень быстро.Но я на самом деле не ищу всего слова.

То, что я хочу, скажем, поиск «se» и получение всех слов начинается с «se».Итак, есть ли готовое решение в Java или в каких-либо библиотеках?

Лучший пример: в отсортированном списке быстрое решение для следующей операции

List.subList (String beginIndex, String endIndex) // возвращает интервал

myWordList.subList («ab», «bc»);

Примечание. Это очень похожий вопрос, но принятый ответ не удовлетворяет. Переопределение метода содержит HashSet

Answer 1

Здесь вы ищете структуру данных, обычно называемую «три»:

http://en.wikipedia.org/wiki/Trie

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

Answer 2

Нет большой необходимости в новых структурах: проблему можно решить с помощью бинарного поиска в вашем списке. В частности, вы можете изменить двоичный поиск, чтобы он возвращал первый соответствующий элемент (первый элемент с указанным префиксом).

List.subList (String beginIndex, String endIndex) // возвращает интервал
Я могу быть глупым, но какой индекс имеет строковый тип? Вы можете уточнить эту часть?

Answer 3

Структура Trie очень хорошо подходит для словарей и поиска слов с общими префиксами. В Google Collections / Guava есть вклад реализации Trie .

Answer 4

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

Чтобы получить первый, запустите бинарный поиск с исходной строкой поиска ("se"), сравнивая ее с текущейположение в каждой итерации.Остановитесь, когда слово в текущей позиции будет больше строки поиска, но текущее 1-е слово будет ниже.

Чтобы получить последний индекс, запустите другой двоичный поиск по поисковому запросу + "z" ("sez "), но теперь останавливаются только тогда, когда слово в текущем индексе меньше, чем" sez ", а current + 1 больше.

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

Этот метод основан на двух предположениях:

• Сравнение строк показывает, что «b» больше, чем «az»
• «z» - самое высокое значение символа в списке слов

Этот алгоритм реализован в манипуляциях с данными JavaScriptбиблиотека (jOrder.net).