Crear una matriz de combinaciones únicas a partir de una matriz de cadenas

Question

Estoy escribiendo algo que toma un bloque de texto y lo divide en posibles consultas de bases de datos que podrían usarse para buscar bloques de texto similares. (Algo similar a la lista de "preguntas similares" que se genera mientras escribo esto) El proceso básico:

1. palabras Retire el tope de texto
2. Quitar los caracteres especiales
3. De texto restante crear una matriz de único " tallos"
4. crear una matriz de combinaciones posibles del conjunto de filamentos (donde estoy atascado ... tipo de)

Esto es lo que tengo hasta ahora:

//baseList starts with an empty array 
    //candList starts with the array of unique stems 
    //target is where the arrays of unique combinations are stored 

    function createUniqueCombos(baseList,candList,target){ 

    for(var i=0;i<candList.length;i++){   

     //copy the base List 
     var newList = baseList.slice(0); 

     //add the candidate list item to the base list copy 
     newList.push(candList[i]); 

     //add the new array to the target array 
     target.push(newList); 

     //re-call function using new array as baseList 
     //and remaining candidates as candList 
     var nextCandList = candList.slice(i + 1);  
     createUniqueCombos(newList,nextCandList,target); 
    } 

} 

Esto funciona, pero en bloques de texto de más de 25 palabras, bloquea mi navegador. Me doy cuenta de que matemáticamente podría haber una gran cantidad de combinaciones posibles. Lo que me gustaría saber es:

1. ¿Hay alguna manera más eficiente de hacerlo?
2. ¿Cómo podría definir una longitud de matriz de combinación mínima/máxima?

Answer 1

Creo que su lógica es fundamentalmente defectuosa debido a la cantidad de combinaciones que está creando.

Un enfoque que tomaría sería;

1. Dividir el texto en palabras individuales (que llamaremos esta variable split_words)
2. Quitar los caracteres especiales
3. Eliminar palabras cortas/comunes (y, o, I, a); o bien hacerlo por la longitud, o más inteligente por una lista de negro de las palabras
4. tiene una tabla (por ejemplo blocks) que tiene columnas block_id y word

5. tiene una consulta SQL como

y luego tendrá una lista de block_ids que se ordenan dependiendo de cuántas palabras en común tienen los bloques.

Answer 2

Encontrado esta pregunta anterior: Algorithm to find articles with similar text

Una de las respuestas proporciona un enlace a un artículo que sugiere la búsqueda de cuántos pares de caracteres adyacentes están contenidos en ambas cadenas. [http://www.catalysoft.com/articles/StrikeAMatch.html]

El ejemplo está en Java, pero estoy seguro de que puede ser portado fácilmente a JS:

/** @return an array of adjacent letter pairs contained in the input string */ 
private static String[] letterPairs(String str) { 
    int numPairs = str.length()-1; 
    String[] pairs = new String[numPairs]; 
    for (int i=0; i<numPairs; i++) { 
     pairs[i] = str.substring(i,i+2); 
    } 
    return pairs; 
} 

/** @return an ArrayList of 2-character Strings. */ 
private static ArrayList wordLetterPairs(String str) { 
    ArrayList allPairs = new ArrayList(); 
    // Tokenize the string and put the tokens/words into an array 
    String[] words = str.split("\\s"); 
    // For each word 
    for (int w=0; w < words.length; w++) { 
     // Find the pairs of characters 
     String[] pairsInWord = letterPairs(words[w]); 
     for (int p=0; p < pairsInWord.length; p++) { 
      allPairs.add(pairsInWord[p]); 
     } 
    } 
    return allPairs; 
} 

/** @return lexical similarity value in the range [0,1] */ 
public static double compareStrings(String str1, String str2) { 
    ArrayList pairs1 = wordLetterPairs(str1.toUpperCase()); 
    ArrayList pairs2 = wordLetterPairs(str2.toUpperCase()); 
    int intersection = 0; 
    int union = pairs1.size() + pairs2.size(); 
    for (int i=0; i<pairs1.size(); i++) { 
     Object pair1=pairs1.get(i); 
     for(int j=0; j<pairs2.size(); j++) { 
      Object pair2=pairs2.get(j); 
      if (pair1.equals(pair2)) { 
       intersection++; 
       pairs2.remove(j); 
       break; 
      } 
     } 
    } 
    return (2.0*intersection)/union; 
} 

Answer 3

Su problema podría resolverse fácilmente con mi binomial coefficient class. Eche un vistazo al código de mi answer a un problema algo relacionado. No sé si portar el código C# a un programa SQL almacenado sería una buena idea o no.Probablemente sería más fácil transferirlo a java o js y llamar a los procs almacenados desde ese código.