Как найти вхождения сотен поисковых фраз в большом тексте (PHP, MySQL)?

Question

[Ushelec]

Дано:

1) Художественный текст размером до 10 мегабайт.
2) Список поисковых фраз (фразы состоят из разного количества слов), который будет пополнятся. Счет идет на сотни фраз.

Необходимо:

1) Найти все вхождения поисковых фраз в тексте.
2) Подсветить вхождения.

В наличии Mysql и PHP. У меня такие вопросы:

1) Как к этой задаче подступиться? Какой способ поиска будет оптимальным?
2) Потянет ли рядовой виртуальный хостинг выполнение такой задачи хотя бы одним пользователем одновременно без нареканий хостера?

Comments

[Александр]

Художественный текст будет неизменен или нужен поиск по разным текстам?

[Ushelec]

@zlobin Текст будет неизменным, его загружает пользователь. Т.е. один текст.

Answer 1

[Николай Елисеев]

Сложного ничего не вижу. Как то давно, тоже надо было найти в большом тексте (около 15 мб) пару фраз.
1) Поиск осуществлять strpos, начиная с последней найденной позиции. Таким образом Вы получите позиции вхождения фраз в текст - тогда не будет проблем с подсветкой.
2) Если фразы будут добавляться, а текст при этом останется исходным, я бы сделал обработку один раз, сохранил для каждой фразы точки вхождения и при дальнейшей обработке просто добавлял бы новые фразы, искал бы по ним вхождения и сохранял. Это позволит Вам сэкономить ресурсы и раздавать результат большому количеству пользователей.

Comments

[Ushelec]

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

[Николай Елисеев]

Ну, я даже не в каком месте здесь задействовать MySQL. Оно Вам надо, только тогда, когда что то хранить собираетесь.

Вообще, если у Вас все это надо клиенту, можно все это реализовать на JavaScript и не париться за ресурсы которые может скушать PHP, пусть кушает ресурсы компьютера пользователя.

[Ushelec]

@nelis Я рассудил, что MySql будет искать намного быстрее, чем операторами php. А вот насчет JavaScript очень интересная мысль, правда совсем не знаю этот язык.

[Николай Елисеев]

1) На PHP это не займет так много времени/ресурсов как кажется. Говорю из опыта. + всегда можно организовать 'умную' очередь
2) MySQL не решает всех Ваших задач + Вы ее не совсем для назначения будете, таким образом использовать.
3) Чтоб написать это на JS, много не надо. Вы поняли алгоритм действий? Из JS Вам надо будет только цикл и работу со строками.

[Ushelec]

@nelis Я совсем не знаю JS, поэтому алгоритм применительно к нему не понял. Можете в общем описать схему? А дальше уже разберусь.

[Николай Елисеев]

1) Вам надо определиться как пользователь будет на сайт текст выгружать.

Дальше действуем с учетом что текст загружен пользователю, например в HTML страницу. Также, предварительно, как то загружены фразы, которые надо искать.

1) Берем текст, суем в переменную, строкового типа
2) Берем список фраз. Из него извлекаем первую, начинаем поиск в текстовой переменной.
3) Ищем все вхождение строки в текст с помощью indexOf, запоминаем в какую либо переменную все позиции для данной строки.
4) Берем следующую фразу и делаем все тоже самое для нее и для всех последующих враз.

В результате: имеем искомые фразы и все позиции вхождения в тексте, имея эту информацию можно поработать с исходным текстом, добавить теги для подсветки.

[Ushelec]

Загрузку текста планирую сделать копипастой, т.е. юзер вставит текст в окно и нажмет кнопку. Спасибо за разьяснение, буду использовать вашу схему как отправную точку. Думаю, разберусь, почитаю, изучу. Еще раз большое спасибо.

[Николай Елисеев]

Не за что :)

Answer 2

[Алексей]

Если стоит задача не вызвать нареканий хостера, нужно делать очередь, разбивать и ставить текст в очередь на обработку.
Если имеется только mysql и php в принципе нет особой разницы как искать, только нужно понимать, что в алгоритм желательно заложить например usleep дабы не создавать скачки загрузки cpu.

Comments

[Ushelec]

Очередь - интересная мысль. Можно будет сделать так - если желающих обработать свой текст много, задания ставим в очередь. Но мне кажется, что даже обработка одного текста будет ресурсоемкой. Представьте, ищем в тексте 2 мегабайта сотню разных поисковых фраз. Это же сто раз надо запустить поиск в одном скрипте. Меня волнует вопрос - средствами php однозначно не стоит ли делать поиск, т.е. занести в базу и средствами mysql искать. Но если средствами mysql, то как именно?

[Николай Елисеев]

@Ushelec посмотрите что я Вам выше написал. Вам MySQL тут ни коем образом не сдался:
1) хранить текст не надо, с Ваших слов
2) Вам надо подсветку пользователям сделать, т.е. позиции вхождения все для каждой фразы, все равно надо искать - и это не в MySQL.

Ну и прочитайте про мое предложение, по поводу сделать все на JS, сопоставьте со своей задачей - это будет более удобное решение.

[Ushelec]

Да, прочитал, задал там вопрос по поводу схемы. Мне тоже видится использование JS оптимальным вариантом.

[Алексей]

@Ushelec в алгоритм желательно заложить например usleep, тогда обработка одного текста не будет ресурсоемкой. Я же написал.

Answer 3

[klirichek]

В принципе, можно попробовать сделать в один проход.
Для каждой фразы делаем ДКА состояний - чтоб ловить поступающие слова и двигать состояние вперёд, если совпадает с ожидающим следующим словом. Если слова закончились - запоминать найденную позицию и сбрасывать состояние. Если новое слово не совпадает - просто сбрасывать состояние.
А дальше - организуем "игру в лото". Проходимся один раз по тексту от начала до конца и "объявляем" всем участвующим ДКА каждое слово. В конце залезаем в них и получаем списки "выигравших" позиций для каждой фразы.
Это в общем. А дальше можно оптимизировать - например, сравнивать не слова, а хэшики от них.
И не "объявлять" каждому "игроку" каждое слово, а собирать у них множество ожидаемых ими хэшиков - и если текущий попадает в множество - двигать состояния у "выигравших", а у всех остальных - сбрасывать.
Ещё шаг - сделать не одно, а два множества. В одном - хэшики тех, что в начальном состоянии (при сбросе они не меняются -> не нужно читать значения заново). Во втором - "играющие".

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