Алгоритм преобразования строк в короткие замены

Question

Я ищу способы детерминированной замены уникальных строк уникальными и оптимально короткими заменами. Таким образом, у меня есть конечный набор строк, и наилучшее сжатие, которого я мог достичь до сих пор, - это алгоритм перечисления, где я упорядочиваю входной набор, а затем заменяю строки перечислением строк символов в расширенном алфавите (a..z , A ... Z, aa ... zz, aA ... zZ, a0 ... z9, Aa ..., aaa ... zaa, aaA ... zaaA, ....).

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

Кто-нибудь знает алгоритм, который имеет подобное сжатие, но не требует знания всех входных строк заранее ?! Например, хеширование не будет работать для меня, так как в зависимости от размера входного набора мне понадобится длина хеша 8-12, чтобы хеши были уникальными, и это было бы слишком долго для замены (в настоящее время строки замены) для моего варианта использования длиной 1-3 символа (<10000 входных строк)). Кроме того, если теоретики среди нас знают, что это пустая трата усилий, мне было бы интересно услышать :-). </p>

Answer 1

«Оптимально короткий» зависит от совокупности строк, из которых взяты ваши образцы.При отсутствии систематической избыточности в совокупности вы обнаружите, что только часть произвольных строк может быть сжата вообще (например, рассмотрите попытку сжатия случайных битовых строк).

Если вы можете сделать предположения о вашейданные, такие как «ожидается, что строки состоят в основном из английских слов», тогда вы можете сделать что-то простое и эффективное на основе частотности букв (например, для английского языка порядок относительной частоты - что-то вроде ETAOINSHRDLUGCY ..., так что вы могли быхотите использовать меньше битов для представления Es и больше битов для представления необычных букв, таких как Q).

Cheers.

Answer 2

Вы можете использовать свою схему перечисления, но отсортированную по порядку, в котором вы впервые встретите входные строки.

Например, первая обработанная вами строка может быть сопоставлена ​​с «a».Следующая отдельная строка будет отображена на «b» и т. Д.

Каждый раз, когда вы обрабатываете строку, вам нужно искать ее, чтобы увидеть, сопоставлена ​​ли она уже.