Çok Desenli Eşleme Algoritması

Question

P1 - Pn.

Bazıları P1 gibi basittir - tüm Pazartesiler, P2 - tüm Salılar; Diğerleri P4 gibi daha karmaşıktır - bu resimde gösterildiği gibi, en kısa sonuç dizesini oluşturmak zorunda tarihleri ​​(V1, V2) özel dizisi vb

tüm çalışma günleri:

Herhangi bir dizi için dizideki tarihleri ​​temsil edecek dize oluşturmanız gerekir. En basit yöntem, 1.5.2013, 2.5.2013, 3.5.2013 gibi bir dizi oluşturmaktır. Ancak sonuç dizesi çok uzun olacaktır.

Önceden tanımlanmış birkaç desen kullanarak daha kısa sonuç dizesi oluşturabiliriz. Sonuç dizesi için

Ben aşağıdaki kuralları kullanın:

Tek tarih formatı: GG.AA.YYYY (10 karakter)
sayımı (tarihleri ​​ve desenler): virgül ve boşluk (2 karakter) tarihlerin
Aralık: GG.AA.YYYY-DD.MM.YYYY (21 karakter) model isimleri
Aralık: Px-Py (5 karakter)
Özel kelimeler: (6 karakterden) hariç

sonuç dizeleri örnekler: P4 kalıbı kullanarak

• V1: 01.05.2013-03.05.2013 hariç

  P4 , 09.05.2013, 10.05.2013, 16.05.2013, 17.05.2013 (80 karakter)

• V1 kullanılarak Pn model:

  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 (

  P1-P3 01.05.2013-19.05.2013, P4 20.05.2013-31.05.2013 (54 charact: en iyi desenler eşleme kullanarak 94 karakter)

• V1 ers)

ana hedefi en kısa sonuç dizesini yaratmaktır. Anladığım kadarıyla, en uygun desen/kalıpları bularak bunu başarabiliriz.

Şu anda, sırt çantası sorununu ve en uzun sık karşılaşılan sorununu uyarlamaya çalışıyorum, ancak doğru yön olup olmadığından emin değilim.

Herhangi bir fikri takdir ediyorum.

---

benim sorunun onun ekstra kısa açıklama için Jan Dvorak-

Teşekkür güncelleme: Amaç tüm önceden tanımlanmış sözlüğü (P1..Pn ve kullanma V tanımlamaktır

kesişme, birleşme ve çıkarma işlemlerine izin verilen ve her işlem ve atomun önceden tanımlanmış bir maliyete (sonuç dizesindeki karakter sayısı) sahip olduğu aralıklar ve tek tarihler.

---

Answer 1

ne istediğimizi çok yakındır nihayet bulundu çözüm. Herkes için

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

Teşekkür katıldı nasıl.

Answer 2

Bu sadece bir öneridir ama tarihlerin dizileri temsil gerçekten kısa dize istiyorsanız, tamamen farklı bir şekilde bu sorunu çözebilir, bu şekilde çok basit ve etkilidir.

1 bir gün "seleceted" temsil edelim ve 0 "unselected" bir gününü temsil edelim, sonra bir ayda özel tarih dizilerini temsil eden bir ikili sayı oluşturabilir, örneğin V1 örneğinde bunu oluşturabilirsiniz ikili sayı:

V1 = 0000011100001110000111110011111 

Yani ilk 0 date 2013/05/01 "seçilmemiş" olduğunu beyan, önümüzdeki 0 Eğer 8 bu numarayı ayırmak durumunda tarih 2013/05/02 vs. "seçilmemiş" olduğunu beyan bit grupları (ikili sayıyı bayt olarak böler) sonra bu bayt dizisini oluşturabilirsiniz:

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

Bu yöntemle V1'i yalnızca 4 bayt kullanarak temsil ediyorsunuz, V1'in 1.5.2013 tarihinde başladığını biliyorsanız, ihtiyacınız olan tek bilgi budur, bu nedenle ilk tarihi de kaydetmeniz gerekir, böylece sadece 3 bayt kullanarak ay ve yıl, bu nedenle örneğin Mayıs 2013 tarih bu şekilde temsil edilebilir:

Mayıs = 5 ay şimdiye ikili 5. ikili 101

2013 Yani 3 kullanan 11111011101 olduğunu bayt sayısını Mayıs 2013'te şu şekilde temsil edebilirsiniz:

0000101 00000111 11011101 
[ 5 ] [  2013  ] 

V1'i bu şekilde temsil edebilirsiniz.

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

Dolayısıyla V1, yalnızca 7 bayt kullanılarak tamamen temsil edilebilir!

bunun yerine bir bayt dizisinin bir dize gerekiyorsa V1 dize V2 durumunda

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

olarak temsil edilebilir, böylece, o zaman bir Base64 Dizesi'ne bu bayt dizisi dönüştürebilirsiniz:

Bu yöntemde, bir ay özel tarih bilgisi dizisinin 7 bayt (veya 64 Dize kullanılıyorsa 12 karakter) olarak gösterilebileceğini biliyorsunuzdur.

Özel dizi bilgilerini yalnızca gereken bir yılda depolamak için: Başlangıç ​​ayı ve yılı için 3 bayt artı 365/8 = 45.625 (46 bayta yuvarlanır), yani 49 bayttır!tüm yıl boyunca, bu 64 üssünde maksimum 69 karakter uzunluğunda !!!

Bu karmaşık bir desen eşleştirme algoritması daha iyi kod bakımı kolay, uygulamak için basit, benim için iyi bir çözüm gibi bu koku. Umarım bu tavsiye şartınıza uygundur. arama uzun zaman sonra