Алгоритм анализа текста слов - PullRequest
1 голос
/ 09 мая 2009

Мне нужен алгоритм, который бы создавал все возможные фразы в текстовом блоке. Например, в тексте:

"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"
..

Вы поняли идею. По сути, смысл состоит в том, чтобы получить все возможные комбинации «фраз» из предложения. Есть мысли, как лучше всего это реализовать?

Ответы [ 5 ]

5 голосов
/ 09 мая 2009

В основном вам нужно сначала разделить блок текста на предложения. Это достаточно сложно, даже на английском языке, так как вам нужно следить за точками, вопросительными знаками, восклицательными знаками и любыми другими ограничителями предложений.

Затем вы обрабатываете одно предложение за раз после удаления всех знаков препинания (запятые, точки с запятой, двоеточия и т. Д.).

Затем, когда у вас останется массив слов, все становится проще:

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

Все, довольно просто (после первоначального массирования текстового блока, который может не быть таким простым, как вы думаете).

Это даст вам все фразы из двух или более слов в каждом предложении.

Труднее всего будет разделение на предложения, разделение на слова, удаление знаков препинания и так далее, но я уже показал вам несколько простых начальных правил, которым нужно следовать. Остальное следует добавлять каждый раз, когда блок текста нарушает алгоритм.

Обновление:

В соответствии с запросом, вот некоторый код 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 (некоторые могут сказать, что это C написано на диалекте Java :-). Это просто для иллюстрации того, как вывести группы слов из предложения, как вы просили.

Он не выполняет все обнаружение необычных предложений и удаление пунктуации, о которых я упоминал в первоначальном ответе.

5 голосов
/ 09 мая 2009

Ну, я не знаю 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
    }
}

Обратите внимание, что второй цикл начинается с i, а не с 1. Это дает вам все фразы, которые начинаются со слова номер i до слова номер j, которое больше, чем i (поэтому все фразы содержат как минимум два слова).

Ах, я только что понял, что вы, вероятно, не хотите, чтобы фразы пересекали границы предложений. Таким образом, вам понадобится внешний цикл, который сначала разбивает текст на предложения, но затем запускает его для каждого предложения.

Это кажется довольно понятным, если у вас есть опыт программирования вообще, но на всякий случай: операторы for являются циклами [как for(i=1; i<=n; i++)], split - это некоторая функция, которая принимает строку и разбивает ее на массив слов - это не совсем тривиально, но, вероятно, для этого есть библиотечная функция, len задает длину массива, join помещает их обратно вместе с пробелами между ними, а синтаксис [i:j] означает все элементы от i до j включительно (в python это на самом деле будет [i:j+1]). О, и я неявно предположил, что массивы начинаются с индекса 1, а не с нуля; В качестве упражнения я оставляю замену массивов C на основе 0 ...

Наконец, чтобы ответить на конкретные вопросы:

  • Обратите внимание, что "второй" цикл на самом деле является внутренним циклом; для каждого значения i (первого слова фразы) мы делаем цикл от i+1 до конца предложения, чтобы получить последнее слово фразы.

  • Теперь, когда у нас есть число первых и последних слов, функция join - которую вам придется написать - объединяет отдельные строки word[i], word[i+1], ... word[j] с пробелами между ними, чтобы сформировать фразу , На практике это может означать, что функция может быть объявлена ​​как join(words, i, j) и возвращает строку, хотя в некоторых языках есть способы сделать это проще.

2 голосов
/ 09 мая 2009

Просто токенизируйте предложение и используйте CombinationGenerator. Алгоритм описан Кеннетом Х. Розеном, Дискретная математика и ее приложения, 2-е издание (Нью-Йорк: McGraw-Hill, 1991), стр. 284-286.

Вот код и пример использования: http://www.merriampark.com/comb.htm

1 голос
/ 23 мая 2010

Возможно, вы уже знаете, что техническим термином для таких фраз является Shingle. Вы можете получить дранку для ввода текста с помощью ShingeMatrixFilter от Lucene.

1 голос
/ 09 мая 2009

Может играть с str_word_count(); и строить его как угодно.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...