Una piccola considerazione, solo su questa parte:
Quote:
|
...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:
Codice:
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:
Codice:
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.