Algoritmo di denominazione del prodotto

Question

Sto lavorando a un nuovo sito Web che può generare nomi di società/prodotti. Qualcuno può entrare nel sito e digitare un gruppo di parole che potresti voler includere nel significato del prodotto in qualche modo.

Ad esempio, hai appena inventato un robot che pulisce una fuoriuscita di petrolio. Immetti un elenco di parole: robot, olio, versamento, autonomo, intelligente, ecc. Il codice prenderà le parole, troverà sinonimi, prefissi e suffissi per tutte quelle parole e cercherà di schiacciarle insieme in modo cool.

L'olio darebbe il sinonimo di petrolio e il prefisso petro. Mashing che insieme a robot darebbe "Petrobot". Oppure, per una nuova versione di una sveglia, l'elenco: "intelligente, allarme, orologio, consapevole, connesso" potrebbe fornire il nome del prodotto "Orologio Cognizant".

Il sito dovrebbe presentare un elenco di purè di parole e puoi scegliere tra i nomi migliori.

La mia domanda è questa. Qualche idea su come generare queste purè di parole insieme? Al momento, cercherò sinonimi, prefissi e suffissi e li memorizzerò in un array. Quindi cercherò lettere comuni tra le parole e le sovrapporrò il più possibile. cioè Direct TV diventa DirecTV. Questa ricerca di forza bruta sembra un po 'poco elegante.

Esistono altri metodi per generare nomi di prodotti a cui è possibile pensare o un approccio più semplice a quello che ho suggerito?

Volevo solo vedere se c'era un altro metodo a cui le persone possono pensare. Ovviamente questo sito sarà gratuito e aperto e collegherò a questo argomento nella pagina relativa al sito, quindi per favore non pensare a questo post come se io stessi approfittando della comunità.

Answer 1

Vorrei memorizzare tutti i prefissi delle parole in una multi-hashmap. Per verificare se una parola inizia con "bot", devi solo eseguire una ricerca nella mappa prefisso.

Dopodiché si tratta solo di una traversata in ampiezza del "grafico" di parole "collegabili".

Qualcosa di simile a questo:

import java.util.*; 

public class WordMasher { 

    int maxWordLen = 0; 
    Set<String> words = new HashSet<String>(); 
    HashMap<String, Set<String>> prefixes = new HashMap<String, Set<String>>(); 

    public WordMasher(String... words) { 
     for (String word : words) { 
      this.words.add(word); 
      maxWordLen = Math.max(maxWordLen, word.length()); 
      for (int i = 0; i < word.length() - 1; i++) 
       putPrefix(word.substring(0, i), word); 
     } 
    } 


    private void putPrefix(String pref, String word) { 
     getPrefixSet(pref).add(word); 
    } 


    public Set<String> getMashes() { 

     Set<String> mashes = new HashSet<String>(); 
     for (String word : words) { 
      Set<String> newWordsLeft = new HashSet<String>(words); 
      newWordsLeft.remove(word); 
      mashes.addAll(getMashes(word, newWordsLeft)); 
     } 

     return mashes; 
    } 

    private Set<String> getPrefixSet(String prefix) { 
     if (!prefixes.containsKey(prefix)) 
      prefixes.put(prefix, new HashSet<String>()); 
     return prefixes.get(prefix); 
    } 


    private Set<String> getMashes(String prefix, Set<String> wordsLeft) { 

     Set<String> mashes = new HashSet<String>(); 

     int prefLen = prefix.length(); 

     for (int n = Math.min(prefLen, maxWordLen); n >= 1; n--) { 

      String toMatch = prefix.substring(prefLen - n, prefLen); 
      List<String> alts = new ArrayList<String>(getPrefixSet(toMatch)); 
      alts.retainAll(wordsLeft); 
      for (String alt : alts) { 

       String newPrefix = prefix + alt.substring(n); 
       mashes.add(newPrefix); 

       Set<String> newWordsLeft = new HashSet<String>(wordsLeft); 
       newWordsLeft.remove(alt); 
       for (String tail : getMashes(newPrefix, newWordsLeft)) 
        mashes.add(tail); 
      } 
     } 
     return mashes; 
    } 


    public static void printProductNames(String... words) { 
     System.out.println("Products for " + Arrays.toString(words) + ":"); 
     for (String product : new WordMasher(words).getMashes()) 
      System.out.println(" " + product); 
     System.out.println(); 
    } 

    public static void main(String[] args) { 

     printProductNames("robot", "liquid", "oil", "cleaner", "spill", "turbo"); 
     printProductNames("world", "domination", "yellow", 
       "monkey", "donkey", "banana"); 
    } 
} 

Stampe:

Products for [robot, liquid, oil, cleaner, spill, turbo]: 
    turboiliquid 
    oiliquid 
    spilliquid 
    cleanerobot 
    roboturbo 
    cleaneroboturboil 
    roboturboiliquid 
    cleaneroboturbo 
    cleaneroboturboiliquid 
    turboil 
    roboturboil 

Products for [world, domination, yellow, monkey, donkey, banana]: 
    monkeyellow 
    yelloworldonkey 
    donkeyelloworld 
    donkeyelloworldomination 
    worldonkey 
    monkeyelloworldomination 
    yelloworldomination 
    worldomination 
    monkeyelloworldonkey 
    yelloworld 
    monkeyelloworld 
    donkeyellow 
    worldonkeyellow 

Se la velocità è un problema qui, si consiglia di modificare le String s per StringBuilder s.

Answer 2

Un albero suffisso può essere la struttura di dati che si sta cercando per supportare le varie operazioni in modo efficiente: - http://en.wikipedia.org/wiki/Suffix_tree