Ricerca e conteggio di sottostringhe uguali in un insieme di stringhe

Question

Ricerca e conteggio di sottostringhe uguali in un insieme di stringhe

#1 da (2 voti)
#2 da (-1 voti)

7

Sto pensando a un modo per trovare parti simili in Stringhe. Ho un set di stringhe di lunghezza variabile, cioè:

Il quick brown fox salta
fox force five
il coniglio è molto più veloce della volpe
è

Per prima cosa, ho pensato solo a tokenizzare le stringhe e contare i token, ma nel caso di "quick" qui devo anche abbinare "più veloce".

Quindi l'output dovrebbe essere qualcosa del genere (una mappatura dei token al conteggio, se il conteggio è 1 è omesso):

{
  "the": 3,
  "fox": 3,
  "quick": 2,
  "is": 2
}

Il caso d'uso è il seguente:

L'utente raggruppa le stringhe in categorie, l'obiettivo è di fornire suggerimenti per una nuova stringa a quale categoria potrebbe appartenere. Quindi l'idea era di cercare tutte le stringhe correnti in una categoria per parole chiave come questa.

algorithms regular-expressions strings string-matching

posta Chris 07.07.2016 - 08:57

fonte

2 risposte

Leggi altre domande sui tag algorithms regular-expressions strings string-matching

È possibile simulare e inserire tratti in PHPUnit? Devo essere in grado di adattare il mio tipo al loro e il loro al mio

score 2 · Answer 1

Poiché il conteggio di stringhe identiche è banale, affronterò la parte della tua domanda relativa al fatto che il conteggio "più veloce" sia "veloce". Come menzionato nei commenti, questo è chiamato stemming Nota che la derivazione è specifica per la lingua, quindi dovrai sapere in quale lingua si trovano i tuoi termini.

Pubblicherò un esempio per Java poiché non hai specificato un linguaggio di programmazione. La libreria lucene-analyzers-common ha stemmer in molte lingue. Supponendo che l'inglese (altre lingue siano simili), vorresti fare qualcosa del tipo:

SnowballProgram stemmer = new EnglishStemmer();
// for each term:
stemmer.setCurrent(term);
stemmer.stem();
String stemmedTerm = stemmer.getCurrent();
// count terms

Tieni presente che la creazione di un EnglishStemmer non è così veloce, quindi desideri riutilizzare lo stesso attacco se le prestazioni sono importanti.

score -1 · Answer 2

Questa soluzione presuppone che le tue parole saranno separate da spazi. Per considerare eventuali segni di punteggiatura, si dovrebbe anche attenerli all'ingresso stringa alla chiamata temp.split (). Ovviamente se vuoi lavorare su più stringhe allora sarebbe meglio spostare la divisione e il ciclo in un metodo e chiamarlo per ogni stringa di input che vorresti fosse inclusa nel conteggio.

Hashmap<String,Integer> wordFrequency = new Hashmap<String,Integer>();
String temp = "whatever string thing is being checked"
String[] stringList = temp.split(" ");
for (string s : stringList){
    if (!wordFrequency.keySet().contains(s)){
        wordFrequency.put(s,1);
    }
    else{
        wordFrequency.put(s,wordFrequency.get(s)++);
    }
}
System.out.println(wordFrequency.entrySet()); 
//I believe that Set has a well defined toString() implementation