Algorithm for analyzing the text of words
I need an algorithm that would generate all possible phrases in a block of text. For example, in the text:
"My username is click upvote. I have 4k rep on stackoverflow"
It will create the following combinations:
"My username"
"My Username is"
"username is click"
"is click"
"is click upvote"
"click upvote"
"i have"
"i have 4k"
"have 4k"
..
You get the idea. Basically, the point is to get all possible combinations of "phrases" from a sentence. Any thoughts on how best to implement this?
a source to share
Basically you need to separate the block of text from the sentences first. It is quite difficult, even in English, as you have to search for periods, question marks, exclamation marks and any other sentence terminators.
Then you process one sentence at a time after you remove all punctuation marks (commas, semi-colon, colons, etc.).
Then, when you're left with an array of words, it becomes easier:
for i = 1 to num_words-1:
for j = i+1 to num_words:
phrase = words[i through j inclusive]
store phrase
It's quite simple (after initially massaging the text block, which may not be as easy as you might think).
This will give you all phrases of two or more words in each sentence.
Splitting into sentences, splitting into words, removing punctuation, etc. will be the hardest, but I've already shown you some simple starting rules. The rest should be added every time a block of text breaks the algorithm.
Update:
As requested, here's some Java code that gives the phrases:
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 ("==========");
}
}
which outputs:
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 []
==========
Now, keep in mind that this is pretty simple Java (some might say C is written in a Java dialect :-). It is simply intended to illustrate how to deduce word groupings from a sentence as you wish.
In the original answer, I didn't mention decoy detection and punctuation.
a source to share
Well, I don't know PHP or java, but basically you want a double loop over all the words in your text. Here are some pseudo codes:
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
}
}
Note that the second loop starts at i, not 1. This gives you all the phrases starting at the word number i until the word j, which is greater than i (so all phrases have at least two words).
Ah, I just realized that you probably don't want phrases to cross sentence boundaries. Thus, you need an outer loop that first breaks the text into sentences and then runs it for each sentence.
It seems pretty clear if you have any programming experience at all, but just in case: Operators for
are [like for(i=1; i<=n; i++)
] loops , split
is some function that takes a string and splits it into an array of words - it's not entirely trivial, but maybe for this a library function, len
gives the length of the array, join
puts them back together with spaces in between, and the syntax [i:j]
means all elements from i
to j
inclusive (in python this would actually be [i:j+1]
). Oh, and I implicitly assumed that arrays start at index 1, not zero; I'm leaving the changes to the C
0-based arrays as an exercise ...
Finally, to answer specific questions:
-
Note that the "second" loop is actually an inner loop; for each meaning
i
(first word of a phrase) we move fromi+1
to the end of the sentence to give the last word of the phrase. -
Now that we have the number of the first and last words, the function
join
you will have to write concatenates the individual linesword[i], word[i+1], ... word[j]
with spaces in between to form a phrase.In practice, this could mean that the function can be declared likejoin(words, i, j)
and returns a string. although some languages have ways to make it easier.
a source to share
Just highlight the sentence and use the CombinationGenerator. The algorithm is described by Kenneth Rosen, Discrete Mathematics and Its Applications, 2nd Edition (NY: McGraw-Hill, 1991), pp. 284-286.
Here's the code and usage example: http://www.merriampark.com/comb.htm
a source to share
You may already know that the technical term for these phrases is Shingle. You can get shingles for text input using Lucene ShingeMatrixFilter .
a source to share