Habr 25+<p>[Перевод] Сжатые структуры данных</p><p>Введение Несколько месяцев назад в поисках идей по ускорению кода я изучал множество научных статей по computer science. Не буду притворяться, что хорошо их понимал, но меня не пугает непонятное, и я готов признать своё невежество 1 . Я обнаружил статью, написанную пятнадцать лет назад 2 , в которой было множество новых для меня концепций. Мне никак не удавалось в них разобраться. Что же делать дальше? Можно искать другие статьи, чтобы они заполнили мои пробелы. Это рискованное предприятие, потому что они могут запутать ещё больше, но избежать этого нельзя. Я нашёл статью с нужной структурой данных, в которой упоминался исходный код с веб-сайта. Код был написан на C++, а я работаю на Rust, но решил, что всё равно стоит на него взглянуть. Однако зайдя на сайт, я не обнаружил там ресурс, поэтому я написал владельцу веб-сайта, который оказался преподавателем computer science. Этот преподаватель ( Гонсало Наварро ) очень тепло меня принял и сразу же ответил мне 3 4 . И только в процессе общения с ним я осознал, что видел его фамилию на множестве статей в этой области. Оказалось, я познакомился с одним из специалистов мирового уровня в области сжатых структур данных (succinct data structure). Невежество может завести очень далеко. Что же такое сжатые структуры данных? Если вы изучали в последние десятилетия computer science, то могли сталкиваться с ними, но мне не доводилось встречаться с ними в процессе работы программистом, а если и доводилось, то я сразу же о них забыл. Но я считаю, что эти структуры данных обладают потрясающими свойствами. Все мы пользуемся массивами и хэш-таблицами 5 , популярны также различные деревья. Нам не нужно полностью понимать их устройство, чтобы эффективно пользоваться их свойствами. А теперь я задаюсь вопросом, почему же люди не используют сжатые структуры данных чаще. Я решил, что стоит немного о них рассказать.</p><p><a href="https://habr.com/ru/companies/ruvds/articles/890232/?utm_campaign=890232" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">habr.com/ru/companies/ruvds/ar</span><span class="invisible">ticles/890232/?utm_campaign=890232</span></a></p><p><a href="https://zhub.link/tags/xml" class="mention hashtag" rel="tag">#<span>xml</span></a> <a href="https://zhub.link/tags/json" class="mention hashtag" rel="tag">#<span>json</span></a> <a href="https://zhub.link/tags/%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F" class="mention hashtag" rel="tag">#<span>деревья</span></a> <a href="https://zhub.link/tags/abstract_syntax_tree" class="mention hashtag" rel="tag">#<span>abstract_syntax_tree</span></a> <a href="https://zhub.link/tags/ast" class="mention hashtag" rel="tag">#<span>ast</span></a> <a href="https://zhub.link/tags/%D0%B4%D0%BD%D0%BA" class="mention hashtag" rel="tag">#<span>днк</span></a> <a href="https://zhub.link/tags/%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D0%B5_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85" class="mention hashtag" rel="tag">#<span>сжатие_данных</span></a> <a href="https://zhub.link/tags/ruvds_%D0%BF%D0%B5%D1%80%D0%B5%D0%B2%D0%BE%D0%B4%D1%8B" class="mention hashtag" rel="tag">#<span>ruvds_переводы</span></a></p>