Найти префиксную подстроку, которая дает лучшее сжатие

Question

Проблема:

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

Пример:

"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), что слишком дорого.

Answer 1

Использовать лес префиксных деревьев (trie) ...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

тогда мы сможем найти лучший результат и гарантировать его, максимизируя (depth * frequency), который будет заменен вашим escape-персонажем. Вы можете оптимизировать поиск, выполнив сначала поиск максимума по глубине ветки и границы.

От сложности: O (C), как упомянуто в комментарии, для его построения и для нахождения оптимального, это зависит. Если вы закажете частоту первых элементов (O (A) - где A - размер алфавита языков), то вы сможете вырезать больше ветвей и иметь хороший шанс получить сублинейное время.

Я думаю, что это понятно, я не собираюсь это писать - что это домашнее задание? ;)

Answer 2

Ну, первым шагом будет сортировка списка. Затем один проход по списку, сравнение каждого элемента с предыдущим, отслеживание самых длинных 2-символьных, 3-символьных, 4-символьных прогонов и т. Д. Тогда цифра на 20 3-символьных префиксов лучше, чем на 15 4-символьных префиксов.

Answer 3

Я бы попробовал начать с сортировки списка. Затем вы просто переходите от строки к строке, сравнивая первый символ с первым символом следующей строки. Если у вас есть совпадение, вы посмотрите на следующий символ. Вам нужно будет найти способ отслеживать лучший результат на данный момент.