2GIS_HACKATHON

• Introduction
• Building and running
• List of symbols
• Brute Force algorithm
• Raita algorithm

Introduction

• Все представленные алгоритмы работают с нуль-терминированной последовательностью байт (C-String). Такое решение было принято ввиду наличия уточнения о возможной бесконечной длины строки haystack, соответственно ожидать на вход строковый тип std::string не имеет смысла. Кроме того обработка, "сырой" нуль-терминированной последовательности байт будет занимать меньше времени.
• Алгоритмы основаны на идее итерирования в прямом направлении относительно начала строки haystack и последовательном получении доступа к ее символам. Поэтому в теории, длина такой строки ничем не ограничена. На практике, конечно же, длина такой строки ограничена максимальным размерном указателя в системе (2^64 в случае 64-разрядного процессора).
• Все алгоритмы учитывают лишь первое вхождение подстроки из needle в haystack.
• Структора программы была разбита на три модуля: Model, View и Controller, согласно устоявшемуся принципу MVC.
• Все классы реализованы в пространстве имен gis.
• Методы поиска в модели, могли бы выводить значения непосредственно в stdout, что было бы отчасти эффективно и не требовало бы дополнительной памяти. Однако такой подход сделает трудоемким написание unit-тестов. Именно поэтому все методы поиска модели возвращают std::vector<EntryData>, где EntryData - это структура, содержащая информацию о найденном входждени какой-либо построки из needle в haystack, длиной не менее threshold. Структура имеет три поля:
  • _length - длина совпадения
  • _h_offset - позиция от начала строки haystack, где было найдено совпадение
  • _n_offset - позиция от начала строки needle, где было найдено совпадение
• Методы View, вызывая соответствующие методы модели через контроллер, выводят результат непосредственно на экран.
• Для смены алгоритма поиска предусмотрен паттерн программирования стратегия: необходимо предварительно методом setSearch() указать адрес объекта, реализующего алгоритм поиска. Список классов, реализующих данные алгоритмы:
  • Search_1 - Brute Force algorithm
  • Search_2 - Raita algorithm

Building and running

• Для сборки и запуска алгоритма необходимо запустить команду make из директории src в проекте.
• Данные для поиска вводятся в файле main.cpp в массивы haystack и needle соответственно. Здесь же осуществляется выбор алгоритма поиска.
• Запуск unit-тестов осуществляется командой make test.

List of symbols

• В этом разделе приведен список обозначений для удовства описания алогритмов.
  • m - длина паттерна (в данном случае needle)
  • n - длина исходной строки haystack (введена только для описания, так как пользоваться этой величиной в алгоритме нельзя по причинам, изложенным выше)

Brute Force algorithm

• Алгоритм простого перебора наиболее прос в реализации и обладает приемлимой скоростью для случаев, когда m < n. Вместе с тем, скорость данного алгоритма значительно падает на больших объемах данных, особенно, когда m >= n.
• Данный алгоритм не требует стадии препроцессинга, а также не потребляет дополнительной памяти.
• Алгоритм посимвольно проходится по haystack, сравнивая последовательность символов с needle. В случае совпадения не менее, чем threshold символов подряд, алгоритм сдвигает начало поиска на длину найденного участка и продолжает до тех пор, пока не встретит терминирующий ноль в haystack.
• Как видно из описания алгоритма, его реализация требует минимум трех вложенных циклов - внешний для прохода по haystack, следующий по вложенности - для прохода по needle и, наконец, наиболее вложенный - для последовательного сравнения символов. Соответственно, вычислительная сложность такого алгоритма в худшем случае составит O(n^2*m).
• Оптимизация: Так как алгоритм учитывает лишь первое вхождение подстроки из needle, то после первого же нахождения совпадающей последовательности, длиной не менее threshold символов, из второго цикла можно выйти, сэкономив тем самым ресурсы.

Raita algorithm

• Алгоритм, разработанный Тимом Райта для поиска фиксированной подстроки в строке является модификацией алгоритма Бойера-Мура, который считается одним из самых быстрых для данной задачи.
• В качестве искомой подстроки берется строка длиной threshold из строки haystack. Далее применяется непосредственно алгоритм Райты по поиску вхождения данной подстроки в needle. Если вхождение найдено, проверяются также дальнейшие символы до тех пор, пока они совпадают. Совпадение записывается в результат, а окно поиска по haystack строке сдвигается на длину найденного паттерна (либо на 1, если совпадение не найдено).
• Алгоритм Райты заключается в том, что на стадии препроцессинга заполняется массив, содержащий значения сдвигов паттерна по исходной строке в зависимости от встреченного символа. Сравнение паттерна со сторокой также происходит необычно: сначала сравниваются последние элементы, затем первые, затем средние и только если все они совпадают, сопоставляются оставшиеся символы. Если паттерн не был найден на текущей итерации, он сдвигается на несколько символов вправо. Значение сдвига определяется из массива, полученного на этапе препроцессинга.
• Именно благодаря сдвигам, алгоритм Райты выигрывает по скорости в сравнении с наивным перебором (уточнение: это справедливо на больших строках, и при n ~ m) - в случае наивного перебора, сдвиг всегда происходит на единицу.
• Дополнительно алгоритм требует хранения массива из 128 целых чисел (128 - размер алфавита).