1

A very useful learning tool I stumbled across for Chinese was a massive list of sentences that, barring the first 10 or 15, only differed by the ones before by one or two words, or at least as few as possible: The creator had sorted them by relation, obviously starting with a few standard sentences to prevent the first ones from being random and complex.

I am a little confused about how to go about writing my own implementation of such and algorithm. Now bear with me (unless you stopped reading b/c this question is out of line for this site) as I have been called "stupid" by several teachers but I was thinking of this incredibly inefficient algorithm:

  • Take first sentence (sentence number one)
  • Cycle through each sentence thereafter and count the number of different words (different from 1st sentence) (by looping through each word of each sentence) - assign a number in an array depicting this.
  • Cycle again and find those with the lowest associated numbers
  • If there is one sentence with the lowest number of different words - make that the next sentence in the list (sentence number two)
  • If there are multiple sentences, sort them by which have the most words in the top 1000 words in the language and thus are most useful
  • With the selected sentences (with the most similar words to sentence 1) sorted by word frequency, choose the one or ones that are most frequent as sentences 2, 3 etc.
  • Start all over by checking the next sentence in the sequence against the last one combined with all previous ones to find lowest number of new words across all sentences

For a corpus of 100, 000 sentences, I will be looping millions of times for each few sentences most likely. There must be a better way. My overall goal is as follows:

Have each sentence in the array (sequence, what have you) have as few new words as possible, with "new" words defined as those not present in any previous sentences.

  • 1
    If a teacher calls you "stupid", ignore it; they're lazy, burned out or have insufficient resources or training. It's not a teachers job to label you but to find a way to present the material that works for you. The difficulty for teachers is that that may take time they don't have. In other words, the label "stupid" may have less to do with you and more with to do with them. – outis May 9 '15 at 8:32
0

You could look at this as a simple sorting problem. Consider each "word" to be a unique symbol in an alphabet. To make this efficient you might parse all your sentences into tokens, where each token is a unique number representing a unique word. Does word order matter? You did not specify. If it does, then sort the words (or tokens) within each sentence. Now sort all the sentences using your favorite sorting tool. Similar sentences will be naturally grouped together.

On the other hand, what you may really want is not a single sorted list of sentences, but multiple lists, each representing a cluster of words commonly found together. That is considerably harder.

  • 1
    It's not quite sorting as you're not comparing pairs of sentences (the value of each sentence is a function not only of that sentence but also of all sentences that precede it in the list) and the comparison doesn't appear to have the transitive property. In particular, if two sentences differed only in their first token, they'd wind up in different sections of the list, even though they should probably be close. It's closer to Damerau–Levenshtein distance than an ordering, but not quite that either. – outis May 9 '15 at 8:30
  • @outis My answer has the tokens sorted within each sentence as a first step. But you are completely correct. If the algorithm output is not an ordered list, the output is probably a set of lists, where each set represents some type of cluster. Not having access to a sample of what is desired, it is difficult to say what the output should be. Determining the clusters could be difficult. – Frank Hileman May 9 '15 at 16:40
1

Here is how I would do this in .Net:

pass 1. Make a Dictionary of sentences lower case with the value being the original list item index. You can use this opportunity to drop out any duplicate sentences.

pass 2. Make a Dictionary of word frequencies. Sort this into a list.

pass 3. Make a Dictionary of sentences, value = calculate (least frequent word position in list above * sentence length)

pass 4. Make a List - Use Linq to sort by calculation, lowest to highest. - this may already be your list

pass 5. Make a Dictionary of first use of word

pass 6. Move all sentences that have more than 2 not yet used words half way up list (don't move the first 20 or so).

redo pass 5 and pass 6 until the list stops changing or you have made enough iterations so that the list probably won't be improved any more. Perhaps limit the number of iterations to 20. With 100,000 items, 20 iterations will be enough to move anything that needs to be there, to the end of the list.

Finally, Make a final list by using your list and your first dictionary to refer back to your original list in order to restore original case.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.