Попытка выяснить основной алгоритм поиска паттернов - PullRequest
Новая
       8

Попытка выяснить основной алгоритм поиска паттернов

2 голосов
/ 21 июля 2011

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

Я хочу иметь возможность разбить эти данныена следующие виды фрагментов:

d (повторяется 1x) ab (повторяется 3x) a (1x) cda (3x) b (1x)

Я знаком с базовым кодированием длины серии, но я действительно не знаю, как это сделать, когда длина «вещи» может быть переменной (в моем примере, cda - это 3 порции данных, но d - это одна порция).Имею ли я какой-то смысл?Буду признателен за вашу помощь.

Ответы [ 2 ]

1 голос
/ 21 июля 2011

Основная трудность здесь заключается в «жадности» алгоритма и его неоднозначности.Учитывая ваш пример, каково правило, чтобы программа не представляла вашу строку как:

d X 1 ababab X 1 <<<<< ----- вот проблемаcda X 1 b X 1 </p>

Или еще хуже: d X 1 abababcdab X 1

Вы понимаете, о чем я.Таким образом, вам нужно установить набор правил, которым будет следовать алгоритм, и тогда код будет писать сам.Чтобы получить представление об этом, вы можете попробовать взглянуть на некоторый код синтаксического анализа регулярного выражения в grep.c, хотя он может быть более продвинутым, чем то, что вам нужно.

Для начала рассмотрим алгоритм, который: 1Ограничивает, насколько далеко он будет сканировать (т. Е. Устанавливает максимальную длину подстроки). 2. Отдает предпочтение более длинным подстрокам, в зависимости от # 1

Например, возьмите «aaaaaaaaaaaaaaaa» (то есть 16 a).Это может быть: a X 16 aa X 8 aaaa X 4 aaaaaaaa X 2 aaaaaaaaaaaaaaaa X 1

Если вы установите максимальную длину совпадения 4 и предпочитаете самое длинное совпадение, то ответ однозначен: aaaa X 4Теперь вы можете написать алгоритм.

0 голосов
/ 21 июля 2011

Основная трудность здесь заключается в «жадности» алгоритма и его неоднозначности. Учитывая ваш пример, каково правило, чтобы программа не представляла вашу строку как:

Д Х 1 Ababab X 1 CDA X 1 б х 1

Или еще хуже: д х 1 abababcdab X 1

Вы понимаете, о чем я. Таким образом, вам нужно установить набор правил, которым будет следовать алгоритм, и тогда код будет писать сам. Чтобы получить представление об этом, вы можете попробовать взглянуть на код синтаксического анализа регулярного выражения в grep.c, хотя он может быть более продвинутым, чем вам нужно.

Для начала рассмотрим алгоритм, который:

  1. Ограничивает, насколько далеко он будет сканировать (т.е. устанавливать максимальную длину подстроки)
  2. Предпочитает более длинные подстроки, в зависимости от # 1

Например, возьмите "aaaaaaaaaaaaaaaa" (что составляет 16 а).
Это может быть любой из них:

X 16

AA X 8

аааа х 4

аааааааа Х 2

aaaaaaaaaaaaaaaa X 1

Если вы установите максимальную длину совпадения 4 и отдадите предпочтение самому длинному совпадению, тогда ответ будет однозначным: aaaa X 4. Теперь вы можете написать алгоритм.

Кстати, комментарий к алгоритму LZW (Lempel-Ziv-Welch) точный; это то, что делает этот алгоритм, хотя он динамически создает словарь по мере сканирования и пытается выразить более поздние элементы в терминах более ранних. Например:

аааааааааааааааа (опять 16 из них)

= bbbbbbbb (где b = aa)

= cccc (где c = bb)

= dd (где d = cc)

= е (где е = дд)

Это не совсем то, как работает LZW, но вы поняли.

...