[JAVA] Espressioni regolari stile xml

[Vincenzo1968]

Originariamente inviato da sottovento

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

[Vincenzo1968]

Originariamente inviato da 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

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.

Vedremo, vedremo...



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

[sottovento]

Originariamente inviato da Vincenzo1968

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.

Vedremo, vedremo...



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]

Originariamente inviato da 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.

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]

Originariamente inviato da 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.

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]

Originariamente inviato da 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.

This.

[sottovento]

Originariamente inviato da Vincenzo1968

This.

Come fai a conoscere l'automa in anticipo?

[Vincenzo1968]

Originariamente inviato da sottovento

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]

[VICIUS]

Originariamente inviato da 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.

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]

Originariamente inviato da VICIUS

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.

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...

[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/L...amming1974.pdf

[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

[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