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

А если сначала выделить основы слов запроса, то есть две-три, создать заодно общий список разрешённых им окончаний, поискать именно основы в словах аннотации - быстрые алгоритмы алгоритмы поиска подстроки см. в трёхтомнике Кнута, а потом только для найденных вхождений проверить остаток слова по списку разрешённых окончаний? Операций будет меньше примерно на порядок.

Это самый простой способ.

Вот второй навскидку: произвести синтезом все словоформы слов запроса, отсортировать по алфавиту, отсортировать слова аннотации по алфавиту, запомнив с ними позицию в аннотации, произвести сортировку слиянием. Подсветить позиции с номерами, где произошло совпадение.

Ну и так далее.

Но вообще мне странно, что это место вызывает проблемы с производительностью. Вот залезть лишний раз в индекс - да, понимаю, дисковая операция (в общем случае). А подсветка делается в памяти, с очень маленькими текстами.

Если у вас есть синтез кроме анализа (в т.ч для несловарных слов!), то подойдут любые версии "многострочного" поиска: хэш, тернарное дерева, DFA(в духе fgrep), Ахо-Горасик, бит-параллельные методы и т.п. Если синтеза нет или он не для всех видов слов, то вариантов два: хранить номера слов в индексе и доставать их при подсветке, или воспользоваться неполным сравнением: по началам слов, по основам и т.п.

Отдельно стоит вопрос все ли вы слова собираетесь подсвечивать. Если, например, как Я-Сайт - только "результативные", то нужно либо хранить позиции, либо делать "микроиндексирование" с "микропоиском"

Илья

У меня уже есть участок текста, который необходмо вывести в результатах, и я уже знаю, что найденное слово начинается, скажем, с 15-ой позиции.

Наример: поисковая фраза "тестовый поиск"

Выводится цитата:

"... в этом случае при тестовом поиске не было найдено требуемых документов, но при изменении поискового запроса ..."

Первое слово "тестовом" выделить не проблема, я точно знаю, что оно там есть, и начинается с 15 позиции.

Но проверить надо и остальные слова. Ведь еще надо выделить слово "поиске" и "поискового".

Словарь хранится в виде CRC32 основной формы, и CRC32 слова. По CRC32 слова я нахожу CRC32 основной формы и сраниваю с CRC32 основной формы слов из поисковго заросва - совпадает - выделяю.

Можеть есть можно выделить как-то без обращения к словарю ?

Простите, а как вы собираетесь разрешать коллизии?

никак.

Ну и зря. "Зря" - это насчет "никак".

А вообще задача вполне простая. Если Вы храните в индексе координату слова, то вообще непонятно, о чем идет речь. Если же нет, но хотите подсвечивать вхождения online, и у Вас есть качественный и быстрый морфологический анализатор, то задача также решается достаточно просто. Практически исчерпывающие ответы дали Игорь и Илья, я от себя лишь добавлю, как практически та же задача была в свое время решена мной.

В пакете проверки русской орфографии и грамматики "Пропись 4.0" была функция замены русского слова со всеми формами, в том числе и в встраиваемая в Microsoft Word. Чтобы быстро искать в "евойном" тексте, то есть средствами самого Word, для слова порождался набор формальных шаблонов с использованием полной парадигмы слова, а далее каждое найденное вхождение уже проверялось морфологическим анализатором на соответствие искомой словоформе.

Понятно, что для этого нужен качественный полнофункциональный морфологический анализатор. Ну, а где его взять - не буду говорить, а то Петренка меня осудит за саморекламу :)

А что, она не соответствует действительности? :)

Mikek:

Keva:

Ваш полнофункциональный морфологический анализатор позволяет рассматривать слова "поиск" и "поиско'вый" как формы одного и того же слова? Или анализатор содержит связи между разными частями речи, чего я в поиске Рамблера не замечал?

Неплохое решение уже предложил Игорь Ашманов. Берете вашу фразу:

"... в этом случае при тестовом поиске(6) не было найдено требуемых документов, но при изменении поискового(15) запроса(16) ..."

разбиваете по словам и сортируете с учетом позиций в документе:

...

запроса 16

поиске 6

поискового 15

...

Потом берете список всех возможных окончаний, убираете их, после чего бинарным поиском здесь уже можно найти основы слов из запроса и подсветить.

Увы, согласен с Андреем. Кто-то из ваших пользователей обязательно наткнется на найденное "не то" слово.

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