Algoritmo de nombre del producto

Question

Estoy trabajando en un nuevo sitio web que puede generar nombres de empresas/productos. Alguien puede ingresar al sitio y escribir un grupo de palabras que quizás quiera incluir en el significado del producto de alguna manera.

es decir, acaba de inventar un robot que limpia un derrame de petróleo. Ingresa una lista de palabras: robot, aceite, derrame, autónomo, inteligente, etc. El código tomará las palabras, buscará sinónimos, prefijos y sufijos para todas esas palabras y tratará de mezclarlas de manera genial.

El aceite produciría el sinónimo petróleo y el prefijo petro. Mashing que junto con el robot daría "Petrobot". O bien, para una nueva versión de un reloj de alarma, la lista: "inteligente, alarma, reloj, consciente, conectado" podría dar como resultado el nombre del producto "Reloj inteligente".

El sitio presentaría una lista de palabras combinadas y puede elegir de los mejores nombres.

Mi pregunta es esta. ¿Alguna idea sobre cómo generar estas palabras mezcladas? En este momento, voy a buscar sinónimos, prefijos y sufijos y los almacenaré en una matriz. Luego voy a buscar letras comunes entre las palabras y las superpongo tanto como sea posible. es decir, Direct TV se convierte en DirecTV. Esta búsqueda de fuerza bruta parece un poco poco elegante.

¿Hay algún otro método para generar nombres de productos que pueda pensar o un enfoque más sencillo al que sugerí?

Solo quería ver si había otro método que la gente pueda pensar. Por supuesto, este sitio será gratuito y estará abierto, y enlazaré con este tema en la página de aproximadamente del sitio, así que no piense en esta publicación como que me estoy beneficiando de la comunidad.

Answer 1

Guardaría todos los prefijos de las palabras en un multi-hashmaps. Para verificar si una palabra comienza con "bot" solo tendrías que hacer una búsqueda en el prefijo-mapa.

Después de eso, es solo un recorrido transversal del "gráfico" de palabras "conectables".

Algo como esto:

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"); 
    } 
} 

Prints:

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 

Si la velocidad es un problema aquí, es posible que desee cambiar los String s a StringBuilder s.

Answer 2

Un árbol de sufijos puede ser la estructura de datos que busca apoyar a sus diversas operaciones de manera eficiente: - http://en.wikipedia.org/wiki/Suffix_tree