Алгоритм для анализа текста слов

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

Update:

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

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

Answer 2

Ну, я не знаю 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. Это дает вам все фразы, которые начинаются от числа слов я на слово число у, которое больше, чем я (так что все фразы имеют как минимум два слова).

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

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

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

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

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

Answer 3

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

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

Answer 4

Может играть с str_word_count(); и построить его, как вам нравится.

Answer 5

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