На плохих данных у меня сейчас поиск за О(M+N*M), а на обычных быстрее чем strstr'шный O(M*N).
Спасибо за ссылки. Сяду читать, на пару дней как минимум хватит.
О(M+N*M) — это худший случай, я о нём написал. И в обычных текстах такого не бывает.
Хотя да, вы правы. В худшем случае в текущей реализации съедать намного больше времени, чем обычный strstr. Такое сравнение надо заменить на что-то более адекватное, когда искомый текст повторяющийся.
Точно! Суффиксный массив, вот как называется то, что делается на этапе 1.
Остальное описание тоже похоже:
Если в суффиксном массиве существую суффиксы начинающиеся с буквы найденной в тексте на позиции pl*i позиции, то для всех этих суффиксов вычисляется начало строки и начинается сравнение за то самое О(М), правда для обычных текстов почти всегда будет прерываться на первых символах.
По идее КМП покажет себя, только когда текст будет неудобным для этого алгоритма. Потому что КМП проходит по всем символам, а этот алгоритм может перепрыгивать большие блоки символов.
Хотя если текст неудобный, то в принципе легко заменить N*M из внутренней части алгоритма на тот же КМП, модифицировав его с учётом уже известных индексов начала строк.
Например:
Текст — массив любых символов от 1 до 255, заканчивающийся \0
Искомая строка — массив любых символов от 1 до 255, заканчивающийся \0
Поиск по тексту на естественном языке в самый раз.
Алгоритм станет очень медленным, если в строке искомой строке P очень часто встречается какой-то символ и одновременно этот символ очень часто встречается в тексте S. Это легко отследить на этапе составления таблицы с индексами и перекинуть на другой алгоритм. Частота вхождения должна быть действительно большой, но насколько большой я пока не считал. То есть нежелательно что-бы S и P имели вид: «оооооооооz», если символ «о» одинаковый в S и P. Короткие циклические S и P вида: «абвабвабвабв» с одинаковыми символами алгоритм тоже кажется не должен любить, но я не уверен, я не проверял.
Но это не совсем точно, потому что сказано только для текущей реализации, той что в статье.
1. Сигнатура действительно не совпадает. Там требуется длинна, что-бы он не перескочил через конец строки. Об этом я забыл упомянуть. Это действительно важно, просто забыл написать. Сейчас добавлю.
Да это действительно не прямая замена strstr, размер строки нужен обязательно. Я наверно неправильно выразился.
Это алгоритм, идею которого я почему-то не находил в поисковике(я ещё не во всех алгоритмах разобрался, возможно он где-то там и есть). Хотя идея проверять строку вот такими скачками совсем не очевидна, но очень полезна, и с помощью неё вполне можно сильно ускорить поиск.
Сравнение со strstr тоже скорее исторически обоснованное, потому что именно его я пытался обогнать на маленьких значениях искомой строки. Мне сказали, что у меня не получится именно на маленьких значениях, вот я и пытался.
Правильнее наверно было добавить другие алгоритмы поиска подстроки. Я добавил Кнута-Морисса-Пратта, он оказался медленней чем strstr(возможно из-за плохой реализации) и я его убрал, что-бы не отвлекал.
2. Значение max_len просто часть этой реализации алгоритма, по историческим причинам. Когда-то была кривая зависимости скорости выполнения от размера искомой строки и там около сотни был примерно минимум, поэтому он и сохранился. Вполне возможно он должен иметь другое значение, что-бы работать быстрее.
Большую часть суффикса разбирать на индексы нет смысла, потому что проверяться они будут очень редко. Поэтому ввел такое ограничение max_len. Но значение его в 140 действительно не очень обосновано.
Если бенчмарки — это код, где сравнивается быстродействие, то конечно могу выложить. Но там обычные си функции с не очень качественным кодом и если есть какие-то стандарты, которых нужно придерживаться в бенчмарках, то там их нет. Просто функции сравнения скорости. Выложить их код прямо сюда, в комментарии или на какой-то специальный сервис?
Если тестовый набор набор данных — это тесты, то они тоже в коде на си. И тоже могу выложить
А если тестовый набор данных — это то, на чем строился график, то это по моему текст русскоязычной книги, её я конечно выложить не могу.
strstr брался тот, который из string.h. Я конечно поискал сам исходный код этой функции, но тот код, который я нашел всегда был примерно одинаковым — двойным циклом. И работал примерно с одинаковой скоростью, с тем что появляется при подключении string.h. Возможно там действительно могут быть разные реализации, но я честно говоря не настолько силён в си, что-бы в этом разобраться.
Кнут — Моррис — Пратт в моей списанной с интернета реализации получился чуть-чуть медленнее чем сам strstr. Поэтому я его даже на график не стал ставить. Остальные я пока изучаю.
Спасибо за ссылки. Сяду читать, на пару дней как минимум хватит.
Хотя да, вы правы. В худшем случае в текущей реализации съедать намного больше времени, чем обычный strstr. Такое сравнение надо заменить на что-то более адекватное, когда искомый текст повторяющийся.
Остальное описание тоже похоже:
Если в суффиксном массиве существую суффиксы начинающиеся с буквы найденной в тексте на позиции pl*i позиции, то для всех этих суффиксов вычисляется начало строки и начинается сравнение за то самое О(М), правда для обычных текстов почти всегда будет прерываться на первых символах.
А что такое DC3? Поиск не помогает.
Хотя если текст неудобный, то в принципе легко заменить N*M из внутренней части алгоритма на тот же КМП, модифицировав его с учётом уже известных индексов начала строк.
Текст — массив любых символов от 1 до 255, заканчивающийся \0
Искомая строка — массив любых символов от 1 до 255, заканчивающийся \0
Поиск по тексту на естественном языке в самый раз.
Алгоритм станет очень медленным, если в строке искомой строке P очень часто встречается какой-то символ и одновременно этот символ очень часто встречается в тексте S. Это легко отследить на этапе составления таблицы с индексами и перекинуть на другой алгоритм. Частота вхождения должна быть действительно большой, но насколько большой я пока не считал. То есть нежелательно что-бы S и P имели вид: «оооооооооz», если символ «о» одинаковый в S и P. Короткие циклические S и P вида: «абвабвабвабв» с одинаковыми символами алгоритм тоже кажется не должен любить, но я не уверен, я не проверял.
Но это не совсем точно, потому что сказано только для текущей реализации, той что в статье.
Да, наверно вы правы.
Да это действительно не прямая замена strstr, размер строки нужен обязательно. Я наверно неправильно выразился.
Это алгоритм, идею которого я почему-то не находил в поисковике(я ещё не во всех алгоритмах разобрался, возможно он где-то там и есть). Хотя идея проверять строку вот такими скачками совсем не очевидна, но очень полезна, и с помощью неё вполне можно сильно ускорить поиск.
Сравнение со strstr тоже скорее исторически обоснованное, потому что именно его я пытался обогнать на маленьких значениях искомой строки. Мне сказали, что у меня не получится именно на маленьких значениях, вот я и пытался.
Правильнее наверно было добавить другие алгоритмы поиска подстроки. Я добавил Кнута-Морисса-Пратта, он оказался медленней чем strstr(возможно из-за плохой реализации) и я его убрал, что-бы не отвлекал.
2. Значение max_len просто часть этой реализации алгоритма, по историческим причинам. Когда-то была кривая зависимости скорости выполнения от размера искомой строки и там около сотни был примерно минимум, поэтому он и сохранился. Вполне возможно он должен иметь другое значение, что-бы работать быстрее.
Большую часть суффикса разбирать на индексы нет смысла, потому что проверяться они будут очень редко. Поэтому ввел такое ограничение max_len. Но значение его в 140 действительно не очень обосновано.
Если бенчмарки — это код, где сравнивается быстродействие, то конечно могу выложить. Но там обычные си функции с не очень качественным кодом и если есть какие-то стандарты, которых нужно придерживаться в бенчмарках, то там их нет. Просто функции сравнения скорости. Выложить их код прямо сюда, в комментарии или на какой-то специальный сервис?
Если тестовый набор набор данных — это тесты, то они тоже в коде на си. И тоже могу выложить
А если тестовый набор данных — это то, на чем строился график, то это по моему текст русскоязычной книги, её я конечно выложить не могу.
strstr брался тот, который из string.h. Я конечно поискал сам исходный код этой функции, но тот код, который я нашел всегда был примерно одинаковым — двойным циклом. И работал примерно с одинаковой скоростью, с тем что появляется при подключении string.h. Возможно там действительно могут быть разные реализации, но я честно говоря не настолько силён в си, что-бы в этом разобраться.