|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Voloshchuk 2:5020/400 16 Sep 2002 16:22:16
To : Serj Okladnikov
Subject : Re: поиск
--------------------------------------------------------------------------------
> Hужно найти слово в предложении без пробелов. Сейчас я проверяю символы по
> очереди и если очередной не совпадает с соответствующим в слове, то я
начинаю
> сравнивать первый символ слова с несовпавшим, второй с следующим:
> пчелылюбятмед
> .челн.....
> ....челн..
> Вопрос такой, можно ли так делать, или нужно проверять начиная не с
несовпашего
> а с следующего:
> пчелылюбятмед
> .челн.....
> ..челн....
Так делать нельзя, но и двигать каждый раз на один символ не обязательно.
Hасколько я знаю, наиболее эффективным является алгоритм Боуэра-Мура. В
общих чертах он работает так.
Мы "прикладываем" сравниваемый образец к началу текста и сравниваем их. Если
они не совпали, то смотрим, какая буква в ТЕКСТЕ находится напротив
последней буквы образца. Если такой буквы о ОБРАЗЦЕ нет, то он сдвигается
сразу на его длину. (В твоем примере можно на 4 символа, а не на 3). Если же
такая буква в ОБРАЗЦЕ есть, то он сдвигается настолько, чтобы она встала
напротив этой же буквы текста. После этого переходим к началу алгоритма,
т.е. к сравнению.
Hа самом деле алгоритм работает несколько сложнее по двум причинам.
1. Для определения наличия буквы в образце необходимо просканировать весь
образец, а для этого нужно столько же сравнений, сколько и для посимвольного
поиска (как в твоем втором примере). Чтобы этого избежать, создается массив
размером 256 слов (разумеется, если символы 8-битные) и заполняется сначала
числом, равным длине образца, а затем сканируется образец и, используя код
каждого его символа как индекс этого массива, заполняется числом, равным
позиции символа от конца образца. Т.е. в твоем примере
a['ч'] = 3;
a['е'] = 2;
a['л'] = 1;
a['н'] = 0;
Таким образом, для получения величины сдвига достаточно обратится к этому
массиву с соответствующим индексом.
2. Второе усложнение заключается в самой процедуре сравнения образца с
текстом. Оно происходит от последнего символа образца к первому. Если они не
совпали, делаем все как описано выше. Если же они совпали, то переходим к
предпоследнему символу и сравниваем его с символом, находящимся напротив
него в ТЕКСТЕ. Hо в этом случае при определении сдвига вносятся
соответствующие поправки. Если же мы просканировали весь образец от конца к
началу и в нем совпали все символы, значит искомый образец найден.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
поиск |
Serj Okladnikov |
08 Sep 2002 02:09:04 |
 Re: поиск |
Slavik Levchenko |
08 Sep 2002 13:16:53 |
  поиск |
Serj Okladnikov |
08 Sep 2002 19:29:01 |
 Re: поиск |
akrivosheev@utc.ru |
08 Sep 2002 21:54:42 |
|
Re: поиск |
Andrey Belyakov |
09 Sep 2002 02:05:50 |
|
Re: поиск |
akrivosheev@utc.ru |
09 Sep 2002 07:20:51 |
|
поиск |
Evgeniy Trubachev |
10 Sep 2002 10:49:45 |
|
Re: поиск |
Evgeniy Bezimyannikov |
19 Sep 2002 14:40:36 |
|
Re: поиск |
Valentin Davydov |
09 Sep 2002 17:05:16 |
|
Re: поиск |
akrivosheev@utc.ru |
09 Sep 2002 18:49:25 |
|
Re: поиск |
Vladislav Gusev |
10 Sep 2002 18:22:49 |
 Re: поиск |
akrivosheev@utc.ru |
10 Sep 2002 23:53:44 |
|
Re: поиск |
Vladislav Gusev |
11 Sep 2002 13:45:51 |
|
поиск |
Georgy Plechanov |
11 Sep 2002 19:42:50 |
|
Re: поиск |
Andrew Ezhguroff |
13 Sep 2002 15:22:25 |
|
поиск |
Georgy Plechanov |
13 Sep 2002 18:26:54 |
|
Re: поиск |
Valentin Davydov |
16 Sep 2002 03:13:47 |
|
Re: поиск |
Vladislav Gusev |
16 Sep 2002 12:56:32 |
|
Re: поиск |
Andrey Belyakov |
09 Sep 2002 19:44:29 |
|
Re: поиск |
Sergiy Kanilo |
08 Sep 2002 20:19:15 |
|
Re: поиск |
Sergey Voloshchuk |
16 Sep 2002 16:22:16 |
|
|
