Percorso: "Rappresentazione e analisi del testo e dei documenti" UNITA' 2 - Pattern matching e espressioni regolari SINTESI ... 1. Pattern matching e pattern recognition Cerchiamo di procedere per passi, dato che la parola inglese "pattern" non ha un perfetto equivalente in Italiano. Possiamo pensare ad un "pattern" come a una forma, una disposizione di elementi, riconoscibile (da un umano o da una macchina). "Pattern recognition" (termine usato in psicologia e nel campo del machine learning) si riferisce appunto al riconoscimento di "pattern", nel senso di configurazioni regolari, nei dati sensori o nei dati digitali. L'espressione "pattern matching", tipica della computer science (informatica) ha un'accezione più ristretta: si riferisce all'atto di verificare se una certa sequenza di elementi - caratteri nel caso di nostro interesse - corrisponde al pattern specificato, o a uno dei pattern specificati. 2. Le espressioni regolari (RE) Le espressioni regolari (nel seguito RE, da "regular expression") sono uno dei più comuni e potenti formalismi per specificare dei pattern, con riferimento al testo inteso come stringa (o sequenza) di caratteri. Nel campo del software, dei linguaggi di programmazione, le RE rappresentano una tecnica largamente applicabile, estremamente potente, che può anche mettere in soggezione. La teoria delle espressioni regolari ha origine dallo studio del linguista Chomsky sulle "gerarchie di grammatiche". Ma l'uso delle espressioni regolari nella programmazione si è diffuso a partire dagli anni '80 insieme a quello del sistema operativo Unix e del linguaggio di programmazione Perl. Anzi, il nucleo di Perl, un linguaggio specialistico per il trattamento dei testi, era costituito proprio dalle espressioni regolari. Un'espressione regolare è una stringa di caratteri che rappresenta un pattern e che quindi identifica, per tramite di esso, un insieme di stringhe di caratteri. 3. Primi esempi di espressioni regolari Salvo eccezioni, una qualsiasi stringa costituisce un pattern che identifica le occorrenze letterali (esatte) in un testo di quella stringa stessa. Esempio: la stringa "casa" può essere usata come RE per cercare le occorrenze letterali (una sola) della stringa stessa nella frase "una casa di carta". Invece la stringa ".*" è una RE che corrisponde a (è soddisfatta da) una qualsiasi stringa di caratteri: il punto (.) è un "meta-carattere" che sta per "un carattere qualsiasi", mentre l'asterisco (*) è un "quantificatore" che specifica un numero qualsiasi di ripetizioni, anche zero; quindi si tratta di una RE soddisfatta da "Nel mezzo del cammin di nostra vita", "Casetta in Canadà", "barca", "". La stringa "(\w\d-)+" include il meta-carattere "\w" che sta per un qualsiasi carattere ammissibile in una parola, il meta-carattere "\d" che sta per un qualsiasi cifra decimale e il carattere "-" letterale; le parentesi tonde delimitano un gruppo che, come specificato dal "quantificatore" più (+), può ripetersi una o più volte; quindi si tratta di una RE soddisfatta da stringhe come "A1-b2-c5-E4-" A questo punto è possibile verificare gli esempi usando uno strumento online come [3] o [8]. 4. Possibili usi delle espressioni regolari Le espressioni regolari possono essere usate per: - cercare / contare le occorrenze di una stringa in un testo, ed effettuare sostituzioni massive [4] - effettuare la segmentazione di un testo in frasi - effettuare la segmentazione di una frase in token (parole, numeri, date, ecc.) - analizzare un file di log; per esempio il log degli gli accessi ad un sito web - creare filtri per guidare l'attività di un web spyder, per esempio uno creato con l'applicazione Scrapy [5] - effettuare lo "scraping" dei dati da una o più pagine web (text/data mining) [5] - convalidare indirizzi email, numeri di telefono, date, ecc. nei moduli interattivi di browser web e di altre applicazioni - creare filtri per la ricerca in alcuni database specialistici - creare filtri per analizzare i dati raccolti da GoogleAnalytics.. 5. Sintassi delle RE: caratteri regolari e meta-caratteri [2] Ecco un sunto molto sbrigativo degli elementi che compongono una RE. In una RE ogni carattere può figurare come un carattere "regolare", che rappresenta se stesso, letteralmente, o un carattere "speciale". Di regola una lettera è un carattere regolare; può diventare un meta-carattere se preceduto da un back-slash (\). Nel caso del carattere punto (.) la convenzione si inverte: il punto da solo funge da meta-carattere jolly; lo si fa precedere da "\" per trasformarlo in un letterale. I caratteri speciali includono - meta-caratteri che stanno non per veri caratteri ma per la posizione iniziale e finale nella stringa: ^$ - meta-caratteri che servono a specificare "classi di caratteri": ^[-] esempio: [3-6] = una cifra compresa tra 3 e 6; il carattere ^ (negazione) trasforma una classe nel suo complemento - meta-caratteri che denotano in forma abbreviata una specifica classe di caratteri; esempi: \d = cifra decimale \w = "word character" (carattere che appartiene a una delle classi: lettere maiuscole o minuscole, cifre, underscore) - meta-caratteri che servono a delimitare "gruppi" di altri caratteri e meta-caratteri: (|) all'interno delle parentesi tonde, la barra verticale separa opzioni alternative - meta-caratteri "quantificatori"; i principali sono: ?*+{,} ? = 0 o 1 occorrenze, * = 0 o più occorrenze, + = 1 o più occorrenze, {M,N} = da un minimo di M a un massimo di N occorrenze i quantificatori si applicano a singoli caratteri o meta-caratteri, a classi di caratteri, a gruppi di caratteri NOTA: i seguenti caratteri sono considerati caratteri regolari fuori da un contesto che li qualifichi come meta-caratteri: -]{} 6. Altri esempi di espressioni regolari [1] ... 7. Applicazioni che incorporano "regular expression engines" Solamente alcuni esempi: - Notepad ++. Le funzioni di ricerca e sostituizione di stringhe consentono di selezionare la modalità "espressione regolare", - Eclypse. E' un diffuso IDE (integrated development environment) open source. Include "plugin" per sviluppare praticamente in tutti i moderni linguaggi di programmazione. Le potenti funzioni di ricerca e sostituzione all'interno del singolo file e dell'intero progetto possono lavorare in modalità "espressione regolare". ... 8. Servizi online che implementano "regular expression engines" Tutti i linguaggi di programmazione moderni, in particolare quelli orientati alla programmazione su Internet, includono direttamente o tramite librerie un interprete delle RE, chiamato "regular expression engine". E' possibile esercitarsi, per esempio, installando Python e lanciano il suo interprete. Tuttavia la sintassi delle RE può variare leggermente da linguaggio a linguaggio [10]. I seguenti sono esempi di strumenti interattivi accessibili liberamente sul web: - Regex101 è un "regular expression exerciser" online. E' molto interessante la sua capacità di "introspezione", cioè di esplicitare i "ragionamenti" applicati per individuare i match (le corrispondenze) tra la RE e il testo prova. Tuttavia è molto dipendente dai dettagli della sintassi riconosciuta. [3] - Regex Tester è un altro "regular expression exerciser" online. Non ha la capacità di introspezione di Regex101, ma rende più semplice la scelta di alcune modalità di ricerca e/o sostituzione. Inoltre gestisce in modo più completo gli "script" Unicode diversi dal "Latin"; per esempio la RE "(\w\d-)*" citata più sopra funziona anche con un testo di prova che includa lettere dell'alfabeto Arabo (l'interpretazione del meta-carattere \w è più multiculturale). [8] - Regex Cross­word consente di esercitarsi con una sorta di parole crociate in cui le definizioni sono sostituite da RE [9] ACRONIMI CL - Computational Linguistics NLP - Natural Language Processing RIFERIMENTI (webography) [1] Patrick Triest, You Should Learn Regex, https://blog.patricktriest.com/you-should-learn-regex/ (2017) [2] Regular Expressions Reference, https://www.regular-expressions.info/reference.html [3] Regex101, online regular expression exerciser, https://regex101.com/ [4] Notepad ++ a free source code editor, https://notepad-plus-plus.org/ [5] Scrapy - An open source framework for web spydering and scraping, https://scrapy.org/ [6] Sam Hughes, Learn regular expressions in about 55 minutes, https://qntm.org/files/re/re.html [7] Chandra Lingam, Python Regex Guide, Cheat Sheet And Interactive Tool (Video Tutorial), https://www.youtube.com/watch?v=Fkc-9iEhMKM (2016) [8] Regex Tester, online regular expression exerciser, http://regexstorm.net/tester [9] Regex Cross­word, online regular expression exerciser, https://regexcrossword.com/ [10] Comparison of regular expression engines, https://en.wikipedia.org/wiki/Comparison_of_regular_expression_engines DA WIKIPEDIA Pattern, https://en.wikipedia.org/wiki/Pattern Pattern recognition, https://en.wikipedia.org/wiki/Pattern_recognition Pattern matching, https://en.wikipedia.org/wiki/Pattern_matching Espressione regolare, https://it.wikipedia.org/wiki/Espressione_regolare Regular expression, https://en.wikipedia.org/wiki/Regular_expression