Помогите мне оптимизировать поиск по индексированной строке

Question

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

1. Отобразить вхождения пар символов в пределах более крупной строки (Pair -> Список позиций).
2. Для каждой пары сохраните также количество вхождений, найденных в большей строке.
3. Получить все пары символов в поисковом слове.
4. Используя полученную пару, которая встречается в строке реже всего, проверьте в каждой позиции оставшиеся символы поискового запроса на совпадение.

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

Много ли еще я могу сделать, чтобы сделать это быстрее? Правильно ли я подхожу к этому?

Answer 1

Строковый поиск - тема с глубокими исследованиями:

http://en.wikipedia.org/wiki/String_searching_algorithm

Вы думаете о поиске, например, Два последовательных символа и сохранение частоты этой комбинации - это очень дорогая операция, даже если вы используете балансировочные структуры данных. Я действительно не вижу, как хранение последовательных символов в качестве шага предварительной обработки поможет вам.

Итак, очевидно, что существует много алгоритмов для поиска строк. Что я нахожу интересным, так это то, что есть некоторые алгоритмы, которым даже не нужно сканировать каждый символ в тексте. Пример: если вы ищете слово «abbbbbc» и обнаруживаете символ «d» в качестве следующего символа основного текста, вы можете сразу же перейти на 5 символов вперед, даже не смотря на то, что они есть, тогда если Следующим символом является 'b' или 'c', вам, очевидно, придется вернуться назад и посмотреть, допустили ли вы ошибку в прыжке, но если нет, то вы пропустили более 5 символов без необходимости сравнения. Однако это трудно реализовать и приводит к теории конечных автоматов.

Answer 2

Другой ответ относится к алгоритму Бойера Мура.Он использует предварительную обработку подстроки, а не поисковый материал.Это считается быстрый неиндексированный поиск.

Существуют и другие алгоритмы поиска, полезные для многократного поиска в одном и том же документе.Рассмотрим Aho-Corasick.

Однако алгоритм, который я использовал и похож на описанный вами, реализован в Python ниже.Идея состоит в том, чтобы для каждого элемента получить набор индексов, где он появляется.Затем для поиска используйте наименее общий символ в подстроке в качестве списка контрольных точек.Переберите подстроку для каждой контрольной точки, разрывая, когда не удается найти индекс.

Вы должны проверить это, чтобы увидеть, работает ли он быстрее, чем Бойер Мур или другие алгоритмы.Этот может быть в состоянии быть улучшенным.Было бы хорошим упражнением, опоздание на пять лет.

class IndexRegistry(object):
    def __init__(self, iterable):
        self._store = defaultdict(set)
        for index, val in enumerate(iterable):
            self._store[ val ].add( index )

    def find(self, items):
        _, refIndex, refItem =  min( 
                                            [ ( len(self._store[item]), index, item ) 
                                                    for index, item in enumerate(items)
                                             ], 
                                            key=lambda el: el[0] 
                                        )

        for referenceIndex in self._store[ refItem ]:
            startIndex = referenceIndex - refIndex
            for itemIndex, item in enumerate(items):
                absIndex = startIndex + itemIndex
                if absIndex not in self._store[ item ]:
                    break #substring broken
            else: #no break
                yield startIndex

    def __contains__(self, items):
        try:
            next(self.find(items))
        except StopIteration:
            return False

        return True