Tạo mảng kết hợp độc đáo từ mảng chuỗi

Question

Tôi đang viết một thứ gì đó có khối văn bản và chia nhỏ thành các truy vấn cơ sở dữ liệu có thể được sử dụng để tìm các khối văn bản tương tự. (Một cái gì đó tương tự như "câu hỏi tương tự" danh sách được tạo ra khi tôi nhập này) Quá trình cơ bản:

1. từ Remove thẳng từ văn bản
2. Remove ký tự đặc biệt
3. Từ văn bản còn lại tạo ra một loạt các độc đáo " xuất phát"
4. Tạo một mảng kết hợp có thể có của mảng của xuất phát (nơi tôi đang mắc kẹt ... loại)

Dưới đây là những gì tôi có cho đến nay:

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

} 

Tác phẩm này, nhưng trên các khối văn bản lớn hơn 25 từ hoặc hơn, nó làm hỏng trình duyệt của tôi. Tôi nhận ra rằng toán học có thể có một số lượng lớn các kết hợp có thể. Điều tôi muốn biết là:

1. Có cách nào hiệu quả hơn để thực hiện việc này không?
2. Làm cách nào để xác định độ dài mảng kết hợp tối thiểu/tối đa?

Answer 1

Tôi nghĩ rằng logic của bạn về cơ bản là thiếu sót do có bao nhiêu kết hợp bạn đang tạo.

Cách tiếp cận tôi muốn thực hiện sẽ là;

1. Chia văn bản thành lời nói cá nhân (chúng tôi sẽ gọi biến split_words này)
2. Remove ký tự đặc biệt
3. Di ngắn/từ thông dụng (và, hoặc, I, a); hoặc làm điều này bằng chiều dài, hoặc một cách thông minh hơn bằng cách một danh sách đen của từ
4. Có một bảng (ví dụ blocks) trong đó có cột block_id và word

5. Có một truy vấn SQL như

và sau đó bạn sẽ có danh sách block_ids được sắp xếp tùy thuộc vào số lượng các từ chung mà các khối có.

Answer 2

Tìm thấy câu hỏi trước này: Algorithm to find articles with similar text

Một trong những câu trả lời cung cấp một liên kết đến một bài viết mà gợi ý tìm kiếm có bao nhiêu cặp nhân vật liền kề được chứa trong cả chuỗi. [http://www.catalysoft.com/articles/StrikeAMatch.html]

Các ví dụ là trong Java nhưng tôi chắc chắn có thể được chuyển một cách dễ dàng để 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

Vấn đề của bạn có thể dễ dàng giải quyết với binomial coefficient class tôi. Hãy xem mã từ số answer của tôi đối với sự cố liên quan đến phần nào. Tôi không biết nếu porting mã C# trên một proc lưu trữ SQL sẽ là một ý tưởng tốt hay không.Nó có lẽ sẽ dễ dàng hơn để chuyển nó sang java hoặc js và gọi procs được lưu trữ của bạn từ mã đó.