Множественный алгоритм сопоставления шаблонов

Question

У вас есть несколько шаблонов дат P1 - Pn.

Некоторые из них просты, как P1 - все понедельники, P2 - все вторники; другие являются более сложными, как P4 - все рабочие дни и т.д.

Для пользовательского массива дат (V1, V2), я должен создать кратчайший результирующую строку, как показано на картинке:

Для любого массива мы должны создать строку, которая будет представлять даты в массиве. Самый простой способ - создать строку, например 1.5.2013, 2.5.2013, 3.5.2013 ... Но строка результата будет очень длинной.

Используя несколько предопределенных шаблонов, мы можем создать более короткую строку результата.

Для строки результата я использую следующие правила:

Single Формат даты: ДД.ММ.ГГГГ (10 символов)
перечислений (даты и модель): запятая и пространство (2 символа)
Интервал дат: ДД.ММ.ГГГГ-ДД.ММ.ГГГГ (21 символов)
Интервал имен шаблонов: Px-Py (5 символов)
Специальные слова: кроме (6 символов)

Примеры результатов строк:

• V1 с помощью P4 шаблона:

  P4, за исключением 01.05.2013-03.05.2013 , 09.05.2013, 10.05.2013, 16.05.2013, 17.05.2013 (80 знаков)

• V1, используя шаблон Рп:

  Рп 06.05.2013-08.05.2013, 13.05.2013-15.05.2013, 20.05.2013-24.05.2013, 27.05.2013-31.05.2013 (94 символов)

• V1 с использованием лучших образцов матча:

  P1-P3 01.05.2013-19.05.2013, P4 20.05.2013-31.05.2013 (54 CHARACT ERS)

Основной цель состоит в том, чтобы создать самые короткие строки результата. Насколько я понимаю, мы можем добиться этого, найдя наилучшие совпадающие шаблоны/шаблоны.

В настоящее время я пытаюсь адаптировать проблему ранца и самую длинную общую проблему подпоследовательности, но я не уверен, что это правильное направление.

Буду признателен за любые идеи.

---

обновленный

Благодаря Jan Dvorak за дополнительную краткое описание моей проблемы:

Цель состоит в том, чтобы описать V используя предопределенный словарь (P1..Pn и все интервалы и отдельные даты), где разрешено пересечение, объединение и вычитание, и каждая операция и атом имеют предопределенную стоимость (количество символов в строке результата).

---

Answer 1

После долгого поиска мы наконец нашли решение, которое очень близко к тому, что мы хотим. как участие

http://www.fpz.unizg.hr/traffic/index.php/PROMTT/article/view/1287

Спасибо за все.

Answer 2

Это только предложение, но если вы хотите действительно короткую строку, которые представляют массивы дат, вы могли бы решить эту проблему совершенно по-другому, этот путь очень просто и эффективно.

Позвольте 1 представить день "seleceted" и пусть 0 представляет день "unselected", тогда вы можете построить двоичное число, которое представляет собой настраиваемые массивы дат в месяц, например, для случая V1, вы можете сгенерировать это двоичное число:

V1 = 0000011100001110000111110011111 

Таким образом, первый 0 заявляет, что дата 1.5.2013 является «невыбранной», следующими 0 заявляют, что дата 2.5.2013 является «невыбранной» и т.д. Если вы разделите это число в 8 (деление двоичного числа в байтах), вы можете создать этот массив байтов:

V1(starting in May 1, 2013) = 00000111 - 00001110 - 00011111 - 00111110 (4 bytes) 

С помощью этого метода вы представляете V1, используя всего 4 байта, это единственная информация, которая вам нужна, если вы знаете, что V1 начинается с даты 1.5.2013, поэтому вам также нужно сохранить начальную дату, чтобы вы могли представлять месяц и год, используя только 3 байта, так, например, дата май 2013 может быть представлена ​​следующим образом:

мая = пятый месяц, так что 5 в двоичной системе составляет 101

2013 в двоичном виде 11111011101 таким образом, используя 3 байты вы можете представить в мае 2013 года следующим образом:

0000101 00000111 11011101 
[ 5 ] [  2013  ] 

Таким образом, вы можете представлять V1 как этот

V1= 0000101 - 00000111 - 11011101 00000111 - 00001110 - 00011111 - 00111110 
    [Month] [  Year  ] [  V1 custom array of dates   ] 

Таким образом, V1 может быть полностью представлен с использованием всего лишь 7 байт!

Если вам нужна строка вместо массива байтов, то вы можете преобразовать этот байтовый массив в Base64 String, так V1 может быть представлен в виде строки

V1 in Base64 is Cg+6Dhw+Pg== (using just 12 characters!!) 

В случае V2:

V2 = 0000101 - 00000111 - 11011101 11111111 - 11111111 - 11111111 - 11101110 
    [Month] [  Year  ] [  V2 custom array of dates   ] 

V2 in Base64 is Cg+7////bg== (using just 12 characters again!!) 

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

Чтобы сохранить информацию о настраиваемых массивах за год, вам просто нужно: 3 байта для начального месяца и года, плюс 365/8 = 45,625 (округлено до 46 байт), то есть 49 байт!за весь год, что в базе 64 имеет максимальную длину 69 символов !!!

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