1

テキストのブロック内にすべての可能なフレーズを作成するアルゴリズムが必要です。たとえば、テキストでは：

"My username is click upvote. I have 4k rep on stackoverflow"

次の組み合わせが作成されます。

"My username"
"My Username is"
"username is click"
"is click"
"is click upvote"
"click upvote"
"i have"
"i have 4k"
"have 4k"
..

あなたはその考えを理解します。基本的に重要なのは、文から「フレーズ」の可能なすべての組み合わせを取得することです。これを最適に実装する方法について何か考えはありますか？

4

5 に答える 5

5

PHPやJavaはわかりませんが、基本的には、テキスト内のすべての単語を二重にループする必要があります。ここにいくつかの擬似コードがあります：

words = split(text)
n = len(words)
for i in 1...n-1 {        // i = first word in phrase 
    for j in i+1...n {       // j = last word in phrase
        phrase = join(words[i:j])
        print phrase
    }
}

2番目のループは1ではなくiから始まることに注意してください。これにより、単語番号iから単語番号jまでのすべてのフレーズが得られます。これはiより大きいです（したがって、すべてのフレーズには少なくとも2つの単語があります）。

ああ、私はあなたがおそらくフレーズが文の境界を越えてほしくないことに気づきました。したがって、最初にテキストを文に分割し、次に各文でこれを実行する外部ループが必要になります。

プログラミングの経験があれば、これはかなり明らかなようですが、念のために言っておきます。forステートメントは[のようなfor(i=1; i<=n; i++)]ループsplitであり、文字列を受け取り、それを単語の配列に分割する関数です。これは完全に些細なことではありませんが、おそらくこれを行うためのライブラリ関数がlenあり、配列の長さを指定し、joinそれらを間にスペースを入れて戻します。構文は、からまで[i:j]のすべての要素を意味します（Pythonでは、これは実際にはそうなります）。ああ、そして私は暗黙のうちに配列がゼロではなくインデックス1で始まると仮定しました。演習として、0ベースの配列への変更を残します...ij[i:j+1]C

最後に、特定の質問に答えるために：

  • 「2番目の」ループは実際には内部ループであることに注意してください。（フレーズの最初の単語）の値ごとに、文の最後までiループしi+1て、フレーズの最後の単語を指定します。

  • 最初と最後の単語の数がわかったので、join関数（これを作成する必要があります）は、個々の文字列word[i], word[i+1], ... word[j]をスペースで連結してフレーズを形成します。実際には、これは関数が文字列のように宣言されjoin(words, i, j)て文字列を返す可能性があることを意味する場合がありますが、一部の言語にはこれを簡単にする方法があります。

于 2009-05-09T09:42:10.683 に答える
5

基本的に、最初にテキストのブロックを文に分割する必要があります。ピリオド、疑問符、感嘆符、その他の文の終了記号に注意する必要があるため、英語でも十分に注意が必要です。

次に、すべての句読点（コンマ、セミコロン、コロンなど）を削除した後、一度に1つの文を処理します。

次に、単語の配列が残っていると、次のようになります。

for i = 1 to num_words-1:
    for j = i+1 to num_words:
        phrase = words[i through j inclusive]
        store phrase

それは、非常に単純です（テキストブロックの最初のマッサージの後、あなたが思うほど単純ではないかもしれません）。

これにより、すべての文に2つ以上の単語のすべてのフレーズが表示されます。

文への分離、単語への分離、句読点の削除などは最も難しいビットですが、従うべきいくつかの簡単な初期ルールをすでに示しました。残りは、テキストのブロックがアルゴリズムを破るたびに追加する必要があります。

アップデート：

要求に応じて、フレーズを与えるJavaコードを次に示します。

public class testme {
    public final static String text =
        "My username is click upvote." +
        " I have 4k rep on stackoverflow.";

 

    public static void procSentence (String sent) {
        System.out.println ("==========");
        System.out.println ("sentence [" + sent + "]");

        // Split sentence at whitspace into array.

        String [] sa = sent.split("\\s+");

        // Process each starting word.

        for (int i = 0; i < sa.length - 1; i++) {

            // Process each phrase.

            for (int j = i+1; j < sa.length; j++) {

                // Build the phrase.

                String phrase = sa[i];
                for (int k = i+1; k <= j; k++) {
                    phrase = phrase + " " + sa[k];
                }

                // This is where you have your phrase. I just
                // print it out but you can do whatever you
                // wish with it.
                System.out.println ("   " + phrase);
            }
        }
    }

 

    public static void main(String[] args) {
        // This is the block of text to process.

        String block = text;
        System.out.println ("block    [" + block + "]");

        // Keep going until no more sentences.

        while (!block.equals("")) {
            // Remove leading spaces.

            if (block.startsWith(" ")) {
                block = block.substring(1);
                continue;
            }

            // Find end of sentence.

            int pos = block.indexOf('.');

            // Extract sentence and remove it from text block.

            String sentence = block.substring(0,pos);
            block = block.substring(pos+1);

            // Process the sentence (this is the "meat").

            procSentence (sentence);

            System.out.println ("block    [" + block + "]");
        }
        System.out.println ("==========");
    }
}

出力：

block    [My username is click upvote. I have 4k rep on stackoverflow.]
==========
sentence [My username is click upvote]
   My username
   My username is
   My username is click
   My username is click upvote
   username is
   username is click
   username is click upvote
   is click
   is click upvote
   click upvote
block    [ I have 4k rep on stackoverflow.]
==========
sentence [I have 4k rep on stackoverflow]
   I have
   I have 4k
   I have 4k rep
   I have 4k rep on
   I have 4k rep on stackoverflow
   have 4k
   have 4k rep
   have 4k rep on
   have 4k rep on stackoverflow
   4k rep
   4k rep on
   4k rep on stackoverflow
   rep on
   rep on stackoverflow
   on stackoverflow
block    []
==========

さて、これはかなり基本的なJavaであることに注意してください（Java方言で書かれたCだと言う人もいるかもしれません:-)。これは、要求されたとおりに文から単語のグループ化を出力する方法を説明するためのものです。

元の回答で述べたような凝った文の検出と句読点の削除をすべて行うわけではありません。

于 2009-05-09T10:55:50.553 に答える
2

文をトークン化し、CombinationGeneratorを使用するだけです。このアルゴリズムは、Kenneth H. Rosen、Discrete Mathematics and its Applications、第2版（NY：McGraw-Hill、1991）、284〜286ページで説明されています。

コードと使用例は次のとおりです： http ：//www.merriampark.com/comb.htm

于 2009-05-09T15:10:56.000 に答える
1

好きなように遊んでstr_word_count();構築することができます。

于 2009-05-09T17:51:24.950 に答える
1

そのようなフレーズの専門用語がシングルであることをすでにご存知かもしれません。LuceneのShingeMatrixFilterを使用して、入力テキストの帯状疱疹を取得できます。

于 2010-05-23T03:44:08.450 に答える