Расширенный поиск по шаблону C # в длинной строке (100-25000 символов)

Question

Позвольте мне начать с этого: я не могу сжать это или что-то подобное.

То, что я пытаюсь сделать, это поиск по довольно большим строкам. Я использую блоки данных, которые выглядят как 0g12h. (0 - это цвет из моей палитры. g - это пробел для деления чисел. 12 означает, что 12 пикселей подряд используют этот цвет. h - для повторного деления чисел.)

У меня проблема в том, что блоки не одинаковой длины. Они варьируются от 0g1h до 2546g115h. По сути, я хочу создать палитру общих шаблонов, чтобы сэкономить место. Скажем, у меня есть: 12g345h19g12h190g11h, встречающееся, по крайней мере, три раза, тогда я мог бы сэкономить место, если бы у меня было что-то вроде: a=12g345h19g12h190g11h в массиве палитр и просто поставить 'a' в строке. Или даже не смотрите на блоки данных, как вы видите в прикрепленном файле, вы получаете g640h тонну раз.

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

Вот отличный пример, поскольку вы можете визуально увидеть шаблон: http://pastebin.com/5dbhxZQK. Я выбрал этот файл, потому что знал, что он будет иметь избыточную избыточность; большинство не так просто.

Answer 1

Вы можете использовать словарь (вероятно, Dictionary<string, int> и просто сколько раз встречается каждый шаблон, затем вернуться и переписать строку с соответствующими заменами.

Однако я бы порекомендовал вам прочитатьНемного об алгоритмах сжатия, то, что вы реализуете, похоже на схему Run Length Encoding (RLE). Затем вы пытаетесь снова сжать поверх этого, рассмотрите, как работает сжатие скользящего окна (что делает GZIP) какальтернатива вашей RLE. Или посмотрите на кодирование Хаффмана как на механизм, уменьшающий объем пространства, необходимого для создаваемых вами кодовых слов (в простых терминах кодирование Хаффмана использует более короткие символы для более частых шаблонов и более длинные символы для менее частых шаблонов в«оптимальный» способ)

Это забавное игровое пространство для игры! Удачи!