Задачка

[antilamer]

Пусть хочется хранить в памяти большое количество строк среднего размера (например, несколько миллионов строк по 10-20кб). Известно:
0) Хочется сэкономить память и хранить каждую строку как можно более сжатой.
1) Набор всё время меняются: добавляются новые строки, удаляются старые
2) Каждая строка сама по себе сжимается, но не очень
3) Многие строки очень похожи друг на друга (но есть несколько "классов эквивалентности"); при сжатии нескольких строк сразу, сжатие получилось бы в несколько раз лучше.

Иными словами, хочется реализовать какой-то вот такой интерфейс:

interface CompressedSet {
Handle Add(String s);
String Get(Handle h);
void Release(Handle h); // Get(h) will not happen again
}

Как быть?

Приходит в голову следующее:
1) Хранить небольшими коллективно сжатыми группами по примерно K: Add находит неполную группу и пересжимает ее с добавлением этой строки; Get разжимает всю группу и достает из нее нужное; Release пересжимает группу без этой строки.
2) Завести какой-нибудь shared dictionary-based компрессор, у которого dictionary с подсчётом ссылок. Есть такие?

P.S. Задачка скорее праздная; некоторые из предположений в реальности нарушаются. Но интересно же!