Applicativo per analisi testo libero

[phantom85]

Ciao a tutti,

per motivi didattici devo realizzare un programma che prende in input un testo (piuttosto breve, sui 200 caratteri circa) e da questo testo estragga 4 elementi (Nome, Aggettivi, Città, Indirizzo).

Il testo però che prende in input è libero, cioè non ha un ordine preciso e quindi devo realizzare qualcosa che analizzi il testo. Mi riferisco al campo del text mining...

Gli aggettivi sono riferiti al nome, ad esempio il nome è in genere di una persona e l'aggettivo può essere la professione di questa persona o qualsiasi tipo di caratteristica fisica (alto, basso ecc ecc). Inoltre gli aggettivi possono non esserci nel testo.

Stesso discorso per l'indirizzo che può essere omesso nel testo.

Aggiungo che ho 4 raccolte (database) sui Nomi, Aggettivi, Città e Indirizzi...ma per ora non vorrei preoccuparmi di come collegare l'applicativo ai database ma soprattutto vorrei capire che algoritmo del text mining utilizzare e successivamente come implementarlo.


Qualcuno saprebbe darmi qualche consiglio? :)

Grazie ;)

[MEMon]

butta giù qualche esempio di input, così ragioni su qualcosa di concreto.

[phantom85]

Ad esempio:

Vorrei trovare Samantha alta vicino piazza Navona a Roma :D :D :D

E' un esempio come un altro e da questo testo vorrei che un applicativo estraesse ciò:

Nome: Samantha
aggettivi: alta
Città: Roma
indirizzo: piazza Navona

:confused:

[MEMon]

Ma la frase deve essere corretta?
Per dire, i nomi propri e i nomi di città devono essere obbligatoriamente inseriti con la iniziale maiuscola?

Gli indirizzi devono essere preceduti da parole chiave quali:via, viale, piazza ecc ecc?

[MEMon]

Sei sicuro che il l'input non sia più semplicemnte una cosa del genere:

"Giovanni Rossi abita a Roma in via Trastevere n°100"

Magari con le posizioni scambiate ma comunque di questo tipo...

No perchè altrimenti se hai una frase del genere:
"Lunedì mi trovo con Jessica la tettona al pub in via Garibaldi, e martedì vado ad un rave party in piazza Tal dei Tali insieme a Pamela la sfacciata."
Qui cosa dovresti tirar fuori?

[phantom85]

Hai fatto bene a chiedere queste cose!

Sicuramente il testo può essere scritto con o senza maiuscole, o meglio, non ci deve essere differenza tra lettera maiuscola o minuscola.

L'esempio che hai fatto (giovanni rossi abita...) è quello a cui mi riferisco. Anche perchè il testo di input sarà piuttosto breve! L'ordine non conta.

E' anche corretto supporre che l'indirizzo sia preceduto da parole chiave come via, piazza ecc

[banryu79]

Sicuramente il testo può essere scritto con o senza maiuscole, o meglio, non ci deve essere differenza tra lettera maiuscola o minuscola.

Beh, con questa hai già tirato fuori una regola:
- dato il testo in input, trasformare ogni parola in "lower case".

[phantom85]

Beh, con questa hai già tirato fuori una regola:
- dato il testo in input, trasformare ogni parola in "lower case".

Ok sicuramente potrebbe essere l'inizio...

...per il resto però non so ancora come fare. Sto leggendo qualcosa sul text mining e ho letto del cosiddetto "tagging" che consiste nel "taggare" (stile facebook :D :D :D ) le parole, in base a cosa rappresentano. Naturalmente il tagging va fatto solo sulle parole di mio interesse, quindi saltando congiuzioni, preposizioni ecc ecc

ES:

Giovanni Rossi abita a Roma in via Trastevere n°100


<nome>Giovanni Rossi</nome> abita a <citta>Roma</citta> in <indirizzo>via Trastevere</indirizzo> n° 100.


PS: del numero civico non mi interessa ;)

[banryu79]

Il secondo passo è quello di mettere la mani su ogni singola parola (token), per poi poterla analizzare.

Forse prima è il caso di stabilire quali sono i tipi di token di interesse (es.: NOME, AGGETTIVO) e quindi fissare le regole che caratterizzano quel tipo di token.

Sto "pensando ad alta voce"; non sono un esperto in materia, ma sto solo ragionando.
Non so se il tuo caso è risolvibile con l'applicazione di un automa a stati finiti per il parsing del testo in input e l'estrazione e catalogazione dei singoli token, magari è il caso.

Resterebbe solo da stabilire quali sono le regole che identificano un NOME da un qualsiasi altro token, e in particolare che determinano se un determinato token di tipo NOME è un NOME_PERSONA o NOME_CITTA', per dire.


Aggiungo che ho 4 raccolte (database) sui Nomi, Aggettivi, Città e Indirizzi...

Questo significa forse che non devi stabilire tu delle regole per identificare il tipo di un dato token, ma basta che lo confronti con i dati a disposizione fino a che non trovi una corrispondenza?
Oppure devono esistere lo stesso le regole e la base dati viene usata per raccogliere tutti i token già identificati (e quindi a sua volta è usata per anche per l'identificazione di un nuovo token?)

Si vede che sono ignorante in materia? :D

[phantom85]

banryu79...innanzitutto grazie per la risposta :)

Seconda cosa: non mi sembri affatto un ignorante in materia. Io ho iniziato ad addentrarmi in questo campo da poche settimane quindi vista la complessità dell'argomento, non ne so ancora molto...:mc:

La questione degli automi a stati finiti la stavo leggendo giusto oggi, in particolare il discorso dell' Hidden Markov Model.

Per il discorso delle basi di dati credo proprio che dovrò realizzare l'identificazione del token prima di collegarmi al rispettivo db. :rolleyes:

Come potrei realizzare le regole per ogni singolo token?

[banryu79]

Seconda cosa: non mi sembri affatto un ignorante in materia. Io ho iniziato ad addentrarmi in questo campo da poche settimane quindi vista la complessità dell'argomento, non ne so ancora molto...:mc:

Guarda, la mia non è falsa modestia: quando ti ho detto che sono ignorante in materia intendevo alla lettera :O
Cioè non ne so nulla, quello he ho scritto è frutto di mie congetture :D


Come potrei realizzare le regole per ogni singolo token?

Ecco, questo E' il problema.

Supponiamo di aver stabilito questi due passi iniziali:
[1] dato il testo in input, produrre in output il testo equivalente in cui ogni parola è trasformata in "lower case";
[2] dato il testo prodotto al punto [1] come input, produrre in output la pila formata da tutte le singole parole (token) incontrate nel testo: questo significa il non considerare i segni di punteggiatura e gli spazi bianchi (sto implicitamente assumendo il fatto che spazi e punteggiatura non ci servono per verificare le regole di individuazione e catalogazione dei token, cosa che potrebbe essere falsa, ma come ho detto sono ignorante in materia).

Ora facciamo un'ulteriore supposizione: che i tipi di token che ci interessano siano solo questi due:
NOME - un qualsiasi sostantivo (tavolo, Luca, Parma, prosciutto, patata, ecc..)
AGGETTIVO - un qualsiasi aggettivo riferito a un sostantivo (marrone[riferito a tavolo], babbeo[riferito a Luca], popolata[riferito a Parma], squisito[riferito a prosciutto], americana[riferito a patata])

Come si fa nel seguente testo di input:

"La patata americana è sul nuovo tavolo di Luca."

ad estrarre i diversi token che abbiamo definito sopra?
--
token_type: NOME, token_value: "patata";
token_type: AGGETTIVO, token_value: "americana", token_refTo: "patata";
--
token_type: NOME, token_value: "tavolo";
token_type: AGGETTIVO, token_value: "nuovo", token_refTo: "tavolo";
--
token_type: NOME, token_value: "Luca";

Io suppongo di partire da una pila che, per il testo di input qui sopra, dopo l'applicazione del punto [2], sarebbe così formata:
[Luca] <- top
[di]
[tavolo]
[nuovo]
[sul]
[è]
[americana]
[patata]
[La]

A questo punto la pila verebbe passata come input all'algoritmo che la analizza (in base alle regole stabilite per identificare i singoli token di interesse) per estrarre tutti i token interessanti.

Definire, per ogni tipo di token desiderato, l'insieme di regole che lo individuano in un qualsiasi testo temo sia parecchio complesso: prova solo a riflettere sul come identificare il toke di tipo NOME.

E' chiaro che se non si può fare nessuna assunzione sul testo in input la cosa diventa ben complessa: vicecersa se sappiamo in anticipo qualcosa sul come è fomato il testo in ingresso, possiamo fare delle assunzioni che ci facilitano il compito di scrivere il nostro analizzatore lessicale (credo di questo si tratti, cioè di un analizzatore lessicale).

Magari non c'entra niente, ma tanto per farti un'idea su cosa sia uno scanner (analizzatore lessicale) e sul discorso della categorizzazione dei token, prova a leggere questi due articoli (il sito è di un utente di questo forum):
- http://www.guidealgoritmi.it/ShowArticle.aspx?ID=2
- http://www.guidealgoritmi.it/ShowArticle.aspx?ID=6

Spero per te che qualche utente più esperto intervenga nella discussione, ciao :)

[phantom85]

A questo punto la pila verebbe passata come input all'algoritmo che la analizza (in base alle regole stabilite per identificare i singoli token di interesse) per estrarre tutti i token interessanti.

Definire, per ogni tipo di token desiderato, l'insieme di regole che lo individuano in un qualsiasi testo temo sia parecchio complesso: prova solo a riflettere sul come identificare il token di tipo NOME.

E' chiaro che se non si può fare nessuna assunzione sul testo in input la cosa diventa ben complessa: vicecersa se sappiamo in anticipo qualcosa sul come è fomato il testo in ingresso, possiamo fare delle assunzioni che ci facilitano il compito di scrivere il nostro analizzatore lessicale (credo di questo si tratti, cioè di un analizzatore lessicale).

Eh si, stabilire le regole credo sia alquanto difficile, in quanto come hai appunto notato tu la situazione cambia nel caso si potessero fare assunzioni sul testo (tipo sintassi, ordine della parole ecc ecc). Il problema è che nel mio caso si tratta di un testo libero, insomma un po' come quando si fa una ricerca su un motore di ricerca, alla fine si può scrivere quello che si vuole ma il motore di ricerca spesso restituisce proprio ciò che avevamo intenzione di cercare!

Sulle assunzioni però vorrei chiarire un attimo in questi giorni, probabilmente un minimo di assunzione si potrebbe fare...ci devo ragionare.

C'è anche un'altra cosa...consideriamo questo esempio


Vorrei trovare una massaggiatrice thailandese a Olbia.



In questo caso quello che mi interessa è:
NOME == massaggiatrice
AGGETTIVO == thailandese
CITTA == olbia

del resto non mi interessa.

Ma se ad esempio avessi questa situazione


Vorrei cercare una massaggiatrice massaggiatrice thailandese a Olbia


In questo caso ciò che mi interessa è uguale al caso precedente e vorrei che la ripetizione errata di massaggiatrice non venga considerata.


Spero per te che qualche utente più esperto intervenga nella discussione, ciao :)

Ti ringrazio per l'aiuto in ogni caso...fossero tutti così disponibili!! :)

[banryu79]

Ciao,
senti, ma se in input devi ricevere un testo in linguaggio naturale (in italiano insomma) immesso da un utente che potenzialmente può scrivere quel che gli pare, sono dolori :D

In pratica il tuo analizzatore lessicale, in teoria, si troverebbe a dover fare i conti con la grammatica della lingua italiana.
La situazione quindi non è proprio "semplice" come potrebbe essere, se invece stessimo parlando di un analizzatore lessicale per un linguaggio formale.

Ti consiglio la lettura di queste informazioni (la fonte è wikipedia) per farti un'ulteriore idea: inoltre nella pagina in inglese trovi utili riferimenti per mettere (forse) arrivare a mettere le mani su informazioni precise circa eventuali tecniche già sperimentate per l'analisi linguistica (che mi sembra e temo :D sia quello che a te occorre).

- http://it.wikipedia.org/wiki/Grammatica_formale#Grammatiche_analitiche
- http://en.wikipedia.org/wiki/Formal_grammar#Analytic_grammars

Questo è più specifico:
- http://en.wikipedia.org/wiki/Link_grammar

Prendi con le pinze tutto quello che ti ho detto, ripeto, sono idee che mi sono fatto oggi, dopo aver letto il tuo post e aver eseguito dei collegamenti nel mio cervello con vari concetti sentiti a pezzettini e mai approfonditi :sofico:

[phantom85]

Qui mi sa che la questione è molto più grande del previsto :mc: :mc: :mc:

[phantom85]

Forse ho individuato il campo della questione.

Il Text Mining è qualcosa di enorme, vastissimo e cercare di individuare il modello e i concetti che si avvicinano di più al mio problema è piuttosto difficile.

Tuttavia grazie anche ai tuoi link e grazie al supporto del manuale sul Text Mining credo che il mio caso riguardi la cosiddetta Stochastic Context-Free Grammar.

Ora cercare di rendere concrete queste teorie mi risulta alquanto oscuro...:( :( :(

[banryu79]

Forse ho individuato il campo della questione.
[...snip...]
credo che il mio caso riguardi la cosiddetta Stochastic Context-Free Grammar.
Partendo da quella nozione ho trovato queste due pagine wiki che potrebbero interessarti (info generiche e link a risorse esterne), ma soprattutto, un tool in Java hostato su sourceforge, che potrebbe fare al caso tuo, se per quello che devi implementare puoi appoggiarti a framework esistenti, oppure come fonte di consultazione e studio, se devi neccessariamente farti tutto da zero.

Comunque la mole di teoria che sta dietro all'intera faccenda è enorme (e sicuramente interessantissima).

[1] - Natural language processing (http://en.wikipedia.org/wiki/Natural_language_processing)
[2] - Part-of-speech tagging (http://en.wikipedia.org/wiki/Part-of-speech_tagging)
[3] - JTextPro: A Java-based Text Processing Toolkit (http://jtextpro.sourceforge.net/)

[phantom85]

Ti ringrazio per l'ennesima volta :)

Per quanto riguarda l' NLP avevo incontrato il tema durante la lettura di un testo sul text mining. Anche l'NLP è un campo vastissimo...purtroppo :D

Il POS-tagging invece l'ho capito abbastanza bene, o almeno la teoria, infatti ne avevo parlato nel mio post 8 e credo sia una delle possibili vie da seguire. Il problema è che anche sui libri non c'è scritta quasi mai la risposta alla mia domanda "Come fare" ma quasi sempre spiega di cosa si tratta. :muro:

Ho letto che esistono molti tagger sviluppati, ma sono quasi introvabili :cry:

Ho scaricato il tool, lo proverò su linux essendo file tar.gz e spero di riuscire a usarlo e a capirne il funzionamento. Naturalmente posso utilizzare qualsiasi cosa per raggiungere lo scopo, l'importante è capire!

Concordo con te che la mole di teoria dietro alla questione è ENORME, ma anche io la reputo molto interessante!! ;)

edit: ho trovato anche questo (http://www.danieldk.eu/Code/Jitar) ma non ho idea di come farlo partire...:mbe:

[phantom85]

[3] - JTextPro: A Java-based Text Processing Toolkit (http://jtextpro.sourceforge.net/)

Ehm...ho avviato ubuntu e ho utilizzato i soliti comandi per installarlo...ma mi dà un sacco di errori... :( :( :(

[banryu79]

edit: ho trovato anche questo (http://www.danieldk.eu/Code/Jitar) ma non ho idea di come farlo partire...:mbe:

Non ho capito se ti rifersci a Citar (implementato in C++) oa Jitar (porting in Java di Citar).

Nel caso tu sia interessato a Citar, nella pagina che hai linkato è spiegato come utilizzarlo:

Building Citar

Builing Citar requires a C++ compiler and Qt 4.5.

Citar can be built on Unix systems by invoking the ''qmake'' command which creates the build infrastructure, followed by ''make''. Command-line utilities for training and evaluating the tagger will be produced. Compilation will also produce the libsitar.a library, which you can use to integrate the tagger in your own programs.


Se invece eri interessato a Jitar, basta che ti scarichi lo zip contenente i sorgenti e leggi il file Readme: c'è scritto tutto. Occhio che per farlo girare serve almeno la versione 5 del JDK (adesso siamo arrivati alla 6 e qualcosa).

Consultando un post della developement group/list (http://groups.google.com/group/jitar-devel) ci sono indicazioni su come ottenere un "Brown corpus" per eseguire il training. Inoltre l'autore dice che Jitar è stabile, nel senso che i bug sono stati risolti e che il sistema di tagging è soddisfacente. Lo sviluppo è ancora attivo.

Ciao :)

[phantom85]

Non ho capito se ti rifersci a Citar (implementato in C++) oa Jitar (porting in Java di Citar).

Nel caso tu sia interessato a Citar, nella pagina che hai linkato è spiegato come utilizzarlo:


Se invece eri interessato a Jitar, basta che ti scarichi lo zip contenente i sorgenti e leggi il file Readme: c'è scritto tutto. Occhio che per farlo girare serve almeno la versione 5 del JDK (adesso siamo arrivati alla 6 e qualcosa).

Consultando un post della developement group/list (http://groups.google.com/group/jitar-devel) ci sono indicazioni su come ottenere un "Brown corpus" per eseguire il training. Inoltre l'autore dice che Jitar è stabile, nel senso che i bug sono stati risolti e che il sistema di tagging è soddisfacente. Lo sviluppo è ancora attivo.

Ciao :)


Grazie, mi riferivo a Jitar...appena ho un attimo di tempo faccio delle prove leggendo il readme.

Ora mi sto avventurando nella creazione dell'automa dell'algoritmo...:muro:


edit: nel frattempo sto facendo delle ricerche su vari analizzatori lessicali, ma purtroppo tutti quelli che trovo sono analizzatori di linguaggi di programmazione e non di testi "normali"...