Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

(hopefully I landed on the right stack exchange site)

I was hoping to brainstorm a little bit on the subject of storing n-gram data. In my project, I am trying to solve linguistic problems where I know all (n-1) data items and want to statistically guess my n using linear interpolation over all applicable n-grams. (Yes, there is a tagger that assigns tags to known words according to its lexicon and a suffix tree that tries to guess the word kind for unknown words; the n-gram component discussed here will be tasked with resolving ambuguity.)

My initial approach would be to simply store all observed n-grams (for n = 1..3, i.e. monogram, bigram, trigram) data in respective SQL databases and call it a day. But the requirements of my project may change to include other vector lengths (n), and I would like my application to adapt to 4-gram without a lot of work (updating schema, updating application code, etc.); ideally, I would simply tell my application to work with 4-grams now without having to change code much (or at all) and train its data from a given data source.

To sum up all requirements:

  • Ability to store n-gram data (initially for n = {1, 2, 3}
  • Ability to change what kinds of n-grams should be used (between application runs)
  • Ability to (re-)train n-gram data (between application runs)
  • Ability to query the data store (e.g. if I have observed A, B, C, I'd like to know the most frequently observed item for what might follow using my trained 4-, 3-, 2-, 1-gram data sets)

    The application will most likely be read-heavy, data sets most likely won't be retrained that often

  • The solution employs the .NET Framework (up to 4.0)

Now what design would be better fit for such a task?

  • A fixed table managed by a SQL server (MSSQL, MySQL, ...) for each n (eg. dedicated tables for bi-grams, tri-grams, etc.)
  • Or a NoSQL document database solution that stores the first n-1 as the key of the document, and the document itself contains the n-th value and observed frequencies?
  • Or something different?
share|improve this question
3  
I think this would be better suited on Stack Overflow. –  Konrad Rudolph Apr 1 '11 at 13:45
1  
Perhaps a trie (prefix tree) data structure would fit your requirements? –  Schedler Apr 1 '11 at 14:09
1  
I'd suggest Stack Overflow or even cstheory.stackexchange.com –  Steve Haigh Apr 1 '11 at 16:04
    
Okay, thanks. I'll try to get the question up over there. –  Manny Apr 4 '11 at 11:36
2  
This question is perfectly suited for programmers.stackexchange.com and should not be migrated to stackoverflow, IMO. It's exactly the kind of “whiteboard situation“ question that should be asked here. Check meta for details. –  user281377 Jul 10 '11 at 8:56
show 3 more comments

3 Answers

Given that you won't know the optimal range of N, you definitely want to be able to change it. For example, if your application predicts the likelihood that a certain text is English, you would probably want to use character N-grams for N 3..5. (That's what we found experimentally.)

You haven't shared details about your application, but the problem is clear enough. You want to represent N-gram data in a relational database (or NoSQL document-based solution). Before suggesting a solution of my own, you may want to take a look at the following approaches:

  1. How to best store Google ngrams in a database?
  2. Storing n-grams in database in < n number of tables
  3. Managing the Google Web 1T 5-gram with Relational Database

Now, having not read any of the above links, I suggest a simple, relational database approach using multiple tables, one for each size of N-gram:

create table ngram_1 (
    word1 nvarchar(255),
    frequency int
) primary key (word1);

create table ngram_2 (
    word1 nvarchar(255),
    word2 nvarchar(255),
    frequency int
) primary key (word1, word2);

create table ngram_3 (
    word1 nvarchar(255),
    word2 nvarchar(255),
    word3 nvarchar(255),
    frequency int
) primary key (word1, word2, word3);

create table ngram_4 (
    word1 nvarchar(255),
    word2 nvarchar(255),
    word3 nvarchar(255),
    word4 nvarchar(255),
    frequency int
) primary key (word1, word2, word3, word4);

I would structure the program code to handle any number of ngram_N tables via configuration. You could declaratively change the program to use N-gram range N(1..6) after creating the ngram_5 and ngram_6 tables.

You could put all of the data in a single table with the maximum necessary columns (i.e. store bigrams and trigrams in ngram_4, leaving the final columns null), but I recommend partitioning the data. Depending on your database engine, a single table with a large number of rows can negatively impact performance.

To query frequency, you could use a query like this:

select n1.frequency + n2.frequency + n3.frequency + n4.frequency
from ngram_1 n1
join ngram_2 n2 on n1.word1 = n2.word1
join ngram_3 n3 on n1.word1 = n3.word1 and n2.word2 = n3.word2
join ngram_4 n4 on n1.word1 = n4.word1 and n2.word2 = n4.word2
    and n3.word3 = n4.word3
where n1.word1 = ? and n2.word2 = ? and n3.word3 = ? and n4.word4 = ?;
share|improve this answer
add comment

Not the most efficient, but simple and wedded to the database like you want:

Table: word
Colums:
word (int, primary key) - a unique identifier for each word
text (varchar) - the actual word

Table: wordpos
Columns:
document (int) - a unique identified for the document of this word
word (int, foreign key to word.word) - the word in this position
pos (int) - the position of this word (e.g., first word is 1, next is 2, ...)

wordpos should have indexes on document and pos.

bigrams are:

select word1.text as word1, word2.text as word2
from wordpos as pos1, wordpos as pos2, word as word1, word as word2
where pos1.document = pos2.document
      and pos1.pos = pos2.pos - 1
      and word1.word = pos1.word
      and word2.word = pos2.word

Then you can count() and group your way to frequencies and stuff.

To change to trigrams, it is easily to generate this string to include a word3.

I've done this before actually (even though the SQL up there is probably a little rusty). I settled on a set of flat files that could be seeked into easily then streamed off of disk. Kinda depends on your hardware how to do it better.

share|improve this answer
add comment

Contrary to what the others are suggesting, I'd suggest to avoid any data structures more complex than a hashmap or a key-value store.

Keep in mind your data access requirements: a) 99% requests - query ngram "aaa-bbb-ccc" and retreive the value (or 0) b) 1% requests - inserting/updating a count of specific ngram c) there is no (c).

The most effective way is to retrieve it with a single lookup. You can use an out-of-bounds (or escaped) separator to combine the full n-gram in a single string (e.g. "alpha|beta|gamma" for 3gram, "alpha" for unigram, etc) and just fetch that (by the hash of that). That's how quite a lot of NLP software does it.

If your ngram data is small (say, < 1 gb) and fits in memory , then I'd suggest to use an efficient in-program memory structure (hashmaps, trees, tries, etc) to avoid overhead; and just serialize/deserialize to flat files. If your ngram data is terabytes or more, then you may choose NoSQL key-value stores split on multiple nodes.

For extra performance, you may want to replace all words everywhere with integer ids so that your core algorithm doesn't see any (slow) strings at all; then it's slightly different to implement the same idea.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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