Wie Muster optimal in Musterguppen zerlegen?

[himitsu]

Tachchen,

ich versuch es nochmal besser zu erklären.

Es geht im Prinzip um ein Set of WideChar
(genauer geht es um einige DynCharSets, aber dieses ist eigentlich belanglos)

Ich hab praktisch ein Set und möchte dieses möglichst effizient in eines von ein paar vordefinierten "Sets" und den Rest zerlegen.

Es handelt sich dabei um mehrere zusammengesetzte CharSets aus einem RegEx-Ausdruck.

Einfaches Beipsiel: [a-zABC0-9] und dieses soll zu [[:lower:]] + [[:digi:]] + [ABC] ( [ABC[:lower:][:digi:]] ) werden.
(hab für das Beispiel jetzt mal nur die entsprechenden ASCII-Zeichen und nicht alle des ganzen Unicodebereichs verwendet)

Nur blöd, daß es sich hierbei um eine Gruppe von 65-tausend Zeichen und über 30 "Standard"-Sets handelt,
welche auch noch "negiert" enthalten sein können.

[\0-\\:-\x{FFFF}] sollte z.B. [^[:digit:]], bzw. \D ergeben.


Alle Kombinationen durchzuprobieren ist auch nicht so optimal, immerhin kann es mehrere solcher Sets in einem Ausdruck geben und selbst nur ein Durchgang würde ewig dauern.

Bei nur 30 Standardklassen (Sets) würden es schon 60 Klassen ergeben, da jede auch invers enhalten sein kann und dann kann alles zusammen auch nochmal invertiert sein ... macht also hier schonmal 2^120 Kombinationen.

OK, Einiges könnte man ignorieren, da einige Klassen aus anderen zusammengesetzt sind.
z.B. wenn [:alpha:] enthalten ist, dann sind [:lower:] und [:upper:] irrelevant, da sie dort schon drin vorkommen sind, aber dennoch bleiben Unmassen an Möglichkeiten übrig, um alles bruteforcemaßig durchzuprobieren.

Wie könnte ich so also möglichst "einfach"/schnell einen geparsten RegEx-Ausdruck, welcher nur noch die zusammengerechneten und optimierten Werte enthält, wieder zurück in einen String überführen?


Grund:
Eigentlich hatte ich nicht vor das Originalsuchmuster zu speichern und falls nötig Eines aus den zerlegten Daten wieder zusammenzusetzen.

[HERMES]

Wenn du das so machen willst dürfte nur (algorithmisch) schwer exakt zu bestimmen sein, denn so wie das ausssieht (ohne all zulange drüber nachgedacht zu haben) lässt sich das auf Binpackaging oder das Rucksackproblem ( bin mir mit dem namen nicht ganz sichen) - aufjedenfall auf eines der Standardbesipiele für NP vollständige Probleme reduzieren. Eine effiziete Approximation ist möglich, allerdings sind die Algorithmen recht komplex.
Ich weis nicht so genau was du damit vorhast, wenn du etwas "parsen" willst könnte dir das Verfahren zu Tabellenkompression das in der lexikalischen Analyse häufig eingesetzt wird helfen.

[himitsu]

Nja, ich hab hier die Anfänge einer vollständig unicodefähigen RegEx-Klasse (ePCRE),
welche bei Übergabe eines Ausdrucks (als String natrülich) diesen in eine entsprechende Baumstruktur zerlegt, wobei von diesen Charsets nur das Ergebnis im Baum zurückbleibt.
Und der Original-Ausdruck wird aktuell auch noch nicht gespeichert.

Nun kann man jetzt der Klasse z.B. über ein Property Expression diesen Ausdruck übergeben (soweit kein Problem),
aber dieses Property kann man ja "leider" auch auslesen und dafür müßte dann der Baum wieder in einen String zurückverandelt werden.

So war es geplant und es funktioniert auch, aber leider hab ich ganz übersehn, daß es jetzt häßlich wäre, wenn ich jetzt ellenlange [...] Ausdrücke im String hätte
und würde diese gern kürzen.

alleine [[:alnum:]] würde ja so aussehn:

Zitat:

[0-9A-Za-zª²³µ¹ºÀ-ÖØ-öø-ȟȢ-ȳɐ-ʭʰ-ʸʻ-ˁˠ-ˤˮͅͺΆΈ-ΊΌΎ-ΡΣ-ώϐ-ϗϚ-ϳЀ-ҁҌ-ӄӇӈӋӌӐ-ӵӸӹԱ-Ֆՙա-ևא-תװ-ײء-غف-ٕ٠-٩ٰ-ۓە-ۜۡ-ۭۨ۰-ۼܐ-ܬܰ-ܿހ-ްँ-ःअ-हऽ-ौॐक़-ॣ०-९ঁ-ঃঅ-ঌএঐও-নপ-রলশ-হা-ৄেৈোৌৗড়ঢ়য়-ৣ০-ৱਂਅ-ਊਏਐਓ-ਨਪ-ਰਲਲ਼ਵਸ਼ਸਹਾ-ੂੇੈੋੌਖ਼-ੜਫ਼੦-ੴઁ-ઃઅ-ઋઍએ-ઑઓ-નપ-રલળવ-હઽ-ૅે-ૉોૌૐૠ૦-૯ଁ-ଃଅ-ଌଏଐଓ-ନପ-ରଲଳଶ-ହଽ-ୃେୈୋୌୖୗଡ଼ଢ଼ୟ-ୡ୦-୯ஂஃஅ-ஊஎ-ஐஒ-கஙசஜஞடணதந-பம-வஷ-ஹா-ூெ-ைொ-ௌௗ௧-௯ఁ-ఃఅ-ఌఎ-ఐఒ-నప-ళవ-హా-ౄె-ైొ-ౌౕౖౠౡ౦-౯ಂಃಅ-ಌಎ-ಐಒ-ನಪ-ಳವ-ಹಾ-ೄೆ-ೈೊ-ೌೕೖೞೠೡ೦-೯ംഃഅ-ഌഎ-ഐഒ-നപ-ഹാ-ൃെ-ൈൊ-ൌൗൠൡ൦-൯ංඃඅ-ඖක-නඳ-රලව-ෆා-ුූෘ-ෟෲෳก-ฺเ-๎๐-๙ກຂຄງຈຊຍດ-ທນ-ຟມ-ຣລວສຫອ-ູົ-ຽເ-ໄໍ໐-໙ໜໝༀ༠-༩ཀ-ཇཉ-ཪཱ-ཱྀྈ-ྋྐ-ྗྙ-ྼက-အဣ-ဧဩဪာ-ဲံး၀-၉ၐ-ၙႠ-Ⴥა-ჶᄀ-ᅙᅟ-ᆢᆨ-ᇹሀ-ሆለ-ቆቈቊ-ቍቐ-ቖቘቚ-ቝበ-ኆኈኊ-ኍነ-ኮኰኲ-ኵኸ-ኾዀዂ-ዅወ-ዎዐ-ዖዘ-ዮደ-ጎጐጒ-ጕጘ-ጞጠ-ፆፈ-ፚ፩-፱Ꭰ-Ᏼᐁ-ᙬᙯ-ᙶᚁ-ᚚᚠ-ᛪក-ៈ០-៩᠐-᠙ᠠ-ᡂᡄ-ᡷᢀ-ᢩḀ-ẛẠ-ỹἀ-ἕἘ-Ἕἠ-ὅὈ-Ὅὐ-ὗὙὛὝὟ-ώᾀ-ᾴᾶ-ᾼιῂ-ῄῆ-ῌῐ-ΐῖ-Ίῠ-Ῥῲ-ῴῶ-ῼⁿℂℇℊ-ℓℕℙ-ℝℤΩℨK-ℭℯ-ℱℳ-ℹⅠ-Ↄ〆〇〡-〩〸-〺ぁ-ゔァ-ヺㄅ-ㄬㄱ-ㆎㆠ-ㆷ㐀-䶵一-龥ꀀ-ꒌ가-힣豈-鶴ff-stﬓ-ﬗיִײַ-ﬨשׁ-זּטּ-לּמּנּסּףּפּצּ-ﮱﯓ-ﴽﵐ-ﶏﶒ-ﷇﷰ-ﷻﹰ-ﹲﹴﹶ-ﻼ０-９Ａ-Ｚａ-ｚｦ-ｯｱ-ﾝﾠ-ﾾￂ-ￇￊ-ￏￒ-ￗￚ-ￜ]

Aktuell wäre die einfach Lösung, daß ich nun doch den Ausgangsstring speichere und es "keine" Möglichkeit gibt den "Baum" wieder zurückzuverwandeln, aber dann wären auch die schon funktionierenden und hierzugehörenden Codeteile alle umsonst.

[HERMES]

Wenn du das ganze schon in einem Baum hast kannst du den doch einfach traversieren und das Ergebnis davon zurückgeben. Schlieslich hast du ja eine Semantik für deinen Ausdruck durch das erstellen des Baumes festgelegt. Das Ergebnis ist nicht unbedingt schön, die durch den Ausdruck beschriebene Sprache ist aber die gleiche wie des Ursprünglichen. Wenn jeder Ausdruck einen eindeutigen Baum hat kannst du den Originalausdruck (von Whitespace und unnötiger KLammerung abgesehen) wiederherstellen.
Den ursprünglichen Ausdruck zu speichern ist aber am einfachsten. Oder gib einfach einen leeren string zurück.

[himitsu]

Nja, das Problem ist, daß alle "Character Classes" ala [...] und alles Verwandte in dem Baum das selbe Ergebnis liefern.

Und zwar nur noch einen einziges CharSet vom Typ TDynamicCharSet" und es somit keine Infomationen mehr gibt, woraus dieses Set mal zusammengesetzt wurde.
Das Einzige, welches ich direkt erstellen kann, wäre ein eventuell ellenlanger Ausdruck, so wie er oben schonmal gepostet wurde.

[a-zABC0-9]
[A-C\l\d]
[ABC[:lower:][:digit:]]
[abcdefghijklmnopqrstuvwxyzABC0123456789]
usw.

Das ist praktisch alles das Selbe und ich würde jetzt praktisch gern eine möglichst kurze Entsprechung dieser Gruppe erhalten.
Wobei das Erste allerdings wohl die beste/übersichtlichste Lösung wäre.


Aktuell würde ich wohl erstmal den Originalstring mit speichern und diesen dann zurückgeben,
aber es wäre dennoch schön, wenn es hierfür irgendwann mal eine praktikable Lösung gäbe.

[HERMES]

Da hatte ich dich oben falsch verstanden, ichdachte du speicherst symbolische Werte im Baum. Dann wären wir doch beim Optimierungsproblem aus meinem ersten Post...

[himitsu]

Neee, es ist eine Klasse für die Auswertung von erweiterten Perl-Compatible Regular Expressions.
Und in dem Baum wird praktich der ganze Ausdruck entsprechend abgelegt, wobei diese Charsets eben eines er Elemente darstellt.

Nur bei diesem Rucksackproblem hätte ich dann noch einige Probleme:
Mehrere Klasse verfügen über selbe Zeichen, welche aber praktisch jeweils mehrfach vorkommen können,
außerdem entspricht die Anzahl der Zeichen nicht dem Platzverbrauch.

in [\0-\x{FFFF}] würde [:lower:] reinpassen ... wenn ich jetzt alle "Kleinbuchstaben" entferne, dann bleiben zwar weniger Zeichen im restlichen Set zurück, aber der Platzverbrauch würde durch die Optimierungen wie "-" (Gruppen) insgesamt größer.


Hab jetzt mal durchgezählt und ich komme wohl etwa auf 47 Zeichen-Klassen ... sagen wir also einfach mal 50.
Davon noch die Intertierten, das macht dann 100 ... also mindesten 2^100 Kombinationen und das Ganze dann nocheinmal, da ja das ganze Set auch nochmal invertiert sein könnte.

> Das wären dann also 2 * 2^100 Kombinatonen von 8 KB großen Datenblöcken, welche da so verglichen und verrechnet werden müßten.

[HERMES]

Ist wohl eher ein erweitertes Set Coverage ( Mengenüberdeckungsproblem ) als das Rucksackproblem, das macht die Sache aber auch nicht besser.