Лаконічна структура даних () — в інформатиці це структура даних, яка використовує обсяг пам'яті, «близький» до теоретико-інформаційної нижньої межі, але при цьому (на відміну від інших стиснених подань) усе ще забезпечує ефективне виконання операцій запитів.
Це поняття було вперше запропоноване Джейкобсоном для кодування бітових векторів, (непозначених) дерев і планарних графів. На відміну від загальних алгоритмів стиснення без втрат, лаконічні структури даних зберігають можливість працювати з ними безпосередньо, без попереднього розпакування. Пов'язаним є поняття стисненої структури даних (), оскільки розмір збережених або закодованих даних у цьому випадку також залежить від конкретного вмісту самих даних.
Якщо — теоретико-інформаційна кількість біт необхідна для збереження даних, то представлення цих даних називається: неявним якщо воно займає біт, наприклад, , лаконічним якщо воно займає біт, наприклад, чи , компактним якщо воно займає біт, наприклад, .
Приклади Неявними структурами даних є нуль-термінований рядок, вектор, купа. Часто зміни в неявних структурах даних вимагають значних перестановок, як от в купі.
Лаконічними структурами є зубчастий масив, геш-таблиця.
Лаконічні індекси Словники з лаконічними індексами, які також називають rank/select словниками, є лаконічною структурою, яка може використовуватись для представлення бінарних дерев, -арних дерев, мультимножин, суфіксних дерев та суфіксних масивів. Основною їх задачею є збереження підмножини універсальної множини , яку задано бітовим масивом де iff Лаконічні індекси підтримують звичайні операції (пошук, вставка/видалення), а також спеціальні операції: — повертає кількість елементів рівних до позиції ; — повертає позицію -ого повторення значення ; де .
Існує просте представлення яке використовує біт (початковий бітовий масив та додаткових біт), що підтримує виконання rank та select за логарифмічний час.
Ідея полягає в рекурсивному поділі масиву на дрібніші масиви до деякої малої величини, для якої зберігатимуться обчислені значення rank.
Лаконічні геш-таблиці Аналогічним чином обчислюється отримальна довжина геш-ключа для статичної таблиці.
Примітки