Archief - [PROG]Java Maximum lengte van reguliere expressies

Hallo,

Ik moet voor mijn eindwerk een soort van decodering maken voor bestanden met ASCII karakters (gelegen tussen 31 en 127 decimaal, dus speciale tekens zoals ACK, DEL, CARRIAGE RETURN, e.a. komen er niet in voor). Ik maak hiervoor gebruik van reguliere expressies.

A.d.h.v. een beschrijving in XML worden patronen gegenereerd voor bepaalde onderdelen in een bestand. Die patronen kunnen enorm lang worden. Het langste patroon heeft een lengte van 22390 karakters. En nu komt het probleem: wanneer de decoder dit patroon moet vinden in uitgelezen gegevens, dan slaagt hij gewoon vast! Een patroon van 17634 karakters lang wordt dan weer probleemloos gevonden.

Ik heb al hier al 12 verschillende beschrijvingen gemaakt voor 12 verschillende types van bestanden en daarbij lukt de decodering probleemloos. Enkel bij dit ene bestand met dat lange patroon in slaagt de decoder compleet vast, dus was mijn vraag of er een maximum lengte staat op reguliere expressies?

MVG, horse_99.

Edit

Ik heb net dit gevonden:

http://mail.python.org/pipermail/python-list/2006-January/321624.html zei:

> I have a regular expression that is approximately 100k bytes. (It is
> basically a list of all known norwegian postal numbers and the
> corresponding place with | in between. I know this is not the intended
> use for regular expressions, but it should nonetheless work.

Err. No.

A while back it was established in this forum that re's per design can have
a maximum of 99 match groups ... I suspect that every "|" silently consumes
one match group.

Klik om te vergroten...

Als dit waar is zit ik wel met een probleem, want het langste patroon bevat zo'n 12000 match groups.

Edit

Correctie: 1544 match groups in dat lange patroon , maar dan is het nog boven de 99 . Maar dit blijkt eigenlijk geen probleem want het patroon van 17634 karakters heeft 1216 match groups en werkt wel.

Eerlijk gezegd snap ik heel weinig van je uitleg en je probleem, zou je jezelf wat kunnen verduidelijken?

lengte doet er denk ik niet toe

wat belangerijker is is dat je genoeg plaats zal moeten hebben voor je matches.

Ma decoderings algoritmen worden niet echt vaak gedaan via regexes. Als je het toch nodig hebt kan je (imho) beter je specifieke regex simuleren met uw eigen state machine en on the fly decoderen ipv eerst alles op te halen :/.

Okee ik zal mezelf wat verduidelijken, want mijn uitleg trekt inderdaag op niets.

Ik moet bestanden kunnen verwerken waar meetgegevens instaan. In een bestand zit één data header en meerdere data records. Het is de bedoeling dat je met een Data Description Language die structuur kan beschrijven. Ik maak hiervoor gebruik van XML. Een beschrijving van één onderdeel in een bestand ziet er bijvoorbeeld zo uit:


Dit is nu een heel simpele beschrijving: <block> is een onderdeel in een bestand, met daarin de velden die in dat onderdeel zitten. De naam van de tag definieert het type, tussen de tags staat de naam van het veld. Het attribuut length geeft de lengte aan in bytes dat het veld inneemt.

A.d.h.v. die tag namen die het type aangeven worden dus patronen gegeneerd, dat uiteraard overeenkomt met hoe zo'n type er uit kan zien. Vervolgens worden alle velden samengesteld tot één groot patroon en het is dat patroon waarmee wordt gewerkt. Bovenstaand <block> geeft bijvoorbeeld dit patroon:

"^(\d{2}-\d{2}-\d{2})(\d{2}:\d{2})( *\d{1,4})( *\d{1,4})$"

De kleuren verduidelijken hoe het overeenkomt met bovenstaand <block>. Vervolgens wordt er een lijst van die <block> patronen constant gezocht in een bestand en zo worden velden gedecodeerd. Ik hoop dat het nu wat duidelijker is .

Dit was nu een simpel voorbeeld, maar in de werkelijkheid kunnen die patronen redelijk groot worden (dat van 20000+ karakters heb ik ondertussen vereenvoudigt tot een van 10000- karakters). Probleem is dat zelfs dit verkorte patroon nog altijd niet werkt, daarom vroeg ik mij een beetje af of ik niet aan de grens zat van een maximum lengte van een reguliere expressie.

killgore, wat bedoel je precies met regex simuleren?

Je krijgt dus een bestand dat je moet 'decoderen' (=data uithalen), de structuur van de verschillende onderdelen van het bestand is je gegeven door een xml beschrijving ervan. Die xml beschrijving gebruik je dan om een (regex) patroon op te stellen. En met dat regex patroon haal je de data uit je bestand. Juist?

Jouw probleem stelt zich doordat de regex patronen afgeleid uit de xml beschrijvingen van de bestandsonderdelen te groot worden. Juist?

Indien 2x juist: Kan je niet de verdeel en heers techniek toepassen? Je bestand opdelen in kleinere stukjes die zeker bij elkaar horen, of niet direct een zo specifiek patroon op je bestand toepassen, maar een meer algemeen, en hetgeen het algemene patroon dan herkent apart met specifieke patronen aanpakken? Je probleem kleiner maken zodat het wel vlot oplosbaar wordt.

Hydra, je hebt gelijk over het eerste deel, het tweede weet ik nog altijd niet zeker. Ik vind op het internet niets over een maximum lengte voor reguliere expressies in Java, dus ik denk dat er geen (?) is. Ik heb mijn patronen voor integers nu simpeler gemaakt, zodat het patroon voor die 3088 bytes nu nog 9266 karakters lang is.

Elke integer definitie levert dit patroon op: ([/]{9})|( *\d{1,9} *).

(Opmerking: allemaal schuine strepen = overload, m.a.w. de werkelijke waarde past niet binnen het lengte van het veld, dit wordt omgezet naar 999999999. Spaties voor of na het getal kunnen voorkomen.)

Dit blijft problemen opleveren. Een reeks van 304 integers wordt gematched en een reeks van 386 integers niet. Ik heb dit zelfs getest door het fragment van 3088 bytes uit het bestand te knippen en apart proberen te matchen.

Maar, soit. In de 8 weken stage die ik al heb gedaan, heb ik al geleerd dat er vroeg of laat wel een oplossing uit de bus zal komen .

Hydra, wat je daar als laatste vermeldt is trouwens nog een interessante techniek die ik zeker eens ga bekijken.

Je gebruikt waarschijnlijk de standaard java.util.regex ?

Anders moet je eens die van Jakarta proberen en zien of het een verschil uitmaakt.