Finding n-gram frequencies in a large set of sentences

user_10273668 0
Viewed 739

I have a set of text messages. Lets call them m1, m2, ..... The maximum number of message is below 1,000,000. Each message is below 1024 characters in length, and all are in lowercase. Lets also pick an n-gram s1.

I need to find frequency of all possible substring from all of these messages. For example, lets say we have only two messages:

m1 = a cat in a cage
m2 = a bird in a cage

The frequency of some n-gram in these two messages:

'a' = 4
'in a cage' = 2
'a bird' = 1
'a cat' = 1
...

Note that, as in = 2, in a = 2, and a cage = 2 are subsets of in a cage = 2 and have same frequency, they should not be listed. Only take the longest one that have the highest frequency; follow this condition: the longest sn-gram should consist of at most 8 words, with a total character count below 30. If a n-gram exceeds this limit, it can be broken into two or more n-grams and listed separately.

I need to find such n-grams for all of these text messages and sort them by their number of occurrences in descending order.

How to I approach this problem? I need a solution in javascript.

PS: I need help, but do not know to where to ask this. If the question is not for this site, then where should I post it? please guide this newbie here.

string-matching substring algorithm javascript
1 Answers

May be you can approach as follows. I will edit to add explanation as soon as i have some time.

var subSentences = (w,...ws) => ws.length ? ws.reduce((r,s) => (r.push(r[r.length-1] + ` ${s}`), r),[w])
                                              .concat(subSentences(...ws))
                                          : [w],
    frequencyMap = sss => sss.reduce((map,ss) => subSentences(...ss.split(/\s+/)).reduce((m,s) => m.set(s, m.get(s) + 1 || 1), map), new Map());

    frequencies  = frequencyMap(["this is a test string",
                                 "this is another one",
                                 "yet another one is here"]);

console.log(...frequencies.entries()); // logging map object seems not possible hence entries
.as-console-wrapper { max-height : 100% !important
                    }

user_45432070
Related