[regex] zo klein mogelijke match *

[xos]

Hoi,

ik ben sinds kort bezig met reguliere expressies. Ik heb de reg exp zoals een string gevonden moet worden inmiddels opgesteld en dat werkt goed. Nu weet ik dat een reg exp van links naar rechts begint te matchen per character. En hier zit het probleem. Stel ik heb de volgende string:

code:

A B A B B C  
1 2 3 4 5 6

Nu wil ik de kleinste mogelijke string vinden welke begint met AB en eindigd met BC. Wat er nu gebeurd is er wordt een match gevonden op AB. Vervolgens wordt er gezocht naar BC. Deze wordt gevonden op positie 5 & 6. Terwijl er een kleinere match gevonden kan worden van positie 3,4,5 & 6. Nu wil ik alleen de kleinste match vinden.

Is dit mogelijk met een reg exp?

[.oisyn]

Lekkere titel

[elnino]

Heb je al gekeken naar greediness (gulzigheid)?

Als dit aanstaat, zal hij zoveel mogelijk matchen. Hoe dit aan of uitgezet kan worden hangt af van op welke manier je de Regular Expression aanroept. In PHP kan dit bijvoorbeeld worden ingesteld met de U-modifier van de Perl-compatible Regex functies (preg_*). Zie ook http://www.php.net/manual/nl/pcre.pattern.modifiers.php.

[Commander Koen]

AB([^A][^B])*BC

zou moeten werken

[edit] em verbeterd was een stomme fout

[ Voor 43% gewijzigd door Commander Koen op 26-12-2003 00:05 ]

[.oisyn]

Commander Koen
die klopt niet, dat matcht bijvoorbeeld niet ABBBC, terwijl dat wel een goede is. Je stuk tussen de haakjes wil ook altijd 2 tekens matchen, dus dat betekent dat als er een oneven aantal tekens tussen de AB en de BC staat er nooit gematched wordt.

basterd
Ik weet niet wat de volgorde is waarop de greedyness wordt toegepast, maar je zou eens kunnen proberen te matchen op .*AB.*BC
Misschien dat de greedyness als eerst wordt toegepast op de eerste .*, waardoor de 2e .* zo klein mogelijk is.

Overigens matcht dat niet ABC (geen idee of dat ook de bedoeling is, maar in feite begint ABC met AB en eindigt het met BC. Dan zou het dit worden: .*A(B.*)?BC

[elnino]

.oisyn schreef op 26 december 2003 @ 00:14:
Overigens matcht dat niet ABC (geen idee of dat ook de bedoeling is, maar in feite begint ABC met AB en eindigt het met BC. Dan zou het dit worden: .*A(B.*)?BC

Het lijkt me dat ABC geen goede match is, of in ieder geval niet de bedoeling. Er kunnen eigenlijk twee dingen nu gematcht worden, namelijk:

code:

A B A B B C
    A B B C

waarbij het de bedoeling is dat de laatste gematcht wordt. Althans dat maak ik uit de topicstart op.

Ik weet alleen niet zeker of greediness alleen van voren naar achteren werkt, of dat het altijd de kortste match maakt.

[Commander Koen]

@.oisyn

de sub-expressie ([^A][^B]) matcht alles behalve de string AB dus ABBBC wordt in mijn expressie wel gematcht

@elnino

Ja greediness uitzetten werkt alleen van voor naar achter.

[edit] als ik erover nadenk klopt die regexp toch niet...

[ Voor 41% gewijzigd door Commander Koen op 26-12-2003 00:48 ]

[crisp]

nee, .oisyn heeft gelijk ([^A][^B]) wil altijd 2 karakters matchen, dus dat zal niet altijd werken. Ik zat zelf te denken aan recursie dmv (?R), maar ik krijg het zo snel niet voor elkaar. Waarschijnlijk dat het met een loopje wel zal werken.

[Commander Koen]

Met een lookahead character kan het natuurlijk wel ... maarjah dat werkt alleen bij perl style regexps en niet met posix regexps.

edit: AB([^B]|(?<!A)B)*BC

oh en het is een lookbehind geworden

[ Voor 24% gewijzigd door Commander Koen op 26-12-2003 01:08 . Reden: toevoeging ]

[Verwijderd]

PHP:

preg_match('/cb(.*?)ba/i', strrev("ABABBC"), $matches);
echo strrev($matches[0]);

Nu is hij not greedy van achteraf

[.oisyn]

Hebbes

AB(?:[^A]|A(?!B[^C]))*BC

Even uitleggen. A(?!B) betekent natuurlijk: match A als het niet gevolgd wordt door B. Dus ik dacht, we moeten alles matchen, maar als het een A is, dan mag het niet gevolgd worden door een B. Dat vertaalt dus naar de regex "match alles behalve A, of een A die niet gevolgd wordt door een B", oftewel: [^A]|A(?!B)

Dat doe je meerdere keren, dus dat wordt: (?:[^A]|A(?!)B)*
De ?: staat er omdat je geen extra submatch wilt doen van wat tussen de haakjes staat. De totale regex wordt dan AB(?:[^A]|A(?!)B)*BC

Alleen hier zit een fout in, deze matcht namelijk ABABC niet, terwijl dat wel zou moeten. Dat komt omdat er een B staat na de 2e A, wat niet mag. Een A gevolgd door BC mag dus wel, maar een A gevolgd door een B en een andere letter dan C weer niet. Het (?!B) gedeelte wordt dan ook (?!B[^C]).

En dan kom je op AB(?:[^A]|A(?!B[^C]))*BC
Ik kan zo snel geen uitzondering hiermee bedenken die wel matcht terwijl dat niet zou moeten, of andersom

.edit: hmz rijkelijk laat voortaan eerst refreshen nadat ik een potje scrabble heb gespeeld

[ Voor 5% gewijzigd door .oisyn op 26-12-2003 02:59 ]

[xos]

Ey bedankt voor de reacties. De oplossingen van commander koen & .oisyn werken idd. Maar ik kwam erachter dat ik niet volledig ben geweest .

Via koen heb ik gezocht op lookbehind in google en wat documentatie gelezen en zelf een proggie gemaakt. Hetgeen wat ik nog niet verteld heb is dat de afstand tussen begin en eind variabel moet zijn in stappen van drie. Toelichting:

Het doel is een perl programma te maken wat bepaalde sequences zoekt in een text file. Deze tekst files zijn enkele mb groot en bestaan uit DNA sequences. BV8:

code:

TGA ATT GCC AAT TGG AAA ATG ...

Drie van deze characters vormen samen 1 "groep". Nu zijn er 3 verschillende groepen te onderscheiden. Een groep welke staat voor start (AGT|GGT), een groep welke voor een einde codeert (TAA|TAG|TGA) en de derde groep zijn andere combinaties van de letters ACGT (noem deze even rest groep).

Wat nu de bedoeling is een match te vinden welke bestaat uit een:

code:

 start - n * rest - stop

.bv: AGT ACC ATT TAA

Het probleem zit er nu in dat er telken groepen van drie aangehouen moet worden. Wat dus geen match zou moeten opleveren is het volgende:

AGT ACC ATT AAA

Dus ik had de volgende exp bedacht:

code:

/(?<=((GGT|ATG)\w\w\w){0,})(TAA|TAG|TGA)/g

Wat vervolgens de volgende melding gaf:

code:

$./test2.pl fasta.test
Variable length lookbehind not implemented in regex; marked by <-- HERE in m/(?<=((GGT|ATG)(\w\w\w)){0,})(TAA|TAG|TGA) <-- HERE 
/ at ./test2.pl line 44

Dus ik vermoed dat het helaas niet mbv lookbehind kan.

code:

$ perl -v
This is perl, v5.8.0 built for i386-linux-thread-multiperl -v

[ Voor 3% gewijzigd door xos op 26-12-2003 03:24 . Reden: wat enters invoeren om de layout beetje te handhave n ]

[Commander Koen]

dit begrijp ik uit je verhaal:
1.Die tekstfile krijg je dus aangeleverd?
2. en er zijn geen scheidings tekens zoals comma's of spaties (in je voorbeeld staan spaties)
3. een start seqeuentie kan op elke positie in het bestand starten.

[xos]

Commander Koen schreef op 26 december 2003 @ 11:41:
dit begrijp ik uit je verhaal:
1.Die tekstfile krijg je dus aangeleverd?
2. en er zijn geen scheidings tekens zoals comma's of spaties (in je voorbeeld staan spaties)
3. een start seqeuentie kan op elke positie in het bestand starten.

Dat klopt,

ik krijg een textfile aangeleverd. Hierin staan op meerdere regels rijen met characters zonder scheidingtekens. In mijn voorbeeld heb ik die neergezet om het duidelijk te krijgen dat er per 3 gematched moet worden. In het bestand zijn meerdere start sequences aanwezig en meerdere stop sequences. Nu wil ik voor al deze sequences de kleinst mogelijke hit vinden.

[Skaah]

Kun je het zelf niet splitsen op drie tekens? Ik neem aan dat je op een aardige machine zit te werken die geen t.net achtige loads kent zodat je best een paar (mega)bytes geheugen hiervoor kunt gebruiken.

[Commander Koen]

Je kan niet zomaar splitsen in strings van 3 karakters. een startsequentie kan bijvoorbeeld ook op positie 2 in het bestand beginnen

[Commander Koen]

code:

 (((AGT)|(GGT))((TAA)|(TAG)|(TGA)))|(((AGT)|(GGT))([ACGT]{3})?(?<!(AGT)|(GGT))([ACGT]{3})*?((TAA)|(TAG)|(TGA)))

Hij is wat complex geworden, maar als het goed is werkt hij, al heb ik niet uitputtend getest.
dit stuk:

code:

(((AGT)|(GGT))((TAA)|(TAG)|(TGA)))

matcht een begin en een einde en zorgt ervoor dat begin eind eind niet wordt gematcht.

code:

([ACGT]{3})?

zorgt dat:

code:

(?<!(AGT)|(GGT))([ACGT]{3})*?

niet altijd faalt. En *? zorgt er natuurlijk voor dat de expressie niet greedy is.

[crisp]

is het niet slimmer om zoiets gewoon met een loop en een simpelere regexp te doen?
Het maakt het geheel denk ik wel een stuk onderhoudbaarder en mogelijk zelfs sneller...

[Commander Koen]

crisp schreef op 26 december 2003 @ 16:32:
is het niet slimmer om zoiets gewoon met een loop en een simpelere regexp te doen?
Het maakt het geheel denk ik wel een stuk onderhoudbaarder en mogelijk zelfs sneller...

Waarschijnlijk wel
Maar het oplossen met één regexp was natuurlijk leuk om te doen

[crisp]

Commander Koen schreef op 26 december 2003 @ 16:44:
[...]

Waarschijnlijk wel
Maar het oplossen met één regexp was natuurlijk leuk om te doen

dat is waar

[xos]

Commander Koen schreef op 26 december 2003 @ 14:35:

code:

 (((AGT)|(GGT))((TAA)|(TAG)|(TGA)))|(((AGT)|(GGT))([ACGT]{3})?(?<!(AGT)|(GGT))([ACGT]{3})*?((TAA)|(TAG)|(TGA)))

Erg bedankt voor je antwoord. Opzich gaat alles goed tot op het moment dat er meerdere start reeksen worden gevonden voordat 1 stop reeks wordt gevonden.

Dit gaat dus perfect:

code:

GGT AAA TAA GGT AAA TAA

Geeft:
GGTAAATAA 1     9
GGTAAATAA 10    18

code:

GGT GGT AAA TAA
Geeft:
GGTAAATAA 4     12
Zoals het hoort

Het probleem doet zich voor bij een volgende reeks

code:

GGT AAA GGT AAA TAA

Geeft:
GGTAAAGGTAAATAA 1       15
wat het volgende had moeten zijn:
GGTAAATAA 7 15

Er moet dus nog iets worden ingebouwd waardoor [START][TUSSEN]n[START][TUSSEN]n[STOP] niet matched. Maar kan dit uberhaupt wel? Als je zorgt dat ie geen match geeft op die tekst vind hij dan niet helemaal niks, omdat hij nu deze match vind?

@crisp, idd het woord recursie is bij mij ook al eens door het hoofd gevlogen maar ik wilde weten of dit eigenlijk mogelijk is met een reg exp.

[Commander Koen]

code:

(((AGT)|(GGT))((TAA)|(TAG)|(TGA)))|(((AGT)|(GGT))([ACGT]{3})?((?<!(AGT)|(GGT))([ACGT]{3}))*?((TAA)|(TAG)|(TGA)))

fixed was een kewstie van een paar haakjes
Daarom is het dus beter om het niet met een hele lange regexp te doen, of heel intensief te testen.

Dus het is het inderdaad beter om het met een recursieve/iteratieve functie te doen.

[crisp]

hier iteratief (in javascript):

JavaScript:

var t = 'ABGGTAGGTAAAGGTAAATAAGGTAAATAAGGTAAATAAGGTGGTAAATAAGGTAAAGGTAAATAAAGTTGAAGTGGTABCTAG';
var re1 = /((\w{3})*?)(GGT|AGT)((\w{3})*?(TAA|TAG|TGA))/g
var re2 = /((\w{3})*?)(GGT|AGT)(.*)/

var x, y, i, j, k;

var m = re1.exec(t);

while (m != null) {

  i = m.index + m[1].length;
  j = re1.lastIndex;

  x = m[3];
  y = m[4];
  k = re2.exec(y);

  while (k != null) {
    i += k[1].length + 3;
    x = k[3];
    y = k[4];
    k = re2.exec(y);
  }

  alert(x+y+' '+(i+1)+' '+j);

  m = re1.exec(t);

}

output:

code:

GGTAAATAA 13 21
GGTAAATAA 22 30
GGTAAATAA 31 39
GGTAAATAA 43 51
GGTAAATAA 58 66
AGTTGA 67 72
GGTABCTAG 76 84

[ Voor 44% gewijzigd door crisp op 27-12-2003 12:37 ]

[xos]

Ey bedankt commander koen, volgens mij werkt ie nu perfect. Er moet alleen nog kunnen opgegeven worden hoe groot de tussenliggende sequences minimaal moet zijn maar daar moet ik zelf lijkt me nog wel uit kunnen komen.

Maar idd een andere oplossing is waarschijnlijk in dit geval gemakkelijker...

[Commander Koen]

Crisp in re1 staat een klein foutje, zoals het nu staat kan een start sequentie alleen op 0 of op een veelvoud van 3 beginnen. Het was geloof ik de bedoeling dat de startsequentie op elke positie in de string kon beginnen.

dus

code:

var re1 = /(\w*?)(GGT|AGT)((\w{3})*?(TAA|TAG|TGA))/g

[crisp]

Commander Koen schreef op 27 december 2003 @ 14:04:
Crisp in re1 staat een klein foutje, zoals het nu staat kan een start sequentie alleen op 0 of op een veelvoud van 3 beginnen. Het was geloof ik de bedoeling dat de startsequentie op elke positie in de string kon beginnen.

dus

code:

var re1 = /(\w*?)(GGT|AGT)((\w{3})*?(TAA|TAG|TGA))/g

dat wist ik niet zeker, maar is inderdaad vrij eenvoudig aan te passen