На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Алгоритм поиска подстроки в строке
    Народ помогите найти алгоритм для поиска в строке подстроки, обічній дельфиевский Pos() слишком слабый и в больших оюъемах (30МБ) уже ужасно тормозит, может посоветуете чтонибудь другое ? И еще как снять ограничение на размер открываемого файла в дельфи?
      Самому написать.
      идея - обычно ты ищещь первую букву искомой строки в тексте, потом проверяешь
      совпадают ли остальные буквы. Дык а попробуй искать не первую букву искомой строки
      а самую редкую. тогда колиество лишних сравнений (если 1 буквы совпала а остальные нет)
      будет меньше.
        Редкую где?
        В исходной строке. Так сначала потребуется найти её.
          Есть такой алгоритм(кажется (с) Кнут):

          1.
          Считаем хэш-функцию типа H(s) = s[0] + s[1] + ... + s[n-1], где s - подстрока длиной n, которую нужно найти. Вместо + можно взять xor или что-нибудь еще.

          2.
          Считаем значение хэш-функции для первых n символов строки S в которой ведется поиск.

          3. i = n;

          4.
          Если H совпадает с H(s), проверяем посимвольным сравнением и делаем выводы, если нет - идем дальше:
          H = H - S[i-n] + S[i]; i++;

          5. Goto 4

          Т.е. фишка в том, что мы не пересчитываем каждый раз значение хэша заново, а вычисляем его из предыдущего всего за две быстрые операции (само собой, такое возможно только для определенного класса хэш-функций)
          Сообщение отредактировано: Ivan_Govnoff -
            Что-то мне кажется, что етот, с хеш-функцией, алгоритм (1) будет НЕ быстрее, чем ранее предложенный алгоритм (2) (поиск первой буквы, затем сравнение остальных), в том случае, если  буквы в просматриваемом тексте распределены равномерно... Если же неравномерно, то (1) в среднем будет работать с такой же скоростью, что и (2), но у (2) будут случаи "плохих" и "хороших" искомых подстрок :)

            Самым быстрым, вроде, считают алгоритм Бойера-Мура, но его еффективность проявляется только при значительной длине искомой подстроки.
            Сообщение отредактировано: Visitor -
              У меня курсовик был на эту тему. Могу намылить.
                Цитата Visitor, 12.10.03, 03:18:46
                Что-то мне кажется, что етот, с хеш-функцией, алгоритм (1) будет НЕ быстрее, чем ранее предложенный алгоритм (2) (поиск первой буквы, затем сравнение остальных), в том случае, если  буквы в просматриваемом тексте распределены равномерно... Если же неравномерно, то (1) в среднем будет работать с такой же скоростью, что и (2), но у (2) будут случаи "плохих" и "хороших" искомых подстрок :)

                Ясен пень, если тебе хватает первого метода, то и не нечего извращаться, просто я предлагаю другой хороший вариант.
                  редкая - например "Ъ".

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

                  кстати простой вариант с первой буквой - этот тот же хеш. просто хеш фукнция от строки - взять первую букву.
                    В журнале "Программист" была статья в свое время на эту тему.
                    Самый эффективный поиск там был начиная с конца текста.
                    Ищешь с конца первое вхождение первого символа подстроки. При повторяющихся символах в подстроке сдвигать можно на разнице между двумя вхождениями этих символов.
                    По-моему так....
                      Блин... Ну хоть строгое доказательство приводи :) Ни один алгоритм, не использующий знание о структуре искомой подстроки и просматриваемого текста, в среднем не будет работать быстрее, чем самый очевидный из уже предложенных :)

                      2 lunc: Алгоритм Бойера-Мура примерно так и делает. Только там прописаны сдвиги для каждого символа искомой подстроки
                      Сообщение отредактировано: Visitor -
                        Цитата Visitor, 13.10.03, 20:22:23

                        2 lunc: Алгоритм Бойера-Мура примерно так и делает. Только там прописаны сдвиги для каждого символа искомой подстроки


                        Про него я и говорил :)
                        Пример:

                        Let us consider the following example    (надо найти вхождение Override):
                                Override     (совпадают символы ide)
                                      Override   (совпадает символ e)

                        В начале в текущей позиции находим первый с конца образца символ не соответствующий символу в строке (стоп-символ). Чтобы не пропустить ни одной возможной позиции сдвигаем образец вправо до первого вхождения стопового символа. Повторяем.

                        Описан этот алгоритм и еще несколько 9включая на конечных автоматах) в журнале Программист #6 2002 "Алгоритмы: "умный" поиск в тексте"
                          Тогда сдаюсь - согласен :)
                          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                          0 пользователей:


                          Рейтинг@Mail.ru
                          [ Script execution time: 0,0586 ]   [ 15 queries used ]   [ Generated: 21.05.24, 07:23 GMT ]