從字符串數組創建獨特組合陣列

我正在寫一些需要一段文本並將其分解成可用於查找可能的數據庫查詢的內容，這些查詢可用於查找類似的文本塊。（產生類似於「類似的問題」清單的東西，而我鍵入此）的基本過程：從字符串數組創建獨特組合陣列

從文本中刪除停用詞
刪除特殊字符
從剩餘的文本創建的獨特數組「莖」
創建的陣列的可能組合的陣列的莖（種......在那裏我卡住了）

這是我到目前爲止有：

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

}

這可以工作，但是對於大於25個字左右的文本塊，它會崩潰我的瀏覽器。我意識到數學上可能存在大量可能的組合。我想知道的是：

有沒有更有效的方法來做到這一點？
如何定義最小/最大組合數組長度？

來源

2012-07-10 HartyeTech

這是一個夢幻般的第一個問題。歡迎來到StackOverflow！您的瀏覽器可能會因使用的內存量而崩潰，或者遞歸太多。 – Bojangles 2012-07-10 13:54:54

你是否真的需要所有的組合？你不能在處理它們時立即生成它們而不是積累龐大的數組？也嘗試重寫你的算法迭代而不是遞歸。 – 2012-07-10 13:57:00

謝謝，我已經有很長一段時間了）@ OlegV.Volkov不，我不需要所有組合，我希望能夠爲返回的組合數組定義最小/最大長度。感謝您的迭代建議。 – HartyeTech 2012-07-10 14:06:18

我認爲你的邏輯根本上是有缺陷的，因爲你創建了多少個組合。

我會採取的方法是;

拆分文本爲單個單詞（我們會打電話給這個變量split_words）
刪除特殊字符
刪除短/常用詞（與，或，我，一個）;或者通過長度做到這一點，或者更智能地由字的黑名單
具有帶有列block_id和word
有一個SQL查詢表（例如blocks）如

，然後你會得到一個block_ids的列表，這些列表的排列順序取決於塊有多少個單詞。

來源

2012-07-10 13:59:01 Matt

感謝您的回覆。在進入這一步之前，我已經在做1,2和3了。我正在處理服務器端的專有平臺和數據庫技術，並且實施像您所建議的解決方案是我考慮過的。不幸的是，打破數據我將搜索到單個詞是不可能的。 – HartyeTech 2012-07-10 14:14:26

發現這個前面的問題：Algorithm to find articles with similar text

答案之一提供了一個鏈接，建議找到許多相鄰的字符對如何在包含兩個字符串的文章。 [http://www.catalysoft.com/articles/StrikeAMatch.html]

的例子是在Java中，但我敢肯定，可以很容易地移植到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; 
}

來源

2012-07-10 14:20:41 mcknz

這很酷。我想要做的就是「投網」找到其他「文章」來做這種比較。一旦我想出我的原始問題，這樣的事情可能會是下一步。 – HartyeTech 2012-07-10 14:30:55

你的問題可以與我binomial coefficient class迎刃而解。看看我的answer中的代碼是否有點相關的問題。我不知道將C＃代碼移植到SQL存儲過程是否是個好主意。將它移植到java或js並從該代碼調用存儲的特效可能會更容易。

來源

2012-09-26 17:34:10

從字符串數組創建獨特組合陣列

回答

相關問題