Utwórz tablicę unikatowych kombinacji z tablicy łańcuchów

Question

Piszę coś, co zajmuje blok tekstu i dzieli go na możliwe zapytania bazy danych, które mogą być użyte do znalezienia podobnych bloków tekstu. (Coś podobnego do listy „podobne pytania” jest generowany podczas gdy to piszę) Podstawowy proces:

1. Usuń przystanek słowa z tekstu
2. usunąć znaki specjalne
3. Z pozostałego tekstu utworzyć tablicę wyjątkowy " łodygi”
4. Załóż wachlarz możliwych kombinacji tablicy łodyg (gdzie utknąłem ... niby)

Oto co mam do tej pory:

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

} 

To działa, ale na blokach tekstu większych niż 25 słów powoduje awarię przeglądarki. Rozumiem, że matematycznie może istnieć ogromna liczba możliwych kombinacji. Co chciałbym wiedzieć to:

1. Czy jest to skuteczniejszy sposób?
2. Jak zdefiniować długość tablicy kombinacji min/maks?

Answer 1

Myślę, że twoja logika jest zasadniczo wadliwa z powodu tego, ile kombinacji tworzysz.

Podejście, które bym wziął;

1. podzielić tekst na poszczególne słowa (nazwijmy tę zmienną split_words)
2. Usuń znaki specjalne
3. Usuń krótkie/wspólny słów (i, lub I, a); albo to zrobić długości, lub bardziej inteligentnie czarną listę słów
4. mieć tabeli (np blocks), który ma kolumny block_id i word

5. Czy zapytanie SQL, takich jak

, a następnie będziesz mieć listę block_ids, które są uporządkowane w zależności od tego, ile słów mają wspólne bloki.

Answer 2

Znalazłem ten poprzednie pytanie: Algorithm to find articles with similar text

Jedną z odpowiedzi pod warunkiem, link do artykułu, który sugeruje znalezienie jak wiele par przylegających znaków są zawarte w obu ciągów. [http://www.catalysoft.com/articles/StrikeAMatch.html]

Przykładem jest w Javie, ale jestem pewien, że może być łatwo przeniesione do 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

Twój problem można łatwo rozwiązać z moim binomial coefficient class. Spójrz na kod z mojego answer do nieco pokrewnego problemu. Nie wiem, czy przeniesienie kodu C# do SQL przechowywanego proc byłoby dobrym pomysłem, czy nie.Najprawdopodobniej łatwiej byłoby przenieść go na java lub js i wywołać przechowywane procesy z tego kodu.