Google Picasa вас спасет — это практически лучший софт общего назначения для управления фотографиями, что я видел на Linux (подозреваю что и на Win).
Если никакой профессиональной деятельности с фотками не предполагается, то есть только два действия, которые можно делать с альбомами: 1) показать друзьям подвыборку из 5% фотографий 2) посмотреть раз в год самому 20% из фотографий. 80% фотографий не будут посмотрены никем и никогда, но это и не важно, мы не против хомячества :) Перед показом друзьям хочется минимально приукрасить фотки, при этом не попортив оригинал (ибо хомячество).
Раскидываете все по папочкам вида «2008/2008.02/2008.02.23 какое нибудь описание», чтобы даже выдранное из контекста название папки содержало полную инфу (в picasa так удобнее полное имя папки «2008.02.23 какое нибудь описание», а если ручками по папкам шариться, то надо иметь иерархию). Натравливаете picasa на эти все фотки и формируете прямо в ней подборки-альбомы, которые подправляете прямо в picasa (большинству людей хватает двух-трех кнопок вроде «сделать зашибись» и «сделать зашибись, если первый вариант не понравился», которые благоразумно вынесены в удобное место). Редактирование запоминается, но не затрагивает оригинал, если не нажимать «сохранить». Легким нажатием кнопки сделанные подборки-альбомы публикуются на вашем аккаунте у гугла, после чего можно всем рассылать ссылочки и ждать восторженных отзывов. В большинстве случаев и сами вы смотрите именно опубликованные фотки, т.к. нет желания рыться в тех трех тысячах снимков, что вы привезли из поездки.
Таким образом фотографии
1) отсортированы
2) в целости и сохранности
3) есть отретушированный набор для показа
4) этот набор опубликован в вебе
Основное практическое применение — это как раз индексация текстов для быстрого поиска в них. Т.е. например проиндексировать по-простому (без морфологии) справку для полнотекстового поиска, или же проиндексировать геном. Думаю не совру, если скажу что практически все поисковики пользуются суффиксными массивами тоже. Слишком уж много сложностей с деревьями.
Да, немного неправильно выразился. Сами элементы не копируются, копируется таблица мэппинга индексов при переаллокации. Т.е. всплески могут быть все-равно и они будут O(n). Но константа, конечно, сильно меньше, чем в векторе.
Ну deque тут не поможет. Обычно у STL-ного deque тоже переаллокация с копированием элементов происходит. Например в gcc используется реализация с вектором и циклической индексацией. Т.е. когда место в векторе закончится, то будет все то же самое.
Думаю ваш алгоритм может быть полезен когда вычисление хэша от набора объектов заметно дешевле их сравнения. Т.е. не для строк, а для, каких-нибудь больших и сложных объектов.
Почему за линейное время в простом случае, когда для k=i-r+1 дуального i Z[k] меньше чем оставшийся Z-блок понятно — просто смотрим результат для Z[k] и вписывем в i-ю ячейку. Очевидно О(1).
Допустим Z[k] больше или равно расстоянию до конца Z-блока. Тогда мы будем проверять h+1 символов правее конца нашего самого правого Z-блока. При этом окажется, что Z[i]=Z[k]+h, что при отсчете от i-ой позиции закончится дальше, чем текущий r-тый Z-блок на h позиций. А значит r-тый мы разжалуем и возьмем за любимый Z-блок этот самый новый Z[i]. Но он будет заканчиваться на h позиций дальше, а значит для этих h позиций мы схалтурим на следующих шагах с проверкой не сравнивая больше их для других суффиксов, так как по логике подобия Z-блоков такая обработка уже совершалась. Таким образом второй тип шага для каждого символа будет проделан 1 раз. Что и дает общую сложность O(n). Да, нет гарантии что каждый шаг выполнится за O(1), но общий все-таки O(n).
1) a) Ну собственно так и считаю. Второй вариант совсем извращенный, хотя похоже тоже O(mn), если, конечно, он работает.
б) Да, точно. Не углядел. Кстати, а это уже аргумент за «break» — он заметнее.
2) Ну если так, то в принципе они и описаны. Динамическое программирование на рекуррентном соотношении дала бы именно такие алгоритмы. Собственно а в чем разница? Вы решаете n задачек нахождения некой функции в каждой точке. И для этого используете предыдущие результаты вычислений. В описаниях приведены правила перехода в i+1 позицию при наличии решений до 1..i позиций. Разве что само соотношение не записано, ибо условия, когда его применять, весьма муторно выписывать.
Для Z-функции получилось бы в точности то самое. Для префикс-функции возможно получился бы какой-то побочный вариант вроде «сильной префикс функции» — когда результаты «откатов» назад протаскиваются вперед чтобы не повторять откаты. Но это был бы по сути такой же КМП.
3) Если интересно, то вот здесь есть еще синонимы этой структуры. На мой взгляд «бор» — веселее. Бор — это же лес деревьев. Кроме того, более широко распространено.
1) Ну хорошо, вот ваш пример который без «отката». Вот вы вошли во внутренний цикл, пощупали i+1-й символ, i+2-й, i+3-й, и тут бац! Облом. Не то. И дальше вы выходите и внутреннего и продолжаете с i+1-й позиции. И чем не откат назад? Вы же уже смотрели i+1, i+2 и т.д. символы. По логике то же самое, а код к тому месту, которое значилось как пример как делать не надо, я не писал :)
Кстати, если бы сделали break во внутреннем цикле, то вышли бы гораздо раньше, а так даже если вторая буква из пятисот не совпала, вы все-равно все пятсот шерстите.
2) Можно, но если что-то можно записать нерекурсивно, то зачем это делать рекурсией? И факториал рекурсивно считается, но зачем? Чтобы потом надеяться, что компилятор соптимизирует?
3) Это одно и то же. Бор — это лес деревьев во всех смыслах. Как ни странно, это вполне употребимый термин.
Оба алгоритма просматривают строки последовательно. Т.е. оба найдут первое вхождение в общем случае раньше, чем обработают всю строку. Правда КМП обнаруживает конец вхождения, а Z-функция начало. В случае длинного шаблона поиска в этом будет разница на длину X (КМП обработает на |X| символов больше), если вы это имели ввиду.
Вообще, производительность методов эквивалентна. Z-функция в самом плохом случае выполняет 2|X|+2|A| сферических операций, а КМП — 3|X|+3|A|. Но наступление этих самых плохих ситуаций происходит при синтетических заготовках текста, например КМП обычно не три раза каждый символ смотрит, а полтора раза в среднем. В реальной жизни еще надо думать о каких именно операциях идет речь.
А вообще эти алгоритмы интересны не столько тем, что они особо быстрые, сколько тем, что Z-функция и преффикс-функция используются в других алгоритмах работы со строками. А самым быстрым считают Бойера-Мура и его модификации, как утверждает википедия.
Если никакой профессиональной деятельности с фотками не предполагается, то есть только два действия, которые можно делать с альбомами: 1) показать друзьям подвыборку из 5% фотографий 2) посмотреть раз в год самому 20% из фотографий. 80% фотографий не будут посмотрены никем и никогда, но это и не важно, мы не против хомячества :) Перед показом друзьям хочется минимально приукрасить фотки, при этом не попортив оригинал (ибо хомячество).
Раскидываете все по папочкам вида «2008/2008.02/2008.02.23 какое нибудь описание», чтобы даже выдранное из контекста название папки содержало полную инфу (в picasa так удобнее полное имя папки «2008.02.23 какое нибудь описание», а если ручками по папкам шариться, то надо иметь иерархию). Натравливаете picasa на эти все фотки и формируете прямо в ней подборки-альбомы, которые подправляете прямо в picasa (большинству людей хватает двух-трех кнопок вроде «сделать зашибись» и «сделать зашибись, если первый вариант не понравился», которые благоразумно вынесены в удобное место). Редактирование запоминается, но не затрагивает оригинал, если не нажимать «сохранить». Легким нажатием кнопки сделанные подборки-альбомы публикуются на вашем аккаунте у гугла, после чего можно всем рассылать ссылочки и ждать восторженных отзывов. В большинстве случаев и сами вы смотрите именно опубликованные фотки, т.к. нет желания рыться в тех трех тысячах снимков, что вы привезли из поездки.
Таким образом фотографии
1) отсортированы
2) в целости и сохранности
3) есть отретушированный набор для показа
4) этот набор опубликован в вебе
Значит ждем статью про суффиксный автомат ;) Очень интересно почитать.
Почему за линейное время в простом случае, когда для k=i-r+1 дуального i Z[k] меньше чем оставшийся Z-блок понятно — просто смотрим результат для Z[k] и вписывем в i-ю ячейку. Очевидно О(1).
Допустим Z[k] больше или равно расстоянию до конца Z-блока. Тогда мы будем проверять h+1 символов правее конца нашего самого правого Z-блока. При этом окажется, что Z[i]=Z[k]+h, что при отсчете от i-ой позиции закончится дальше, чем текущий r-тый Z-блок на h позиций. А значит r-тый мы разжалуем и возьмем за любимый Z-блок этот самый новый Z[i]. Но он будет заканчиваться на h позиций дальше, а значит для этих h позиций мы схалтурим на следующих шагах с проверкой не сравнивая больше их для других суффиксов, так как по логике подобия Z-блоков такая обработка уже совершалась. Таким образом второй тип шага для каждого символа будет проделан 1 раз. Что и дает общую сложность O(n). Да, нет гарантии что каждый шаг выполнится за O(1), но общий все-таки O(n).
б) Да, точно. Не углядел. Кстати, а это уже аргумент за «break» — он заметнее.
2) Ну если так, то в принципе они и описаны. Динамическое программирование на рекуррентном соотношении дала бы именно такие алгоритмы. Собственно а в чем разница? Вы решаете n задачек нахождения некой функции в каждой точке. И для этого используете предыдущие результаты вычислений. В описаниях приведены правила перехода в i+1 позицию при наличии решений до 1..i позиций. Разве что само соотношение не записано, ибо условия, когда его применять, весьма муторно выписывать.
Для Z-функции получилось бы в точности то самое. Для префикс-функции возможно получился бы какой-то побочный вариант вроде «сильной префикс функции» — когда результаты «откатов» назад протаскиваются вперед чтобы не повторять откаты. Но это был бы по сути такой же КМП.
3) Если интересно, то вот здесь есть еще синонимы этой структуры. На мой взгляд «бор» — веселее. Бор — это же лес деревьев. Кроме того, более широко распространено.
Кстати, если бы сделали break во внутреннем цикле, то вышли бы гораздо раньше, а так даже если вторая буква из пятисот не совпала, вы все-равно все пятсот шерстите.
2) Можно, но если что-то можно записать нерекурсивно, то зачем это делать рекурсией? И факториал рекурсивно считается, но зачем? Чтобы потом надеяться, что компилятор соптимизирует?
3) Это одно и то же. Бор — это лес деревьев во всех смыслах. Как ни странно, это вполне употребимый термин.
Вообще, производительность методов эквивалентна. Z-функция в самом плохом случае выполняет 2|X|+2|A| сферических операций, а КМП — 3|X|+3|A|. Но наступление этих самых плохих ситуаций происходит при синтетических заготовках текста, например КМП обычно не три раза каждый символ смотрит, а полтора раза в среднем. В реальной жизни еще надо думать о каких именно операциях идет речь.
А вообще эти алгоритмы интересны не столько тем, что они особо быстрые, сколько тем, что Z-функция и преффикс-функция используются в других алгоритмах работы со строками. А самым быстрым считают Бойера-Мура и его модификации, как утверждает википедия.