Комментарии 66
А вот и penny аукционы подъехали
С Бойером-Муром бы сравнить. В целом, эвристики схожие.
Вот только каждый раз, когда вы сохраняете скриншот с текстом и графиками в формате jpeg, Б-г убивает котёнка. Вы не могли бы найти время и перепилить иллюстрации, допустим, в формат PNG? Пожалейте котят!
Каждый раз когда Вы пишете «б-г» или «Б-г» вместо «бог» или «Бог» умирает не только котёнок, а ещё пара тигрят и львенок. Пожалейте зверей, блин.
А как лучше — с большой буквы или с маленькой?
Я вообще думал, что каждый раз, когда я пишу «Бог» вместо «Б-г», Б-г убивает еврея…
Я не убиваю котят. Да и jpeg-артефактов не особо видно тут. Всё в порядке.
А почему бы не воспользоваться стандартными алгоритмами, которым учат в вузах: Кнут — Моррис — Пратт, z-функция, Укконен, Суффиксный автомат, Ахо-Корасик и т.д.?
Потому что им нужна предобработка данных из-за которой выигрывать они будут только при условии частого поиска по одной и той же строке?
Сложность этих алгоритмов O(N+M) (в худшем случае), сложность strstr O(N*M), сложность вашего уже на этапе сортировки индексов не меньше чем O(N) + поиск, который будем считать пропорционален максимальному числу символов в 1 ячейке. В худшем случае, на строке вида abababababababa… (600,000 символов) когда мы будем искать к примеру ababa… аa (255 символов) мы сделаем 600,000/2 (начальных позиций) * 255 (длина) сравнений что может быть даже медленее, чем strstr. Пример — http://ideone.com/3Ucg7Z ваш метод — 1.1s, strstr — 0,05.
О(M+N*M) — это худший случай, я о нём написал. И в обычных текстах такого не бывает.
Хотя да, вы правы. В худшем случае в текущей реализации съедать намного больше времени, чем обычный strstr. Такое сравнение надо заменить на что-то более адекватное, когда искомый текст повторяющийся.
Хотя да, вы правы. В худшем случае в текущей реализации съедать намного больше времени, чем обычный strstr. Такое сравнение надо заменить на что-то более адекватное, когда искомый текст повторяющийся.
Ребят, напишите кто-нить пост человеческий, как сложность алгоритмов считать
Внутренне чувствую, что сложности алгоритмов – ваша любимая тема :)
А вообще, я не знаю, можно ли выразительно пересказать первую главу Макконнелла (ISBN 5-94836-005-9) в одном посте, сохраняя точность и полноту, а потом добавить «парочку» примеров из остальных глав – для закрепления и понимания.
А вообще, я не знаю, можно ли выразительно пересказать первую главу Макконнелла (ISBN 5-94836-005-9) в одном посте, сохраняя точность и полноту, а потом добавить «парочку» примеров из остальных глав – для закрепления и понимания.
Мне этот вариант понравился https://habrahabr.ru/company/mailru/blog/266811/
НЛО прилетело и опубликовало эту надпись здесь
Кнут — Моррис — Пратт в моей списанной с интернета реализации получился чуть-чуть медленнее чем сам strstr. Поэтому я его даже на график не стал ставить. Остальные я пока изучаю.
Опишите пожалуйста требования к алгоритму: какой алфавит (все 256 значений или намного меньше?) какой образец (длина?), какой текст (длина — порядка 1МБ?) Нужны ли повторные поиски того же образца или поиски разных образцов на том же тексте? Известны ли какие-то особенности текста (текст на естественном языке?) Известно ли что будет часто: образец не будет найден, будет найден, или будет найден в самом начале (образец очень часто встречается в тексте). Ответы на эти вопросы могут сильно повлиять на выбор алгоритма.
Например:
Текст — массив любых символов от 1 до 255, заканчивающийся \0
Искомая строка — массив любых символов от 1 до 255, заканчивающийся \0
Поиск по тексту на естественном языке в самый раз.
Алгоритм станет очень медленным, если в строке искомой строке P очень часто встречается какой-то символ и одновременно этот символ очень часто встречается в тексте S. Это легко отследить на этапе составления таблицы с индексами и перекинуть на другой алгоритм. Частота вхождения должна быть действительно большой, но насколько большой я пока не считал. То есть нежелательно что-бы S и P имели вид: «оооооооооz», если символ «о» одинаковый в S и P. Короткие циклические S и P вида: «абвабвабвабв» с одинаковыми символами алгоритм тоже кажется не должен любить, но я не уверен, я не проверял.
Но это не совсем точно, потому что сказано только для текущей реализации, той что в статье.
Текст — массив любых символов от 1 до 255, заканчивающийся \0
Искомая строка — массив любых символов от 1 до 255, заканчивающийся \0
Поиск по тексту на естественном языке в самый раз.
Алгоритм станет очень медленным, если в строке искомой строке P очень часто встречается какой-то символ и одновременно этот символ очень часто встречается в тексте S. Это легко отследить на этапе составления таблицы с индексами и перекинуть на другой алгоритм. Частота вхождения должна быть действительно большой, но насколько большой я пока не считал. То есть нежелательно что-бы S и P имели вид: «оооооооооz», если символ «о» одинаковый в S и P. Короткие циклические S и P вида: «абвабвабвабв» с одинаковыми символами алгоритм тоже кажется не должен любить, но я не уверен, я не проверял.
Но это не совсем точно, потому что сказано только для текущей реализации, той что в статье.
Алгоритм КМП покажет себя при поиске подстрок больших чем 256 символов, он чуть медленее сам по себе, зато не содержит внутри сложности размер искомого образца. O(N) против O(N*M).
По идее КМП покажет себя, только когда текст будет неудобным для этого алгоритма. Потому что КМП проходит по всем символам, а этот алгоритм может перепрыгивать большие блоки символов.
Хотя если текст неудобный, то в принципе легко заменить N*M из внутренней части алгоритма на тот же КМП, модифицировав его с учётом уже известных индексов начала строк.
Хотя если текст неудобный, то в принципе легко заменить N*M из внутренней части алгоритма на тот же КМП, модифицировав его с учётом уже известных индексов начала строк.
«длинна» поправьте в самом начале. Причем два раза подряд, врятли опечатка. Статьи рекомендую хотя б через вёрд прогонять :)
Если Бойер-Мур кажется сложным, то можно начать с упрощённого варианта Бойера-Мура-Хорспула
А нельзя было вычислить все значения хешей отрезков длины от 1 до 255 для всей строки (сложность (255*L), памяти такой же порядок). Тогда поиск будет происходить за O(log L) или даже за O(1) (если использовать unordered_*), после чего при хорошей (хороших) хеш-функции можно даже не проверять результат, вероястно коллизии незначительна. Это метод если исходная строка не меняется.
Если длина образца не меняется, то можно считать хеши только от нужной длины, что убирает константу 255 из сложность алгоритма. После чего это будет чистый алгоритм Рабина-Карпа.
Если это разовая операция (каждый раз строка в которой надо искать новая), то существует целый класс алгоритмов: Z-функция, КМП — алгоритм и другие.
На какую из этих областей рассчитан ваш алгоритм и действительно ли он быстрее общеизвестных?
Если длина образца не меняется, то можно считать хеши только от нужной длины, что убирает константу 255 из сложность алгоритма. После чего это будет чистый алгоритм Рабина-Карпа.
Если это разовая операция (каждый раз строка в которой надо искать новая), то существует целый класс алгоритмов: Z-функция, КМП — алгоритм и другие.
На какую из этих областей рассчитан ваш алгоритм и действительно ли он быстрее общеизвестных?
НЛО прилетело и опубликовало эту надпись здесь
Можно подробнее про поиск на AVX?
strstr() — зло, ибо ищет ещё и ноль которого может не быть.
Он не ищет 0, он использует 0 в паттерне только для определения его длины.
strstr() — зло, ибо ищет ещё и ноль которого может не быть.
The strstr() function finds the first occurrence of the substring needle in the string haystack. The terminating null bytes ('\0') are not compared.
А можно пожалуйста выложить код бенчмарков вместе с тестовым набором данных?
И с какой именно реализацией strstr проводилось сравнение? Внезапно, их тоже много.
Меня смущает два момента:
1. сигнатура не совпадает с библиотечной, т.е. для прямой замены не годится:
2. понятно, что делает max_len, но непонятно, откуда взялось волшебное число 140.
И с какой именно реализацией strstr проводилось сравнение? Внезапно, их тоже много.
Меня смущает два момента:
1. сигнатура не совпадает с библиотечной, т.е. для прямой замены не годится:
char *strstr(const char *s1, const char *s2)
2. понятно, что делает max_len, но непонятно, откуда взялось волшебное число 140.
char * my_strstr(const char * str1, const char * str2,size_t slen){
unsigned char max_len = 140;
Еще в тему – есть интересная статья, в которой автор утверждает, что создал самый быстрый вариант поиска подстроки в строке, и в доказательство приводит подробные сравнения алгоритмов.
1. Сигнатура действительно не совпадает. Там требуется длинна, что-бы он не перескочил через конец строки. Об этом я забыл упомянуть. Это действительно важно, просто забыл написать. Сейчас добавлю.
Да это действительно не прямая замена strstr, размер строки нужен обязательно. Я наверно неправильно выразился.
Это алгоритм, идею которого я почему-то не находил в поисковике(я ещё не во всех алгоритмах разобрался, возможно он где-то там и есть). Хотя идея проверять строку вот такими скачками совсем не очевидна, но очень полезна, и с помощью неё вполне можно сильно ускорить поиск.
Сравнение со strstr тоже скорее исторически обоснованное, потому что именно его я пытался обогнать на маленьких значениях искомой строки. Мне сказали, что у меня не получится именно на маленьких значениях, вот я и пытался.
Правильнее наверно было добавить другие алгоритмы поиска подстроки. Я добавил Кнута-Морисса-Пратта, он оказался медленней чем strstr(возможно из-за плохой реализации) и я его убрал, что-бы не отвлекал.
2. Значение max_len просто часть этой реализации алгоритма, по историческим причинам. Когда-то была кривая зависимости скорости выполнения от размера искомой строки и там около сотни был примерно минимум, поэтому он и сохранился. Вполне возможно он должен иметь другое значение, что-бы работать быстрее.
Большую часть суффикса разбирать на индексы нет смысла, потому что проверяться они будут очень редко. Поэтому ввел такое ограничение max_len. Но значение его в 140 действительно не очень обосновано.
Если бенчмарки — это код, где сравнивается быстродействие, то конечно могу выложить. Но там обычные си функции с не очень качественным кодом и если есть какие-то стандарты, которых нужно придерживаться в бенчмарках, то там их нет. Просто функции сравнения скорости. Выложить их код прямо сюда, в комментарии или на какой-то специальный сервис?
Если тестовый набор набор данных — это тесты, то они тоже в коде на си. И тоже могу выложить
А если тестовый набор данных — это то, на чем строился график, то это по моему текст русскоязычной книги, её я конечно выложить не могу.
strstr брался тот, который из string.h. Я конечно поискал сам исходный код этой функции, но тот код, который я нашел всегда был примерно одинаковым — двойным циклом. И работал примерно с одинаковой скоростью, с тем что появляется при подключении string.h. Возможно там действительно могут быть разные реализации, но я честно говоря не настолько силён в си, что-бы в этом разобраться.
Да это действительно не прямая замена strstr, размер строки нужен обязательно. Я наверно неправильно выразился.
Это алгоритм, идею которого я почему-то не находил в поисковике(я ещё не во всех алгоритмах разобрался, возможно он где-то там и есть). Хотя идея проверять строку вот такими скачками совсем не очевидна, но очень полезна, и с помощью неё вполне можно сильно ускорить поиск.
Сравнение со strstr тоже скорее исторически обоснованное, потому что именно его я пытался обогнать на маленьких значениях искомой строки. Мне сказали, что у меня не получится именно на маленьких значениях, вот я и пытался.
Правильнее наверно было добавить другие алгоритмы поиска подстроки. Я добавил Кнута-Морисса-Пратта, он оказался медленней чем strstr(возможно из-за плохой реализации) и я его убрал, что-бы не отвлекал.
2. Значение max_len просто часть этой реализации алгоритма, по историческим причинам. Когда-то была кривая зависимости скорости выполнения от размера искомой строки и там около сотни был примерно минимум, поэтому он и сохранился. Вполне возможно он должен иметь другое значение, что-бы работать быстрее.
Большую часть суффикса разбирать на индексы нет смысла, потому что проверяться они будут очень редко. Поэтому ввел такое ограничение max_len. Но значение его в 140 действительно не очень обосновано.
Если бенчмарки — это код, где сравнивается быстродействие, то конечно могу выложить. Но там обычные си функции с не очень качественным кодом и если есть какие-то стандарты, которых нужно придерживаться в бенчмарках, то там их нет. Просто функции сравнения скорости. Выложить их код прямо сюда, в комментарии или на какой-то специальный сервис?
Если тестовый набор набор данных — это тесты, то они тоже в коде на си. И тоже могу выложить
А если тестовый набор данных — это то, на чем строился график, то это по моему текст русскоязычной книги, её я конечно выложить не могу.
strstr брался тот, который из string.h. Я конечно поискал сам исходный код этой функции, но тот код, который я нашел всегда был примерно одинаковым — двойным циклом. И работал примерно с одинаковой скоростью, с тем что появляется при подключении string.h. Возможно там действительно могут быть разные реализации, но я честно говоря не настолько силён в си, что-бы в этом разобраться.
DC3 для построения суффиксного массива, затем поиск по суффиксному массиву за O(M)?
Точно! Суффиксный массив, вот как называется то, что делается на этапе 1.
Остальное описание тоже похоже:
Если в суффиксном массиве существую суффиксы начинающиеся с буквы найденной в тексте на позиции pl*i позиции, то для всех этих суффиксов вычисляется начало строки и начинается сравнение за то самое О(М), правда для обычных текстов почти всегда будет прерываться на первых символах.
А что такое DC3? Поиск не помогает.
Остальное описание тоже похоже:
Если в суффиксном массиве существую суффиксы начинающиеся с буквы найденной в тексте на позиции pl*i позиции, то для всех этих суффиксов вычисляется начало строки и начинается сравнение за то самое О(М), правда для обычных текстов почти всегда будет прерываться на первых символах.
А что такое DC3? Поиск не помогает.
DC3 — это алгоритм построения суффиксного массива за О(n).
https://www.google.co.uk/search?q=dc3+algorithm+for+suffix+array&ie=utf-8&oe=utf-8&client=firefox-b&gfe_rd=cr&ei=calqV6rTDqnS8Afu0ovwAg
Есть ссылка на статью авторов: https://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf
(На удивление свежая статья. Там ещё и c++ код есть. 50 строк.)
Мне кажется, у вас поиск за (m log n), я не прав? У вас же посимвольное сравнение в строке?
Алгоритм для поиска за O(m) есть в статье авторов: http://www.zbh.uni-hamburg.de/pubs/pdf/AboKurOhl2004.pdf
Вообще, на хабре уже были статьи про суффиксные массивы: https://habrahabr.ru/post/115346/
https://www.google.co.uk/search?q=dc3+algorithm+for+suffix+array&ie=utf-8&oe=utf-8&client=firefox-b&gfe_rd=cr&ei=calqV6rTDqnS8Afu0ovwAg
Есть ссылка на статью авторов: https://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf
(На удивление свежая статья. Там ещё и c++ код есть. 50 строк.)
Мне кажется, у вас поиск за (m log n), я не прав? У вас же посимвольное сравнение в строке?
Алгоритм для поиска за O(m) есть в статье авторов: http://www.zbh.uni-hamburg.de/pubs/pdf/AboKurOhl2004.pdf
Вообще, на хабре уже были статьи про суффиксные массивы: https://habrahabr.ru/post/115346/
На плохих данных у меня сейчас поиск за О(M+N*M), а на обычных быстрее чем strstr'шный O(M*N).
Спасибо за ссылки. Сяду читать, на пару дней как минимум хватит.
Спасибо за ссылки. Сяду читать, на пару дней как минимум хватит.
>> DC3 — это алгоритм построения суффиксного массива за О(n).
Это тот самый алгоритм, о котором обычно рассказывают на лекциях, где идея в том, что мы переходим к новому алфавиту, состоящему из групп символов? Или это что-то новое придумали?
Это тот самый алгоритм, о котором обычно рассказывают на лекциях, где идея в том, что мы переходим к новому алфавиту, состоящему из групп символов? Или это что-то новое придумали?
НЛО прилетело и опубликовало эту надпись здесь
Друзья, подскажите начинающему программисту.
Хорошую статью про хеши и каким способом лучше всего искать вхождения слов в объемных текстах (>100 000 знаков).
C# медленно работает в этом плане. Запускал в потоках, что ускоряет, но хотелось бы увеличить скорость раз в 10.
Автор,
не совсем понял Вашу методику, но очень интересно. «Цикл с шагом по символам предложения»?
Не понял, что ищем… Символ из ключевого слова?
Хорошую статью про хеши и каким способом лучше всего искать вхождения слов в объемных текстах (>100 000 знаков).
C# медленно работает в этом плане. Запускал в потоках, что ускоряет, но хотелось бы увеличить скорость раз в 10.
Автор,
не совсем понял Вашу методику, но очень интересно. «Цикл с шагом по символам предложения»?
Не понял, что ищем… Символ из ключевого слова?
man boost не?
Это лишь простая эвристика, которая хорошо работает на подобранных вами данных, но плохо работает в общем случае. Если вы действительно упираетесь в скорость
strstr, Бойер-Мур, использующий похожую эвристику, считается одним из самых быстрых алгоритмов. Хорошая реализация есть в Folly, авторы утверждают о 30-кратном (в среднем) ускорении по сравнению с std::string::find в случае успешного поиска, и в 1,5-кратном ускорении в случае неуспешного поиска.Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я ускорял strstr