Let's assume we have Google's 1T n-grams. I want to be able to:

  • Search for n-grams containing all of a set of words (such as finding all n-grams containing the words "dog" and "bone" in any position)
  • The above search but for n-grams of a particular size only
  • Search for n-grams using a template (such as finding all n-grams which fit the template "the dog __ the __" where the blanks are to be filled with a single word)
  • 1
    Welcome! I think you might get better answers at Stack Overflow, the Stack Exchange devoted to programming. (I tried to choose this for my close vote, but only Meta Linguistics was offered as a choice...).
    – robert
    Dec 22 '13 at 19:02
  • 1
    Actually I think that this is more closely related to natural language processing than to programming itself. This is the closest stack exchange to NLP.
    – mtanti
    Dec 22 '13 at 19:04
  • @mtanti: I don't see anything here about natural language processing. This is just about data, so computational linguistics but not NLP. Dec 23 '13 at 3:03

The Trie data structure is commonly used in NLP. This, and its descendants, Suffix Tree and Generalized Suffix Tree provide both, an efficient way to store commonly occurring sub-sequences, and a fast way to search for sub-sequences.

  • I agree but can a trie be efficiently represented in a database?
    – mtanti
    Dec 23 '13 at 8:05
  • It can but a nosql database might be more suitable for the representation than a relational database.
    – Atamiri
    Dec 23 '13 at 10:35
  • @mtanti: I don't have any experience with databases. Aren't database keys hashes? If so, it can't be efficiently represented. However, if you were creating your own database, you can use this Trie itself as a hash. That should make searches very fast.
    – prash
    Dec 24 '13 at 10:24
  • They're more likely to be b-trees which are basically sorted trees. I'm programming in Python and I don't think there's an easy way to make generic file based data structures.
    – mtanti
    Dec 24 '13 at 12:05

You could store all tokens in a relational database in a separate table and build up a positional index (sacrificing space for speed of query processing). Then you could use simple SQL expressions to formulate all types of queries you've listed.

  • Actually the WHERE statement "WHERE (ele0 = 'dog' or ele1 = 'dog' or ele2 = 'dog' or ele3 = 'dog') AND (ele0 = 'bone' or ele1 = 'bone' or ele2 = 'bone' or ele3 = 'bone')" is quite slow.
    – mtanti
    Dec 23 '13 at 9:32
  • It shouldn't be if you use a good index but what I meant is having an explicit index on a table with the tokens and their positions in the tuple.
    – Atamiri
    Dec 23 '13 at 10:39
  • It is indexed but still too slow to process in bulk operations. In my case I want to check which words tend to replace a word in an ngram for every word in the corpus.
    – mtanti
    Dec 23 '13 at 10:50
  • In this case sql won't work. Build up an efficient structure in memory and use an efficient (procedural) language to execute queries.
    – Atamiri
    Dec 23 '13 at 11:58
  • I would but there's too much data to keep it in memory.
    – mtanti
    Dec 23 '13 at 14:49

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.