Как превратить список строк в список кортежей, найдя в них самые большие повторяющиеся шаблоны в python3?

Question

Я пытался найти решение своей проблемы в течение некоторого времени, но пока не нашел ни одной хорошей идеи.

У меня есть список больших строк, в которых повторяются некоторые шаблоны символов (без пробелов). Для моих нужд мне нужно уменьшить объем памяти, который занимают эти строки, найдя эти шаблоны и преобразовав список строк в два списка: один список, в котором все шаблоны набраны один раз, и один список, в котором есть кортежи/списки указателей на шаблон list, чтобы исходную строку можно было воссоздать из кортежа.

Например, для списка строк['FOOBAR', 'BARFOO']я хотел бы получить['FOO', 'BAR'], [(0, 1), (1, 0)]

Слова в списке шаблонов должны иметь длину не менее 2 (если у нас нет другого выбора, например, если между двумя повторяющимися шаблонами есть только один символ или вся входная строка имеет длину только 1) - или лучше всего как можно дольше (поскольку адресация также занимает память, поэтому, если какое-то слово встречается один раз, оно должно иметь только один указатель, а не несколько).

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

Ниже я показываю пример скрипта, как это должно работать:

      def getLists(str_list):
    # code here
    return pointers, out_strings


strings = ["FGJohnyRFGDERT", "VBSJohnR", "AAERFGR"]
pointers, out_strings = getLists(strings)
print(pointers, out_strings)
# [(0, 1, 2, 0, 3, 4, 5), (6, 1, 7), (8, 4, 0, 7)]["FG", "John", "yR", "D", "ER", "T", "VBS", "R", "AA"]

Заранее спасибо за помощь! <3

РЕДАКТИРОВАТЬ: кто-то предложил сжатие, такое как zlib. К сожалению, мне нужно распаковать исходные строки в малом объеме памяти и на очень простом языке, который не поддерживает zlib. Таким образом, хотя алгоритм сжатия может быть очень сложным, распаковка должна быть максимально простой.

Answer 1

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

Другая мысль заключается в том, что вы можете изменить структуры данных. Например, вместо a изstr, попробуйтеlistизbytesилиbytearrayс настраиваемым протоколом поиска и сегментации данных.

Во всяком случае, вот пример использования zlib:

      import zlib

compressed_strings = [
    zlib.compress(string.encode(), 9) 
    for string in strings
]
assert strings == [
    zlib.decompress(compressed_string) 
    for compressed_string in compressed_strings
]

Лучший,