Это же и будет алгоритм Дейкстры. По крайней мере тот же вариант, который описан в статье в коде (в текстовом описании алгоритм в статье немного отличается от варианта в коде). Есть еще два варианта Дейкстры: 1 не помещать повторно в кучу то, что там уже находится, а просто выполнять heapifyUp для такого узла из кучи (минусы: куча с heapifyUp есть не в каждой библиотеке и ее придется реализовать самому; поддерживать указатели на узлы из кучи не так просто и ресурсозатратно; плюсы: используем О(n) памяти под кучу, а не О(m)), и 2 вообще изначально положить в кучу все узлы (минусы и плюсы в таком варианте те же)
Бегло прошёлся по бенчмаркам в интернете и, судя по всему, LZMA и его производные даже против deflate (это LZ77 с Хаффманов) дают в 1.5 - 2 раза лучшее сжатие. А против LZW они будут ещё лучше (LZW проигрывает deflate по сжатию, но не так драматически). По-моему это не "сравнимая" степень сжатия. Зависит от сжимаемых данных, конечно, но эти бенчмарки часто довольно репрезентативны. Недавно, кстати, на хабре была хорошая статья на близкую тему: https://habr.com/ru/post/570694/ (там же есть ссылка на один хороший бенчмарк; ещё можно посмотреть http://www.mattmahoney.net/dc/text.html). Много раз уже сталкивался с похожим мнением, что сжатие не важно и важнее скорость. Согласен, есть такие приложения, где это так. Но даже в таком случае LZW далеко не лучший выбор и методы на основе LZ77 (не обязательно LZMA) работаю лучше. Например, zstd с флагом "level 2" (или около того), судя по бенчмаркам, так же эффективен по степени сжатия, как deflate с наилучшим сжатием, но раз в 5 быстрее декодирует. Я уверен, что LZW с Хаффманом/арифметиком декодирует медленнее, чем deflate (LZW для декодирования использует более сложного вида словарь, а deflate просто копирует уже декодированные куски); в интернете пишут, что LZW в 2 раза медленнее декодирует, чем deflate, в некоторых реализациях. Без Хаффмана LZW точно по-быстрее будет, но тоже не факт, что быстрее чем deflate. Так что zstd явно гораздо лучше в этом отношении и чем LZW, и чем deflate.
Я думаю, что это сделано для простоты реализации. LZW - очень простой но при этом эффективный алгоритм, который каждый может реализовать без мудрствований. Но если продолжать вашу мысль и довести её до идеала, то оптимально было бы применять для каждой фразы LZW адаптивное интервальное кодирование или что-то в этом духе. Тогда вся последовательность из z фраз LZW будет занимать всего log2(256) + log2(257) + ... + log2(255 + z) + 1 битов, ну или log2(256) + log2(257) + ... + log2(d) + log2(d) + ... + log2(d) + 1 битов, если размер словаря ограничен d фразами (например, d = 2^16, как обычно полагают). В стандартных реализациях LZW (типа LZC) тоже есть механизмы уменьшения размера кодов для первых фраз (хоть и не такие оптимальные): обычно первые фразы занимают последовательно 9, 10, ..., 16 битов, а потом словарь перестаёт расти. Вполне возможно, что на реальных датасетах этот простой трюк не намного хуже более хитрого оптимального кодирования. Вообще, если нужно сжатие по-лучше, то лучше сразу обращаться к LZMA, а не пытаться тюнить LZW.
Точно помню, что видел либо на хабре, либо на гиктаймс статью с подробным расследованием этой атаки от какой-то чешской или словакской фирмы, занимающейся ИБ (может avast, но не уверен). Всё обшарил, пытался загуглить разными запросами, но так и не смог найти. Может быть кто-нибудь помнит, как называлась та статья? Хочется вспомнить аргументы «стороны обвинения».
Вспомнился обширный интересный комментарийkraidiky о невероятной разумности компилятора фортран. Правда, он не стал, как автор, раздувать из комментария статью (может, всё таки, зря).
О том, что у человека при просмотре такого выступления может возникнуть ощущение, что для выправления собственной речи не обязательно избавляться от слов-паразитов и рваных фраз, что это всё мелочи. Однако, по своему опыту сужу, что речь многих докладчиков, не обладающих той же харизмой, чувством юмора и чувством аудитории, как докладчик на видео выше, страдает именно и главным образом от рваных фраз, слов-паразитов и ненамеренно высокомерных реплик (как в списке в статье). Вот от таких ошибок статья и предостерегает (и справедливо, судя по количеству совершающих эти ошибки), но при этом честно упоминает, что хорошие докладчики иногда нарушают все эти правила и начинающего это может ввести в заблуждение, что типа так и надо. Имхо, не у всех достаточно харизмы/уверенности в себе/ещё чего-то, чтобы превратить свои недостатки в достоинства, как на видео выше.
Однако отдельные личности с критическим мышлением предостерегают нас от ошибки при выборе примеров для подражания. Далеко не всё, что говорят даже самые лучшие спикеры, положительно воспринимается аудиторией.
Так что очень даже в тему это видео. Что позволено Юпитеру…
То что вы ищете называется cache-oblivious model: https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
Эта модель, придуманная ещё в середине девяностых, несколько более сложна, чем традиционная RAM, поэтому под неё разработано меньше алгоритмов. Так получается, я полагаю, потому что при решении ещё нерешённой задачи люди сначала предпочитают всесторонне рассмотреть её в близкой (и часто практической), но более простой обычной RAM, а уже потом смотрят на кэш/внешнюю память/параллелизм.
Более логичным выглядит предположение, что популярность этого алгоритма вытекает из его простоты.
Скорее всего вы правы, но всё таки есть немало программистов, которые краем уха где-то слышали об оптимальности LRU при каких-то условиях, что частично оправдывает его использование (смотрите мой комментарий выше).
Вы совсем как-то заклеймили LRU. Верю, что, вероятно, на многих реальных паттернах использования кэша LRU проигрывает некоторым другим кэшам. Но есть у LRU одна особенность: в худшем случае его поведение в некотором смысле наилучшее по отношению к «ясновидящему» оптимальному алгоритму. Это доказано Слейтором и Тарьяном в статье Amortized efficiency of list update and paging rules (раздел 4). Немного огрублённо их результат можно сформулировать так:
Для любой константы c>1 и для любой последовательности s обращений к кэшируемым элементам (кэшируемые элементы имеют одинаковый размер) выполняется F_LRU(s) <= c F_OPT(s), где F_LRU(s) и F_OPT(s) — это число непопаданий в кэш на последовательности s для, соответственно, алгоритма LRU с размером кэша n и ясновидящего алгоритма OPT с размером кэша (1 — 1/c)n.
И обратно: для любого алгоритма кэширования A найдётся сколь угодно длинная последовательность s обращений к кэшируемым элементам, такая что F_A(s) >= c F_OPT(s), где F_A(s) — это число непопаданий в кэш на последовательности s для алгоритма A с размером кэша n, а у OPT опять размер кэша (1 — 1/c)n.
Если вы рассматриваете строку, в которой последний символ отличается от всех остальных символов (как в примере), то для строки длины N количество вершин в суффиксном дереве всегда будет больше N (корень + по листу на каждый суффикс). Но, естественно, вершин может быть больше, чем N+1. Тем не менее, количество вершин всегда не больше 2N+1. Чтобы в этом убедиться достаточно последовательно вставлять в дерево каждый суффикс: когда вы вставляете суффикс появляется одна или две вершины (лист + вершина, к которой этот лист крепится, если её ещё нет).
В случае произвольной строки ситуация несколько иная: вершин также не больше 2N+1, но может быть и меньше, чем N (например, для строки aaaaaaaaaaa суффиксное дерево содержит всего две вершины).
В тексте я неявно опирался на тот факт, что в дереве с n листьями, в котором у каждой нелистовой вершины есть как минимум два потомка, всегда O(n) вершин. Я не учёл, что это, вообще-то, не очень очевидно.
Если кому-то интересно, сейчас появился алгоритм построения суффиксного дерева по-проще — это модификация старого алгоритма Вейнера. Можно посмотреть тут: habrahabr.ru/post/258121 (с исходником) или тут www.youtube.com/watch?v=q9bPAVSmzfA
Не совсем так. Он онлайновый, но не слева направо, а справа налево. Большинство онлайновых задач, решаемых Укконеном, (но не все) могут быть решены с помощью упрощённого Вейнера на перевёрнутой строке и, наоборот, есть онлайновые задачи, которые могут быть решены онлайново Вейнером на перевёрнутой строке, но непонятно как их решать Укконеном.
Я видел ваш код. Впечатляет, конечно, как вы его удавили, но он объективно ужасен. Приемлемые короткие реализации Укконена — это что-то типа вот этого. Но код там всё равно больше, а главное в коде больше ветвлений (а значит он сложнее для понимания).
Конечно, вы правы. Но здесь задача, как я понимаю, может быть поставлена так: дана довольно длинная строка, в которой периодически ищут по регулярным выражениям какие-то недлинные подстроки. Вместо того, чтобы каждый раз делать проход по всей строке, возможно, может получиться с помощью суффиксного дерева обрабатывать только те части строки, где возможно вхождение регулярного выражения — таких частей может оказаться немного; глупый пример: если первый символ регвыра — буква а, то смотрим только подстроки, начинающиеся с а (фактически, поддерево под символом а). Хотя я понимаю, что это довольно узкая задача.
Спасибо за комментарий. Вы имеете ввиду возможность предварительно построить по тексту суффиксное дерево и затем искать по регулярному выражению не по всей строке, а только в «нужных» ветках дерева, я верно понял? Звучит интересно, но я такого не встречал и сходу не знаю насколько это реализуемо.
Это же и будет алгоритм Дейкстры. По крайней мере тот же вариант, который описан в статье в коде (в текстовом описании алгоритм в статье немного отличается от варианта в коде). Есть еще два варианта Дейкстры: 1 не помещать повторно в кучу то, что там уже находится, а просто выполнять heapifyUp для такого узла из кучи (минусы: куча с heapifyUp есть не в каждой библиотеке и ее придется реализовать самому; поддерживать указатели на узлы из кучи не так просто и ресурсозатратно; плюсы: используем О(n) памяти под кучу, а не О(m)), и 2 вообще изначально положить в кучу все узлы (минусы и плюсы в таком варианте те же)
Бегло прошёлся по бенчмаркам в интернете и, судя по всему, LZMA и его производные даже против deflate (это LZ77 с Хаффманов) дают в 1.5 - 2 раза лучшее сжатие. А против LZW они будут ещё лучше (LZW проигрывает deflate по сжатию, но не так драматически). По-моему это не "сравнимая" степень сжатия. Зависит от сжимаемых данных, конечно, но эти бенчмарки часто довольно репрезентативны. Недавно, кстати, на хабре была хорошая статья на близкую тему: https://habr.com/ru/post/570694/ (там же есть ссылка на один хороший бенчмарк; ещё можно посмотреть http://www.mattmahoney.net/dc/text.html). Много раз уже сталкивался с похожим мнением, что сжатие не важно и важнее скорость. Согласен, есть такие приложения, где это так. Но даже в таком случае LZW далеко не лучший выбор и методы на основе LZ77 (не обязательно LZMA) работаю лучше. Например, zstd с флагом "level 2" (или около того), судя по бенчмаркам, так же эффективен по степени сжатия, как deflate с наилучшим сжатием, но раз в 5 быстрее декодирует. Я уверен, что LZW с Хаффманом/арифметиком декодирует медленнее, чем deflate (LZW для декодирования использует более сложного вида словарь, а deflate просто копирует уже декодированные куски); в интернете пишут, что LZW в 2 раза медленнее декодирует, чем deflate, в некоторых реализациях. Без Хаффмана LZW точно по-быстрее будет, но тоже не факт, что быстрее чем deflate. Так что zstd явно гораздо лучше в этом отношении и чем LZW, и чем deflate.
Я думаю, что это сделано для простоты реализации. LZW - очень простой но при этом эффективный алгоритм, который каждый может реализовать без мудрствований. Но если продолжать вашу мысль и довести её до идеала, то оптимально было бы применять для каждой фразы LZW адаптивное интервальное кодирование или что-то в этом духе. Тогда вся последовательность из z фраз LZW будет занимать всего log2(256) + log2(257) + ... + log2(255 + z) + 1 битов, ну или log2(256) + log2(257) + ... + log2(d) + log2(d) + ... + log2(d) + 1 битов, если размер словаря ограничен d фразами (например, d = 2^16, как обычно полагают). В стандартных реализациях LZW (типа LZC) тоже есть механизмы уменьшения размера кодов для первых фраз (хоть и не такие оптимальные): обычно первые фразы занимают последовательно 9, 10, ..., 16 битов, а потом словарь перестаёт расти. Вполне возможно, что на реальных датасетах этот простой трюк не намного хуже более хитрого оптимального кодирования. Вообще, если нужно сжатие по-лучше, то лучше сразу обращаться к LZMA, а не пытаться тюнить LZW.
Так что очень даже в тему это видео. Что позволено Юпитеру…
Эта модель, придуманная ещё в середине девяностых, несколько более сложна, чем традиционная RAM, поэтому под неё разработано меньше алгоритмов. Так получается, я полагаю, потому что при решении ещё нерешённой задачи люди сначала предпочитают всесторонне рассмотреть её в близкой (и часто практической), но более простой обычной RAM, а уже потом смотрят на кэш/внешнюю память/параллелизм.
Скорее всего вы правы, но всё таки есть немало программистов, которые краем уха где-то слышали об оптимальности LRU при каких-то условиях, что частично оправдывает его использование (смотрите мой комментарий выше).
Для любой константы c>1 и для любой последовательности s обращений к кэшируемым элементам (кэшируемые элементы имеют одинаковый размер) выполняется F_LRU(s) <= c F_OPT(s), где F_LRU(s) и F_OPT(s) — это число непопаданий в кэш на последовательности s для, соответственно, алгоритма LRU с размером кэша n и ясновидящего алгоритма OPT с размером кэша (1 — 1/c)n.
И обратно: для любого алгоритма кэширования A найдётся сколь угодно длинная последовательность s обращений к кэшируемым элементам, такая что F_A(s) >= c F_OPT(s), где F_A(s) — это число непопаданий в кэш на последовательности s для алгоритма A с размером кэша n, а у OPT опять размер кэша (1 — 1/c)n.
В случае произвольной строки ситуация несколько иная: вершин также не больше 2N+1, но может быть и меньше, чем N (например, для строки aaaaaaaaaaa суффиксное дерево содержит всего две вершины).
В тексте я неявно опирался на тот факт, что в дереве с n листьями, в котором у каждой нелистовой вершины есть как минимум два потомка, всегда O(n) вершин. Я не учёл, что это, вообще-то, не очень очевидно.
Надеюсь я смог ответить на ваш вопрос.
Короткую реализацию алгоритма Укконена можно найти тут: codeforces.com/blog/entry/16780?locale=ru
Я видел ваш код. Впечатляет, конечно, как вы его удавили, но он объективно ужасен. Приемлемые короткие реализации Укконена — это что-то типа вот этого. Но код там всё равно больше, а главное в коде больше ветвлений (а значит он сложнее для понимания).