[JAVA] algoritmo di riconoscimento delle parole in un testo

[lillo85]

Salve a tutti,
devo realizzare un'applicazione che faccia un'operazione particolare:

supponiamo di avere memorizzato in una variabile di tipo String un testo lungo e non banale come per esempio il contenuto di un sms inviato tramite cellulare.
Lo scopo é implementare un algoritmo che possa "interpretare" il testo, ovvero analizzarlo e individuare determinate parole utili che corrispondono a parole chiave che per esempio fanno parte di un grande insieme di parole che abbiamo memorizzato da qualche parte (una sorta di vocabolario di riferimento).

Qualcuno ha dei suggerimenti o può aiutarmi a realizzare questo?grazie a tutti.

[clockover]

Magari ho capito male io cosa intendevi però c'è il metodo di String contains(Charsequence c) che ti dice se quella stringa contiene una una sequenza di caratteri richiesta! Poi forse ho capito male io cosa intendevi

[lillo85]

purtroppo non è facile nemmeno da spiegare..

in pratica ho un file xml che contiene determinate parole chiave che dovrei estrarre.. inoltre devo analizzare una stringa e individuare se ci sono o meno al suo interno delle parole che fanno parte dell'insieme di parole chiave citato sopra(estratto dal file xml).. non è una cosa banale.. proprio x questo avrei bisogno di suggerimenti.. forse si dovrebbe ricorrere anche ad algoritmi di elaborazione del testo complessi.. ma non so da dove iniziare .. se qualcuno ha dovuto affrontare lo stesso problema e ha dei suggerimenti .. grazie..

[clockover]

Secondo me trovi tutto qui http://download.oracle.com/javase/6/...ng/String.html

c'è di tutto. Cerca le parole, va alla loro posizione, ecc..

Se poi ti serve un parser XML se non mi sbaglio c'è la classe DOMParser della Apache Fundation, che però non ho mai usato! Magari cercando in rete trovi qualcosa di interessante.

[banryu79]

Una piccola considerazione, solo su questa parte:

...il testo, ovvero analizzarlo e individuare determinate parole utili che corrispondono a parole chiave che per esempio fanno parte di un grande insieme di parole che abbiamo memorizzato da qualche parte (una sorta di vocabolario di riferimento).

Notando che il "vocabolario" (il set di parole chiave) può essere formato da molti elementi, suggerisco l'utilizzo di un algoritmo di string matching del tipo "Rabin-Karp" con pattern multipli (la complessità resta lineare, quantificata rispetto al numero dei caratteri del testo in input e, suppongo, al numero dei caratteri del pattern più lungo).

Purtroppo devi implementarti a mano l'algoritmo, a meno che non trovi qualche libreria di terze parti che ne fornisca un'implementazione utile; non c'è niente del genere, che io sappia, nel JDK.

Tempo fa implementai una versione base del Rabin-Karp, te la posto più che altro come spunto: a te non serve direttamente perchè esegue la ricerca rispetto ad un singolo pattern, tu invece hai bisogno di confrontare pattern multipli contemporaneamente.
Devi capire a cosa serve e come viene utilizzato l'hashing, perchè è proprio questo che ti permetterebbe di considerare contemporaneamente N pattern durante il confronto.

Questo per quanto riguarda l'efficienza della ricerca nel testo delle parole chiave; altrimenti l'approccio "naive" è quello suggerito da clockover: per ogni parola chiave (per ogni pattern) esegui una ricerca sull'intero testo a colpi di String.indexOf...

Penso esistano anche altri algoritmi oltre al Rabin-karp e sue varianti per eseguire string matching con pattern multipli.
In ogni caso dovresti determinare anche le altre caratteristiche tipiche (lunghezza tipica del/dei pattern, lunghezza tipica del testo in input) che ti aspetti: i vari algoritmi di string matching possono essere più o meno indicati anche in base a questi parametri.

Ovviamente tutto questo "sbattimento" solo se l'efficienza è un requisito primario, e in tal caso varrebbe secondo me la pena di affrontare subito la questione, perchè a seconda dell'algoritmo scelto, delle sue caratteristiche e di eventuali altre esigenze specifiche della tua applicazione la strutturazione del codice di contorno potrebbe assumere diverse forme...

il mio RabinKarpMatcher giocattolo:

package stringmatching.algo;

import java.util.ArrayList;
import java.util.List;

/**
 * This algorithm is based on a hashing function to compute a value for each 
 * substring examined. So it speeds up the comparison between the pattern and 
 * the text substring (hash value examined vs explicitly checking each 
 * character) for mismatches (an explicit check must be performed to confirm 
 * a positive hash match).
 * Good algorithm for performing multiple-pattern searches, expecialy with long 
 * patterns.
 *
 * For implementation notes and values choosed for variables 'D' and 'Q' see:
 * http://www.cs.unibo.it/~martini/ASD/NotesuRK.htm
 *
 * The 'D' value rapresent the cardinality of the Alphabet, aka how many different 
 * values are mapped in the Alphabet. For Java String implementation consult the 
 * javadoc of class java.lang.Character to see how string of characters are 
 * rapresented. Here is a brief memo:
 *
 * 08 bit -> 255     (ASCII values)
 * 16 bit -> 65535   (UTF-16 values, as char in Java)
 * 21 bit -> 2097152 (Basic Multilingual Plane values, as int in Java)
 *
 * Q has to be a prime number chosen so that D*Q <= 2^31-1
 * Knowing that 2^31-1 = 2.147.483.647
 * For D=256 we can choose Q=8388593 
 * because (256*8388593=2.147.479.808) <= (2.147.483.647)
 * 
 * For D=65536 we can choose Q=32749 
 * because (65536*32749=2.146.205.715) <= (2.147.483.647)
 * 
 * @author Francesco Baro
 */
public class RabinKarpMatcher
{
    /** ASCII alphabet cardinality */
    public static final int D_ASCII = 256;

    /** UTF-16 alphabet cardinality */
    public static final int D_UTF16 = 65536;

    /** Alphabet cardinality used in hash calculations */
    protected static int D = D_UTF16;

    /** Complement used for modulo calculations */
    public static int Q = 32749;

    /**
     * Rabin-Karp string matching algorithm implementation.
     * @param text  the text.
     * @param pattern the pattern to look for in the text.
     * @return a List of all the offset in the text that are valid matches 
     * of the pattern.
     */
    public static List<Integer> doMatch(String text, String pattern) {
        List<Integer> matches = new ArrayList<Integer>();
        char[] T = text.toCharArray();
        char[] P = pattern.toCharArray();
        // initial hash values
        int p=0, t=0;
        for (int i=0; i<P.length; i++) {
            p = (D*p + P[i]) % Q;
            t = (D*t + T[i]) % Q;
        }
        // check matches & rehash
        final int h = (int) (Math.pow(D, P.length-1) % Q);
        for (int s=0; s<=T.length-P.length; s++) {
            if (p==t && isMatching(T,P,s))
                matches.add(s);
            if (s < T.length-P.length)
                t = (D * ((t+(Q-(T[s]*h)%Q))%Q) + T[s+P.length]) % Q;
        }
        return matches;
    }
    
    private static boolean isMatching(char[] T, char[] P, int s) {
        for (int i=0; i<P.length; i++)
            if (P[i] != T[i+s])
                return false;
        return true;
    }

    /**
     * Set the Alphabeth cardinality, this affects the maximus number of 
     * value/symbols recognised in the alphabet used in parsing the text 
     * and how the hash values are computed. Defaults to UTF-16.
     * @param cardinality
     */
    public static void setCardinality(int cardinality) {
        D = cardinality;
        // calculate maximum complement value for D:
        int num = 2147483647/D;
        while (!isPrime(num)) num--;
        Q = num;
    }

    // brute force prime number checker
    private static boolean isPrime(int candidate) {
        int div = 2;
        while (candidate%div != 0) {
            div++;
        }
        return div == candidate;
    }

}

Un test scritto al volo:

public RabinKarpTest
{
    public static void main(String[] args) {
        String text =
        "Figlio di Lulubelle Loon e di Eider Duck, nonché fratello di Abner, detto Chiarafonte," +
        " è un papero decisamente fantastico e dinamico. Grande studioso, al pari di Pico de Paperis, " +
        "da questi si differenzia soprattutto per il metodo: confusionario e basato soprattutto sulla " +
        "manualistica spicciola e sui corsi per corrispondenza, riprendendo e anzi esaltando all'ennesima " +
        "potenza alcuni aspetti della personalità di Pippo. Le sue avventure spesso prendono l'avvio dalle " +
        "sue idee stravaganti, che hanno sempre conseguenze tragicomiche e finiscono spesso per coinvolgere " +
        "anche Paperino. Al contrario del cugino, nervoso e pessimista, Paperoga è un tipo ottimista e " +
        "solare, tanto da rasentare l'ingenuità. Sempre vestito con maglione e cappello rosso, è uno dei " +
        "pochi paperi a presentare una capigliatura lunga e disordinata, in contrasto quindi soprattutto " +
        "con il cugino Gastone. Sua vittima preferita resta sempre e comunque il povero Paperino e il suo " +
        "gatto Malachia (Tabby) che, in alcune storie recenti apparse su Topolino, è il nome del gatto di " +
        "Paperoga. Nelle storie disegnate da Tony Strobl e apparse in Italia nei primi anni settanta " +
        "Paperoga possiede anche un cane, chiamato Arcibaldo in Italia.Spirito affine è il cugino " +
        "Sgrizzo Papero, personaggio ideato da Romano Scarpa. Tra l'altro il suo primissimo look ricorda " +
        "molto l'aspetto di Sgrizzo (capelli corti e disordinati) e verrà ripreso in alcune storie opera " +
        "sempre di Tony Strobl, a metà anni sessanta. Alla fine questo aspetto alla Sgrizzo di Paperoga " +
        "diventa così popolare nelle pubblicazioni statunitensi, che quando verrà tradotta l'Enciclopedia " +
        "Disney illustrata da Giovan Battista Carpi, si interviene in maniera pesante e maldestra sia " +
        "sul testo sia sui disegni nel tentativo di far passare Paperoga per il cugino Paperino. Se " +
        "Paperino dispone di un suo alter ego mascherato che lotta contro il male in Paperinik, anche " +
        "Paperoga possiede una identità segreta ovverosia Paper Bat, supereroe imbranatissimo e " +
        "sgangheratissimo dal mantello rosso come Superman  e dalla tuta grigia come il Batman della " +
        "serie televisiva degli anni '60 con Adam West, che agisce nelle tenebre notturne e immancabilmente " +
        "inciampa in qualche bidone della spazzatura facendo così svegliare e imbestialire il dormiente " +
        "vicinato.";
        
        // create large input text
        StringBuilder temp = new StringBuilder();
        int i = 0;
        while (i++ < 1000)
            temp.append(text);
        text = temp.toString();
        temp = null;

        String pattern = "Paperino";

        // perform RK string matchin
        long start = System.currentTimeMillis();
        List<Integer> matches = RabinKarpMatcher.doMatch(text, pattern);
        long end = System.currentTimeMillis();

        // compile output message
        String msg = "Pattern:\""+pattern+"\"\nFounded "+matches.size()+" matches on text";
        if (matches.size()>0)
            msg+=" at:\n";
        for (Integer index : matches)
            msg += index+", ";
        if (matches.size()>0)
            msg = msg.substring(0, msg.length()-2);
        msg += ".\n";
        msg += "in "+(end-start)+" millisec.";

        // print output message
        System.out.println(msg);
    }
}

Da me ci mette circa un centinaio di milisec a matchare tutte le 4000 occorrenze.

[lillo85]

grazie mille, mi riferivo proprio ad un algoritmo di questo tipo, e ho letto un po' come funziona, volevo chiederti però:
la funzione hash la si può scegliere di tipi differenti?

magari provo a cercare altri tipi di algoritmi che abbiano lo stesso scopo, cosi posso confrontarli e scegliere quello più adatto, il problema è anche riuscire a implementare però algoritmi cosi complessi, se hai /avete altri suggerimenti li accetto volentieri,

grazie mille per l'aiuto e le spiegazioni..

[dierre]

Scusa ma che intendi per interpretare il testo? Se hai bisogno di "dedurre" qualcosa, io suggerirei di usare un'ontologia.
Oppure hai semplicemente bisogno di riconoscere dei pattern specifici invece che singole parole?

[lillo85]

intendo questo:

ho un testo all'interno di una stringa e devo analizzare questo testo per verificare se al suo interno sono presenti delle parole che fanno parte di pattern multipli specifici..

Inoltre tali pattern sono i valori associati a parole chiave che si trovano all'interno di un file xml ( che dovrò anche analizzare per estrarre tali valori, e guarda caso tale file xml è proprio un'ontologia)

quindi mi ci vuole un buon algoritmo (non banale) che sappia fare l'analisi e individuare le corrispondenze..

[dierre]

Ah ok!

Datti una letta qui: http://bio.informatics.indiana.edu/s...I690/aomtp.pdf