7

私は、テキストのブロックを取得し、それを類似のテキストのブロックを見つけるために使用できる可能性のあるデータベースクエリに分解するものを書いています。（これを入力しているときに生成される「類似の質問」リストに似たもの）基本的なプロセス：

  1. テキストからストップワードを削除する
  2. 特殊文字を削除する
  3. 残りのテキストから、一意の「ステム」の配列を作成します
  4. ステムの配列の可能な組み合わせの配列を作成します（私が立ち往生している場所...一種）

これが私がこれまでに持っているものです：

    //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ワード程度を超えるテキストのブロックでは、ブラウザがクラッシュします。数学的には、考えられる組み合わせが膨大な数になる可能性があることを認識しています。私が知りたいのは：

  1. これを行うためのより効率的な方法はありますか？
  2. 最小/最大の組み合わせ配列の長さをどのように定義できますか？
4

3 に答える 3

1

作成している組み合わせの数が原因で、ロジックに根本的な欠陥があると思います。

私がとるアプローチは次のとおりです。

  1. テキストを個々の単語に分割します（この変数をこの変数と呼びますsplit_words）
  2. 特殊文字を削除する
  3. 短い/一般的な単語（および、または、I、a）を削除します。これを長さで行うか、よりインテリジェントに単語のブラックリストで行います
  4. blocks列block_idと_word

  5. 次のようなSQLクエリがあります

    SELECT block_id FROM blocks 
WHERE word IN (split_words) GROUP BY block_id 
ORDER BY COUNT(*) DESC

block_ids次に、ブロックに共通する単語の数に応じて並べ替えられたリストが表示されます。

于 2012-07-10T13:59:01.897 に答える
1

この前の質問を見つけました：同様のテキストを持つ記事を見つけるためのアルゴリズム

回答の1つは、両方の文字列に含まれる隣接する文字のペアの数を見つけることを提案する記事へのリンクを提供しました。[ 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-10T14:20:41.940 に答える
0

あなたの問題は私の二項係数クラスで簡単に解決できます。やや関連する問題に対する私の答えからのコードを見てください。C＃コードをSQLストアドプロシージャに移植するのが良いかどうかはわかりません。それをjavaまたはjsに移植し、そのコードからストアドプロシージャを呼び出す方がおそらく簡単でしょう。

于 2012-09-26T17:34:10.393 に答える