Главная > Словарь
1999

Один из способов экономного хранения текста состоит в том, что текст записывается как последовательность номеров из словаря, содержащего все встречающиеся в тексте слова. Для экономного хранения словаря слова располагают по алфавиту, разбивают на небольшие группы (в каждой не больше m слов), а каждую группу сжимают, используя так называемое сжатие слева: в каждом слове указывается, сколько букв нужно взять из предыдущего слова, а дальше записывается остаток, завершающийся специальным символом. Например, группа

чернила, чернильница, чернильный, чернильными, черт, чертеж, чертежница, чиж

представляется как

0чернила*6ьница*8ый*9ми*3т*4еж*6ница*1иж*

Здесь * – признак конца слова (отдельный байт), а числа – количества букв от предыдущего слова (числа помещаются в один байт). Требуется составить программу, которая, получив число m, количество слов n и упорядоченный список слов, вычислила бы такое разбиение слов на группы (без нарушения алфавитного порядка), при котором сжатая запись словаря имела бы наимньшую длину.

Проводить само сжатие не требуется. Число m не превосходит 32, тем самым ограничивая количество шагов, требуемых для извлечения слова из словаря, а n меньше 30000.

 
Hosted by uCoz