[JAVA] Espressioni regolari stile xml

[Tecnomiky]

Sto creando un programma per gestire gli ebook, per gestirli creo un file txt con il nome dell'ebook.

Il file dove contenere qualcosa del genere:

<title>Mio libro</title><year>2012</year><home>Mia casa</home>


che espressione regolare dovrei usare per recuperare il contenuto tra <title></title> o tra <year></year>.

Ringrazio tutte le persone che mi aiuteranno.

[The_ouroboros]

cerca qualche lib gia pronta.
Estrarre da tag con sole regex è pericoloso..:D

[sottovento]

Scusa la fretta, ma oggi l'impianto sta facendo i capricci e devo fare una modifica molto pesante.
Per questo motivo, la regex che ti propongo l'ho provata solo usando vim, non Java:


\(<title>\)\([^<]*\)\(<\/title>\)


In questa regex do' per scontato che il simbolo "<" non possa comparire nel titolo. Mi sembra ragionevole, in quanto se realmente comparisse dovrebbe essere codificata, per esempio, con &lt;

Questa regex cerca le stringhe in formato <title>...</title> e suddivide la stringa trovata in 3 gruppi: il primo gruppo conterra' <title>, il secondo il titolo ed il terzo </title>

Per quanto ne so, Java puo' manipolare i gruppi (non l'ho mai provato, pero'), basta guardare qui:
http://docs.oracle.com/javase/tutorial/essential/regex/groups.html

Puoi quindi estrarre i dati dal secondo gruppo

[Tecnomiky]

Ho provato il codice di sottovento ma non funziona, comunque lo ringrazio per l'aiuto.

[sottovento]

Ho provato il codice di sottovento ma non funziona, comunque lo ringrazio per l'aiuto.

Va aggiustata, ovviamente. In particolare i backslash.
Se non hai fretta lo posso fare stasera, quando torno a casa

[The_ouroboros]

Parsing XML with REGEX in Java (http://stackoverflow.com/questions/335250/parsing-xml-with-regex-in-java)

[Vincenzo1968]

Che casino 'ste regexp in Java!

Secondo me è meglio scriversi un bel pushdown automaton ad hoc.

Il codice viene un po' più lungo ma più leggibile, ma più efficiente.

[The_ouroboros]

non tantissimo.
Il fatto è che solo in Perl sono una parte del linguaggio.
Cmq anche il link consiglia di usare librerie apposite.
Il parsing xml è insidioso con regex

[VICIUS]

Ho provato il codice di sottovento ma non funziona, comunque lo ringrazio per l'aiuto.
Prova questo. Dovrebbe andare:
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class Main {

public static void main(String[] args) {
String xml = "questa è la stringa xml con <title>Titolo</title> dentro";

Pattern TITLE = Pattern.compile("<title>([^<]+)</title>");

Matcher matcher = TITLE.matcher(xml);
while (matcher.find()) {
System.out.println("Titolo: " + matcher.group(1));
}
}
}
Ho tolto le parentesi attorno a <title> e </title> perché se non si deve catturare il testo o raggruppare non serve metterle. Poi ho sostituito il * con un + così cattura solo tag che hanno testo al loro interno.

[Vincenzo1968]

Praticamente bisognerà confrontare i tempi della soluzione proposta da Vicius col mio pushdown automaton.

Secondo me vince l'automa:

http://swtch.com/~rsc/regexp/regexp1.html

Naturalmente il confronto andrà fatto su un file di grosse dimensioni(o su tantissimi file di piccole-medie dimensioni).

Ne verrà fuori una sorta di mini-contest.

[Tecnomiky]

Ho provato ma mi esce questo
<title>Mio libro</title>

e la stringa contiene questo:
<title>Mio libro</title><year>2012</year><home>Mia casa</home>

[VICIUS]

Ho provato ma mi esce questo
<title>Mio libro</title>
Se hai usato il codice che ho postato è impossibile che ritorni la stringa completa. Il capturing group è attorno al solo contenuto. NON può ritornarti anche i tag.

Posta il codice completo che hai usato e poi vediamo cosa hai sbagliato.

[Vincenzo1968]

http://expat.sourceforge.net/

http://www.xml.com/pub/a/1999/09/expat/index.html

[sottovento]

Ho tolto le parentesi attorno a <title> e </title> perché se non si deve catturare il testo o raggruppare non serve metterle. Poi ho sostituito il * con un + così cattura solo tag che hanno testo al loro interno.
Si, sono un ragazzo ridondante :D
Cmq sono d'accordo, la regex deve funzionare cosi' com'e'.

@Tecnomiky - hai copiato correttamente il codice? Sembra che ti sia dimenticato di mettere l'1 nell'istruzione


System.out.println("Titolo: " + matcher.group(1));

[Tecnomiky]

Non avevo aggiunto l' 1 dentro alla parentesi del matcher.group

[sottovento]

Praticamente bisognerà confrontare i tempi della soluzione proposta da Vicius col mio pushdown automaton.

Secondo me vince l'automa:

http://swtch.com/~rsc/regexp/regexp1.html

Naturalmente il confronto andrà fatto su un file di grosse dimensioni(o su tantissimi file di piccole-medie dimensioni).

Ne verrà fuori una sorta di mini-contest.
Una regexpr praticamente E' la specifica di un automa!
Dunque, per fare un confronto dovresti scrivere un software che PRIMA accetti in ingresso un automa qualunque, specificato nel modo che vuoi tu, e poi ne confronti i tempi. Cosi' puoi vedere quanto le prestazioni dipendono dall'implementazione e non da restrizioni che hai imposto da una parte e non dall'altra ;)

[Tecnomiky]

Comunque ho risolto grazie all'aiuto di sottovento. Si può chiudere

[Vincenzo1968]

Una regexpr praticamente E' la specifica di un automa!
Dunque, per fare un confronto dovresti scrivere un software che PRIMA accetti in ingresso un automa qualunque, specificato nel modo che vuoi tu, e poi ne confronti i tempi. Cosi' puoi vedere quanto le prestazioni dipendono dall'implementazione e non da restrizioni che hai imposto da una parte e non dall'altra ;)

Si ma spesso sono implementate in maniera non ottimale. Vedi articolo postato ;)

Io dico che con una implementazione ad hoc, senza dunque dover creare al volo l'automa per una generica regexp, il programma(in Java stesso, non in C) sarebbe più efficiente.

;)

[Vincenzo1968]

Comunque ho risolto grazie all'aiuto di sottovento. Si può chiudere

Ah ok.

[sottovento]

Si ma spesso sono implementate in maniera non ottimale. Vedi articolo postato ;)

Io dico che con una implementazione ad hoc, senza dunque dover creare al volo l'automa per una generica regexp, il programma(in Java stesso, non in C) sarebbe più efficiente.

;)

Ho capito di non aver capito: se voglio cercare una determinata stringa data in ingresso dall'utente, e tale stringa e' una regexp, cosa proponi di fare?

[Vincenzo1968]

Ho capito di non aver capito: se voglio cercare una determinata stringa data in ingresso dall'utente, e tale stringa e' una regexp, cosa proponi di fare?

Voglio dire che i motori di ricerca con regexp(in Java o in qualunque altro linguaggio/tool), ricevuta in input la regexp devono:

1) Costruire al volo l'automa(nfa o dfa).
2) Iniziare la ricerca nel testo con l'automa costruito nel passo 1.

Un automa ad hoc, per il problema specifico, parte direttamente dal passo 2. E si tratta di un dfa, molto più efficiente rispetto a un nfa.

Può essere pure che molti linguaggi/tool al giorno d'oggi costruiscano(al volo) un dfa anziché un nfa. Ma mi pare difficile, ché la costruzione di un dfa è O(n^2) mentre l'nfa è O(n).

[Vincenzo1968]

Dal libro Automi linguaggi e calcolabilità di Hopcroft, Motwani e Ullman:

Cap. 4 - Conversione da espressione regolare ad automa(pag. 161):

Possiamo concludere che la costruzione di un e-NFA da un'espressione regolare richiede tempo lineare nella lunghezza dell'espressione.
Possiamo eliminare le e-transizioni da un e-NFA di n stati per farne un NFA normale, in tempo O(n^3), senza aumentare il numero di stati.
La trasformazione in DFA può comunque richiedere tempo esponenziale.

[sottovento]

Perdonami, ma non ho ancora capito: ho bisogno di effettuare una ricerca su di un testo. Cosa devo fare?
Da quel poco che ho capito sembra che mi proponi di scrivere un programma super-ottimizzato ad hoc, invece che utilizzare un grep.

Si, e' vero che il tempo e' O(n^2) o O(n^3) o altro, ma n e' la lunghezza dell'espressione, non del testo. Sono interessato a sapere qualcosa a proposito della lunghezza N del testo!!

Come dire: e' inutile salvare la goccia dallo spino, se dietro la botte il coccone e' saltato via :D

[Vincenzo1968]

Perdonami, ma non ho ancora capito: ho bisogno di effettuare una ricerca su di un testo. Cosa devo fare?
Da quel poco che ho capito sembra che mi proponi di scrivere un programma super-ottimizzato ad hoc, invece che utilizzare un grep.

Si, e' vero che il tempo e' O(n^2) o O(n^3) o altro, ma n e' la lunghezza dell'espressione, non del testo. Sono interessato a sapere qualcosa a proposito della lunghezza N del testo!!

Come dire: e' inutile salvare la goccia dallo spino, se dietro la botte il coccone e' saltato via :D

Niente, se non ci apriamo un contest non ne usciamo. Mi toccherà asfaltare Vicius e, questa volta, usando Java non C: lui con le sue espressioni regolari e io col mio automino.

Quindi tu dici che Java utilizza un dfa? Vedremo(nel contest). Intanto, anche se costruisse al volo un dfa deve sempre costruirlo prima di effettuare la ricerca(e l'algoritmo è piuttosto complicato rispetto alla costruzione di un e-nfa). Io parto già dal passo 2. :D

Vedremo, vedremo... :huh:

:D

Ah! il punto 2 del contest riguarderà il traduttore da regexp a italiano. ;)

[sottovento]

Niente, se non ci apriamo un contest non ne usciamo. Mi toccherà asfaltare Vicius e, questa volta, usando Java non C: lui con le sue espressioni regolari e io col mio automino.

Quindi tu dici che Java utilizza un dfa? Vedremo(nel contest). Intanto, anche se costruisse al volo un dfa deve sempre costruirlo prima di effettuare la ricerca(e l'algoritmo è piuttosto complicato rispetto alla costruzione di un e-nfa). Io parto già dal passo 2. :D

Vedremo, vedremo... :huh:

:D

Ah! il punto 2 del contest riguarderà il traduttore da regexp a italiano. ;)

Devi scusarmi ancora, ma proprio non capisco. So di essere un po' lento.
Tu fai una cosa: mi dici qual e' il problema, quali sono gli ingressi, le uscite e perche' non se ne esce se non con un contest.
Io pensavo che il problema fosse cercare una stringa in un testo, anche di grandi dimensioni, ma ora non ne sono sicuro.

Per quanto riguarda il contest.... beh, ne ho uno grosso domani, visto che ben 2 chilometri di impianto e' fermo e devo farlo ripartire. Ma se mi avanza tempo provo a leggere i post

[wingman87]

Vincenzo sta dicendo che con le regexp i passi sono:
1 - costruzione automa nfa
2 - ricerca nel testo

Invece la sua soluzione prevede che lui abbia già implementato un automa dfa ad hoc e quindi parte già dal punto 2. Inoltre avendo implementato un dfa invece di un nfa, guadagna in prestazioni anche nel secondo punto.

[sottovento]

Vincenzo sta dicendo che con le regexp i passi sono:
1 - costruzione automa nfa
2 - ricerca nel testo

Invece la sua soluzione prevede che lui abbia già implementato un automa dfa ad hoc e quindi parte già dal punto 2. Inoltre avendo implementato un dfa invece di un nfa, guadagna in prestazioni anche nel secondo punto.

Sono un analfabeta di ritorno, probabilmente ho finito l'universita' troppi anni addietro. Per quanto mi ricordo, una espressione regolare genera un linguaggio [regolare], il quale e' descrivibile anche come automa a stati finiti. Immagino che le cose non siano cambiate, fino a questo punto.

La mia perplessita' e' che la costruzione dell'automa nfa/dfa avviene perche' ad ogni espressione regolare che l'utente si sogna corrisponde un diverso automa. Quindi i vari tool di ricerca costruiscono l'automa e lo fanno evolvere.
Sbaglio?

Vincenzo invece dice di avere l'automa gia' pronto. Va da se' che tale automa, essendo gia' pronto e' sicuramente piu' veloce poiche' il punto #1 non deve essere eseguito (ce l'ho gia' l'automa). E' corretto?

[wingman87]

Fin qui è corretto. Vincenzo aggiunge che le regexp generano automi nfa mentre lui ne scriverebbe uno dfa, più efficiente.

In verità anche se io sono relativamente fresco di università, non so cosa generino le regexp.

[sottovento]

Fin qui è corretto. Vincenzo aggiunge che le regexp generano automi nfa mentre lui ne scriverebbe uno dfa, più efficiente.

In verità anche se io sono relativamente fresco di università, non so cosa generino le regexp.

Quello che dice Vincenzo e' corretto: pur essendo un risultato sorprendente, gli automi a stati finiti deterministici e non deterministici sono tra loro equivalenti, vale a dire (in questo caso, visto che parliamo di linguaggi) possono essere utilizzati per riconoscere la stessa classe di linguaggi.

E' vero anche che le regexpr sono usate per riconoscere linguaggi e la teoria ha dimostrato che la classe dei linguaggi riconosciuti da regexpr e automi a stati finiti e' la stessa.

Mi rimane la perplessita', ma spero in un intervento di Vincenzo che chiarifichi: una volta stabilita una regexpr, ho stabilito un linguaggio. Nel nostro caso pratico, ho stabilito che voglio trovare (riconoscere) una certa sequenza di caratteri nel mio testo.

Come si fa a conoscere in anticipo l'automa che andra' bene per la mia ricerca? Immagino che in questi anni si siano trovate cose nuove e magari esiste. Mi servirebbero spiegazioni, e non saprei come googlare per ottenerle...

[Vincenzo1968]

Vincenzo sta dicendo che con le regexp i passi sono:
1 - costruzione automa nfa
2 - ricerca nel testo

Invece la sua soluzione prevede che lui abbia già implementato un automa dfa ad hoc e quindi parte già dal punto 2. Inoltre avendo implementato un dfa invece di un nfa, guadagna in prestazioni anche nel secondo punto.

This.

[sottovento]

This.
Come fai a conoscere l'automa in anticipo?

[Vincenzo1968]

Quello che dice Vincenzo e' corretto: pur essendo un risultato sorprendente, gli automi a stati finiti deterministici e non deterministici sono tra loro equivalenti, vale a dire (in questo caso, visto che parliamo di linguaggi) possono essere utilizzati per riconoscere la stessa classe di linguaggi.

E' vero anche che le regexpr sono usate per riconoscere linguaggi e la teoria ha dimostrato che la classe dei linguaggi riconosciuti da regexpr e automi a stati finiti e' la stessa.

Mi rimane la perplessita', ma spero in un intervento di Vincenzo che chiarifichi: una volta stabilita una regexpr, ho stabilito un linguaggio. Nel nostro caso pratico, ho stabilito che voglio trovare (riconoscere) una certa sequenza di caratteri nel mio testo.

Come si fa a conoscere in anticipo l'automa che andra' bene per la mia ricerca? Immagino che in questi anni si siano trovate cose nuove e magari esiste. Mi servirebbero spiegazioni, e non saprei come googlare per ottenerle...

Non si può. Io ho parlato di un automa ad hoc per il problema specifico. È chiaro che le librerie regexp presenti nei vari linguaggi vanno bene per la generalità. La mia soluzione andrebbe bene solo per file formattati nel modo descritto da Tecnomiky:


<title>Mio libro</title><year>2012</year><home>Mia casa</home>

Se volessimo trattare file con diversa struttura, dovremmo modificare l'implementazione dell'automa.

È chiaro anche che non è il caso d'implementare un automa ad hoc se si tratta di leggere uno o pochi file di piccole dimensioni. In questo caso vanno benissimo anche le regexp. Ma, se avessimo a che fare con file di grosse dimensioni(o con tantissimi file), varrebbe la pena, secondo me, implementare un automino ad hoc.
Anche perché esistono tools per Java quali JFlex e JCup(che sono gli equivalenti C/C++ di Flex e Bison). Con Flex/JFlex specifichi i token, tramite regexp, e il programma ti genera un bel dfa. ;)

[Vincenzo1968]

Eqque qua:

http://jflex.de/

http://www.cs.princeton.edu/~appel/modern/java/CUP/
http://www2.cs.tum.edu/projects/cup/

JFlex syntax highlighting for Vim:

http://jflex.de/vim.html

[Vincenzo1968]

Arieqquequa(per chi preferisce C/C++):

http://www.gnu.org/software/flex/
http://flex.sourceforge.net/

http://www.gnu.org/software/bison/

[Vincenzo1968]

http://img46.imageshack.us/img46/8588/hahapp.jpg

http://www.hwupgrade.org/public/style_emoticons/default/everything_went_better_than_expected.png http://www.hwupgrade.org/public/style_emoticons/default/fyeah.png

[VICIUS]

Vincenzo sta dicendo che con le regexp i passi sono:
1 - costruzione automa nfa
2 - ricerca nel testo

Invece la sua soluzione prevede che lui abbia già implementato un automa dfa ad hoc e quindi parte già dal punto 2. Inoltre avendo implementato un dfa invece di un nfa, guadagna in prestazioni anche nel secondo punto.

Se il testo da processare non è banale, allora il tempo impiegato per fare il parsing della regexp e la costruzione del automa non è neanche paragonabile a quello impiegato per la ricerca. Stiamo parlando di 5, 6 o 7 ordini di grandezza di differenza tra i due. Nel caso di stringhe molto brevi basta banalmente spostare la costruzione del automa fuori dal ciclo per non ripeterla inutilmente tutte le volte.

Costruirsi a mano un automa per risparmiare pochi microsecondi è il classico esempio di premature optimization in cui si parte a testa bassa senza fare un minimo di profiling. In questo caso poi si tratta di un'ottimizzazione che in caso di cambiamenti alle specifiche ti taglia le gambe. Modificare una regexp è infinitamente più semplice ed immediato che andare a modificare cicli con if/switch innestati tra loro.

Dfa e nfa in teoria sono solo due modi diversi di esprimero lo stesso automa. NON ci sono differenze di prestazioni. Il problema degli nfa usati da linguaggi come java o ruby è che col tempo sono state aggiunte sempre più funzioni che spesso non è semplicemente possibile implementare con un normale automa. Una su tutte è l'introduzione delle backreference. A fare i pignoli non le si dovrebbe nemmeno chiamare espressioni regolari perché non si tratta più di un linguaggio regolare.

Ci sono alcuni casi patologici in queste implementazioni che fanno esplodere il numero di confronti rendendo il match impossibile. L'articolo che ha postato vincenzo lo spiega bene. Si tratta comunque di poche istanze che è facile prevenire una volta che si è capito come funziona il backtracking.

[Vincenzo1968]

Se il testo da processare non è banale, allora il tempo impiegato per fare il parsing della regexp e la costruzione del automa non è neanche paragonabile a quello impiegato per la ricerca. Stiamo parlando di 5, 6 o 7 ordini di grandezza di differenza tra i due. Nel caso di stringhe molto brevi basta banalmente spostare la costruzione del automa fuori dal ciclo per non ripeterla inutilmente tutte le volte.

Costruirsi a mano un automa per risparmiare pochi microsecondi è il classico esempio di premature optimization in cui si parte a testa bassa senza fare un minimo di profiling. In questo caso poi si tratta di un'ottimizzazione che in caso di cambiamenti alle specifiche ti taglia le gambe. Modificare una regexp è infinitamente più semplice ed immediato che andare a modificare cicli con if/switch innestati tra loro.

Dfa e nfa in teoria sono solo due modi diversi di esprimero lo stesso automa. NON ci sono differenze di prestazioni. Il problema degli nfa usati da linguaggi come java o ruby è che col tempo sono state aggiunte sempre più funzioni che spesso non è semplicemente possibile implementare con un normale automa. Una su tutte è l'introduzione delle backreference. A fare i pignoli non le si dovrebbe nemmeno chiamare espressioni regolari perché non si tratta più di un linguaggio regolare.

Ci sono alcuni casi patologici in queste implementazioni che fanno esplodere il numero di confronti rendendo il match impossibile. L'articolo che ha postato vincenzo lo spiega bene. Si tratta comunque di poche istanze che è facile prevenire una volta che si è capito come funziona il backtracking.

http://www.hwupgrade.org/public/style_emoticons/default/dumb.png

Ma che cacchio dici? l'NFA ha il backtracking. Che cacchio dici? Leggiti l'articolo che ho postato e vedrai la differenza che c'è tra nfa e dfa. Leggiti il libro di Hopcroft e vedrai. Vedrai vedrai. Ammatula che "una volta che si è capito come funziona il backtracking": l'nfa deve tornare indietro in caso di non corrispondenza verso la fine della stringa(per input malformato, per esempio). Leggi, leggi Hopcroft.

In quanto al "premature optimization" ti vorrei far notare che Knuth viene spesso, come in questo caso, citato a sproposito.

Premature optimization is the root of all evil è una frase di Knuth che si trova all'interno di un articolo in cui l'autore si spinge a considerare come buono l'uso del famigerato goto pur di migliorare le prestazioni.
In quell'articolo l'autore scrive che ama il codice leggibile e ben ordinato ma non ama per niente il codice inefficiente.

Vorrei vedere, nel caso di file xml di grosse dimensioni, le regexp in confronto al dfa superottimizzato(e con piena minimizzazione degli stati) come quello prodotto dagli strumenti suindicati...

http://www.hwupgrade.org/public/style_emoticons/default/patpat.gif

[Vincenzo1968]

Knuth e "Premature optimization":

Tratto dall'articolo Structure Programming with goto Statements":

Before beginning a more technical discussion. I should confess that the title of this article was chosen primarily to generate attention.
There are doubtless some readers who are convinced that abolition of go to statements is merely a fad. and they may see this title and think, "Aha! Knuth is rehabilitating the go to statement, and we can go back to our old ways of programming again." Another class of readers will see the heretical title and think, "When are diehards like Knuth going to get with it?" I hope that both classes of people will read on and discover that what I am really doing is striving for a reasonably well balanced viewpoint about the proper role of go to statements. I argue for the elimination of go to's in certain cases, and for their introduction in others.

I believe that by presenting such a view I am not in fact disagreeing sharply with Dijkstra's ideas, since he recently wrote the following: "Please don't fall into the trap of believing that I am terribly dogmatical about [the go to statement].
I have the uncomfortable feeling that others are making a religion out of it, as if the conceptual problems of programming could be solved by a single trick, by a simple form of coding discipline!" [29]. In other words, it, seems that fanatical advocates of the New Programming are going overboard in their strict enforcement of morality and purity in programs.

...

Of course I wouldn't bother making such optimizations on a oneshot job, but when it's a question of preparing quality programs, I don't want to restrict myself to tools that deny me such efficiencies.
There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

...

Now that I have discussed how to remove go to statements, I will turn around and show why there are occasions when I actually wish to insert them into a go to-less program.
The reason is that I like well-documented programs very much, but I dislike inefficient ones; and there are some cases where I simply seem to need go to statements, despite the examples stated above.


http://sbel.wisc.edu/Courses/ME964/Literature/knuthProgramming1974.pdf

:bimbo:

[Vincenzo1968]

In other words, it, seems that fanatical advocates of the New Programming are going overboard in their strict enforcement of morality and purity in programs.

Sembra il vostro ritratto :asd:

:rotfl:

http://www.hwupgrade.org/public/style_emoticons/default/lol.png

[Vincenzo1968]

http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx

The .NET Framework regular expression engine is a backtracking regular expression matcher that incorporates a traditional Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl. This distinguishes it from faster, but more limited, pure regular expression Deterministic Finite Automaton (DFA) engines such as those found in awk, egrep, or lex

http://www.hwupgrade.org/public/style_emoticons/default/lol.png

[VICIUS]

Ma che cacchio dici? l'NFA ha il backtracking. Che cacchio dici? Leggiti l'articolo che ho postato e vedrai la differenza che c'è tra nfa e dfa. Leggiti il libro di Hopcroft e vedrai. Vedrai vedrai.
Un automa a stati finiti è deterministico se tutte le coppie (stato, simbolo di ingresso) producono una singola transizione allo stato successivo. Per gli automi non deterministici questo non è vero e quindi ci possono essere più transizioni.

Il backtracking non è una caratteristica degli nfa ma semplicemente una tecnica usata dalle varie librerie che implementano le regexp per trovare tutte le possibili soluzioni. Rileggiti articolo e libro che non hai capito bene.

In quanto al "premature optimization" ti vorrei far notare che Knuth viene spesso, come in questo caso, citato a sproposito.

Premature optimization is the root of all evil è una frase di Knuth che si trova all'interno di un articolo in cui l'autore si spinge a considerare come buono l'uso del famigerato goto pur di migliorare le prestazioni.
In quell'articolo l'autore scrive che ama il codice leggibile e ben ordinato ma non ama per niente il codice inefficiente.
Cosa c'entra knuth? :confused:

Vorrei vedere, nel caso di file xml di grosse dimensioni, le regexp in confronto al dfa superottimizzato come quello prodotto dagli strumenti suindicati...

http://www.hwupgrade.org/public/style_emoticons/default/patpat.gif
Un automa a stati finiti deve scorrere tutti i caratteri uno alla volta per trovare tutti i match nel file xml. Si tratta di una soluzione lineare O(n) che dipende solo dalla dimensione del file quindi piuttosto efficiente.

La regexp dipende tantissimo dall'implementazione ma in java dovrebbe procedere così:
1. La parte iniziale "<title>" è composta da soli litteral. Può usare boyer-moore per cercare la prima occorrenza da cui partire con il match. Mi pare di ricordare che come algoritmo sia O(n/m) quindi più efficiente del normale automa.
2. Una volta trovato l'inizio del tag può fare la parte centrale di cattura del contenuto senza backtracking. [^<]+ è un semplice ciclo for.
3. Una volta catturato il contenuto esegue il test per "</title>" anche qui si tratta di soli litteral quindi ciclo for.
4. Se fa match riparte dal punto 1 partendo con la ricerca dopo </title> perché ormai il testo è stato consumato. Se non c'è stato parte dalla posizione successiva al <title> perché le () introducono backtracking.

L'uso di boyer-moore per trovare l'inizio dei match ed il fatto che il resto equivale in sostanza ad un dfa mi fa pensare che la regexp potrebbe essere più performante o in sostanza equivalente. ;)

[Vincenzo1968]

Si ma

http://www.hwupgrade.it/forum/showpost.php?p=39106131&postcount=40

http://www.hwupgrade.org/public/style_emoticons/default/lol.png

[VICIUS]

http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx

The .NET Framework regular expression engine is a backtracking regular expression matcher that incorporates a traditional Nondeterministic Finite Automaton (NFA) engine such as that used by Perl, Python, Emacs, and Tcl. This distinguishes it from faster, but more limited, pure regular expression Deterministic Finite Automaton (DFA) engines such as those found in awk, egrep, or lex

http://www.hwupgrade.org/public/style_emoticons/default/lol.png
Conferma ogni singola parola che ho scritto. Il matcher di c# fa uso di backtracking e di un nfa. Non è l'automa ma il matcher ad usarlo.

[Vincenzo1968]

http://algs4.cs.princeton.edu/54regexp/

http://www.hwupgrade.org/public/style_emoticons/default/lol.png

[Vincenzo1968]

https://github.com/knowitall/openregex

Implementation

Regular expressions are evaluated using Thomson NFA, which is fast and not have the pathological cases that most regular exprsesion libraries have. For more information about Thomson NFA in comparison to recurseive backtracking, read http://swtch.com/~rsc/regexp/regexp1.html. Future work may involve compiling NFAs to DFAs.

Future Work

Compile to DFA.
Use parser combinators for parsing regular expressions.

http://www.hwupgrade.org/public/style_emoticons/default/lol.png

[VICIUS]

http://algs4.cs.princeton.edu/54regexp/

http://www.hwupgrade.org/public/style_emoticons/default/lol.png
Classici pattern patologici. Nel primo caso è l'alternazione unita al * mentre nel secondo è il doppio * interno ed esterno a far saltare il tutto. Risolverli è bovino. Basta usare l'atomic grouping o i possesive quantifiers a seconda dei gusti personali.

https://github.com/knowitall/openregex

Implementation

Regular expressions are evaluated using Thomson NFA, which is fast and not have the pathological cases that most regular exprsesion libraries have. For more information about Thomson NFA in comparison to recurseive backtracking, read http://swtch.com/~rsc/regexp/regexp1.html. Future work may involve compiling NFAs to DFAs.

Future Work

Compile to DFA.
Use parser combinators for parsing regular expressions.

http://www.hwupgrade.org/public/style_emoticons/default/lol.png
Ennesima riconferma di quello che scrivevo. Dfa e nfa sono equivalenti.

[Vincenzo1968]

Minchia si, equivalenti sono(in un occhio si e in un occhio no):

http://img15.imageshack.us/img15/7483/myautomaregexp.jpg

Proprio uguali uguali.

http://www.hwupgrade.org/public/style_emoticons/default/dumb.png

RegExpVicius.java:

import java.util.regex.Pattern;
import java.util.regex.Matcher;

// <title>Mio libro</title><year>2012</year><home>Mia casa</home>

public class RegExpVicius {

public static void main(String[] args) {
int x;
String xml = "<title>Mio libro</title><year>2012</year><home>Mia casa</home>";

Pattern TITLE = Pattern.compile("<title>([^<]+)</title>");

x = 0;
while ( x < 100000000 ) {
Matcher matcher = TITLE.matcher(xml);
while (matcher.find()) {
if ( x < 3 )
System.out.println("Titolo: " + matcher.group(1));
}
x++;
}
}
}


RegExpVincenzo1968.java:

import java.io.Console;

public class RegExpVincenzo1968
{
public static void main(String[] args)
{
int x;
String xml = "<title>Mio libro</title><year>2012</year><home>Mia casa</home>";

CParser parser = new CParser();

x = 0;
while ( x < 100000000 )
{
if ( parser.Parse(xml) )
if ( x < 3 )
System.out.println(parser.GetValue());

x++;
}
}
}


Le classi CLexer e CParser sono un adattamento di quelle che avevo postato nel thread sulle espressioni aritmetiche:

http://www.hwupgrade.it/forum/showpost.php?p=38455996&postcount=7

Chi fosse interessato ai sorgenti mi contatti via pm ;)

Il mio dfa non è nemmeno ottimizzato. Non ho nemmeno minimizzato gli stati :rotfl:

http://www.hwupgrade.org/public/style_emoticons/default/lol.png

Vicius, Vicius! L'nfa è una illusione. L'nfa Java una doppia illusione.(semi cit.) :D

EDIT: Non capisco perché mi si sminchia l'indentazione. Il codice è perfettamente indentato. Mah! :mad:

[wingman87]

EDIT: Non capisco perché mi si sminchia l'indentazione. Il codice è perfettamente indentato. Mah! :mad:
Perché un po' è indentato con i tab e un po' con gli spazi

[VICIUS]

Vicius, Vicius! L'nfa è una illusione. L'nfa Java una doppia illusione.(semi cit.) :D
Ci sono diverse cose che non vanno in quel codice che hai postato. Poi potrei farti vedere come portare il tempo di esecuzione sotto i 3 secondi (sarebbe un po' imbrogliare :asd:). Però francamente non ne ho più voglia. Pensavo, anzi no speravo, che col tempo ti saresti un po' aperto cercando di crescere ma vedo non ti interessa. Rimani pure nel tuo piccolo mondo. ;)

[Vincenzo1968]

Perché un po' è indentato con i tab e un po' con gli spazi

No è indentato solo con i tab. Forse la cosa è dovuta al fatto che Geany, non so perché, mi aggiunge un sacco di tab alla fine di ogni riga(e non capisco con quale criterio: ci sono righe senza tab alla fine e righe con un fottìo di tab :confused: ).

Quindi io da me il codice lo vedo perfettamente indentato. Quando lo copincollo qui, evidentemente tutti quei tab a fine riga combinano il casino.

[Vincenzo1968]

Ci sono diverse cose che non vanno in quel codice che hai postato. Poi potrei farti vedere come portare il tempo di esecuzione sotto i 3 secondi (sarebbe un po' imbrogliare :asd:). Però francamente non ne ho più voglia. Pensavo, anzi no speravo, che col tempo ti saresti un po' aperto cercando di crescere ma vedo non ti interessa. Rimani pure nel tuo piccolo mondo. ;)

Che schifìo c'è nel codice che ho postato? E' semplicemente il codice che hai postato tu racchiuso all'interno di un ciclo while che itera per 100000000(leggasi: cento milioni) di volte.

[sottovento]

EDIT: Non capisco perché mi si sminchia l'indentazione. Il codice è perfettamente indentato. Mah! :mad:

Aprilo in gvim e scrivi:

:1,$s/\t/ /g

Cosi' sostituisci tutti i tab con spazi.

Dopo di che, scrivi:

:se expandtab


Questo fa in modo che i tuoi tab vengano automaticamente rimpiazzati con l'adeguato numero di spazi durente l'editing.

[Vincenzo1968]

Aprilo in gvim e scrivi:

:1,$s/\t/ /g

Cosi' sostituisci tutti i tab con spazi.

Dopo di che, scrivi:

:se expandtab


Questo fa in modo che i tuoi tab vengano automaticamente rimpiazzati con l'adeguato numero di spazi durente l'editing.

No ma il problema non sono i tab in sè. Sono i tab a fine riga.
Per esempio:

\tif (x > 0)

me lo ritrovo così:

\tif (x > 0)\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t

Vedi tutti quei tab(\t) alla fine?

È fastidioso anche quando debbo aggiungere del codice alla fine della riga. Mi sposto nella riga, premo il tasto "Fine" e mi ritrovo a millemila chilometri di distanza. Mi tocca eliminarli con backspace. Alla fine mi fa male il ditino. :bimbo:

Non c'è modo, con Vim, di eliminare del tutto i tab a fine riga anziché sostituirli con spazi? Ma i tab all'inizio della riga me li deve lasciare.

[The_ouroboros]

No ma il problema non sono i tab in sè. Sono i tab a fine riga.
Per esempio:

\tif (x > 0)

me lo ritrovo così:

\tif (x > 0)\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t

Vedi tutti quei tab(\t) alla fine?

È fastidioso anche quando debbo aggiungere del codice alla fine della riga. Mi sposto nella riga, premo il tasto "Fine" e mi ritrovo a millemila chilometri di distanza. Mi tocca eliminarli con backspace. Alla fine mi fa male il ditino. :bimbo:

Non c'è modo, con Vim, di eliminare del tutto i tab a fine riga anziché sostituirli con spazi? Ma i tab all'inizio della riga me li deve lasciare.

%s/\t*$//g

[Vincenzo1968]

Comunque:

http://infolab.stanford.edu/~ullman/ialc.html

http://www.amazon.com/gp/product/0321455363/ref=pd_lpo_k2_dp_sr_1?pf_rd_p=1278548962&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0201441241&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=0YHS4Q27CA8DP7KDKZ87
http://ecx.images-amazon.com/images/I/41F8M0325WL._SY320_.jpg

Il testo tratta l'argomento da un punto di vista pratico, non formale. Se preferite qualcosa di più formale, più rigoroso, dovete procurarvi la prima edizione. Ma non è per tutti: dovete avere delle solide basi matematiche. Io, per esempio, non riuscirei a leggerlo. Occhio! Be careful!

http://shop.oreilly.com/product/9780596528126.do
http://akamaicovers.oreilly.com/images/9780596528126/cat.gif

Su quest'ultimo si veda:

- il par. 4.6: NFA, DFA and POSIX
- il par 4.6.3.1: DFA efficiency: you get consistent, clean power. :D

[Vincenzo1968]

Ottimizzato codice. :O Minimizzati stati dell'automa. :O Sostituiti if statement con switch statement. :O

Nuovi tempi:

http://img14.imageshack.us/img14/6803/myjavaautomaton.jpg

http://www.hwupgrade.org/public/style_emoticons/default/lol.png


NFA...
http://www.hwupgrade.org/public/style_emoticons/default/dumb.png

[Vincenzo1968]

http://www.hwupgrade.it/forum/showpost.php?p=38890689&postcount=130

Ma anche no. :asd:

È vero che ho sparato la lettura dei file su thread multipli ma l'ho fatto solo per divertimento. Non credo di aver ottenuto un incremento di prestazioni con quello.

Piuttosto eliminando la regex per la pulizia dei file e passando a nio ho potuto costruirmi in anticipo i bytebuffer che avrei usato poi durante la scrittura, mappare in memoria i file da leggere, gestirmi il buffering a mano ed allocare i buffer fuori dal heap.

Usando collectins.shuffle al posto di Random dovrei aver anche aiutato il processore che di sicuro prima sbarellava a causa degli accessi completamente casuali alla memoria.

:asd: