-1

Ich möchte prüfen, ob ein Satz ein Wort aus einer Liste von Wörtern enthält, die einer Kategorie zugeordnet sind. Also habe ich eine Klasse KeyValue.java mit Wörtern, Kategorienamen und einer Methode filterCategory, um zu prüfen, ob sie das Wort enthält. Jetzt habe ich 10.000 Schlüsselwörtern verschiedene Kategorien für den Text zugeordnet. Aber das Problem ist, es ist viel zu langsam. Können Sie alternative Methoden vorschlagen, um die Klassifizierung zu beschleunigen? Danke für die Hilfe.Überprüfen Sie, ob ein Satz ein Wort aus einer Liste enthält.

public class KeyValue { 
private String key; 
private String value; 

public KeyValue(String key, String value) { 
    this.key = key; 
    this.value= value; 
} 
public KeyValue() { 
} 
public String getKey() { 
    return key; 
} 
public void setKey(String key) { 
    this.key = key; 
} 
public String getValue() { 
    return value; 
} 
public void setValue(String value) { 
    this.value = value; 
} 

Classification.java

class Classification 
{ 

private static List<KeyValue> keyMap = new ArrayList<KeyValue>(); 

static{ 
    getWordMap(); 
} 

public static List<KeyValue> getWordMap() 
{   
    if(keyMap.size()==0) 
    { 
     keyMap.add(new KeyValue("sports","football")); 
     keyMap.add(new KeyValue("sports","basketball")); 
     keyMap.add(new KeyValue("sports","olympics")); 
     keyMap.add(new KeyValue("sports","cricket")); 
     keyMap.add(new KeyValue("sports","t20")); 
    } 
} 

public static KeyValue filterCategory(String filteredText) 
{    
    KeyValue kv = null; 

    for(KeyValue tkv:keyMap) 
    { 
     String value = tkv.getValue(); 
     String lc = filteredText.toLowerCase(); 
     lc = FormatUtil.replaceEnglishSymbolsWithSpace(lc);//remove symbols with space and then normalizes it 

     String lastWord=""; 
     if(lc.contains(" ")) 
     { 
      lastWord = lc.substring(lc.lastIndexOf(" ")+1); 

      if(lc.startsWith(value+" ") || lc.contains(" "+value+" ") || value.equals(lastWord)) 
      { 
       kv = new KeyValue(tkv.getKey(), tkv.getValue()); 
       break; 
      }    
     } 
     else if(lc.contains(value)) 
     { 
      kv = new KeyValue(tkv.getKey(), tkv.getValue()); 
      break;    
     } 
    } 

    if(kv==null) 
    { 
     return new KeyValue("general","0"); 
    } 
    else 
    { 
     kv.setValue("100"); 
     return kv; 
    } 
} 
} 
+0

Schauen Sie in Guava 'Multimap', wie es eine gute ADT ist, dafür zu verwenden. –

+0

Ich bin mir nicht sicher, ob es die Leistung in irgendeiner Weise verbessern wird. – akay

+0

Ein schneller Test gab mir eine ziemliche Verbesserung, als ich den "Kleinbuchstaben" (und den FormatUtil-Aufruf) vor die for-Schleife stellte. Sie müssen es nicht für jeden Schlüssel tun. –

Antwort

0

Ich verstehe nicht, warum Sie sich für dieses Anliegen verwenden Java util.Map nicht, aber ich rate Ihnen, Gebrauch iterieren:

lc = FormatUtil.replaceEnglishSymbolsWithSpace(lc); 
String result= Arrays.stream(lc.split(" ")).filter(s -> s.equals(value)).findFirst().orElse(""); 
      if(result.length()>0) { 
       kv = tkv; 
      } 
+0

Op's Bedingung für ein Match ist anders. Falls mehrere Wörter vorhanden sind, stimmen sie nur überein, wenn sie ** gleich ** sind. Ansonsten stimmt es auf ** enthält ** bereits überein. –

0

Ihre Implementierung ist solide, aber verwendet einen Exhaustive or Brute-Force Search-Algorithmus mit Ihrem KeyValue-Objekt anstelle eines schnelleren übereinstimmenden Algorithmus wie Hashing mit einem HashMap or Hashtable-Objekt.

Annahmen

  • Sie haben 10.000 abgebildet Worte.
  • Sie versuchen, diese Worte gegen einen englischen Satz oder eine Phrase passen wie „Der schnelle braune Fuchs über den faulen Hund springt

Das Problem

Ihre Logik, wie es geschrieben wird, führt eine Brute-Force-Suche durch und versucht 10.000 Übereinstimmungen für jedes Wort in Ihrem Satz. Unter Verwendung des obigen Ausdrucks wird (10.000) x (9) = 90.000 maximale Versuche erstellt, wenn jedes Wort in dem Satz in Ihrem KeyValue-Objekt nicht vorhanden ist.

Diese Logik erzeugt eine Worst-Case oder Big-O, Leistungseinbußen von Θ(n) wo n die Anzahl der Worte in der Liste steht. Dies wird als lineare Suche bezeichnet. Eine faule Verbesserung dieser Methode wäre die Verwendung einer sortierten Liste, die Ihnen eine bessere logarithmische Suche Zeit.

The Fix

Statt Ihre Brute-Force-Suche durchführen, einen Hash-Algorithmus verwenden, die Lookups auf ganze Wörter zu einem Zeitpunkt durchführen wird; oder, wenn Sie eine Mustererkennung mit Zeichenverschiebung durchführen möchten, sehen Sie sich die Rabin—Karp Hash Algorithm an. Im vereinfachten Fall, dass nur ganze Wörter abgeglichen werden, wird Ihr Algorithmus die Wörter Ihres Satzes in Token zerlegen (wie Sie es jetzt tun), und dann eine Hash-Funktion verwenden, die auf Ihre Hash-Werte und zugehörige Kategorien aufsetzt.

Ihre neue Logik trägt eine Big-O-Leistung von Θ(1). Dieser Abgleich mit konstanter Zeit verbessert die Geschwindigkeit Ihrer Anwendung erheblich.

Pseudocode

// Adapting your KeyValue into a simple <Value, Key> map e.g. <"football", "sports"> 
//HashMap<String, String> map = new HashMap<String, String>(); 

// Adapting your KeyValue into a <Value, Set<Key>> map for multiple 
// category keys e.g. <"football", <"sports","sunday","games">> 
HashMap<String, Set<String>> map = new HashMap<String, Set<String>>(); 

// build the hashmap with your values and categories 
Set<String> categories = new HashSet<String>(); 
categories.add("sports"); 
categories.add("sunday"); 
categories.add("games"); 
map.put("football", categories); 
... 

// sanitize your input 
String lc = filteredText.toLowerCase(); 
lc = FormatUtil.replaceEnglishSymbolsWithSpace(lc); 

// tokenize your sentence 
String[] tokens = lc.split("\\s"); 
... 

// search tokens against your hashmap 
for (String token : tokens) { 

    // search the token against the hashmap 
    if (map.containsKey(token)){ 
     Set<String> cats = map.get(token); 
     ... 
    } else { 
     ... 
    } 
} 
+0

Dies ist nicht 0 (1). Wir werden immer noch die Token durchlaufen und je nach Satz. Es könnte ein Zeitungsartikel mit vielen Marken sein. – akay

+0

@akay Die Übereinstimmung eines Wortes im Satz mit der HashMap von Token wird ** Θ (1) ** anstelle von ** Θ (n) **. Dies liegt daran, dass die Hash-Funktion eine Suche mit konstanter Zeit im Vergleich zum linearen Versuch des Abgleichs mit jedem einzelnen Token in der Liste ist, bis sie gefunden wurde (oder nicht gefunden wurde). Kannst du bitte weiter erklären, wenn etwas fehlt? – outkst

+0

Wir haben 10.000 Wörter zu 100 Kategorien zugeordnet. Um herauszufinden, ob ein Satz dieses Schlüsselwort enthält oder nicht, müssen Sie jedes Wort im schlimmsten Fall gegen 10.000 prüfen. Wie kann das 0 (1) sein? Wenn Sie Code schreiben können, der schneller als der Code funktioniert, den ich unten gepostet habe, wird es viel helfen. – akay

0

Auf der Grundlage der Vorschläge, die ich den schnellsten Code bin Entsendung i einfiel.

KeyValue basierte Liste hat in einfache HashMap

für die Vorschläge
private static HashMap<String,String> map = new HashMap<String,String>(); 

Dank modifiziert. Es ist jetzt skalierbar, um in Produktion gebracht zu werden.

public static KeyValue filterCategory(String filteredText) 
{    
    KeyValue kv = null; 
    filteredText = filteredText.toLowerCase(); 
    filteredText = FormatUtil.replaceEnglishSymbolsWithSpace(filteredText); 

    StringTokenizer tokenizer = new StringTokenizer(filteredText); 
    while(tokenizer.hasMoreTokens()) { 
     String temp = tokenizer.nextToken(); 
     if(map.containsKey(temp)) 
     { 
      kv = new KeyValue(map.get(temp),"100"); 
      break; 
     } 
    }  
    if(kv==null) 
    { 
     kv= new KeyValue("general","0"); 
    } 
    return kv; 
} 
Verwandte Themen