Такой вопрос строковый индекс размеры строк от 0 до 256 символов, индекс реализован на B+ Tree, и строки упорядоченны через порядковое сравнение с использованием функции wcscmp, сейчас индекс сжимается по средством использования zlib, но возможно есть какие то схемы сжатия которые бы учитывали что строки упорядоченны и можно как то сжимать "положительную" "разницу"
Здравствуйте, SL, Вы писали:
SL>Такой вопрос строковый индекс размеры строк от 0 до 256 символов, индекс реализован на B+ Tree, и строки упорядоченны через порядковое сравнение с использованием функции wcscmp, сейчас индекс сжимается по средством использования zlib, но возможно есть какие то схемы сжатия которые бы учитывали что строки упорядоченны и можно как то сжимать "положительную" "разницу"
Первое, что приходит в голову, это префиксное сжатие внутри страниц. Словарь префиксов фиксированной длины и ссылки на него в элементах.
Можно еще Хаффмана попробовать, но оверхед может оказаться неприемлемым.
Здравствуйте, SL, Вы писали:
SL>Такой вопрос строковый индекс размеры строк от 0 до 256 символов, индекс реализован на B+ Tree, и строки упорядоченны через порядковое сравнение с использованием функции wcscmp, сейчас индекс сжимается по средством использования zlib, но возможно есть какие то схемы сжатия которые бы учитывали что строки упорядоченны и можно как то сжимать "положительную" "разницу"
чебоксары
чебурашки
чебуреки
человеки
1) общие префиксы смежных слов — можно закодировать длиной префикса
чебоксары
3 урашки
5 еки
2 ловеки
— тут и сокращение длины последовательности, и сокращение разрядности этого знакоместа (вместо wchar_t имеем byte, потому что размер строки <=256)
2) строгое возрастание первого несовпадающего символа — можно закодировать дельтой
чебоксары
3 5 рашки
5 5 ки
2 11 овеки
— это не бог знает какой выигрыш, но чуток энтропию поубавим (как минимум, на 1 бит, а то и опять до байта доведём)
Здравствуйте, antropolog, Вы писали:
A>Здравствуйте, SL, Вы писали:
A>dawg data structure
Вроде то что надо, почитал теорию, посмотрел ряд реализаций https://github.com/chalup/dawggenerator, единственное что у меня "динамика" строки могут добавляться, удаляться, изменяться, а в статьях что я читал и в реализациях рассматривается "статический" случай и алгоритмы в два прохода, на первом строиться префиксное дерево, на втором происходит минимизация.
Мне не совсем подходит такая реализация и при добавлении новой строки нужно сразу искать "минимальный путь", с учетом ограничений ациклического направленного графа, и если не найден "путь", добавлять вершины.
Однопроходную имплементацию лучше взять здесь: https://code.google.com/archive/p/dawgdic/ но в любом случае здесь всё запекается медленно и в статику.
SL>Мне не совсем подходит такая реализация и при добавлении новой строки нужно сразу искать "минимальный путь", с учетом ограничений ациклического направленного графа, и если не найден "путь", добавлять вершины.
Обычно есть "большой" статичный словарь и "маленький" словарь исправлений. Статичный словарь запекается в dawg, а словарь исправлений — обычное prefix tree ( или в вашем случае даже можно взять уже готовую b-tree реализацию ). В теории можно в бекграунде перезапекать периодически dawg с учётом словаря исправлений, но обычно dawg-словарь на несколько десятичных порядков больше по количеству элементов, так что подобным процессом никто не заморачивается (либо это ооооочень редкая процедура ).
Здравствуйте, SL, Вы писали:
SL>Добрый день
SL>Такой вопрос строковый индекс размеры строк от 0 до 256 символов, индекс реализован на B+ Tree, и строки упорядоченны через порядковое сравнение с использованием функции wcscmp, сейчас индекс сжимается по средством использования zlib, но возможно есть какие то схемы сжатия которые бы учитывали что строки упорядоченны и можно как то сжимать "положительную" "разницу" https://blogs.oracle.com/DBStorage/entry/compressing_your_indexes_index_key:
Index Key Compression is perhaps one of the oldest compression features within the Oracle database, released with Oracle 8.1.3
Перекуём баги на фичи!
