Crea serie di combinazioni uniche di array di stringhe

Question

sto scrivendo una cosa che richiede un blocco di testo e si rompe giù in possibili query di database che potrebbero essere utilizzati per trovare i blocchi simili di testo. (Qualcosa di simile alla lista "domande simili" viene generato, mentre scrivo questo) Il processo di base:

1. parole Rimuovere stop da testo
2. rimuovere i caratteri speciali
3. Da testo rimanente creare un array di unico " gambi"
4. creare un array di possibili combinazioni di matrice di steli (dove mi sono bloccato ... tipo di)

Ecco quello che ho finora:

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

} 

Questo funziona, ma su blocchi di testo più grande di 25 parole o giù di lì, si blocca il mio browser. Mi rendo conto che matematicamente ci potrebbe essere un numero enorme di combinazioni possibili. Quello che mi piacerebbe sapere è:

1. Esiste un modo più efficiente per farlo?
2. Come potrei definire un min/max combinazione lunghezza dell'array?

Answer 1

Penso che la tua logica sia fondamentalmente errata a causa di quante combinazioni stai creando.

Un approccio mi piacerebbe prendere sarebbe;

1. Spalato il testo in singole parole (che chiameremo questa variabile split_words)
2. rimuovere i caratteri speciali
3. Togliere brevi parole/comuni (e, o, I, a); o farlo in base alla lunghezza, o in modo più intelligente da una lista nera di parole
4. avere una tabella (ad esempio blocks), che ha colonne block_id e word

5. dispone di una query SQL, ad esempio

e poi avrete una lista di block_ids che vengono ordinati a seconda di quante parole in comune i blocchi hanno.

Answer 2

Trovato questa domanda precedente: Algorithm to find articles with similar text

Una delle risposte fornito un link ad un articolo che suggerisce di trovare quanti coppie di caratteri adiacenti sono contenuti in entrambe le stringhe. [http://www.catalysoft.com/articles/StrikeAMatch.html]

L'esempio è in Java, ma sono sicuro che può essere portato facilmente 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

Il tuo problema potrebbe essere facilmente risolto con la mia binomial coefficient class. Dai un'occhiata al codice dal mio answer a un problema in qualche modo correlato. Non so se il porting del codice C# su un processo memorizzato SQL sarebbe una buona idea o no.Probabilmente sarebbe più facile portarlo su java o js e chiamare i proc memorizzati da quel codice.