Re: поиск

From

Sergey Voloshchuk ()

To

Serj Okladnikov

Date

2002-09-16T16:22:16Z

Area

RU.ALGORITHMS

From: "Sergey Voloshchuk" <sww.kedr@overta.ru>

> Нужно найти слово в предложении без пробелов. Сейчас я проверяю символы по
> очереди и если очередной не совпадает с соответствующим в слове, то я
начинаю
> сравнивать первый символ слова с несовпавшим, второй с следующим:
> пчелылюбятмед
> .челн.....
> ....челн..
> Вопрос такой, можно ли так делать, или нужно проверять начиная не с
несовпашего
> а с следующего:
> пчелылюбятмед
> .челн.....
> ..челн....

Так делать нельзя, но и двигать каждый раз на один символ не обязательно.

Насколько я знаю, наиболее эффективным является алгоритм Боуэра-Мура. В
общих чертах он работает так.
Мы "прикладываем" сравниваемый образец к началу текста и сравниваем их. Если
они не совпали, то смотрим, какая буква в ТЕКСТЕ находится напротив
последней буквы образца. Если такой буквы о ОБРАЗЦЕ нет, то он сдвигается
сразу на его длину. (В твоем примере можно на 4 символа, а не на 3). Если же
такая буква в ОБРАЗЦЕ есть, то он сдвигается настолько, чтобы она встала
напротив этой же буквы текста. После этого переходим к началу алгоритма,
т.е. к сравнению.

На самом деле алгоритм работает несколько сложнее по двум причинам.
1. Для определения наличия буквы в образце необходимо просканировать весь
образец, а для этого нужно столько же сравнений, сколько и для посимвольного
поиска (как в твоем втором примере). Чтобы этого избежать, создается массив
размером 256 слов (разумеется, если символы 8-битные) и заполняется сначала
числом, равным длине образца, а затем сканируется образец и, используя код
каждого его символа как индекс этого массива, заполняется числом, равным
позиции символа от конца образца. Т.е. в твоем примере
a['ч'] = 3;
a['е'] = 2;
a['л'] = 1;
a['н'] = 0;
Таким образом, для получения величины сдвига достаточно обратится к этому
массиву с соответствующим индексом.

2. Второе усложнение заключается в самой процедуре сравнения образца с
текстом. Оно происходит от последнего символа образца к первому. Если они не
совпали, делаем все как описано выше. Если же они совпали, то переходим к
предпоследнему символу и сравниваем его с символом, находящимся напротив
него в ТЕКСТЕ. Но в этом случае при определении сдвига вносятся
соответствующие поправки. Если же мы просканировали весь образец от конца к
началу и в нем совпали все символы, значит искомый образец найден.


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)