複数パターンマッチングアルゴリズム

Question

日付P1〜Pnのパターンがいくつかあるとします。

いくつかのものはP1のようにシンプルです - すべての月曜日、P2 - すべての火曜日;他の人は、P4のような、より複雑なもの - それは絵に示されるように、私は、最短結果の文字列を作成する必要があります日付（V1、V2）のカスタムアレイの場合など

すべての営業日：

任意の配列に対して、配列内の日付を表す文字列を作成する必要があります。最も簡単な方法は、1.5.2013,2.5.2013,3.5.2013 ...のような文字列を作成することですが、結果の文字列は非常に長くなります。

事前定義されたいくつかのパターンを使用して、より短い結果文字列を作成できます。

シングル日付フォーマット：DD.MM.YYYY （10文字）
列挙（日付とパターン）：カンマとスペース（2文字）私は次の規則を使用した結果の文字列の場合

日付の間隔：DD.MM.YYYY-DD.MM.YYYY （21文字）
パターン名の間隔：PX-Pyを（5文字）
の 特別な単語：（6文字）を除い

結果文字列の例：P4のパターンを使用して

• V1：01.05.2013-03.05.2013を除く

  P4 、09.05.2013、10.05.2013、16.05.2013、17.05.2013 （80文字）

• V1使用PNパターン：

  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：最良パターンマッチを使用して94文字）

• V1 ERS）

主な目標は、最短の結果の文字列を作成することです。私が理解しているように、最良のパターン/パターンを見つけることによってこれを達成することができます。

現在、私はナップザックの問題と最も長い共通のサブシーケンスの問題を適応しようとしていますが、正しい方向であるかどうかはわかりません。

私は任意のアイデアに感謝します。私の問題の彼の余分な短い説明のため月ドヴォルザークへ

---

更新

ありがとう：

目標は、事前に定義された辞書（P1..Pnとすべてを使用してVを記述することですインターバル、および減算がすべて許可され、各操作およびアトムには事前定義コスト（結果文字列の文字数）があります。

---

Answer 1

私たちは最終的に私たちが望むものに非常に近い解決策を見つけました。

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

すべてのおかげでは、どのように参加しました。

Answer 2

これは単なる提案ですが、あなたは、日付の配列を表現本当に短い文字列をしたい場合、あなたは全く異なる方法でこの問題を解決することができ、この方法は非常に簡単で効率的です。

1は "seleceted"の日を表し、0は "選択されていない"日を表すとすると、月のカスタム日付配列を表す2進数を構成することができます。進数：

V1 = 0000011100001110000111110011111 

だから、最初の0は、日付2013年5月1日は「未選択」であることを表し、次の0は、あなたが8でこの番号を区切る場合は、日付2013年5月2日にはなど、「未選択」であることを表しますバイトグループ（2進数をバイトで割ったもの）であれば、このバイト配列を作成できます。

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

この方法では、V1をわずか4バイトで表していますが、これはV1が1.5.2013の日付から開始することを知っている場合に必要な情報です。したがって、最初の日付も保存する必要があります2013年5月の日付は、このように表現することができるインスタンスのように、ちょうど3バイトを使用して、月、年、：

月=第五の月のようにバイナリで5は、バイナリで101

2013では、SO 3を使用して11111011101 です2013年5月には次のように表すことができます：

0000101 00000111 11011101 
[ 5 ] [  2013  ] 

このようにV1を表すことができます

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

だから、V1はちょうど7バイトを使って完全に表現することができます!!

あなたの代わりにバイト配列の文字列が必要な場合V1は、文字列V2の場合

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

として表すことができるので、あなたは Base64で文字列にバイト配列に変換することができます。

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

このメソッドを使用すると、1か月のカスタム日付配列を7バイト（または基本64文字列を使用する場合は12文字）で表すことができます。

必要な年にカスタムアレイ情報を保存する： 開始年月の3バイトに365/8 = 45.625（46バイトに四捨五入）、つまり49バイト！一年を通して、ベース64の最大長は69文字です!!!

これは実装が簡単で、コードの管理が容易で、複雑なパターンマッチングアルゴリズムより優れています。この匂いは私にとって良い解決策です。私はこの勧告があなたの要求に合うことを願っています。