1
$\begingroup$

Given a set T={A,B,C}, I need to know the cardinality of all ordered sequential n-grams and the total cardinality of all subsets of those n-grams.

  1. The ordered sequential n-grams of the set T above are {{A},{B},{C},{A,B},{B,C},{A,B,C}} and its cardinality is 6.

  2. The total cardinality of all subsets for those n-grams is sum(1,1,1,2,2,3)=10

So, given set T, what are the formulae for #1 and #2?

$\endgroup$
  • $\begingroup$ Your "ordered sequential n-grams" appear to be simply "subsets". Is that what you intended? $\endgroup$ – j_random_hacker Sep 21 '17 at 19:53
  • $\begingroup$ Yes! Some background: I use those terms because I am trying to solve this in the context of a lookup for full-text search. We have a string and break it into n-grams and then search those. We need to know the total number tokens that get searched when the number of terms in the query is high, and optimize. $\endgroup$ – binarymax Sep 21 '17 at 21:39
  • 1
    $\begingroup$ @j_random_hacker, not exactly. If $ABC$ is a string then the asker considers only nonempty substrings of $ABC$, namely $A,B,C, AB, BC, $ and $ABC$. The problem statement of course needs better wording. $\endgroup$ – fade2black Sep 22 '17 at 6:23
  • $\begingroup$ @evil - I find it strange that this question was closed, considering the commentary was clearly understood and the question answered. Please be specific on what further clarity you require. $\endgroup$ – binarymax Oct 31 '17 at 20:45
3
$\begingroup$

Let $|T| = n$. Then

  1. the number of $n$-symbol sequences is $1$, the number of $(n-1)$-symbol sequences is $2$, $\dots$, the number of $1$-symbol sequences is $n$. Thus the number of all ordered sequential $n$-grams is $1+2+\dots + n = \frac{n(n+1)}{2}$.

  2. The total cardinality of all subsets for those $n$-grams is $$\sum_{k=1}^nk(n-k+1) = (n+1)\sum_{k=1}^nk - \sum_{k=1}^n k^2 = \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6}$$

For $n=3$ we have

  1. $\frac{3\times 4}{2} = 6$
  2. $\frac{3\times 4^2}{2} -\frac{3\times 4 \times 7}{6} = 24 - 14 = 10 $
$\endgroup$

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