Algorytm dopasowania wielu wzorów

Question

Należy wziąć pod uwagę kilka wzorów dat P1 - Pn.

Niektóre z nich są proste jak P1 - wszystkie poniedziałki, P2 - we wtorki; inne są bardziej skomplikowane jak P4 - wszystkie dni robocze itp

dla niestandardowych tablicy dat (V1, V2) Mam do tworzenia najkrótszą wynik ciąg, jak to jest pokazane na zdjęciu:

Dla każdej tablicy musimy utworzyć ciąg, który będzie reprezentował daty w tablicy. Najprostszą metodą jest utworzenie ciągu znaków takiego jak 1.5.2013, 2.5.2013, 3.5.2013 ... Ale ciąg wyniku będzie bardzo długi.

Używając kilku predefiniowanych wzorów możemy stworzyć krótszy ciąg wyników.

dla wyniku ciąg używam następujących zasad:

data pojedynczy format: DD.MM.YYYY (10 znaków)
Wyliczanie (daty i wzory): przecinek i spacja (2 znaki)
przedział dat: DD.MM.YYYY-DD.MM.YYYY (21 znaków)
Interval nazw wzór: PX-Py (5 znaków)
słowa szczególne: oprócz (6 znaków)

Przykłady ciągów Wynik:

• V1 wykorzystujące P4 wzoru:

  P4 wyjątkiem 01.05.2013-03.05.2013 , 09.05.2013, 10.05.2013, 16.05.2013, 17.05.2013 (80 znaków)

• V1 pomocą Pn wzór:

  Pn 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 znaków)

• V1 za pomocą najlepsze dopasowanie wzorów:

  01.05.2013-19.05.2013 P1-P3, P4 20.05.2013-31.05.2013 (54 znak, co ers)

Głównym celem jest stworzenie najkrótszą wynik ciąg. Jak rozumiem, możemy to osiągnąć, znajdując najlepszy pasujący wzór/wzory.

Obecnie próbuję dostosować problem z plecakiem i najdłuższym typowym problemem podciągu, ale nie jestem pewien, czy jest to właściwy kierunek.

Byłbym wdzięczny za wszelkie pomysły.

---

aktualizowane

Dzięki Jan Dvorak za dodatkową krótki opis mojego problemu:

Celem jest opisanie V przy użyciu predefiniowanego słowniku (P1..Pn i wszystkie interwały i pojedyncze daty), w których przecięcie, unifikacja i odejmowanie są dozwolone, a każda operacja i atom mają wstępnie zdefiniowany koszt (liczba znaków w ciągu wynikowym).

---

Answer 1

Po długim czasie poszukiwań znaleźliśmy rozwiązanie, które jest bardzo zbliżone do tego, czego chcemy. jak udział

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

Dzięki za wszystko.

Answer 2

To tylko sugestia, ale jeśli chcesz naprawdę krótki ciąg, który reprezentuje tablice dat, można rozwiązać ten problem w zupełnie inny sposób, w ten sposób jest bardzo prosty i skuteczny.

Niech 1 oznacza dzień "seleceted" i niech 0 oznacza dzień "niewybrany", wtedy możesz skonstruować liczbę binarną, która reprezentuje niestandardowe tablice daty w miesiącu, na przykład dla przypadku V1, możesz to wygenerować liczba binarna:

V1 = 0000011100001110000111110011111 

Tak więc pierwszą 0 oznaczają, że data 5.01.2013 jest „odznaczone”, następnego 0 oznaczają, że data 2.05.2013 jest „odznaczone”, itd. Jeśli oddzielić tę liczbę w 8 bits groups (dzieląc liczbę binarną w bajtach), możesz utworzyć tablicę bajtów:

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

Dzięki tej metodzie reprezentujesz V1 używając tylko 4 bajty, to jedyne informacje, których potrzebujesz, jeśli wiesz, że V1 rozpoczyna się w dniu 1.5.2013, więc musisz również zapisać datę początkową, aby móc reprezentować miesiąc i rok za pomocą zaledwie 3 bajty, więc na przykład data maja 2013 można przedstawić w następujący sposób:

maja = 5-ty miesięcy więc 5 binarnie jest 101

2013 w formacie binarnym jest 11111011101 więc stosując 3 bajtów można reprezentować w maju 2013 r. jako:

0000101 00000111 11011101 
[ 5 ] [  2013  ] 

Możesz więc reprezentować V1 jako ten

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

Tak więc V1 może być w pełni reprezentowany przy użyciu tylko 7 bajtów !!

Jeśli potrzebujesz String zamiast tablicy bajtów, a następnie można przekonwertować tej tablicy bajtów do Base64 String więc V1 może być reprezentowany jako ciąg

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

W przypadku 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!!) 

Dzięki tej metodzie wiesz, że niestandardowa tablica informacji o datach może być reprezentowana w 7 bajtach (lub 12 znaków, jeśli używasz 64 podstawowego łańcucha).

Aby zapisać niestandardowe informacje o tablicy w ciągu roku, wystarczy: 3 bajty na początek miesiąca i rok, plus 365/8 = 45,625 (zaokrąglone do 46 bajtów), czyli 49 bajtów !!przez cały rok, że w bazie 64 ma maksymalną długość 69 znaków !!!

Jest to proste do wdrożenia, łatwe w utrzymaniu w kodzie, lepsze niż skomplikowany algorytm dopasowywania wzorów, ten zapach jest dla mnie dobrym rozwiązaniem. Mam nadzieję, że ta rekomendacja pasuje do waszych wymagań.