Вы знаете способ быстрой фильтрации списка строк для получения подмножества, содержащего указанную строку? Очевидная реализация состоит в том, чтобы просто перебирать список, проверяя каждую строку, содержит ли она строку поиска. Есть ли способ индексировать список строк, чтобы поиск можно было выполнить быстрее?Быстрая фильтрация коллекции строк подстрокой?
Wikipedia article перечисляет несколько способов индексирования подстрок. У вас есть:
- Suffix tree
- Suffix array
- индекс N-грамм, инвертированный файл для всех N-грамм текста
- Сжатый суффикса массив 1
- FM-index
- LZ-индекс
Не действительно ничего жизнеспособного, нет, если у вас нет дополнительных априорных знаний о ваших данных и/или терминах поиска - например, если вы ищете только совпадения на , начиная с ваших строк, то вы могут сортировать строки и просматривать только те, которые находятся в пределах вашего поискового запроса (или даже хранить их в двоичном дереве, и смотреть только на ветки, которые могут совпадать). Аналогичным образом, если ваши потенциальные условия поиска ограничены, вы можете запустить все возможные поисковые запросы против строки, когда она изначально введена, а затем просто сохранить таблицу, с которой совпадают термины, а какие нет.
Помимо этого, просто итерация через это в основном это.
Это зависит от того, находится ли подстрока в начале строки или может быть где угодно в строке.
Если это где-то, вам в значительной степени нужно перебирать весь список, если ваш список не является настолько большим, и запрос случается достаточно часто, что стоит создать более сложное решение для индексирования.
Если подстрока находится в начале строки, это легко. Сортируйте список, найдите начало/конец с помощью поиска biseciton и возьмите это подмножество.
Да, вы могли бы, например, создать индекс для всех комбинаций символов в строках. Строка типа «привет» будет добавлена в индексы для «he», «el», «ll» и «lo». Для поиска строки «ад» вы получите индекс всех строк, которые существуют во всех индексах «he», «el» и «ll», затем прокрутите те, чтобы проверить фактическое содержимое в строках.
Если вы можете предварительно обработать коллекцию, вы можете делать много разных вещей.
Например, вы можете создать trie, включающий все суффиксы ваших строк, а затем использовать это для очень быстрого согласования.
Если вы собираетесь повторно искать один и тот же текст, то, вероятно, стоит suffix tree. При тщательном применении вы можете добиться линейной обработки времени для большинства проблем с строкой. Если нет, то на практике вы не сможете сделать намного лучше, чем Rabin-Karp, который основан на хэшировании и является линейным в ожидаемое время.
Существует множество свободно доступных реализаций суффиксных деревьев. См. Например, это C implementation, или для Java, проверьте структуру Biojava.
Конечно, это зависит от того, насколько эффективно это будет при оптимизации вещей. – Amber
Что называется этим алгоритмом? Я реализовал это недавно, и это было довольно прямолинейно и привело к значительному улучшению скорости для моего конкретного варианта использования. – ChrisInEdmonton
А, это, кажется, инвертированный индекс всех биграмм (n-грамм, где n = 2). – ChrisInEdmonton