Здравствуйте, Vladimir, Вы писали:
V>Подскажите, пожалуйста, алгоритм быстрого поиска подстроки в наборе строк. V>Собственно как организовать набор строк. V>Спасибо.
Здравствуйте, Vladimir, Вы писали:
V>Здравствуйте, Pzz, Вы писали:
Pzz>>А можно контретнее? Что у тебя на входе, уже выделенная подстрока, и набор строк? Надо найти строки, в которые входит данная подстрока?
V>Подсмотрел в программе поиска файлов на компьютере. Там (в программе) при вводе строки поиска в списке отображаются подходящие строки с выделением поискового фрагмента. Причем фрагмент может быть в любом месте строки. У меня строки из таблицы. Предварительная подготовка не критична. V>Вот коротко что я хочу!
Надо говорить, что у тебя есть неизменные тексты, но меняющиеся запросы. И тебе нужно (возможно затратив немного времени на препроцессинг текстов) уметь быстро искать точное вхождение запроса во всех текстах сразу. Так?
Тогда классическое суффиксное дерево подходит лучше всего. Оно строится за линейное время от суммы длин текстов, в которых будет происходить поиск. И после этого для каждого входящего запроса позволяет получить все места, где запрос встречается в текстах. И делает это за линейное время от длины запроса вне зависимости от длин текстов (формально временная сложность — O(|длина запроса| + |число результатов|), так как ещё нужно перечислить все найденные места).
Если же у тебя есть какие-то дополнительные ограничения (например, тексты не влезают в память одной машины) или особенности (например, не нужно уметь искать вхождения с середины слова: скажем, если не обязательно нужно находить "нос" в слове "Ломоносов"), то возможно лучше подойдут другие варианты.
Здравствуйте, Vladimir, Вы писали:
V>Подскажите, пожалуйста, алгоритм быстрого поиска подстроки в наборе строк. V>Собственно как организовать набор строк. V>Спасибо.
А чем КМП (Кнут-Морис-Прат) не подходит? Быстрее, чем O(n+n1+n2+n3+...) всё равно не выйдёт.
Или у тебя много разных строк подставляются в этот самый набор?
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Здравствуйте, Vladimir, Вы писали:
V>Подскажите, пожалуйста, алгоритм быстрого поиска подстроки в наборе строк. V>Собственно как организовать набор строк. V>Спасибо.
Самый простой в реализации вариант — суффиксный массив. И в отличии от суффиксного дерева, потребляет намного меньше памяти.
Здравствуйте, Vladimir, Вы писали:
V>Подскажите, пожалуйста, алгоритм быстрого поиска подстроки в наборе строк. V>Собственно как организовать набор строк. V>Спасибо.
Здравствуйте, Vladimir, Вы писали:
V>Подскажите, пожалуйста, алгоритм быстрого поиска подстроки в наборе строк. V>Собственно как организовать набор строк. V>Спасибо.
Префиксное дерево не подходит, т.к. подразумевается соответствие подстроки с начала строки. По тем же причинам не подходит и суффиксное дерево. Нужен алгоритм что бы предварительно отбрасывать несовпадающие строки.
Здравствуйте, Vladimir, Вы писали:
V>Здравствуйте, Vladimir, Вы писали:
V>>Подскажите, пожалуйста, алгоритм быстрого поиска подстроки в наборе строк. V>>Собственно как организовать набор строк. V>>Спасибо. V>Префиксное дерево не подходит, т.к. подразумевается соответствие подстроки с начала строки. По тем же причинам не подходит и суффиксное дерево. Нужен алгоритм что бы предварительно отбрасывать несовпадающие строки.
Насколько я помню тут такое обсуждали уже, вроде хорошую структуры данных(хорошую по памяти и времени построения) не нашли.
Здравствуйте, Vladimir, Вы писали:
V>Подскажите, пожалуйста, алгоритм быстрого поиска подстроки в наборе строк.
А можно контретнее? Что у тебя на входе, уже выделенная подстрока, и набор строк? Надо найти строки, в которые входит данная подстрока?
Может ли подстрока входить в строку из набора не с начала, а а середины строки?
V>Собственно как организовать набор строк.
Насколько быстрым должен быть алгоритм? Настолько медленным может быть подготовка набора?
Как мне кажется, если требования к скорости поиска велики, набор можно готовить долго и алгоритмическая сложность не проблема, лучший выбор — это детерминированный конечный автомат.
Здравствуйте, Pzz, Вы писали:
Pzz>А можно контретнее? Что у тебя на входе, уже выделенная подстрока, и набор строк? Надо найти строки, в которые входит данная подстрока?
Подсмотрел в программе поиска файлов на компьютере. Там (в программе) при вводе строки поиска в списке отображаются подходящие строки с выделением поискового фрагмента. Причем фрагмент может быть в любом месте строки. У меня строки из таблицы. Предварительная подготовка не критична. При последовательном переборе и сравнении уже на 20К строк видимая задержка (отрисовку в расчет не беру).
Вот коротко что я хочу!
Здравствуйте, Vladimir, Вы писали:
V>Префиксное дерево не подходит, т.к. подразумевается соответствие подстроки с начала строки. По тем же причинам не подходит и суффиксное дерево. Нужен алгоритм что бы предварительно отбрасывать несовпадающие строки.
Почему не подходит? Попробуй посмотреть вот например, описано как сделать full-text-search с помощью trie (префиксного дерева).
Вроде задача похожа на твою 1-в-1 (поиск статей по содержащемуся в их заголовке слову)
То есть, то того что дерево "префиксное", вовсе не означает что оно может использоваться только для поиска с начала строки.
Это просто название структуры данных такое.
Здравствуйте, Vladimir, Вы писали:
V>Подсмотрел в программе поиска файлов на компьютере. Там (в программе) при вводе строки поиска в списке отображаются подходящие строки с выделением поискового фрагмента. Причем фрагмент может быть в любом месте строки. У меня строки из таблицы. Предварительная подготовка не критична. При последовательном переборе и сравнении уже на 20К строк видимая задержка (отрисовку в расчет не беру).
А для одной строки как проверяешь ? Алгоритмом Бойера — Мура ?
Здравствуйте, Vladimir, Вы писали:
V>Подсмотрел в программе поиска файлов на компьютере. Там (в программе) при вводе строки поиска в списке отображаются подходящие строки с выделением поискового фрагмента. Причем фрагмент может быть в любом месте строки. У меня строки из таблицы. Предварительная подготовка не критична. При последовательном переборе и сравнении уже на 20К строк видимая задержка (отрисовку в расчет не беру). V>Вот коротко что я хочу!
А как насчет сделать индекс всех 2-х, может 3-хбайтовых последовательностей по всем строкам, и по введенной подтроке выбирать только подходящие, а дальше уже "доискивать" среди них?
Здравствуйте, bnk, Вы писали:
bnk>Здравствуйте, Vladimir, Вы писали:
V>>Префиксное дерево не подходит, т.к. подразумевается соответствие подстроки с начала строки.
bnk>Почему не подходит? bnk>Вроде задача похожа на твою 1-в-1 (поиск статей по содержащемуся в их заголовке слову)
Не надо туда смотреть — там ерунда. Описанный по ссылке алгоритм не будет работать правильно. Например, он не найдёт запрос "aab" в тексте "xaaabx" (или в аналоге где слова вместо букв "x a a a b x"). То есть даже для поиска одного образца в одном тексте метод плох. Чего уж там говорить об более сложных случаях.
Если интересно, то описанная по ссылке задача (много статических запросов для поиска в динамическом тексте) решается правильно, например, классическим алгоритмом Ахо-Корасик (про то, что связь с trie есть, но она не такая, по ссылке тоже написано)
bnk>То есть, то того что дерево "префиксное", вовсе не означает что оно может использоваться только для поиска с начала строки. bnk>Это просто название структуры данных такое.
Здравствуйте, Pzz, Вы писали:
Pzz>А как насчет сделать индекс всех 2-х, может 3-хбайтовых последовательностей по всем строкам, и по введенной подтроке выбирать только подходящие, а дальше уже "доискивать" среди них?
Для этого подхода можно придумать патологические сценарии, когда поиск тормозит. Но в среднем для околоестественных языков такой подход иногда работает удивительно хорошо. Реальный пример использования: https://swtch.com/~rsc/regexp/regexp4.html
Но там неудобные строки для алгоритма обычно просто выкидываются из индекса, и по ним становится нельзя искать вообще. Но зато по остальным можно искать быстро. И сама реализация алгоритма ну очень простая в плане кода.
Здравствуйте, Vladimir, Вы писали:
V>У меня строки из таблицы.
Имеется в виду таблица БД?
V>При последовательном переборе и сравнении уже на 20К строк видимая задержка (отрисовку в расчет не беру).
Где наибольшая задержка — в загрузке строк или в поиске? И как грузятся строки, загрузили одну, проверили, загрузили другую, проверили или грузятся все сразу, а потом идёт перебор строк?
