Архив форумов ЦИТФорума

[ret]

Может кто подскажет как можно хранить (компактно) в оперативной памяти большие объемы строковых данных организованных иерархически (т.е. в фразах можно выделить лексемы и символ разделителя, и лексемы в разных фразах могут повторяться)?
Ограничения следующие:
1) Словарь лексем (алфавит) неограничен ни по колличеству уникальных лексем ни по максимальной длине лексемы. Так же неограничено количество фраз.
2) Исходная фраза должна быть в объекте представлена некоторым компактным кодом (или ссылкой) на путь, по которому из лексем можно восстановить исходню фразу
2) Код фразы, который хранится в объекте, формируется один раз и неможет быть изменен впоследствии.
3) Фразы поступают последовательно и кодирование должно быть последовательным. Т.е. на вход некоторого кодера поступает фраза, она разбивается на лексемы и создается объект в котором фраза будет выражена некоторым компактным кодом, и этот код уже нельзя будет изменять. При этом, что из себя представляют последующие фразы неизвестно, как и неизвестно то сколько их вообще может быть. Т.е. получить информацию сразу о всех фразах нельзя.

Строить алгоритм в лоб на основе списка не проходит так как отсутствие каких либо ограничений приводит разрастанию указателей.

Ограничение можно принять одно - если в качестве алфавита взять не лексему (которая когда то там прдет и будет уникальной и соответственно должна будет быть добавлена в алфавит), а обычные символы ascii и на основе каких-то априорных данных построить дерево кодирования фраз. Но это не подходит. Скорее подход должен напоминать хранение интернетовских URL

Киньте какие нибудь ссылки или какие нибудь идеи.

[Sclis]

и что? пространные рассуждения о бесконечности вселенной Ничего не ограничено... как бы даже кластер суперкомпьютеров с навороченным распределенным сервером баз данных имеет свои ограничения
когда ты говоришь "количество лексем не ограничено" это ты имеешь в виду, что "может быть аж 12 штук" или "... аж сто тысяч милиёнов"?
за каким-то количественным пределом действительно придется переходить к базе данных. ну база своими способами может полностью хранится в оперативке, не стоит пытаться все с нуля тут писать.
Кэшируй поступающую информацию, а потом обрабатывай ее не спеша.
Так что, если все действительно сильно большое, то наверно ты придешь к базам данных.
есть любопытная книга "Паттерны проектирования" Эрих Гамма и др. там в схожей (как мне кажется) ситуации предлагают использовать паттерн "приспособленец".

[kolobok0]

Не знаю на сколько буду оригинален, но когда то решал похожую задачу. Из базы данных (это номенклатор товара был) в 2 мега - ужал в свой быстрый для доступа формат - где то до 60 килл. Идея состояла в том, что пришедшие на вход фразы есть не сгинерённые бесконечные комбинации, а просто введённые одним лицом (либо группой лиц) данные. всё... Вроде это утверждение имеет жизнь )) Как хранить - ну тут дело вкуса и цвета.. Как разбивать тут есть нюансы ))

удачи.
(круглый)