7

This came up in another question but I figured it is best to ask this as a separate question. Give a large list of sentences (order of 100 thousands):

[
"This is sentence 1 as an example",
"This is sentence 1 as another example",
"This is sentence 2",
"This is sentence 3 as another example ",
"This is sentence 4"
]

what is the best way to code the following function?

def GetSentences(word1, word2, position):
    return ""

where given two words, word1, word2 and a position position, the function should return the list of all sentences satisfying that constraint. For example:

GetSentences("sentence", "another", 3)

should return sentences 1 and 3 as the index of the sentences. My current approach was using a dictionary like this:

Index = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: [])))

for sentenceIndex, sentence in enumerate(sentences):
    words = sentence.split()
    for index, word in enumerate(words):
        for i, word2 in enumerate(words[index:):
            Index[word][word2][i+1].append(sentenceIndex)

But this quickly blows everything out of proportion on a dataset that is about 130 MB in size as my 48GB RAM is exhausted in less than 5 minutes. I somehow get a feeling this is a common problem but can't find any references on how to solve this efficiently. Any suggestions on how to approach this?

4
  • Just to clarify: is position the distance between the two words in the sentence?
    – mpenkov
    Nov 5, 2011 at 1:17
  • Having two "sentence 1"s is confusing. Did it match the second "1" and not the first?
    – shookster
    Nov 5, 2011 at 1:29
  • @shookster: Why is it confusing? The first sentence does not have the word "another" isn't it? Or maybe I misunderstood your question.
    – Legend
    Nov 5, 2011 at 1:34
  • @Legend Nevermind, I misread the sentence "...should return sentences 1 and 3 as the index..." to read sentences 1 and 3, not the indexes 1 and 3.
    – shookster
    Nov 5, 2011 at 1:37

2 Answers 2

14

Use database for storing values.

  1. First add all the sentences to one table (they should have IDs). You may call it eg. sentences.
  2. Second, create table with words contained within all the sentences (call it eg. words, give each word an ID), saving connection between sentences' table records and words' table records within separate table (call it eg. sentences_words, it should have two columns, preferably word_id and sentence_id).
  3. When searching for sentences containing all the mentioned words, your job will be simplified:

    1. You should first find records from words table, where words are exactly the ones you search for. The query could look like this:

      SELECT `id` FROM `words` WHERE `word` IN ('word1', 'word2', 'word3');
      
    2. Second, you should find sentence_id values from table sentences that have required word_id values (corresponding to the words from words table). The initial query could look like this:

      SELECT `sentence_id`, `word_id` FROM `sentences_words`
      WHERE `word_id` IN ([here goes list of words' ids]);
      

      which could be simplified to this:

      SELECT `sentence_id`, `word_id` FROM `sentences_words`
      WHERE `word_id` IN (
          SELECT `id` FROM `words` WHERE `word` IN ('word1', 'word2', 'word3')
      );
      
    3. Filter the result within Python to return only sentence_id values that have all the required word_id IDs you need.

This is basically a solution based on storing big amount of data in the form that is best suited for this - the database.

EDIT:

  1. If you will only search for two words, you can do even more (almost everything) on DBMS' side.
  2. Considering you need also position difference, you should store the position of the word within third column of sentences_words table (lets call it just position) and when searching for appropriate words, you should calculate difference of this value associated with both words.
3
  • 2
    +1 Thank you very much for your time. I think I will go with this. I am thinking of using sqlite for the moment but if that does not work out maybe MySQL.
    – Legend
    Nov 5, 2011 at 1:50
  • 1
    @Legend: Thanks. I believe sqlite is good suited for this, if one database will not be used by multiple users at the same time. If only one user will use it, sqlite is the best in my opinion, so I totally agree with your choice.
    – Tadeck
    Nov 5, 2011 at 2:18
  • 2
    I came back to thank you once again. It goes a long way in saying "use the right tool for the right job" :) The time for building collocations has been reduced from X (X>12 and did not finish as it ran out memory!) hours to 1 hour now using sqlite and it is not even heavy!
    – Legend
    Nov 5, 2011 at 22:44
2

Here's how I did it in Python. Though assuming this needs to be done more than once, a DBMS is the right tool for the job. However this seems to work pretty well for me with a million rows.

sentences = [
    "This is sentence 1 as an example",
    "This is sentence 1 as another example",
    "This is sentence 2",
    "This is sentence 3 as another example ",
    "This is sentence 4"
    ]

sentences = sentences * 200 * 1000

sentencesProcessed = []

def preprocess():
    global sentences
    global sentencesProcessed
    # may want to do a regex split on whitespace
    sentencesProcessed = [sentence.split(" ") for sentence in sentences]

    # can deallocate sentences now
    sentences = None


def GetSentences(word1, word2, position):
    results = []
    for sentenceIndex, sentence in enumerate(sentencesProcessed):
        for wordIndex, word in enumerate(sentence[:-position]):
            if word == word1 and sentence[wordIndex + position] == word2:
                results.append(sentenceIndex)
    return results

def main():
    preprocess()
    results = GetSentences("sentence", "another", 3)
    print "Got", len(results), "results"

if __name__ == "__main__":
    main()
2
  • +1 Thank you for this approach. Actually, I tested this and found it to be super fast for one-time queries. However, I tried doing multiple queries but the lookup time was too high which is expected because there are no indices. But neverthless, an interesting approach. Thank you.
    – Legend
    Nov 5, 2011 at 2:45
  • @Legend: Yeah, it looks through the entire dataset every time you query. I just wanted to try it out :-)
    – shookster
    Nov 5, 2011 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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