Найдите префиксную подстроку, которая обеспечивает наилучшее сжатие
-
02-07-2019 - |
Вопрос
Проблема:
Получив список строк, найдите подстроку, которая, если вычесть ее из начала всех строк, где она совпадает, и заменить управляющим байтом, дает наименьшую общую длину.
Пример:
"foo"
, "fool"
, "bar"
В результате получается:"foo" в качестве базовой строки со строками "\0"
, "\0l"
, "bar"
и общая длина 9 байт. "\0"
является управляющим байтом.Сумма длины исходных строк равна 10, поэтому в данном случае мы сохранили только один байт.
Наивный алгоритм выглядел бы следующим образом:
for string in list
for i = 1, i < length of string
calculate total length based on prefix of string[0..i]
if better than last best, save it
return the best prefix
Это даст нам ответ, но это что-то вроде O ((n* m) ^ 2), что слишком дорого.
Решение
Используйте лес префиксных деревьев (trie)...
f_2 b_1
/ |
o_2 a_1
| |
o_2 r_1
|
l_1
тогда мы сможем найти наилучший результат и гарантировать его, максимально увеличив (depth * frequency)
который будет заменен вашим экранирующим персонажем.Вы можете оптимизировать поиск, сначала выполнив поиск по ветви и ограниченной глубине для получения максимального значения.
О сложности:O (C), как упоминалось в комментарии, для его построения и для нахождения оптимального, это зависит.Если вы закажете частоту первых элементов (O (A) - где A - размер алфавита языков), то вы сможете вырезать больше ветвей и иметь хорошие шансы получить сублинейное время.
Я думаю, это ясно, я не собираюсь это описывать - что это за домашнее задание?;)
Другие советы
Я бы попробовал начать с сортировки списка.Затем вы просто переходите от строки к строке, сравнивая первый символ с первым символом следующей строки.Как только у вас будет совпадение, вы посмотрите на следующий символ.Вам нужно было бы разработать способ отслеживания наилучшего результата на данный момент.
Что ж, первым шагом было бы отсортировать список.Затем один проход по списку, сравнивая каждый элемент с предыдущим, отслеживая самые длинные 2-символьные, 3-символьные, 4-символьные и т.д. прогоны.Тогда цифра в 20 3-символьных префиксах лучше, чем в 15 4-символьных префиксах.